Для решения одной задачи требуется иметь матрицу[A] 16*16, в ней

Question

Для решения одной задачи требуется иметь матрицу[A] 16*16, в ней

часто придется обновлять значения и еще чаще получать значения по двум индексам(i, j). Для proof of concept юзал Vector[Vector[A]] и теперь призадумался об оптимизации.

По книге Окасаки знаю о методе cope by path. Примеры его юза в основном сводятся к древовидным структурам. Поэтому мое теоретическое решение для матрицы выглядит примерно так: сбалансированное полное двоичное дерево, листья - собственно, вместилища значения A. Чтобы обновить значение в i ячейке перекопировать всю структуру не требуется, только путь в дереве, по которому можно добараться до листа i.
Пример на картинке: для обновления 4-го листа не нужно перкопировать фиолетовые поддеревья. Для копирования по пути нужно сделать всего 3 копирования вершин, это по идее быстрее, чем копировать весь Vector.

Хорошее ли это решение? Кто-нить может предложить че-то лучше? Заранее спасибо)

#programming #russian #scala

0

17.09.2019

1 ответов

3 просмотра

hohserg · Answer 1

hohserg Автор вопроса

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

0

17.09.2019

169 похожих чатов

Для решения одной задачи требуется иметь матрицу[A] 16*16, в ней

1 ответов

Похожие вопросы