muestre - programa que imprima los numeros del 1 al 1000 en c++

¿La forma más rápida de ordenar 10 números?(los números son de 32 bits) (10)

¿Qué pasa con un tipo de selección desenrollado y sin rama?

#include <iostream> #include <algorithm> #include <random> //return the index of the minimum element in array a int min(const int * const a) { int m = a[0]; int indx = 0; #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); //see http://stackoverflow.com/a/7074042/2140449 TEST(1); TEST(2); TEST(3); TEST(4); TEST(5); TEST(6); TEST(7); TEST(8); TEST(9); #undef TEST return indx; } void sort( int * const a ){ int work[10]; int indx; #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; //get the minimum, copy it to work and set it at max_int in a GET(0); GET(1); GET(2); GET(3); GET(4); GET(5); GET(6); GET(7); GET(8); GET(9); #undef GET #define COPY(i) a[i] = work[i]; //copy back to a COPY(0); COPY(1); COPY(2); COPY(3); COPY(4); COPY(5); COPY(6); COPY(7); COPY(8); COPY(9); #undef COPY } int main() { //generating and printing a random array int a[10] = { 1,2,3,4,5,6,7,8,9,10 }; std::random_device rd; std::mt19937 g(rd()); std::shuffle( a, a+10, g); for (int i = 0; i < 10; i++) { std::cout << a[i] << '' ''; } std::cout << std::endl; //sorting and printing again sort(a); for (int i = 0; i < 10; i++) { std::cout << a[i] << '' ''; } return 0; }

http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

Las únicas líneas relevantes son las dos primeras #define .

Utiliza dos listas y vuelve a verificar por completo la primera diez veces, lo que sería un tipo de selección mal implementado, sin embargo, evita ramas y bucles de longitud variable, que pueden compensar con procesadores modernos y un conjunto de datos tan pequeño.

Punto de referencia

Comparé con la red de clasificación y mi código parece ser más lento. Sin embargo, intenté eliminar el desenrollado y la copia. Ejecutando este código:

#include <iostream> #include <algorithm> #include <random> #include <chrono> int min(const int * const a, int i) { int m = a[i]; int indx = i++; for ( ; i<10; i++) //see http://stackoverflow.com/a/7074042/2140449 (m > a[i]) && (m = a[i], indx = i ); return indx; } void sort( int * const a ){ for (int i = 0; i<9; i++) std::swap(a[i], a[min(a,i)]); //search only forward } void sortNet10(int * const data) { // ten-input sorting network by Waksman, 1969 int swap; if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; } if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; } if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; } if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; } if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; } if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; } if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; } if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; } if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; } if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; } if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; } if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; } if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; } if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; } if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; } if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; } if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; } if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; } if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; } if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; } if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; } if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; } if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; } if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; } if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; } if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; } if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; } if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; } if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; } } std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) { std::mt19937 g(seed); int a[10] = {10,11,12,13,14,15,16,17,18,19}; std::chrono::high_resolution_clock::time_point t1, t2; t1 = std::chrono::high_resolution_clock::now(); for (long i = 0; i < 1e7; i++) { std::shuffle( a, a+10, g); func(a); } t2 = std::chrono::high_resolution_clock::now(); return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1); } int main() { std::random_device rd; for (int i = 0; i < 10; i++) { const int seed = rd(); std::cout << "seed = " << seed << std::endl; std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl; std::cout << "sort: " << benchmark(sort, seed).count() << std::endl; } return 0; }

Constantemente obtengo mejores resultados para la selección sin sucursales en comparación con la red de clasificación.

