Mejora de pasar a través de una matriz dos veces (bucle anidado en el mismo array)

Question

Tengo un gran conjunto de datos que quiero ciclo a través con el fin de determinar diversas estadísticas sobre el conjunto de datos a partir de un punto en el tiempo 'D1' a un punto a tiempo en el futuro 'D2'. Básicamente, quiero añadir a una base de datos cada vez que la diferencia entre los valores es mayor que 10. Por ejemplo:

Datum[] data = x; 
for(Datum d1 : data){ 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(Datum d2 : tail){ 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 
     } 
    } 
} 

Mi pregunta es, ¿hay un mejor algoritmo/método para hacer esto? Dado que 9 elementos de la cola se reutilizan en la próxima iteración del ciclo externo, ¿puedo beneficiarme de alguna manera de eso? Mi objetivo era bajar esto a mucho menos que (Notación de Big-O) O (n), pero no puedo entenderlo. Por lo general, encontrar un par D1, D2 que satisfaga los criterios significa que el siguiente elemento D1 tendrá una mayor probabilidad de coincidir también. ¿Puedo usar eso para mi ventaja?

Estoy tratando de que esto sea lo más eficiente posible porque el conjunto de datos es muy grande.

Answer 1

Un bucle for-basada índice podría realizar mucho mejor que un iterador, ya que puede indexar la matriz original directamente y evitar el copiado a una nueva matriz. Tendrías mucho mejor localidad de memoria, menos posibilidades de compartir falsa, etc.

Answer 2

En sus zapatos, lo primero que haría es el perfil de un típico conjunto de datos y averiguar donde el tiempo se va. Esto debería dar algunas pistas sobre dónde enfocar sus esfuerzos de optimización.

Suponiendo que el cálculo es tan simple como la resta/comparación, y las matrices se acceden rápidamente, su sugerencia de buscar optimizar el guardado en la base de datos debe ser la siguiente prioridad. Por ejemplo, escribir un archivo de texto y usar una inserción masiva puede proporcionar un rendimiento muy rápido en comparación con las instrucciones de inserción individuales. Si se limita a utilizar insertos separados y está utilizando JDBC, las actualizaciones por lotes serán de gran ayuda, ya que evitan la latencia al comunicarse con la base de datos.

Si ese es todavía no lo suficientemente rápido, considere la partición de la matriz en N particiones, y tienen cada partición procesada por un hilo separado. Esto será particularmente efectivo si el procesamiento está vinculado a la CPU.

Finalmente, busque optimizaciones a nivel de código, como evitar iteradores mediante el uso de un índice. Si el número de elementos escritos en la base de datos es pequeño en comparación con el número de elementos iterados, entonces la creación del iterador puede ser un cuello de botella.

Si el número de elementos es mayor que 10, y crítica, más que puede caber en la memoria caché de la CPU, que será más eficiente para romper la exploración en bloques más pequeños. Por ejemplo, en lugar de escanear 1000 elementos de data2, divídalo en (digamos) 10 escaneos de 100, con cada uno de los 10 escaneos usando un valor diferente de d1. Esto es similar a cómo la multiplicación de matriz se implementa de forma bloqueada y hace un mejor uso de las memorias caché de la CPU.

Aunque está utilizando dos bucles, que normalmente es un algoritmo O (N^2), el segundo bucle tiene un tamaño fijo - 10 elementos, por lo que se reduce a un factor constante simple - usted está haciendo aproximadamente un factor de 10 trabajos más

Answer 3

lo que tienes es un algoritmo de sweepline clásico que son O (k * n) con k el "solapamiento" o la porción que el bucle interno se ejecuta sobre. en su caso es máximo 10 no importa lo que n es

Datum[] data = x; 
for(int i=0;i<data.length;i++){ 
    Datum d1=data[i]; 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(int j=i+1;j<Math.min(i+10,data.length);i++){ 
     d2 = data[j]; 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 

      break;//inner loop 
     } 
    } 
} 

Answer 4

Hay un asintóticamente más rápida manera de resolver este problema, pero tengo serias dudas sobre si sería correr más rápido en la práctica debido a su tamaño de la ventana (10) es tan pequeño.Si desea aumentar este tamaño, que llamaré k, para que sea más grande, entonces puede considerar optar por un enfoque como el siguiente.

Al utilizar este algoritmo, es necesario mantener una ventana de los k elementos que soporta dos operaciones:

1. insertar un nuevo elemento, el desalojo de los más antiguos.
2. Devuelve todos los elementos mayores que algún valor.

Una forma de hacerlo sería almacenar todos sus elementos en una estructura de datos que combine un árbol de búsqueda binaria equilibrado y una cola. La cola contiene todos los elementos k almacenados en el orden en que aparecen en la secuencia original, y se utiliza para que podamos recordar qué elemento desalojar cuando necesitamos agregar un nuevo elemento. El BST equilibrado almacena una copia de cada uno de esos elementos almacenados en orden ordenado. Esto significa que se puede implementar las operaciones anteriores como este:

1. insertar un nuevo elemento, el desalojo de los más antiguos: Añadir el nuevo elemento a la cola y BST. Luego, quite la cola de la cola para obtener el elemento más antiguo y luego elimínelo de la BST. Tiempo de ejecución: O (log k), ya que la BST tiene k elementos en ella.
2. Devuelve todos los elementos mayores que algunos valores: Usando la BST, encuentre el elemento más pequeño al menos tan grande como ese valor en el tiempo O (log n). Luego, escanee el BST y enumere todos los elementos al menos tan grandes como ese elemento. Esto toma el tiempo O (z), donde z es el número total de coincidencias encontradas.

Colectivamente, si tiene n elementos y un total de z pares que necesita insertar en la base de datos, este algoritmo tomará O (n log k + z) tiempo. Para ver esto, tenga en cuenta que hacemos un total de n copias de la operación (1), que toma el tiempo O (log k) cada una. También hacemos n copias de la operación (2), que toma el tiempo O (n log k) para encontrar los sucesores y luego O (z) el tiempo total en todas las iteraciones para listar todos los pares coincidentes.

El tiempo de ejecución asintótico de este algoritmo es bueno en comparación con el algoritmo O (nk) que ha publicado originalmente. Suponiendo que el número de coincidencias no es "realmente enorme" (digamos, del orden de nk), será mucho más rápido a medida que aumenta nyk.

Si los valores que almacena son enteros en un rango pequeño (digamos, 0 - 10,000), puede acelerar esto aún más reemplazando la BST balanceada con una estructura de datos optimizada para enteros, como van Emde Boas tree, que reduce esto a O (n log log k + z). De nuevo, esto solo es más rápido asintóticamente, y si mantiene k constante en 10, esto casi seguro no lo vale.

Espero que esto ayude!