Здравствуйте, Tonal-, Вы писали:

T>Вот сейчас делаю софтинку. Специализированный помошник переводчика. Переводится дерево.
T>Оно содержит ~200000 узлов и сильно ветвится. Только у корня 46 детей. Второй уровень на порядок шире.

T>Дерево отображается в стандартном деревянном виджете QTreeView.
T>Для показе нужно уметь вычислить положение узла в родительском и положение родительского узла в его родительском.
T>Одна из прикладных задач — найти следующий узел удовлетворяющий некоторому условию.
T>Сдедующий — визуально.

T>Сейчас пишу на Python, итемы виджета содержат ссылки на узлы дерева. Узлы содержат слабую ссылку на родителя.
T>Если переводить на Erlang или Haskell, на что будут ссылатся итемы? На путь для каждого узла?

Если переводить на Erlang или Haskell, то основной вопрос будет в биндинге к Qt, которого нет. От того, как он будет устроен, будет очень многое зависеть. Вообще, я бы делал такие контролы ownerdata, чтобы внутри самого контрола ваще ничего не хранилось. А вот как будет выглядеть binding сказать затрудняюсь, и не могу сказать, как будет выглядеть структура.

T>А влезет ли это всё в память?

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

Здравствуйте, Gaperton, Вы писали:
G>Если переводить на Erlang или Haskell, то основной вопрос будет в биндинге к Qt, которого нет.
На qtHaskell ссылка здесь уже неоднократно пробегала.
Про Erlang не в курсе.
G>От того, как он будет устроен, будет очень многое зависеть. Вообще, я бы делал такие контролы ownerdata, чтобы внутри самого контрола ваще ничего не хранилось. А вот как будет выглядеть binding сказать затрудняюсь, и не могу сказать, как будет выглядеть структура.
Насколько я смотрел, в qtHaskell биндинг довольно близок к оригиналу. А в Qt во всю используется MVC, и в списковых виджетах можно ничего не хранить.
Т.е. для списка/дерева/таблицы ты предоставляешь наследника QAbstractItemModel-и, который отвечает за маппирование индексов итемов в данные для отображения, количества строк и колонок, навигацию типа parent/child.

T>>А влезет ли это всё в память?
G>В этом плане отличий от Питона особых быть не должно. Я думаю так. Выкрутится завсегда можно.
В python-е у меня в узле есть обратная ссылка на предка, а в итеме — указатель на узел, т.е. памяти нужно 2*N*sizeof(ptr) вне зависимости от вида дерева.
Что и как нужно хранить в случае иммутабельных данных, и какая память при этом понадобится?

Здравствуйте, Tonal-, Вы писали:

T>>>А влезет ли это всё в память?
G>>В этом плане отличий от Питона особых быть не должно. Я думаю так. Выкрутится завсегда можно.
T>В python-е у меня в узле есть обратная ссылка на предка, а в итеме — указатель на узел, т.е. памяти нужно 2*N*sizeof(ptr) вне зависимости от вида дерева.
T>Что и как нужно хранить в случае иммутабельных данных, и какая память при этом понадобится?

Самое прямолинейное в данном случае — воспользоваться в модели отображением из индекса в значение. В данном случае элементы дерева будут хранить ссылки друг на друга по ID. Накладных расходов — log( N ).

Второй вариант — хранить дерево как дерево, в виде иерархии массивов/туплов(для Эрланга). В данном случае, для доступа к элементу потребуется полный путь к нему с верхушки, представляющий собой набор чисел-индексов. В твоем случае 4-х чисел должно хватить. Упаковывая их в 64 бита (не более чем 2^16 на одной ветви дерева) получаем весьма небольшой оверхэд.