Массоподобное представление данных

Question

Я пытаюсь оптимизировать структуру данных, которая интенсивно используется. Прямо сейчас эта структура данных реализована как динамический массив составных узлов. Типичное использование - последовательный доступ от первого элемента к последнему элементу с чтением и изменением составляющих значений (целых и двойных). Типичный размер массива составляет от 10 до 200 элементов. Другой тип операции - вставка / удаление элементов этого массива. После некоторого профилирования я обнаружил, что вставки очень дороги с точки зрения общей производительности алгоритма, поэтому я решил изменить этот массив на одну из двух структур данных:

1. Массив указателей на элементы
2. Массив индексов для другого массива, содержащего фактические элементы

Таким образом, я буду делать только вставки и удаления в массиве индекса / указателя, который намного дешевле.

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

Answer 1

Существует очень изящная структура данных, называемая многоуровневым вектором, которая поддерживает O (1) поиск в худшем случае, O (1) амортизированное добавление и O (sqrt n) амортизированное вставление в любой точке структуры. Более того, это очень эффективно использует память, тратя впустую только O (sqrt n) служебных данных в любой точке (по сравнению с O (n) издержками динамического массива). Я не знаю, насколько это может быть полезно в вашем конкретном случае, но описание можно найти здесь:

http://www.cs.brown.edu/cgc/jdsl/papers/tiered-vector.pdf

Answer 2

Как выполняется вставка / удаление, неясно, но согласно вашему текущему описанию вы должны использовать простой связанный список.

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

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

Answer 3

Задумывались ли вы об использовании списка пропусков , в частности "индексируемого списка пропусков"?Индексируемый список пропуска дает вам O (logn) операции вставки, удаления и поиска.Кроме того, он похож на текущую реализацию на основе массива, поэтому он не изменит принципиально то, как выглядит структура данных.