Структура данных сетки

Обычно "расширяемые сетки" представлены в виде списка списков (список строк, каждая строка имеет список ячеек), и эти списки представляют собой некоторые связанные списки.

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

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

Наконец, мне нужна какая-то многомерная сетка, но я думаю, что любая 2d простая сетка применима для MD, я прав?

3 ответа

У вас может быть двумерная "связанная матрица" (я забыл правильную терминологию):

... Col 3 ... Col 4 ...
 | |
... --X-- ... --Y-- ...
 | |
... ... ... ... ...

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

Вставка нового столбца между 3 и 4 означает итерацию по ячейкам X в столбце 3 и вставку нового правого соседа Z. Эта новая ячейка Z связывает влево и вправо X и направо на Y. Вам также нужно добавить новый столбец заголовка и связать новые ячейки по вертикали. Затем позиции всех столбцов после 4 можно перенумеровать (col 4 становится col 5).

... Col 3 Col 4 Col 5 ...
 | | |
... --X-----Z-----Y-- ...
 | | |
... ... ... ... ...

Стоимость вставки столбца - O (n) для вставки и связывания новых ячеек и снова O (m) для обновления заголовков столбцов. Это аналогичный процесс для удаления.

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


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

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

Кстати, схема Эдмунда будет хорошо для вас. Несмотря на то, что для удаления строки или столбца длины n требуется время O (n), вы, вероятно, можете амортизировать эту стоимость по сравнению с затратами на создание этих n элементов, делая время удаления O (1).


Я знаю, что "Linked-Lists" обычно оцениваются с теоретической точки зрения, но на практике они обычно неэффективны.

Я бы предложил перейти к контейнерам с произвольным доступом, чтобы получить некоторую скорость. Самый простой был бы массив, но в зависимости от размера данных, о котором мы говорим, может быть лучше двухстрочная очередь или индексированный список пропусков /B *.

Понятно, что оно мало меняет (пока), однако вы можете перейти к заданному индексу в O (1) (массив, deque)/O (log N) (список пропуска /B * tree) а не O (N) с простым связанным списком.

И тогда это время для магии.

Keith уже раскрыл основную идею: вместо фактического удаления столбца вам просто нужно пометить ее как удаленную, а затем "прыгать" над ней, когда вы идете по своей структуре. Однако хэш-таблица требует линейного перехода, чтобы добраться до N-го столбца. Использование дерева Fenwick даст эффективный способ вычисления реального индекса, и вы можете сразу перейти туда.

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

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

licensed under cc by-sa 3.0 with attribution.