El desafío es filtrar un archivo grande rápidamente.
- Entrada: cada línea tiene tres enteros positivos separados por espacios.
Salida: Todas las líneas de entrada
A
B
,T
que satisface ni el criterio siguiente.- Existe otra línea de entrada
C
,D
,U
enD = A
y0 <= T - U < 100
. - Existe otra línea de entrada
C
,D
,U
enB = C
y0 <= U - T < 100
.
- Existe otra línea de entrada
Para hacer un archivo de prueba, use el siguiente script de Python que también se usará para las pruebas. Hará un archivo 1.3G. Por supuesto, puede reducir las nolinas para las pruebas.
import random
nolines = 50000000 # 50 million
for i in xrange(nolines):
print random.randint(0,nolines-1), random.randint(0,nolines-1), random.randint(0,nolines-1)
Reglas. El código más rápido cuando se prueba en un archivo de entrada que hago usando el script anterior en mi computadora gana. La fecha límite es una semana desde el momento de la primera entrada correcta.
Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de ubuntu de 8 GB de RAM en un procesador AMD FX-8350 de ocho núcleos. Esto también significa que necesito poder ejecutar su código.
Alguna información relevante sobre el tiempo
Los tiempos se actualizaron para ejecutar lo siguiente antes de cada prueba.
sync && sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches'
time wc test.file
real 0m26.835s
user 0m18.363s
sys 0m0.495s
time sort -n largefile.file > /dev/null
real 1m32.344s
user 2m9.530s
sys 0m6.543s
Estado de las entradas
Ejecuto la siguiente línea antes de cada prueba.
sync && sudo bash -c 'echo 3 > /proc/sys/vm/drop_caches'
- Perl (esperando la corrección de errores).
- Scala 1 minutos 37 segundos por @James_pic. (Usando scala -J-Xmx6g Filterer largefile.file output.txt)
- Java . 1 minuto 23 segundos por @Geobits. (Usando java -Xmx6g Filter_26643)
- C . 2 minutos 21 segundos por @ScottLeadley.
- C . 28 segundos por @James_pic.
- Python + pandas . Tal vez hay una solución simple "groupby"?
- C . 28 segundos por @KeithRandall.
Los ganadores son Keith Randall y James_pic.
¡No podría distinguir sus tiempos de carrera y ambos son casi tan rápidos como el WC!
1 < n < 2147483647
?Respuestas:
C, ~
74.1 segundosRadix ordena en T, luego camina a través de la matriz buscando coincidencias.
Es rápido porque es compatible con caché. La raíz clasifica razonablemente así, y la caminata final muy. Tengo que verificar cada fila con otras 100, pero están todas adyacentes en el caché.
Agregado: ya no tengo que verificar cada fila con un análisis de otras 100 filas. Una pequeña tabla de recuentos de bits de orden inferior de b en la ventana es suficiente para eliminar la mayoría de las instancias de esta exploración.
Ahora aproximadamente 1/2 tiempo de análisis, 1/3 de tiempo de clasificación, 1/6 de tiempo haciendo la coincidencia real.
fuente
filter.c
para hacer lo mismo, llegué a la pregunta y encontré esto. +1Scala 2.10 - 0:41
El problema es básicamente:
La mayoría de los RDBMS notarían que la unión de
x.a
ay.b
tiene la mayor especificidad, y lo planean como una unión hash.Entonces eso es lo que haremos. Creamos una tabla hash de los datos
a
, la juntamos con la misma tablab
y filtramos la diferenciat
.Compilar con:
Y corre con:
En mi máquina, esto se ejecuta en 2 minutos 27.
Aún así, puede ser interesante probar el enfoque de la respuesta de @ Lembik, pero en un lenguaje más rápido. Corresponde a algo así como una combinación de combinación
t
. En el papel, debería ser más lento, pero tiene una mejor ubicación de caché, lo que puede impulsarlo.Actualizar
Me las arreglé para ahorrar una gran cantidad de tiempo con un cambio sorprendentemente pequeño: un mejor mezclador de hash. El mapa de hash es muy sensible al agrupamiento de hash, por lo que este cambio lo reduce a 1:45 en mi máquina.
La mayor parte de ese tiempo se pasa leyendo los datos en una matriz.
Tengo curiosidad por saber por qué mi código de lectura de datos es mucho más lento que @Geobits. Mi código tarda 70 segundos en leer los datos, más tiempo que el programa completo @Geobits, una vez que
Thread.start
se soluciona el error. Estoy tentado a robar el enfoque de @Geobits para leer datos, pero no estoy seguro de cómo se sentirían los dioses de Stack Exchange al respecto.Actualización 2
He realizado nuevas mejoras, esta vez para el lector de datos. El uso de operaciones de coincidencia de patrones y mónadas dentro del bucle perjudicaba el rendimiento, por lo que lo he simplificado. Creo que
scala.io.Source
es el próximo cuello de botella para abordar.Ha bajado a 1:26 en mi máquina ahora.
Actualización 3
Se deshizo de
probe
OpenHashMultiMap. El código ahora es más java-ish y se ejecuta en 1:15.Actualización 4
Ahora estoy usando un FSM para analizar la entrada. El tiempo de ejecución se ha reducido a 0:41
fuente
StringTokenizer
, pero cuando lo hago, analizo millones de cadenas.String.split
actualmente es un cuello de botella, peroStringTokenizer
no es mucho mejor en este momento: la asignación en un circuito interno estrecho está perjudicando mi GC ya tenso. Estoy trabajando en un FSM que parece ser prometedor (aunque es una exageración total)Java: 1m54s
(En mi i7)
Dado que cada partido estará dentro de 100
t
de su compañero, decidí agrupar las entradast
. Hay un cubo para cada 100, por lo que para verificar un número, solo tiene que comparar con +/- 1 cubos.En promedio, cada grupo contiene solo 100 entradas, por lo que no toma mucho tiempo escanear algunos grupos para cada uno. Más de la mitad del tiempo se gasta en leer y juntar, el emparejamiento toma solo 40 segundos más o menos.
Nota: Dependiendo de la configuración de su JVM, es posible que deba aumentar el tamaño del almacenamiento dinámico. Esto también asume el nombre de archivo de
test.file
. Simplemente cámbielo en la línea 24 si ese no es el caso.fuente
Thread::run
, noThread.start
, así que todo se está ejecutando en elmain
hilo. ConThread::start
, el tiempo de ejecución cae de 1:38 a 0:46 en mi máquina.sort
tiempo. Golpeé el montón hasta 6G, igual que el mío (dijiste que tenías 8G, por lo que parecía una suposición sensata).C - 12 segundos
Decidí transferir mi respuesta de Scala a C, para ver cuánto más rendimiento podía obtener.
Es más o menos el mismo enfoque (construir una tabla hash abierta
a
), excepto que omito el paso donde construyo la matriz inicial e itero directamente desde la tabla hash (por alguna razón, nunca pude lograr que este enfoque funcione en Scala - Sospecho que la culpa es de la línea JVM).No me molesté con los hilos, ya que es difícil hacerlo de forma portátil.
El codigo es:
Compilar con:
Y corre con:
La ubicación del archivo de prueba está codificada como "archivo de prueba".
Una vez más, leer los datos ocupa la mayor parte del tiempo (poco menos de 9 segundos). Emparejar toma el resto del tiempo.
Nuevamente, será interesante ver cómo va esto en contra de la respuesta de Scott Leadley, que usa el mismo lenguaje pero una estrategia diferente. Scott se está uniendo en T, lo que en principio significa que tendrá más para unirse, pero una vez más, unirse en T proporciona una mejor ubicación de caché.
fuente
diff <(sort -n James_pic-c.out) <(sort -n James_pic-scala.out)
a
produce un valor dadon
vecesn >= BUFFER_SIZE + 2
Perl, 17m46s en un Core i7 con 8GB de memoria
Primero, usamos sort -n -k3 para ordenar el campo más importante, aprovechando el paralelismo incorporado en las versiones modernas de sort (1). Luego, dado que perl se ve obstaculizado en gran medida por el hecho de que un escalar simple toma el orden de 80 bytes cada uno (50 millones * 3 * 80 es demasiado, al menos 12 GB), reducimos la salida a 50 millones * 12 bytes array (12 bytes por línea, cada línea contiene 3 enteros que se pueden representar como un entero de 32 bits). Luego disparamos 8 hilos que cubren (aproximadamente) 1/8 de los datos cada uno (+ alguna superposición).
Salida sin clasificar:
Estoy seguro de que esto sería un orden de magnitud más rápido en C, pero probablemente no me tome el tiempo para hacerlo.
fuente
A = D = 8455767
peroU = 50175
,T = 50130
y asíT - U = -45
C # - 30 segundos
Un enfoque diferente de la mayoría si leo bien: no uso ninguna estructura basada en hash.
Tiendo a no obtener resultados, no estoy seguro de si esto es una anomalía estadística o un error en mi razonamiento.Solucionado, la comparación para la ordenación binaria era defectuosa.fuente
x.A
vendrásortedA
yx.B
vendrásortedB
, mientras que en realidad ambos vendránsortedB
, y estoComparer
producirá resultados sin sentido.A
yB
, hay un algoritmo más rápido que iterarA
y buscar en binarioB
cuál esO(n log(n))
(y es efectivamente una tabla hash de pobre). En su lugar, puede fusionar y unir las dos listas, que esO(n)
.B
se distribuirán uniformemente en un rango específico, sería intercambiar la búsqueda binaria por la búsqueda de interpolación, lo que reduce el tiempo de búsqueda deO(log(n))
aO(log(log(n))
.C
Brutal, fuerza bruta, fea en tu cara C. En un cambio elegiría cualquier otro lenguaje compilado.
Compile con "gcc -m64 -pthreads -O". Espera entrada en stdin. Se ejecuta con subprocesos múltiples de forma predeterminada. Use la opción "-s" para usar solo un hilo.
fuente
Finalmente tuve la oportunidad de construir un sistema físico Ubuntu 14.04 similar al de Lembik y hacer una autopsia en mi solución a este rompecabezas. En mi elección de importancia:
apestabaera no performant:En lugar de aburrirlo con otro analizador de FSM, la solución a continuación usa fgets () y un reemplazo local de strtol () [busque s2i ()].
Una implementación de referencia en Ruby:
Es un perro, ~ 50 veces más lento que una solución C, pero Perl es igual de lento y menos conciso.
La solución C:
Compile con "gcc -O3 -std = c99 -Wall -m64".
fuente