Существует ли структура данных «расширяемая 2D-таблица»?

Question

[Mercury13]

Хочу такую структуру данных: расширяемая/сужаемая двухмерная таблица.

То есть: у нас, например, таблица 5×5, и мы к ней сверху добавляем строку, и стала 6×5. А потом справа добавляем два столбца, и стала 6×7. А потом снизу убираем две строки, и стала 4×7.

Расширение и сужение возможно только с краёв — то есть нельзя убрать строку или столбец из середины, и нельзя добавить ничего в середину.

Подскажите, в каком направлении двигаться?

Comments

[Сергей Соколов]

В чем сложность?

[Mercury13]

Сергей Соколов, Как уменьшить количество выделений-перевыделений памяти и переносов данных.

Answer 1

[Mercury13]

Пока остановился на таком механизме.
Есть два одномерных массива — оглавление строк и оглавление столбцов, два одномерных массива — задействованность строк/столбцов, а также двухмерный массив — буфер.

a[i,j] := buffer[rowIndex[i−i0], colIndex[j−j0]]

Если в rowIndex[i−i0] замечен маркер незадействованности, находим незадействованную строку и прописываем её в оглавлении.
Чтобы меньше перевыделять памяти, перевыделение идёт импульсами и с запасом. Например, хотим 20 строк, а выделяем сразу на 30.
Такой массив способен только расширяться, но этого мне хватает.

Answer 2

[Сергей Соколов]

можно не ограничиваться 2D
Как вариант — подсмотреть реализацию ndarray в Numpy.
Частично описано здесь (на англ.)
Данные хранятся в буфере – типа массива в C. И есть метаданные, описывающие "вид" на этот буфер.
Когда меняется форма, создаётся новый объект метаданных, без изменений в самих данных.
Но тут не раскрывается тема вставки, как это изменяет размер буфера – создают новый или расширяют старый. В конце или распихивают по строкам.

Answer 3

[mayton2019]

Коробочное решение это хеш-табличка. Где ключ - координаты ячейки а значение это то что вы положите в ячейку.

Answer 4

[WinPooh32]

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

Вы можете реализовать сами:
1) С помощью связного списка;
2) На массиве, с заранее выделенной памятью, с добавлением элементов в центр. Далее расширять в ту сторону, которая требуется.

Comments

[Mercury13]

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

[WinPooh32]

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

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

[mayton2019]

Поскольку автор не обозначил языка программирования - то дальше обсуждать нечего. С точки зрения алгоритмов здесь нет темы для обсуждения. А вот если-бы мы говорили про С++ тогда можно говорить о
- функциях malloc/re-alloc/free
- массивах. (зубчатых массивах)
- многомерных масссивах
- хеш-табличках (как я выше писал)
- и других структурах данных вплоть до графов. Фантазия - тут безгранична. Все они будут отличаться расходом памяти и ценой операции. По расширению матрицы в сторону.

Тоесть структуры данных интересно обсуждать только в контексте конкретного ЯП.

[Mercury13]

mayton2019, В принципе, любой язык общего назначения. Конкретно мой — Си++. Я понимаю, что в разных языках разные вещи из коробки.

[Mercury13]

Конкретная задача. В Qt Widgets отображение таблиц страшно тормозит. Очертил виновника — типографский движок. Тогда, вероятно, можно создать кэш ячеек?

[mayton2019]

Да можно. Почитай еще про LRU https://habr.com/en/post/450004/

Answer 5

[Александр Скуснов]

Матлаб для матрицы это делает автоматически (можно даже переставлять строки или столбцы в любом порядке). Он на базе Java.