Me pregunto cuál sería el algoritmo más rápido para esto. Tengo 8 enteros entre 0 y 3000 y necesito ordenarlos. Aunque solo hay 8 enteros, esta operación se realizará millones de veces.¿Cuál es el algoritmo de clasificación más rápido para una pequeña cantidad de números enteros?
Por solo 8 enteros y dado que el rango es mucho mayor que 8, la ordenación por inserción es probablemente la mejor. Pruébalo para empezar, y si el perfil indica que no es el cuello de botella, déjalo.
(Dependiendo de muchos factores, el punto de corte en el que la clasificación rápida es mejor que la ordenación de inserción suele ser de entre 5 y 10 elementos).
Lo más rápido sería simplemente escribir un montón de declaraciones if para compararlas y determinar su orden exacta. Eso eliminará la sobrecarga que tiene cualquier algoritmo de clasificación.
Exactamente lo que estaba a punto de sugerir. –
En realidad, ahora que lo pienso ... ¿cuál sería el "algoritmo" para obtener el menor número de IF? O_O –
Esto se llama una red de clasificación y creo que las redes de clasificación óptimas son conocidas por ocho elementos. – templatetypedef
Una buena fuente para comparar algos de clasificación es http://www.sorting-algorithms.com/. Tenga en cuenta que incluso el estado de orden inicial afecta los resultados. Pero de todos modos, para 8 enteros, incluso un tipo de burbuja simple debería hacer el trabajo.
La forma más rápida es una sorting network implementada en hardware. Salvo eso, la manera más rápida se determina solo midiendo. Me gustaría probar
std::sort,if declaraciones, yen ese orden , porque es el orden más fácil para el más difícil (intente obtener ordenación por inserción la primera vez ...) hasta que encuentre algo que pueda mantenerse una vez que la constante 8 tenga el valor nueve.
Además, el tipo de burbuja, la selección se lo merece y el tipo de caparazón merecen un aviso. Nunca los implementé porque tienen mala reputación, pero podrías probarlos.
Una red de clasificación es particularmente efectiva si tiene SIMD. –
@Paul R: Supongo que sí. ¿Tiene MMX, etc., instrucciones de comparación por pares? –
Comparación vertical (register-to-register), sí. Comparación horizontal (compare alto/bajo dentro del registro), no. – greyfade
Para enteros positivos, el tipo más rápido se conoce como el ábaco SORT- es O (n)
http://en.wikipedia.org/wiki/Abacus_sort
Si sólo tiene unos pocos elementos, entonces es poco probable que usted notará ninguna diferencia de rendimiento de elegir cualquier algoritmo en particular.
Una implementación de software de este algoritmo es O (S), donde S es la suma de todos los enteros. En el caso que nos ocupa, esta es una mala idea. –
La siguiente cita de Bentley et al., Ingeniería función de una especie podría ser interesante aquí:
Diversas mejoras en la ordenación por inserción, incluyendo la búsqueda binaria, desenrollado del bucle, y la manipulación n = 2 como un caso especial, no era servicial. El código más simple fue el más rápido.
(Énfasis mío.)
Esto sugiere que llano tipo inserción sin modificaciones de lujo hecho, sería un buen punto de partida.Como ha señalado Peter, ocho elementos son de hecho un poco complicados porque eso está directamente en el rango que generalmente marca el punto de corte entre el tipo de inserción y el de orden rápido.
Para cantidades muy pequeñas de enteros, la clasificación de burbujas puede ser muy rápida. El ordenamiento de burbuja con comparaciones numéricas se puede escribir con una sobrecarga muy baja y para n pequeña, las diferencias de velocidad reales entre O (n log n) y O (n^2) se eliminan.
Aquí es una implementación de una red de tipo fusionar par-impar en C99 (lo siento por el idioma "malo"):
#define CMP_SWAP(i, j) if (a[i] > a[j]) \
{ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
void sort8_network(int *a)
{
CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7);
CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7);
CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5);
CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5);
CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6);
}
lo cronometré en mi máquina contra la ordenación por inserción
void sort8_insertion(int *a)
{
for (int i = 1; i < 8; i++)
{
int tmp = a[i];
int j = i;
for (; j && tmp < a[j - 1]; --j)
a[j] = a[j - 1];
a[j] = tmp;
}
}
Para aproximadamente 10 millones de géneros (exactamente 250 veces todas las 40320 permutaciones posibles), la red de ordenamiento tomó 0.39 segundos mientras que la ordenación de inserción tomó 0.88 segundos. Me parece que ambos son lo suficientemente rápidos. (Las cifras incluyen aproximadamente 0.04 segundos para generar las permutaciones.)
¿La red de clasificación es "óptima"? Quiero decir, ¿hay 19 comparaciones el mínimo absoluto necesario para clasificar 8 elementos? – dariopy
@dariopy: para una red de clasificación en el sentido habitual (es decir, código implementado solo con la macro 'CMP_SWAP' anterior), es mínimo. Podría escribir un montón de declaraciones * anidadas * de manera que cada comparación determine qué otras comparaciones se realizan, teniendo en cuenta de algún modo los resultados de las comparaciones anteriores. El código ya no usaría un número fijo de comparaciones, pero podría funcionar con un máximo de 16 comparaciones (un mínimo de 7). La función sería muy larga, sin embargo, y dudo que sea más rápido. –
¿Ha perfilado su código para mostrar que el género es un cuello de botella? Si no es un cuello de botella, entonces acelerarlo no te comprará mucho. Clasificar ocho enteros cortos es bastante rápido.
En general, std :: sort() será más rápido que cualquier cosa que pueda escribir, a menos que sea un gurú clasificador real.
Ejecuté una biblioteca de algoritmos de ordenamiento frente a todas las permutaciones de {0, 429, 857, 1286, 1714, 2143, 2571, 3000}.
El más rápido fueron:
name time stable in-place
AddressSort 0.537 No No
CenteredLinearInsertionSort 0.621 Yes No
CenteredBinaryInsertionSort 0.634 Yes No
BinaryInsertionSort 0.639 Yes Yes
...
QuickSort 0.650 No Yes
...
BubbleSort 0.802 Yes Yes
Para más información sobre AddressSort ver http://portal.acm.org/citation.cfm?id=320834
Para enteros, podría intentar radix-tipo. Esta encendido).
Años después) para hasta 32 entradas, ver Sorting network generator. Por 8 entradas, da 19 swaps, como la respuesta de Sven Marnach:
o--^--^--------^--------------------------o
| | |
o--v--|--^--^--|--^--^--------------------o
| | | | | |
o--^--v--|--v--|--|--|--^--------^--------o
| | | | | | |
o--v-----v-----|--|--|--|--^--^--|--^--^--o
| | | | | | | | |
o--^--^--------v--|--v--|--|--|--v--|--v--o
| | | | | | |
o--v--|--^--^-----v-----|--|--|-----v-----o
| | | | | |
o--^--v--|--v-----------v--|--v-----------o
| | |
o--v-----v-----------------v--------------o
There are 19 comparators in this network,
grouped into 7 parallel operations.
[[0,1],[2,3],[4,5],[6,7]]
[[0,2],[1,3],[4,6],[5,7]]
[[1,2],[5,6],[0,4],[3,7]]
[[1,5],[2,6]]
[[1,4],[3,6]]
[[2,4],[3,5]]
[[3,4]]
que depende mucho de lo que los valores son, y su orden inicial (y en la aplicación concreta del algoritmo, la plataforma, .. .). En última instancia, tendrá que medir y comparar usted mismo. –
Qué tan importante es el género 'más rápido'. Con tan pocos números hará muy poca diferencia. Entonces, a menos que esto sea algo hiper sensible a la velocidad, comenzaría con cuál es la manera más fácil de ordenar 8 elementos. –
Si la operación se realizará millones de veces, tal vez una cosa sea la ejecución de varias operaciones sort-8-integer en paralelo. N núcleos podrían producir una aceleración N veces ... –