¿Qué algoritmo de clasificación es eficiente para grandes datos y por qué?

Oh chico. El antiguo cómo clasifico el big data. Bueno, dado que he estado involucrado en este tipo de cosas, podría intentarlo.

En primer lugar, las entrevistas técnicas 101 nos dicen que hagamos preguntas aclaratorias. Realmente no especificaste:

• ¿Qué tipo de datos estábamos clasificando? (¿números? cadenas? filas de la base de datos?)
• ¿Cuántos datos son datos grandes ? Gigabytes? Petabytes?
• ¿Cuántas y qué tipo de máquinas tenemos a nuestra disposición?
• ¿Cuánta memoria tenemos?
• ¿Cuánto almacenamiento tenemos?
• ¿Qué tipo de almacenamiento tenemos? El almacenamiento local rápido (SSD), el almacenamiento local lento, el almacenamiento en red, etc., todos vienen a la mente y pueden desempeñar un papel en la decisión de qué estrategia queremos usar.

Entonces, sin respuestas a estas preguntas, realmente no podemos diseñar un algoritmo. Aquí hay una idea. Si me dijeras que estabas clasificando un flujo casi infinito de números enteros , no sudaría. ¿Por qué? Porque la naturaleza nos dio el tipo Radix. Con Radix sort, estás ordenando en tiempo lineal y puedes elegir cuánta memoria gastas. Si me diera 2048 B de memoria para almacenar mis 256 cubos de conteos de 8 bytes, y suficiente almacenamiento rápido, no necesariamente en una máquina, tal vez incluso en la Nube, terminaríamos con esto en poco tiempo.

• ¿Qué es el diagrama de flujo?
• ¿Qué define una solución óptima con respecto al problema de la mochila 0-1?
• ¿Cuáles serían las mejores entradas para un algoritmo de red neuronal que intenta predecir el mercado de valores?
• Cómo aprender la estructura de datos en 1 mes en el albergue
• Teoría de grafos: ¿en qué se diferencian los árboles de expansión construidos a partir de Prim de los árboles de expansión construidos a partir de Kruskal?

Pero, si desea ordenar datos genéricos, como las filas de la base de datos, las cosas pueden volverse un poco más complicadas. En primer lugar, no más clasificación en tiempo lineal. Esa es la menor de tus preocupaciones. Obviamente, está limitado por la memoria disponible y asume que tiene “suficiente” almacenamiento para operaciones intermedias y salida de datos.

Sus principios principales son: cargue todo lo que pueda en la memoria para que pueda ordenar rápidamente (entiéndalo, ja, ja, estoy implicando una clasificación rápida aquí) y asegúrese de distribuir estas cargas de la manera más equitativa posible en todos procesadores disponibles. Si golpeas un OOM (excepción de falta de memoria), bueno, supongo que solo tendrás que derramar lo que has ordenado hasta ahora para liberar memoria disponible y consumir más. Al final de todo, simplemente recoge todo lo que has derramado y combínalo en una secuencia bien ordenada.

Entonces, teniendo eso en mente, dibujemos el algoritmo:

Para cada hilo disponible:

1. Cargar datos en la memoria
1. Si nunca llegas a un OOM, entonces supongo que es tu día de suerte porque pareces tener toda la memoria del mundo, así que sigue cargando.
2. Si llega a un OOM, entonces clasifique todo lo que ha recopilado hasta ahora utilizando un buen algoritmo como Quick Sort o, mejor aún, un híbrido que tenga en cuenta los casos teóricos de Quick Sort.
2. Ordene sus datos en memoria.

De acuerdo, sus hilos han ordenado todo lo que recolectaron, y eso está en la memoria o se ha derramado en algún almacenamiento. Si todo está en la memoria, entonces solo tienes que combinar un montón de arreglos ordenados, ¡woohoo! Sin embargo, estamos clasificando algunos datos muy grandes, así que supongo que ese no es el caso.

Entonces, ahora sabemos que tenemos un montón de archivos que contienen partes ordenadas de la gran secuencia y comenzamos a fusionar cosas. Tenga en cuenta que esto no es una combinación de clasificación, sino que simplemente combina dos matrices ordenadas en una sola matriz ordenada. Entonces, de nuevo,

Para cada hilo disponible:

1. Elija un par de secuencias ordenadas que viven en archivos, ahora. Observe que realmente no necesita cargarlos todos en la memoria. Si todos comenzaron a cargar todo en la memoria, sabes que te quedarás sin batería nuevamente. Después de todo, ya lo hiciste, una vez, ¿recuerdas? Entonces, con solo un poco de memoria extra, escanee los archivos derramados y combínelos en un archivo de salida.
2. Haga eso hasta que solo le quede un gran archivo ordenado, combinado.

Entonces, si tuviera N archivos que contienen secuencias ordenadas derramadas, podría dividirlas en N / 2 pares. Deje que tantos hilos como sea posible mastiquen un par. Si tiene más de N / 2 subprocesos, terminará teniendo archivos N / 2 después de la primera etapa. Luego N / 4 después del segundo. Eventualmente, tendrás solo uno. Si tiene menos hilos que pares, entonces todos sus hilos estarán involucrados en la fusión, pero no podrá procesar todos los pares al mismo tiempo. Eso no es un problema, nadie dice que las secuencias de salida deben ser del mismo tamaño en primer lugar. De todos modos, siempre hay algo para hacer los hilos, no hay razón para dejarlos inactivos.

Entonces, ahora que le queda un gran archivo lleno de datos ordenados, simplemente escanee, engullendo un trozo a la vez y pasándolo por la secuencia. Escanee en paralelo, si su sistema lo permite (es decir, si tiene algún flujo descendente de búfer que combina N flujos de entrada), no me importa.

Entonces, eso sería todo para el caso genérico. Para los más especializados, como el que describí lejos, muy arriba, con enteros, existen soluciones más eficientes que son posibles debido a la naturaleza específica de los datos.

Bastante simple, ¿eh?