necesito ayuda para diseñar el algoritmo de búsqueda de una manera más eficiente

Question

Tengo un problema que involucra el área de biología. En este momento tengo 4 archivos MUY GRANDES (cada uno con 0.1 billones de líneas), pero la estructura es bastante simple, cada línea de estos archivos tiene solo 2 campos, ambos significan un tipo de gen.

Mi objetivo es: diseñar un algoritmo eficiente que pueda lograr lo siguiente: Busque un círculo dentro del contenido de estos 4 archivos. El círculo se define como:

field #1 in a line in file 1 == field #1 in a line in file 2 and 
field #2 in a line in file 2 == field #1 in a line in file 3 and 
field #2 in a line in file 3 == field #1 in a line in file 4 and 
field #2 in a line in file 4 == field #2 in a line in file 1 

No puedo pensar en una manera decente de resolver esto, por lo que acaba de escribir un bucle de fuerza bruta-estúpida-4-capa anidada por ahora. Estoy pensando en clasificarlos como orden alfabético, incluso si eso podría ayudar un poco, pero también es obvio que la memoria de la computadora no me permite cargar todo a la vez. ¿Alguien puede decirme una buena manera de resolver este problema de manera eficiente tanto en tiempo como en espacio? ¡¡Gracias!!

Answer 1

En primer lugar, observo que se puede ordenar una archivo sin almacenar todo de una vez, y que la mayoría de los sistemas operativos tienen algún programa que hace esto, a menudo llamado simplemente "ordenar". Por lo general, puede hacer que ordene en un campo dentro de un archivo, pero si no puede reescribir cada línea para que se ordene de la forma que desee.

Dado esto, puede conectar dos archivos clasificándolos para que el primero se clasifique en el campo # 1 y el segundo en el campo # 2. A continuación, puede crear un registro para cada coincidencia, combinando todos los campos y solo manteniendo en la memoria un fragmento de cada archivo donde todos los campos que ha ordenado tienen el mismo valor. Esto le permitirá conectar el resultado con otro archivo; cuatro de estas conexiones deberían resolver su problema.

Dependiendo de sus datos, el tiempo que lleva resolver su problema puede depender del orden en que realice las conexiones. Una manera bastante ingenua de utilizar esto es, en cada etapa, tomar una pequeña muestra aleatoria de cada archivo, y usar esto para ver cuántos resultados se obtendrán de cada conexión posible, y elegir la conexión que produce el menor número de resultados. Una forma de tomar una muestra aleatoria de N elementos de un archivo grande es tomar las primeras N líneas en el archivo y luego, cuando haya leído en m líneas hasta ahora, lea la siguiente línea, y luego con probabilidad N/(m + 1) intercambia una de las N líneas que tiene reservadas, de lo contrario, deséchalo. Continúa hasta que hayas leído todo el archivo.

Answer 2

Aquí es un algoritmo:

• Seleccione una estructura de consulta apropiada: Si el campo # 1 es un número entero, utilice campos de bits o un diccionario (o un conjunto) si es una cadena; Use una estructura de búsqueda para cada archivo, es decir, 4 en su caso
• Fase de inicialización: para cada archivo: analice el archivo línea por línea y configure el bit apropiado en el campo de bit o agregue el campo al diccionario en la búsqueda correspondiente estructura para el archivo.
• Después de inicializar la estructura de búsqueda anterior, verifique la condición en su pregunta.

La complejidad de esto depende de la implementación de la estructura de búsqueda. Para los campos de bits, será O (1) y para el conjunto o diccionario, será O (lg (n)), ya que generalmente se implementan como un Árbol de búsqueda equilibrada. La complejidad completa será O (n) u O (n lg (n)); Se solución en la cuestión tiene complejidad de O (n^4)

Puede obtener el código y la solución para los campos de bits de here

HTH

Answer 3

Aquí es uno de los enfoques:

Utilizaremos la notación Fxy donde x = número de campo, y = file_no

clasificar cada uno de los 4 archivos en los primeros campos.

Para cada campo F11, busque una coincidencia en el archivo 2. Esto será lineal. Guarde estas coincidencias con los cuatro campos en un nuevo archivo. Ahora, use este archivo y use el campo correspondiente en este archivo y obtenga todas las coincidencias del archivo3. Continuar para el archivo4 y volver al archivo1.

De esta manera, a medida que avance a cada nuevo archivo, se trata de un menor número de líneas. Y como ha ordenado los archivos, busque en forma lineal y puede hacerlo leyendo desde el disco.

Aquí la complejidad en O (n log n) para la clasificación, y O (m log n) para la búsqueda, suponiendo m < < n.

Answer 4

Es un poco más fácil de explicar si su archivo 1 es al revés (por lo que cada segundo elemento apunta a un primer elemento en el archivo siguiente).

1. de inicio con archivos 1, copiarlo en un nuevo archivo de la escritura de cada par A, B como B, A, 'REV'

2. Anexar el contenido del archivo 2 a ella escribiendo cada A, B par como a, B, 'FWD'

3. Ordenar el archivo

4. procesar el archivo en trozos con el mismo valor inicial

   • Dentro de ese grupo trozo las líneas en REV de y FWD de
   • tomar el producto cartesiano de las revoluciones y la FWDs (bucle anidado)
   • escribir una línea con marcha atrás (fwd) concat (rev) excluyendo el repetido contador
   • por ejemplo B, A, 'REV' y B, C, FWD '-> C, B, A, 'REV'

5. Anexar el siguiente archivo a este nuevo archivo de salida (añadiendo 'FWD' para cada línea)

6. Repita desde el paso 3

en esencia usted está construyendo una cadena en orden inverso y el uso de un algoritmo de ordenación basada en archivos para poner juntas las secuencias que se pueden combinar.

Por supuesto sería aún más fácil de leer simplemente estos archivos en una base de datos y deja que haga el trabajo ...