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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

Я знаю, что «связанные списки» обычно ценятся с теоретической точки зрения, но на практике они, как правило, неэффективны.

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

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

А потом пришло время магии.

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

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

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