Структура данных для упорядоченного набора с множеством определенных подмножеств;получить подмножества в том же порядке - PullRequest
Новая
       10

Структура данных для упорядоченного набора с множеством определенных подмножеств;получить подмножества в том же порядке

5 голосов
/ 13 января 2011

Я ищу эффективный способ хранения упорядоченного списка / набора элементов, где:

  1. Порядок элементов в основном наборе изменяется быстро (подмножества поддерживают порядок основного набора)
  2. Многие подмножества могут быть определены и извлечены
  3. Количество членов в основном наборе быстро растет
  4. Члены часто добавляются и удаляются из подмножеств
  5. Должендопускает несколько эффективное объединение любого количества подмножеств

Производительность в идеале должна быть смещена в сторону извлечения первых N элементов любого подмножества (или объединенного подмножества), а память будет находиться в памяти (и, возможно,в конечном итоге на диске)

1 Ответ

2 голосов
/ 26 мая 2011

Я новый участник этого форума, надеюсь, вы не забыли об этом старом вопросе:)

Решение

Сохраните основной набор в индексированной структуре данных - например, какмассив (или массив, если ваша библиотека поддерживает это).Предположим, вы можете связать идентификатор с каждым набором (если нет, то как узнать, какой набор получить?).Итак, теперь нам нужен способ выяснить, какие элементы вашего массива участвуют в этом наборе, а какие нет.

Используйте матрицу (n x m), где n - это количество элементов в вашем массиве.и m - начальное количество комплектов.i относится к индексу строки, а j относится к индексу столбца. 

A[i][j] = 0 if ith element is not in jth set
A[i][j] = 1 if ith element is in jth set

Не используйте простой двумерный массив, выберите ArrayList<ArrayList>.Java / C # / C ++ поддерживают такие общие конструкции, но это не должно быть очень сложно сделать в других языках, таких как Perl.В C # вы даже можете использовать DataTable.

Время, чтобы добавить новый набор

Вы можете добавить новый набор за O(n) время.Просто добавьте новый столбец для этого набора и установите соответствующие строки в 1 для этого столбца.Нет необходимости сортировать этот набор, пока исходный массив отсортирован.

Время добавления нового элемента

В простом отсортированном массиве время для вставки равно O(log n).В нашем случае мы сначала добавим элемент в массив (и при любом индексе, в который мы добавили элемент, матрица также получит строку всего 0 с этим индексом).Затем мы устанавливаем записи в этом столбце равными 1, если элемент принадлежит набору.Таким образом, наихудшим временем выполнения становится O(log n) + O(m).

Время для извлечения первых N элементов из набора

Выберите столбец, соответствующий набору во времени O(1), а затем выберитепервые N записи, которые 1.Это будет линейно.

Время объединения двух наборов

Допустим, мы объединяем наборы в j1 и j2 в третий набор в j3. 

for (int i = 0; i < n - 1; i++) {
    A[i][j3] = A[i][j1] | A[i][j2];
}

Этоснова линейно.

Время для удаления элемента

Сначала найдите элемент в мастер-массиве - это займет O(log n) времени.Затем удалите его из этого массива и удалите строку с этим индексом из матрицы.

Эффективные удаления из массива

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

...