tcl dict, да и и питонячьи структуры тоже.
Вчера потребовалось мне иметь неизменный словарь, который можно обновлять небольшими частями и иметь несколько очень похожих (500 тысяч одинаковых и 5 разных записей) словарей.
Так вот, в Тикле заявлен неизменяемый dict, с подходящим интерфейсом. Но он сделан на хэш-таблице и, поэтому, небольшое изменение словаря приводит к копированию таблицы. Каковая для словаря в 500 тысяч записей обязательно большая.
В результате сложность моего алгоритма получилась O(n^2), а могла бы быть O(nlogn). Что было заметно уже на ~20 тысячах записей, кстати. Обработка новой записи требовала секунды! До 500 тысяч я бы добрался к концу следующего месяца, если бы добрался.
В Питоне же вообще ничего похожего нет, а если и есть (в проекте), то опять на обычном словаре на хэш-таблице с копированием.
Господа!
Даже Clojure выступила лучше. Там словари на HAMT, что и быстро, и разделяемо. С 2009 года, что позже dict, но для столь популярного языка, как Питон, примерно равно началу времён.
Так вот, в Тикле заявлен неизменяемый dict, с подходящим интерфейсом. Но он сделан на хэш-таблице и, поэтому, небольшое изменение словаря приводит к копированию таблицы. Каковая для словаря в 500 тысяч записей обязательно большая.
В результате сложность моего алгоритма получилась O(n^2), а могла бы быть O(nlogn). Что было заметно уже на ~20 тысячах записей, кстати. Обработка новой записи требовала секунды! До 500 тысяч я бы добрался к концу следующего месяца, если бы добрался.
В Питоне же вообще ничего похожего нет, а если и есть (в проекте), то опять на обычном словаре на хэш-таблице с копированием.
Господа!
Даже Clojure выступила лучше. Там словари на HAMT, что и быстро, и разделяемо. С 2009 года, что позже dict, но для столь популярного языка, как Питон, примерно равно началу времён.