Что такое хорошая структура данных для хранения совокупных значений?

Question

Я ищу идею, концепцию или проверенную структуру данных, которая была бы очень эффективной при доступе к коллекции, в которой хранятся совокупные значения.

Пример может пролить больше света на мои нужды:

У меня есть список значений (2,3,5). Этот список при рассмотрении совокупных значений будет (2,5,10).

Теперь я добавлю 1 в начале списка и получу (1,2,3,5) и в совокупном выражении (1,3,6,11).

Мне нужно только взглянуть на совокупные значения, меня совсем не интересуют 1,2,3,5. Мне нужно иметь возможность быстро вставлять в позицию, удалять позицию, и все это должно быстро обновить накопительный массив (в идеале, без итерации по всему массиву и пересчета значений.

Есть идеи или намеки?

@ Кристо (слишком долго, чтобы поместить в комментарии): Чтобы выяснить, почему отрицательные числа делают значение общей суммы бессмысленным, следуйте этому примеру.

Вставьте 1, а затем -1. Сумма 1, чем 0. (1, -1) // (1,0) Вставить 3, а затем вставить -3. Сумма 3, затем 0. (1,3, -1, -3) // (1,4,3,0) Вставьте 2, а затем вставьте -2. Сумма 2, затем 0. (1,3,2, -1, -2, -3) // (1,4,6,5,3,0)

Если бы мое "магическое число" составляло 4, общая сумма не указала бы, превысила ли я его.

PS: Основная причина этого в том, что я могу сказать, прошел ли я определенное значение и где в цепочке.

Answer 1

Единственная оптимизация, о которой я могу подумать - это «ленивая» оценка накопительного списка.

в дополнение к вашему списку исходных значений, отслеживайте номер наивысшей позиции в совокупном списке, который является точным. если вам нужно число больше этого, вы переходите вверх по списку, обновляете значения и индекс.

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 

если конечно, это не принесет вам много пользы, если вы обычно добавляете элементы в начале списка ....

Answer 2

Используйте двоичное дерево поиска с дополнительным свойством, что узлы содержат сумму их поддерева. Все операции по-прежнему O (LG N). Чтобы вставить или удалить значение, вы выполняете обычную процедуру, а также обновляете суммы всех родителей. Получить сумму так же просто, как найти узел, содержащий элемент, и вернуть его сумму минус сумма его правого потомка.

Answer 3

Проверьте таблицу совокупных частот .

Answer 4

В C # я сохраню все фактические значения в списке и использую пользовательский итератор для циклического перебора накопленных значений.

Вы будете пересчитывать только до того момента, когда итератор скажет вам, что вы превысили свой лимит (очевидно, вам придется код для этого).

Я думаю, что ценность в том, что вы можете добавлять / удалять без каких-либо вычислений до тех пор, пока не пришло время перебирать список (что, я думаю, вам нужно сделать в любом случае, чтобы найти номер отсечки).

Answer 5

• Вы можете посмотреть на структуру данных для кумулятивной частоты Двоичных индексированных деревьев

• Вы можете разбить свой диапазон значений на фиксированные битовые диапазоны. Ex. 3 интервала:

  #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;
  }
  

Answer 6

Используя термины C ++, не могли бы вы получить std::list (легкие вставки / удаления в середине) или std::set (всегда отсортированные) для данных и одну переменную для хранения суммы? При каждой вставке / удалении вы меняете сумму соответствующим образом. Сумма представляет наибольшее число в вашем потенциальном накопительном списке. Только когда вы разорите свое магическое число, вам нужно будет выполнить некоторую алгоритмическую работу, чтобы выяснить, куда вы попали.

Обновление:

На основании вашей новой информации я не вижу много доступных ярлыков. Вам нужно часто вставлять или удалять из середины, что предполагает какой-то подход со связанным списком. Вы можете сэкономить немного вычислений, обновляя только те части списка, которые изменились. Пусть L будет список значений, а n будет желаемое место в списке. Чтобы вставить значение x в местоположение n:

• Введите значение x + L(n-1) в местоположении n
• Добавить x ко всем элементам после этого нового n
• Стоп, если вы разорите свой магический номер

Процедура удаления та же самая, за исключением того, что вы вычитаете все последующие значения. Таким образом, вы выполняете большую работу, только если вставляете ее в начале.

Answer 7

Я вижу два простых способа, оба используют базовые типы данных - списки.

1. Сохраняйте исходный список и пересчитывайте совокупные значения при каждом изменении.

2. Сохраняйте только совокупный список и только добавляйте к нему или удаляйте, используя такие функции, как:

   • Добавить (элемент, позиция по умолчанию - конец списка ) добавит значение элемента, начиная с позиция -1.
   • При удалении (позиция) исходное значение рассчитывается путем вычитания двух чисел, а затем перед удалением элемента уменьшается это число из остальной части списка.

   Добавить 2: (2) добавляет 2 в пустой список.

   Добавить 3: (2,5) добавляет 3 в конце списка к предыдущему элементу (2).

   Добавьте 5: (2,5,10) добавляет 5 в конце списка к предыдущему элементу (5).

   Добавить 1 в начале: (1,3,6,11) добавляет 1 в начале списка и увеличивает на 1 до конца (без предыдущих элементов).

   Добавьте 7 на 2-й позиции: (1,8,11,14,19) добавляет 7 и увеличивает на 7 до конца (без предыдущих элементов).

   Удалить 3-ю позицию ( 11 ): (1,8,3,8) получить значение, удалить его, добавить значение к остальным.

Таким образом, все будет синхронизировано без сохранения исходных значений.