[MPlayer-users] [Zopyrus] Дерево на питоне

[Vladimir Mosgalin]

Hi Alex Murphy!

 On 2007.06.09 at 09:29:40 +0500, Alex Murphy wrote next:

>   Есть достаточно большая структура древовидных данных. Поиск элемента
> выполнен в виде словаря словарей. При большом объеме все тормозит на
> поиске :( Попробывал написать прямой словарь, те:
> {
>  '/root/doc1/doc2':obj1,
>  '/root/doc5/doc6':obj2,
> ...
> }
> 
> Проблемы как со скоростью, так и с получением потомков для объекта.
> Вот сижу и думаю, может есть какие-то библиотеки для питона, которые уже
> реализуют быстрое дерево ???

Ну самый примитивный способ - списки - вполне работает. Т.е. элемент это
el=[data, None, None], где el[1] и el[2] - для двоичного дерева - ссылки
на другой такой же. Для двоичного, вообще говоря, должно быть наверное и
что-то готовое, но вот мне к примеру 10-ричное нужно было.

Само дерево было небольшим (200k элементов, глубина до 10), но данных
под узлами висело о-го-го сколько, так что например del всего дерева
тормозил, да копирование шло небыстро (вручную и с весьма
оптимизированным обходом, какой-нибудь deepcopy так вообще умирал на
нем). В итоге, в какой-то момент все это было переписано на C ;))

Да, дерево на связанных классах не советую - все равно реализовываться
выбор элемента будет через словарь, только с лишними вызовами и
хранением этого самого класса, уж лучше через связанные словари. Чуть
быстрее будут словари с индексами по цифрам, а не строчкам. А так, если
отказаться от словарей и считать что doc1 это el[1], doc6 это el[6], со
списками будет еще быстрее.

Дерево же, представленное единым словарем, где нужно слепить путь и
дальше "прямой" доступ, как у тебя я пробовал, на питоне не очень вышло
- в несколько раз тормознее честного дерева. Но при переписывании на C
(я использовал Judy arrays - отличнейшая библиотека, правда на
питоновскую привязку к ней лучше даже не смотреть, нужно реализовывать
самому всю работу и выводить результат в питон самому) выбрал именно
такой путь, в моем случае он оказался эффективнее. Но это C, там строки
быстрые, в отличие от питона..

-- 

Vladimir