¿Cuál es una buena estructura de datos para mantener los valores acumulados?

Question

Estoy buscando una idea, concepto o estructura de datos probada que sea muy eficiente al acceder a una colección que mantiene valores acumulativos.

Ejemplo puede arrojar más luz sobre mi necesidad:

tengo una lista de valores (2,3,5). Esta lista al observar los valores acumulativos sería (2,5,10).

Ahora agregaré 1 al comienzo de la lista y obtendré (1,2,3,5) y en términos acumulados (1,3,6,11).

Solo necesito mirar los valores acumulativos, no estoy interesado en absoluto en el 1,2,3,5. Tengo que ser capaz de insertar rápidamente en la posición, quitar una posición y todo esto debería actualizar rápidamente la formación acumulativa (idealmente sin iteración a través de toda la matriz y volver a calcular los valores.

Cualquier idea o sugerencias?

@ Kristo (demasiado largo para poner en el comentario): Para aclarar por qué los números negativos harían que el valor de la suma total no tenga sentido, siga este ejemplo.

Inserte 1 seguido de -1. Suma es 1 que 0. (1, - 1) // (1,0) Insertar 3 seguido de insertar -3. Suma es 3 luego 0. (1,3, -1, -3) // (1,4,3,0) Insertar 2 seguido de insertar -2. Suma es 2 luego 0. (1,3,2, -1, -2, -3) // (1,4,6,5,3,0)

Si mi "número mágico" fuera 4 la suma total no me diría si la he excedido.

PD: La razón principal de esto es poder decir si supere cierto valor y en qué parte de la cadena.

Answer 1

La única optimización que puedo pensar es hacer una evaluación 'floja' de la lista acumulativa.

Además de su lista de valores de origen, lleve un registro de la posición más alta en la lista acumulativa que sea precisa. si necesita un número más alto que eso, sube la lista, actualizando los valores y el índice.

 
idx values  cumulative operation 
3 (2,3,5)  (2, 5, 10) 
0 (1,2,3,5) (X,X,X,X)  insert 1 at 0 
3 (1,2,3,5) (1,3,6,X)  look for value over 5  
3 (1,2,3,5,4) (1,3,6,X,X) insert 4 at 4 

si Por supuesto, esto no usted hacer un montón de buena si está por lo general la adición de elementos al principio de la lista ....

Answer 2

Compruebe el cumulative frequency table.

Answer 3

Hay dos maneras simples que veo, ambas usan tipos de datos básicos: listas.

1. Conserve la lista original y vuelva a calcular los acumulativos en cada cambio.

2. sólo mantener la lista acumulativa, y sólo añadir a la misma o eliminar mediante el uso de funciones como:

   • Añadir (artículo, la posición defecto es final de la lista) añadiría el valor del elemento de partida desde posición -1.
   • Borrar (posición) calcularía el valor original restando dos números, luego disminuye este número del resto de la lista antes de eliminar el elemento.

   Agregar 2: (2) agrega 2 a la lista vacía.

   Agregar 3: (2,5) agrega 3 al final de la lista al elemento anterior (2).

   Agregar 5: (2,5,10) agrega 5 al final de la lista al elemento anterior (5).

   Agregue 1 al inicio: (1,3,6,11) agrega 1 al principio de la lista y aumenta en 1 hasta el final (sin elementos previos).

   Agregue 7 en la 2da posición: (1,8,11,14,19) suma 7 e incrementa en 7 hasta el final (sin elementos previos).

   Eliminar tercera posición (11 El): (1,8,3,8) obtener el valor, eliminar, añadir el valor al resto.

De esta manera sería mantener todo sincronizado sin mantener los valores originales.

Answer 4

Utilizando términos C++, ¿podría salirse con la std::list (inserta/quita fácilmente en el medio) o std::set (siempre ordenado) para los datos y una variable para contener la suma? En cada inserción/eliminación, modifica la suma según corresponda. La suma representa el número más alto en su lista acumulativa potencial. Solo cuando destruyes tu número mágico necesitas hacer un trabajo algorítmico para descubrir dónde atrapaste.

Actualización:

Sobre la base de la nueva información, no veo muchos atajos disponibles. Debe insertar o eliminar con frecuencia desde el medio, por lo que sugiere algún tipo de enfoque de lista vinculada. Puede guardar un poco de cálculo actualizando solo las partes de la lista que han cambiado. Deje L ser la lista de valores y n sea la ubicación deseada en la lista. Para insertar el valor x en la ubicación n:

• insertar el valor x + L(n-1) en la ubicación n
• Añadir x a todos los elementos después de esta nueva n
• parada cuando se pase el número mágico

El El procedimiento es el mismo para una eliminación, excepto que resta de todos los valores posteriores. De esta manera, solo estás haciendo un montón de trabajo si lo insertas cerca del principio.

Answer 5

En C#, mantendría todos los valores reales en una lista, y usaré un iterador personalizado para recorrer los valores acumulativos.

Solo recalculará hasta el punto en que el iterador le indique que ya pasó su límite (obviamente, tendría que codificar para eso).

Creo que el valor es que puede agregar/eliminar sin hacer ningún cálculo hasta que sea el momento de iterar sobre la lista (que creo que debe hacer de todos modos para encontrar el número de corte).

Answer 6

Uso de un árbol de búsqueda binaria con la propiedad adicional de que los nodos contienen el suma de su subárbol. Todas las operaciones siguen siendo O (lg n). Para insertar o eliminar un valor, realice el procedimiento normal y actualice las sumas de todos los padres. Obtener la suma es tan fácil como encontrar el nodo que contiene el elemento y devolver su suma menos la suma de su hijo derecho.

Answer 7

• Usted puede mirar en una estructura de datos para la frecuencia acumulada Binary Indexed Trees

• Puede romper su rango de valores en rangos de bits fija. Ex. 3 intervalos:

  #define NUM (1<<24) // max value in your data set 
  #define BITS0 8 
  #define BITS1 8 
  int cum0[NUM >> (BITS0+BITS1)]; // sum of cum1 
  int cum1[NUM >> BITS1]; // sum of count 
  int count[NUM]; 
  
  int add(id, val) { // add a value 
      cum0[id >> (BITS0+BITS1)] += val; 
      cum1[id >> BITS1] += val; 
      count[id] += val;      
  } 
  
  int cumvalue(int id) { int cum = 0; // return cum value at index id   
      for(i = 0; i < (id >> (BITS0+BITS1));i++) cum += cum0[i]; i <<= BITS0; 
      for(i = (id & ~((1 << (BITS0+BITS1))-1)) >> BITS1; i < (id >> BITS1); i++) cum+= cum1[i]; i <<= BITS1; 
      for(i = id & ~((1 << BITS1) -1); i < id; i++) cum += count[i];    
      return cum; 
  }