$ gcc -v gcc version 5.2.0 (GCC) $ g++ -std=c++11 -Ofast sort.cpp && ./a.out seed = -1727396418 sortNet10: 2.24137 sort: 2.21828 seed = 2003959850 sortNet10: 2.23914 sort: 2.21641 seed = 1994540383 sortNet10: 2.23782 sort: 2.21778 seed = 1258259982 sortNet10: 2.25199 sort: 2.21801 seed = 1821086932 sortNet10: 2.25535 sort: 2.2173 seed = 412262735 sortNet10: 2.24489 sort: 2.21776 seed = 1059795817 sortNet10: 2.29226 sort: 2.21777 seed = -188551272 sortNet10: 2.23803 sort: 2.22996 seed = 1043757247 sortNet10: 2.2503 sort: 2.23604 seed = -268332483 sortNet10: 2.24455 sort: 2.24304

Estoy resolviendo un problema e implica ordenar 10 números (int32) muy rápidamente. Mi aplicación necesita ordenar 10 números millones de veces lo más rápido posible. Estoy muestreando un conjunto de datos de miles de millones de elementos y cada vez que necesito elegir 10 números (simplificado) y ordenarlos (y sacar conclusiones de la lista ordenada de 10 elementos).

Actualmente estoy usando la ordenación por inserción, pero imagino que podría implementar un algoritmo de ordenación personalizado muy rápido para mi problema específico de 10 números que superaría la ordenación por inserción.

¿Alguien tiene alguna idea sobre cómo abordar este problema?

(Siguiendo la sugerencia de HelloWorld para buscar redes de clasificación).

Parece que una red de comparación / intercambio de 29 es la forma más rápida de hacer una clasificación de 10 entradas. Usé la red descubierta por Waksman en 1969 para este ejemplo en Javascript, que debería traducirse directamente a C, ya que es solo una lista de declaraciones if , comparaciones e intercambios.

Aquí hay una representación gráfica de la red, dividida en fases independientes.

Para aprovechar el procesamiento paralelo, la agrupación 5-4-3-4-4-4-3-2 se puede cambiar a una agrupación 4-4-4-4-4-4-3-2.

Aunque una ordenación de red tiene buenas probabilidades de ser rápida en matrices pequeñas, a veces no se puede superar la ordenación por inserción si se optimiza correctamente. Por ejemplo, inserción por lotes con 2 elementos:

{ final int a=in[0]<in[1]?in[0]:in[1]; final int b=in[0]<in[1]?in[1]:in[0]; in[0]=a; in[1]=b; } for(int x=2;x<10;x+=2) { final int a=in[x]<in[x+1]?in[x]:in[x+1]; final int b=in[x]<in[x+1]?in[x+1]:in[x]; int y= x-1; while(y>=0&&in[y]>b) { in[y+2]= in[y]; --y; } in[y+2]=b; while(y>=0&&in[y]>a) { in[y+1]= in[y]; --y; } in[y+1]=a; }

Cuando trate con este tamaño fijo, eche un vistazo a en.wikipedia.org/wiki/Sorting_network . Estos algoritmos tienen un tiempo de ejecución fijo y son independientes de su entrada. Para su caso de uso, no tiene los gastos generales que tienen algunos algoritmos de clasificación.

El tipo Bitonic es una implementación de dicha red. Este funciona mejor con len (n) <= 32 en una CPU. En entradas más grandes, podría pensar en pasar a una GPU. en.wikipedia.org/wiki/Sorting_network

