Comments 18
Спасибо!
Спасибо большое! Очень полезная библиотека и её хорошее описание.
А для чего нужны отдельные save и load, чем не устраивает pickle/cPickle dump/load?
Тем, что для реализации pickle-протокола для datrie.Trie пришлось бы писать свою сериализацию trie в байты (на С или Cython).
Не то чтобы это было очень сложно, но работы хватит, за час не напишу, наверное. В libdatrie уже есть поддержка сохранения trie в файл на диске, поэтому в datrie реализовано сохранение в файл: методы save и write. Метод write не документирован, но позволяет писать trie в открытый питоний file.
Поддержка pickle была бы хорошей фичей, но ее пока нет, т.к. ее делать было сложнее, чем просто сохранение в файл. Патчи, понятное дело, приветствуются)
Не то чтобы это было очень сложно, но работы хватит, за час не напишу, наверное. В libdatrie уже есть поддержка сохранения trie в файл на диске, поэтому в datrie реализовано сохранение в файл: методы save и write. Метод write не документирован, но позволяет писать trie в открытый питоний file.
Поддержка pickle была бы хорошей фичей, но ее пока нет, т.к. ее делать было сложнее, чем просто сохранение в файл. Патчи, понятное дело, приветствуются)
Можно «схитрить» (не бейте сильно...):
import cPickle, datrie, string
from datrie import AlphaMap
class PickledTrie(datrie.Trie):
_alpha_map = None
def __init__(self, alpha_map=None, _create=True):
self._alpha_map = alpha_map
super(PickledTrie, self).__init__(AlphaMap(alpha_map), _create)
def __reduce__(self):
return PickledTrie, (self._alpha_map, ), None, None, iter(self.items())
def __setitem__(self, k, v):
super(PickledTrie, self).__setitem__(k, v)
pt = PickledTrie(string.ascii_lowercase)
pt[u'foo'] = u'bar'
with open('tmp.dat', 'wb') as f:
cPickle.dump(pt, f)
with open('tmp.dat', 'rb') as f:
z = cPickle.load(f)
print z.items()
__setitem__ лишний, забыл стереть…
Хм, да, можно. Но это такой «хак», понятное дело)
Метод .items() без префиксов сейчас тормозной (раз в 20-30 медленнее, чем у словаря); для сохранения и загрузки придется дублировать trie в памяти в «развернутом» виде (а с текущими save-load можно большой список слов в trie загрузить без загрузки всех отдельных слов как питоньих строк); у AlphaMap есть еще параметр ranges, который может быть использовать удобнее, чем alphabet (и который тут никак не передать).
Но мне нравится) Необходимость создавать отдельный AlphaMap хорошо бы все равно из API убирать.
Вот только если потом пиклинг переписать по-нормальному, то станет нельзя загружать старые trie, сохраненные этим вариантом. Способы обхода есть (например, распиклить trie старой версией, сохранить в файл через save и загрузить через load новой), но мне пока неочевидно, что игра стоит свеч, т.к. не очень представляю, зачем именно пиклинг может понадобиться. А правда, зачем?
Метод .items() без префиксов сейчас тормозной (раз в 20-30 медленнее, чем у словаря); для сохранения и загрузки придется дублировать trie в памяти в «развернутом» виде (а с текущими save-load можно большой список слов в trie загрузить без загрузки всех отдельных слов как питоньих строк); у AlphaMap есть еще параметр ranges, который может быть использовать удобнее, чем alphabet (и который тут никак не передать).
Но мне нравится) Необходимость создавать отдельный AlphaMap хорошо бы все равно из API убирать.
Вот только если потом пиклинг переписать по-нормальному, то станет нельзя загружать старые trie, сохраненные этим вариантом. Способы обхода есть (например, распиклить trie старой версией, сохранить в файл через save и загрузить через load новой), но мне пока неочевидно, что игра стоит свеч, т.к. не очень представляю, зачем именно пиклинг может понадобиться. А правда, зачем?
А фиг его знает, кому «чистый» пиклинг нужен, мне хотелось поигратся… Хотя да, кривовато вышло.
Я, в принципе, за кривые решения, если они позволяют что-то сделать полезное и их потом можно заменить на «прямые» без смены интерфейса) Но тут вылезает досадная неприятность с обновлением со старой версии + польза не очевидна, поэтому в библиотеку этот вариант добавлять не хочется.
Можно в вики добавить, вдруг кому пригодится)
Можно в вики добавить, вдруг кому пригодится)
Я не против… Кстати, с удовольствием попробую решить другие проблемы/накатать фичи для datrie. Есть предложения?
Добавил в вики. Предложения — конечно, есть :)
* реализовать больше методов стандартного питоньего словаря (простор есть — от простых get и pop до хитрых viewitems);
* подумать, как убрать AlphaMap из публичного интерфейса (и datrie.new, наверное, тоже);
* добавить поддержку ключей-байтовых строк для второго питона (обязательно проверив на бенчмарках, что это ничего не затормозило для юникодных строк) — скорее всего, просто декодировать их в юникод из ascii; если затормозило — не добавлять, а явно задокументировать «не будет этого», отрицательный результат — тоже результат;
* реализовать аналог lookup c deepsearch='choose' из Trie::Trie. В datrie это, видимо, выльется в 3 метода first_key(prefix), first_item(prefix), first_value(prefix). С другой стороны, эти методы могут быть не очень нужны, если iteritems(prefix) будет реализован, т.к. они станут просто чуть более эффективной версией next(trie.iteritems(prefix)). С третьей стороны, они все равно могут быть полезны, т.к. они будут более эффективны + еще неизвестно, когда iteritems получится сделать.
* скрипт для бенчмарков довольно неудобный — все запускается сразу и ждать долговато; какой-то интерфейс командной строки к нему был бы очень кстати;
* любые дополнительные бенчмарки — это хорошо (и не только скорости: например, нормальный скрипт замера оперативной памяти — см. psutil и github.com/fabianp/memory_profiler ); вдруг что-то интересно узнать самому?;
* можно в самой libdatrie реализовать итерацию по дереву с каким-то iterator-object, и функциями в духе «next_state(const Trie* trie, IteratorState* state)» и послать патч автору libdatrie; после этого можно переписывать BaseTrie._walk_prefixes и добавлять публичный питоний интерфейс для гуляния по дереву. Theppitak Karoonboonyanan собирался в libdatrie поддержку итерации сам добавить, но не факт, что скоро;
* возможно, __len__ у Trie может быть быстрее (т.к. в отличие от BaseTrie у нас есть self.values — но как это будет работать совместно с __delitem__?)
* попробовать прогнать тесты на narrow-сборке питона (там сейчас довольно ковбойский метод кодирования питоньего юникода в AlphaChar*, в портабельности которого я до конца не уверен);
* ну или просто использовать библиотеку для своих нужд — недостающие фичи или проблемы сами вылезут со временем)
* реализовать больше методов стандартного питоньего словаря (простор есть — от простых get и pop до хитрых viewitems);
* подумать, как убрать AlphaMap из публичного интерфейса (и datrie.new, наверное, тоже);
* добавить поддержку ключей-байтовых строк для второго питона (обязательно проверив на бенчмарках, что это ничего не затормозило для юникодных строк) — скорее всего, просто декодировать их в юникод из ascii; если затормозило — не добавлять, а явно задокументировать «не будет этого», отрицательный результат — тоже результат;
* реализовать аналог lookup c deepsearch='choose' из Trie::Trie. В datrie это, видимо, выльется в 3 метода first_key(prefix), first_item(prefix), first_value(prefix). С другой стороны, эти методы могут быть не очень нужны, если iteritems(prefix) будет реализован, т.к. они станут просто чуть более эффективной версией next(trie.iteritems(prefix)). С третьей стороны, они все равно могут быть полезны, т.к. они будут более эффективны + еще неизвестно, когда iteritems получится сделать.
* скрипт для бенчмарков довольно неудобный — все запускается сразу и ждать долговато; какой-то интерфейс командной строки к нему был бы очень кстати;
* любые дополнительные бенчмарки — это хорошо (и не только скорости: например, нормальный скрипт замера оперативной памяти — см. psutil и github.com/fabianp/memory_profiler ); вдруг что-то интересно узнать самому?;
* можно в самой libdatrie реализовать итерацию по дереву с каким-то iterator-object, и функциями в духе «next_state(const Trie* trie, IteratorState* state)» и послать патч автору libdatrie; после этого можно переписывать BaseTrie._walk_prefixes и добавлять публичный питоний интерфейс для гуляния по дереву. Theppitak Karoonboonyanan собирался в libdatrie поддержку итерации сам добавить, но не факт, что скоро;
* возможно, __len__ у Trie может быть быстрее (т.к. в отличие от BaseTrie у нас есть self.values — но как это будет работать совместно с __delitem__?)
* попробовать прогнать тесты на narrow-сборке питона (там сейчас довольно ковбойский метод кодирования питоньего юникода в AlphaChar*, в портабельности которого я до конца не уверен);
* ну или просто использовать библиотеку для своих нужд — недостающие фичи или проблемы сами вылезут со временем)
Тот вариант, что родился у меня вчера в голове… Что-то в таком роде (не проверял, код из головы, но идея, думаю, ясна):
А вообще всё было бы куда проще и элегантнее, если бы save/load принимали не строки-имена файлов, а file-like object'ы. Тогда этот tempfile не нужен, и pickle обеспечивается за счёт класса StringIO.StringIO.
import cPickle, datrie, tempfile, os
class PicklableTrie(datrie.Trie):
def __reduce__(self):
tempHandle, tempName = tempfile.mkstemp()
try:
os.close(tempHandle) # close the file we opened; now we'd save into it
self.save(tempName)
with open(tempName, 'rb') as inp:
return datrie.__version__, inp.read()
finally:
os.unlink(tempName)
def __setstate__(self, newState):
assert datrie.__version__ == newState[0]
tempHandle, tempName = tempfile.mkstemp()
try:
os.close(tempHandle) # close the file we opened; now we'd save into it
with open(tempName, 'wb') as out:
out.write(newState[1])
self.load(tempName)
finally:
os.unlink(tempName)А вообще всё было бы куда проще и элегантнее, если бы save/load принимали не строки-имена файлов, а file-like object'ы. Тогда этот tempfile не нужен, и pickle обеспечивается за счёт класса StringIO.StringIO.
Кстати, если я правильно понимаю файлики-сорцы, то нужные для использования file-like object'a пункты можно довольно легко портировать из самой либы в обёртку, либо заменить fileutils.c, научив функции file_write_* и file_read_* работать с file-like питоновскими объектами.
Угу, про костыль с временными файлами тоже думал. В принципе, этот вариант даже получше, чем явная сериализация items, т.к. требует меньше оперативной памяти.
Понятное дело, было бы проще, если б file-like объекты все поддерживало) Но там одним изменением fileutils не отделаешься, т.к. вся библиотека работает с FILE* и подразумевает наличие «настоящего» файла (tail.c/tail_fread, darray.c/da_fread).
Кроме того, хорошо бы отвязываться от апстрима по минимуму — если можно в C-код изменений не вносить, то не вносить их; если и вносить, то такие, которые можно в апстрим пропихнуть (== неспецифичные для питона) — например, фикс для MSVC2008 так в транке libdatrie появился недавно.
В том, чтоб встать на путь правки самой библиотеки, есть плюсы — например, можно было бы попробовать минимизировать преобразования PyUnicode <-> AlphaChar* + возможно, сделать TrieData == PyObject*. Кстати, ruby-расширения для libdatrie на этот путь и встало. Но и минусы очевидны — меньше пользы для мировой цивилизации, сложнее обновляться, больше кода поддерживать.
Поэтому конкретно для «правильной» сериализации я бы предпочел дополнительные функции (на С или Cython), а не правку библиотеки.
Понятное дело, было бы проще, если б file-like объекты все поддерживало) Но там одним изменением fileutils не отделаешься, т.к. вся библиотека работает с FILE* и подразумевает наличие «настоящего» файла (tail.c/tail_fread, darray.c/da_fread).
Кроме того, хорошо бы отвязываться от апстрима по минимуму — если можно в C-код изменений не вносить, то не вносить их; если и вносить, то такие, которые можно в апстрим пропихнуть (== неспецифичные для питона) — например, фикс для MSVC2008 так в транке libdatrie появился недавно.
В том, чтоб встать на путь правки самой библиотеки, есть плюсы — например, можно было бы попробовать минимизировать преобразования PyUnicode <-> AlphaChar* + возможно, сделать TrieData == PyObject*. Кстати, ruby-расширения для libdatrie на этот путь и встало. Но и минусы очевидны — меньше пользы для мировой цивилизации, сложнее обновляться, больше кода поддерживать.
Поэтому конкретно для «правильной» сериализации я бы предпочел дополнительные функции (на С или Cython), а не правку библиотеки.
Ну тогда можно костыль со временными файлами загнать прямо в Cython-обёртку: www.cplusplus.com/reference/clibrary/cstdio/tmpfile/ и *_fwrite() из libdatrie
Отличная статья, автору спасибо.
Надо бы допилить до вменяемого состояния свою .NET реализацию по мотивам которой я и писал ту статью по ссылке. Интересно будет сравнить быстродействие, хотя вряд ли оно приблизится к сишной реализации.
Надо бы допилить до вменяемого состояния свою .NET реализацию по мотивам которой я и писал ту статью по ссылке. Интересно будет сравнить быстродействие, хотя вряд ли оно приблизится к сишной реализации.
Sign up to leave a comment.
Префиксные деревья в Python