Эффективный алгоритм вставки / удаления для массива

Question

Я подписываюсь на фид данных и из этого создаю и поддерживаю структуру, используя значения индекса в сообщениях INSERT / DELETE. Я хотел бы спросить собравшихся cognoscenti, знают ли они о каком-либо алгоритме, который может эффективно обрабатывать частичные обновления - обычно пакетные обновления содержат от двух до шести таких сообщений.

Расчетный размер массива составляет около 1000 элементов.

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

Мне приходит в голову, что с некоторой базовой обработкой я могу определить диапазон, на который влияет пакет, и общую дельту размера, и, следовательно, переместить незатронутую хвостовую часть массива только один раз.

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

Другие оптимизации включают распознавание обновлений, таких как:

DELETE 10, INSERT 10 - effectively a replace which requires no copying  
INSERT 10, DELETE 11 - as above  
DELETE 10, DELETE 10, DELETE 10 - bulk deletion can be optimised into one copy operation  
INSERT 11, INSERT 12, INSERT 13 - bulk insertion can be optimised into one copy operation  

и так далее.

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

Учитывая ожидаемый размер массива, древовидные структуры кажутся тяжеловесными: некоторые базовые тесты производительности предполагают, что двоичные или самобалансирующиеся деревья (в данном случае реализация списка красно-черных деревьев) начинают демонстрировать преимущества в производительности только после 15 КБ. - 20 тыс. Элементов: копии массива значительно быстрее при меньших размерах. Я должен, вероятно, добавить, что я использую Java для этой реализации.

Любые намеки, советы или предложения будут приветствоваться.

Приветствия

Mike

Answer 1

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

Если вам нужно совсем немного манипулировать, связанный список может быть полезен.

Для простого понятного кода, однако, я бы использовал Apache Commonsсборщик утилит для необработанного массива или массива в противном случае:

myArray = ArrayUtils.add(myArray, insertionIndex, newItem);

ИЛИ

ArrayList<> mylist = new ArrayList<>(Arrays.asList(myArray));
myList.add(insertionIndex, newItem);

Answer 2

В общем, если у вас есть изменения, перечисленные в порядке индекса, вы можете создать простой цикл, который копирует только один раз.Вот некоторый псевдокод:

array items;
array changes; // contains a structure with index, type, an optional data members
array out; // empty, possibly with ensureCapacity(items.length)
int c = 0, delta = 0;
// c is the current change
//delta tracks how indexing has changed by previous operations
for (i = 0; i < items.length; i++) {
    if c < changes.length {
        curchange = changes[c]
        if (i + delta) == curchange.index {
            c++;
            if (curchange.type == INSERT) {
                out.add(curchange.data)
                delta--;
            } else {
                delta++;
                continue; // skip copying i
            }
        }
    }
    out.add(items[i])
}
for (; c < changes.length; c++) { // handle trailing inserts
    assert(c.index == out.length && c.type == INSERT)
    out.add(c.data);
}

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

Обратите внимание, что он не обрабатывает несколько вставок в одном месте,Это сделало бы код немного более сложным, чтобы сделать это, но это не слишком сложно.

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

Answer 3

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

Например:

class EventQueue
{
  Vector eventQueue;
  HashMap eventMap;

  public synchronized Event getNextEvent()
  {
      Event event = eventQueue.remove(0);
      eventMap.remove(event.getId());  // this would be 10 from 'INSERT 10' 
                                       // in the sample from the OP
  }

  public synchronized addEvent(Event e)
  {
     if( eventMap.containsKey(e.getId())
     {
        // replace events that already exist
        int idx = eventMap.get(e.getId());
        eventQueue.removeElementAt(idx);
        eventQueue.add(idx, e);
     } else {
        // add new events
        eventQueue.add(e);
        eventMap.add(e.getId(), eventQueue.size()); // may be off by one...
     }
  }

  public boolean isReady()
  {
    return eventQueue.size() > 0;
  }
}

class FeedListener extends Thread {
 EventQueue queue;
 EventFeed feed;
 ...
 public void run()
 {
    while(running) {
       sleep(sleepTime);
       if( feed.isEventReady() ) {
         queue.addEvent(feed.getEvent());
       }
    }
 }
}

abstract class EventHandler extends Thread {
 EventQueue queue;
 ...
 public void run()
 {
   while(running)
   {
     sleep(sleepTime);
     if( queue.isReady() )
     {
       Event event = queue.getNextEvent();
       handleEvent(event);
     }
   }
 }

 public abstract void handleEvent(Event event);
}

Answer 4

Если пространство не является ограничением, и у вас не будет дубликатов, перейдите к Set datastructure, в частности Java HashSet.Сила этой структуры данных заключается в том, что вставка и удаление выполняются за O (1) раз, что лучше всего подходит для вас, если производительность является критерием «*».

Более того, всякий раз, когда вы говорите о массивах, помимо их быстрого поиска,у вас есть серьезное ограничение для множества копий массива, которые могут произойти, что не только займет место (для увеличения массива), но также будет низкой эффективностью, так как каждая из операций вставки / удаления может занять O (n) времени.

Answer 5

Существует чрезвычайно простая для реализации структура данных, называемая "декартовы деревья" или "Treaps", которая позволяет O (log N) разбивать, объединять, вставлять и удалять массивы (и многие другие).

2-3 дерева также очень просты в реализации (моя реализация несколько более сложного средства содержала всего 1 ошибку после первой компиляции) и соответствует вашей цели.

Answer 6

Использование связанного списка (java.util.LinkedList) может быть чем-то, на что стоит обратить внимание.Получение элемента по определенному индексу, конечно, дорого, но это может быть лучше, чем копирование массива.

Answer 7

Помимо сортировки отдельных обновлений (как вы уже упоминали), чтобы попытаться объединить вещи, я не знаю, что я бы сильно беспокоился.Честно говоря, 1000 элементов - это ничего особенного.У меня есть система с 25M элементами, использующая простые массовые копии, и она (для наших целей) выходит далеко за рамки более чем достаточно быстрой.но я мог бы сначала взглянуть на него на книжной полке.

Answer 8

Самое простое - запустить обновления и скопировать массив в новый массив при применении обновлений.

1000 не так уж велик, и, вероятно, дальнейшая оптимизация не стоит.

И чтобы сделать вашу жизнь проще, используйте ArrayList.