Por cierto, una buena página para comparar algoritmos de clasificación es esta aquí (aunque le falta la bitonic sort .

http://www.sorting-algorithms.com

La pregunta no dice que se trata de una aplicación basada en la web. Lo único que me llamó la atención fue:

Estoy muestreando un conjunto de datos de miles de millones de elementos y cada vez que necesito elegir 10 números (simplificado) y ordenarlos (y sacar conclusiones de la lista ordenada de 10 elementos).

Como ingeniero de software y hardware, esto me grita absolutamente "FPGA" . No sé qué tipo de conclusiones necesita sacar del conjunto ordenado de números o de dónde provienen los datos, pero sé que sería casi trivial procesar entre cien millones y mil millones de estos "ordenar y ... analizar "operaciones por segundo . He realizado trabajos de secuenciación de ADN asistidos por FPGA en el pasado. Es casi imposible superar el poder de procesamiento masivo de los FPGA cuando el problema es adecuado para ese tipo de solución.

En algún nivel, el único factor limitante se convierte en la rapidez con la que puede insertar datos en un FPGA y la rapidez con que puede sacarlos.

Como punto de referencia, diseñé un procesador de imágenes en tiempo real de alto rendimiento que recibió datos de imágenes RGB de 32 bits a una velocidad de aproximadamente 300 millones de píxeles por segundo. Los datos se transmitieron a través de filtros FIR, multiplicadores de matriz, tablas de búsqueda, bloques de detección de bordes espaciales y una serie de otras operaciones antes de salir por el otro extremo. Todo esto en un FPGA Xilinx Virtex2 relativamente pequeño con un reloj interno que abarca desde aproximadamente 33MHz hasta, si mal no recuerdo, 400MHz. Ah, sí, también tenía una implementación de controlador DDR2 y ejecutaba dos bancos de memoria DDR2.

Un FPGA puede generar una especie de diez números de 32 bits en cada transición de reloj mientras funciona a cientos de MHz. Habrá un breve retraso al comienzo de la operación a medida que los datos llenen la / s tubería / s de procesamiento. Después de eso, debería poder obtener un resultado por reloj. O más si el procesamiento se puede paralelizar mediante la replicación de la tubería de clasificación y análisis. La solución, en principio, es casi trivial.

El punto es: si la aplicación no está vinculada a la PC y el flujo de datos y el procesamiento son "compatibles" con una solución FPGA (ya sea de forma independiente o como una tarjeta de coprocesador en la máquina), no hay forma de que vaya para poder superar el nivel de rendimiento alcanzable con software escrito en cualquier idioma, independientemente del algoritmo.

EDITAR:

Simplemente realicé una búsqueda rápida y encontré un documento que podría serle útil. Parece que se remonta a 2012. Puede mejorar mucho su rendimiento hoy (e incluso en aquel entonces). Aquí está:

Clasificación de redes en FPGA

Por razones similares a las que describí here , las siguientes funciones de clasificación, sort6_iterator() y sort10_iterator_local() , deberían funcionar bien, de donde se tomó la red de clasificación desde here :

template<class IterType> inline void sort10_iterator(IterType it) { #define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);} #define DD1(a) auto data##a=*(data+a); #define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b); #define CB1(a) *(data+a)=data##a; #define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b; DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) SORT2(4,9) SORT2(0,1) SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) #undef CB1 #undef CB2 #undef DD1 #undef DD2 #undef SORT2 }

Para llamar a esta función, le pasé un iterador std::vector .

Puede desenrollar completamente el insertion sort

Para hacerlo más fácil, se pueden usar template recursivas sin sobrecarga de funciones. Como ya es una template , int puede ser un parámetro de template . Esto también hace que la codificación de tamaños de matriz distintos de 10 sea trivial para crear.

Tenga en cuenta que para ordenar int x[10] la llamada es insert_sort<int, 9>::sort(x); ya que la clase usa el índice del último elemento. Esto podría envolverse, pero sería más código para leer.

template <class T, int NUM> class insert_sort; template <class T> class insert_sort<T,0> // stop template recursion // sorting 1 item is a no-op { public: static void place(T *x) {} static void sort(T * x) {} }; template <class T, int NUM> class insert_sort // use template recursion to do insertion sort // NUM is the index of the last item, eg. for x[10] call <9> { public: static void place(T *x) { T t1=x[NUM-1]; T t2=x[NUM]; if (t1 > t2) { x[NUM-1]=t2; x[NUM]=t1; insert_sort<T,NUM-1>::place(x); } } static void sort(T * x) { insert_sort<T,NUM-1>::sort(x); // sort everything before place(x); // put this item in } };

En mis pruebas, esto fue más rápido que los ejemplos de red de clasificación.

Recientemente escribí una pequeña clase que usa el algoritmo Bose-Nelson para generar una red de clasificación en tiempo de compilación.

Se puede usar para crear una clasificación muy rápida para 10 números.

/** * A Functor class to create a sort for fixed sized arrays/containers with a * compile time generated Bose-Nelson sorting network. * /tparam NumElements The number of elements in the array or container to sort. * /tparam T The element type. * /tparam Compare A comparator functor class that returns true if lhs < rhs. */ template <unsigned NumElements, class Compare = void> class StaticSort { template <class A, class C> struct Swap { template <class T> inline void s(T &v0, T &v1) { T t = Compare()(v0, v1) ? v0 : v1; // Min v1 = Compare()(v0, v1) ? v1 : v0; // Max v0 = t; } inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); } }; template <class A> struct Swap <A, void> { template <class T> inline void s(T &v0, T &v1) { // Explicitly code out the Min and Max to nudge the compiler // to generate branchless code. T t = v0 < v1 ? v0 : v1; // Min v1 = v0 < v1 ? v1 : v0; // Max v0 = t; } inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); } }; template <class A, class C, int I, int J, int X, int Y> struct PB { inline PB(A &a) { enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L }; PB<A, C, I, J, L, M> p0(a); PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a); PB<A, C, IAddL, J, XSubL, M> p2(a); } }; template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1> { inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); } }; template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2> { inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); } }; template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1> { inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); } }; template <class A, class C, int I, int M, bool Stop = false> struct PS { inline PS(A &a) { enum { L = M >> 1, IAddL = I + L, MSubL = M - L}; PS<A, C, I, L, (L <= 1)> ps0(a); PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a); PB<A, C, I, IAddL, L, MSubL> pb(a); } }; template <class A, class C, int I, int M> struct PS <A, C, I, M, true> { inline PS(A &a) {} }; public: /** * Sorts the array/container arr. * /param arr The array/container to be sorted. */ template <class Container> inline void operator() (Container &arr) const { PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr); }; /** * Sorts the array arr. * /param arr The array to be sorted. */ template <class T> inline void operator() (T *arr) const { PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr); }; }; #include <iostream> #include <vector> int main(int argc, const char * argv[]) { enum { NumValues = 10 }; // Arrays { int rands[NumValues]; for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100; std::cout << "Before Sort: /t"; for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " "; std::cout << "/n"; StaticSort<NumValues> staticSort; staticSort(rands); std::cout << "After Sort: /t"; for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " "; std::cout << "/n"; } std::cout << "/n"; // STL Vector { std::vector<int> rands(NumValues); for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100; std::cout << "Before Sort: /t"; for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " "; std::cout << "/n"; StaticSort<NumValues> staticSort; staticSort(rands); std::cout << "After Sort: /t"; for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " "; std::cout << "/n"; } return 0; }

Tenga en cuenta que en lugar de una declaración de if (compare) swap , codificamos explícitamente los operadores ternarios para min y max. Esto es para ayudar a empujar al compilador a usar código sin ramificación.

Puntos de referencia

Los siguientes puntos de referencia están compilados con clang -O3 y se ejecutaron en mi MacBook Air de mediados de 2012.

Ordenar datos aleatorios

Comparándolo con el código de DarioP, aquí está el número de milisegundos necesarios para ordenar 1 millón de arreglos int de 32 bits de tamaño 10:

Red de clasificación codificada 10: 88.774 ms
Plantilla Bose-Nelson con plantilla 10: 27.815 ms

Usando este enfoque con plantillas, también podemos generar redes de clasificación en tiempo de compilación para otro número de elementos.

Tiempo (en milisegundos) para clasificar 1 millón de matrices de varios tamaños.
El número de milisegundos para matrices de tamaño 2, 4, 8 es 1.943, 8.655, 20.246 respectivamente.

Créditos a Glenn Teitelbaum para el tipo de inserción desenrollada.

Aquí están los relojes promedio por tipo para pequeñas matrices de 6 elementos. El código de referencia y los ejemplos se pueden encontrar en esta pregunta:
El tipo más rápido de longitud fija de 6 int.

Direct call to qsort library function : 326.81 Naive implementation (insertion sort) : 132.98 Insertion Sort (Daniel Stutzbach) : 104.04 Insertion Sort Unrolled : 99.64 Insertion Sort Unrolled (Glenn Teitelbaum) : 81.55 Rank Order : 44.01 Rank Order with registers : 42.40 Sorting Networks (Daniel Stutzbach) : 88.06 Sorting Networks (Paul R) : 31.64 Sorting Networks 12 with Fast Swap : 29.68 Sorting Networks 12 reordered Swap : 28.61 Reordered Sorting Network w/ fast swap : 24.63 Templated Sorting Network (this class) : 25.37

Funciona tan rápido como el ejemplo más rápido en la pregunta para 6 elementos.

Rendimiento para ordenar datos ordenados

A menudo, las matrices de entrada pueden estar ya ordenadas o en su mayoría ordenadas.
En tales casos, la ordenación por inserción puede ser una mejor opción.

Es posible que desee elegir un algoritmo de clasificación apropiado según los datos.

El código utilizado para los puntos de referencia se puede encontrar aquí .

Un orden de inserción requiere en promedio 29,6 comparaciones para ordenar 10 entradas con un mejor caso de 9 y un peor de 45 (entrada dada que está en orden inverso).

Un {9,6,1} shellsort requerirá en promedio 25.5 comparaciones para ordenar 10 entradas. El mejor caso es 14 comparaciones, el peor es 34 y ordenar una entrada invertida requiere 22.

Por lo tanto, el uso de shellsort en lugar de inserción reduce el promedio de casos en un 14%. Aunque el mejor de los casos aumenta en un 56%, el peor de los casos se reduce en un 24%, lo cual es significativo en aplicaciones donde es importante mantener el rendimiento del peor de los casos bajo control. El caso inverso se reduce en un 51%.

Dado que parece estar familiarizado con el orden de inserción, puede implementar el algoritmo como una red de clasificación para {9,6} y luego agregar el orden de inserción ({1}) después de eso:

i[0] with i[9] // {9} i[0] with i[6] // {6} i[1] with i[7] // {6} i[2] with i[8] // {6} i[3] with i[9] // {6} i[0 ... 9] // insertion sort

Use una red de clasificación que tenga comparaciones en grupos de 4, para que pueda hacerlo en registros SIMD. Un par de instrucciones min / max empaquetadas implementa una función de comparador empacado. Lo siento, no tengo tiempo en este momento para buscar una página que recuerdo haber visto sobre esto, pero espero que buscar en redes de clasificación SIMD o SSE arroje algo.

x86 SSE tiene instrucciones mínimas y máximas de entero de 32 bits para vectores de cuatro entradas de 32 bits. AVX2 (Haswell y versiones posteriores) tienen lo mismo pero para vectores de 256b de 8 ints. También hay instrucciones de barajado eficientes.

Si tiene muchos tipos pequeños independientes, podría ser posible hacer 4 u 8 tipos en paralelo usando vectores. Esp. si está eligiendo elementos al azar (de modo que los datos que se ordenarán no estarán contiguos en la memoria de todos modos), puede evitar barajar y simplemente comparar en el orden que necesite. 10 registros para contener todos los datos de 4 (AVX2: 8) listas de 10 entradas todavía dejan 6 registros para el espacio de memoria virtual.

Las redes de clasificación de vectores son menos eficientes si también necesita clasificar los datos asociados. En ese caso, la forma más eficiente parece ser usar una comparación empaquetada para obtener una máscara de qué elementos cambiaron, y usar esa máscara para combinar vectores de (referencias a) datos asociados.