Здравствуйте, Кодт, Вы писали:
К>Это здесь при чём? К>Как питон хранит хеш-таблицу в двоичном дереве поиска?
сорри комментарий к вот этому. >>Теоретически, разнообразные MRU/MFU-коллекции могут давать заметное ускорение за счёт адаптации к популярным запросам (переупорядочивания элементов).
К>>>Многим ли пользователям окажется недостаточно get(key,defvalue) / setdefault(key,initvalue) / pop(key,defvalue) / items()/iteritems(), чтобы ещё что-то хитрое изобретать? IRO>>поясни, я же ничего не изобретаю, это я бы сказал оптимизация
К>Т.е. нужно было бы завести хэндл и вот такое апи к нему? К>
К>И протащить в питон все горести и печали голых указателей — с их протуханием, стрельбой по памяти, и прочая, и прочая? К>Кому надо такое, биндите питон к сям и стреляйте в ногу. А в скриптовый апи это нафиг-нафиг. Я так думаю...
Я не говорю про синтаксис Питона, а про реализацию. в самой реализации на "С" можно запомнить "индекс" предыдущего найденного элемента. http://habrahabr.ru/post/247843/
вот этот индекс уже будет указывать на конечную "пробированную" структуру.
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, IROV.., Вы писали:
IRO>>не проверяя даже хеши, эта копеечная операция, в многих программах даст те x2
CS>А как же запись и всё такое
CS>
CS>?
CS>На самом деле полезнее было бы в языке иметь что-то типа if?
CS>
CS>if?( var h = d["hello"] )
CS> //use h
CS>
CS>В JS это можно ибо undefined и null есть разные сущности. В Python —
Это уже изменения семантики, и тут большой холивар.
Я же про очевидную оптимизацию существующего строя
Здравствуйте, IROV.., Вы писали:
IRO>Я же про очевидную оптимизацию существующего строя
Я же тебе про проблему твоей оптимизации и говорю.
Любая dict mutating операция должна сбрасывать твой cache. И за этим надо следить.
GC опять же, или сбрасывать cache или считать cached items как used. Ну и т.д.
Я пошел по другому пути. В Sciter/TIScript я кеширую hash value сущностей. Достать объект из map (hash table) по hash value это O(1) операция. И мудрить ничего не надо.
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, IROV.., Вы писали:
IRO>>Я же про очевидную оптимизацию существующего строя
CS>Я же тебе про проблему твоей оптимизации и говорю. CS>Любая dict mutating операция должна сбрасывать твой cache. И за этим надо следить. CS>GC опять же, или сбрасывать cache или считать cached items как used. Ну и т.д.
если бы я хранил PyObject * то да, если же я храню индекс на таблицу, то нет простая проверка key == table[index]->key и все станет ясно — угадали с кешом или ищем дальше.
CS>Я пошел по другому пути. В Sciter/TIScript я кеширую hash value сущностей. Достать объект из map (hash table) по hash value это O(1) операция. И мудрить ничего не надо.
O(1) бывают очень разные
Здравствуйте, IROV.., Вы писали:
IRO>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время
В комментариях к реализации (см. dictnotes) CPython2 есть такой абзац. В CPython3 уже нет. Ну и в коде вообще нет. Возможно проверили и оптимизация не зажгла. Возможно и не проверяли.
IRO>(проверять только на is то есть указатели) IRO>что я упустил?
Знаешь про ABA?
Проверять указатели можно, но их равенство не говорит об том, что это тот же объект, что и был до этого. Пример:
class Foo: ...
class Bar: ...
assert Foo() != Bar()
u = Foo()
d = {deepcopy(u):1}
if u in d: # словарь d проверил наличие и попутно запомнил указатель (id) ключа u
idu = id(u)
del u
v = Bar()
idv = id(v)
assert idu == idv # равенство id не запрещено, если время жизни объектов не пересекаетсяprint(d[v]) # Грабли: указатель на v и на бывший u совпали, но v не равно u.
То есть даже в случае равенства указателей нужно всё-равно обязательно запускать полное сравнение объектов, и вычислять хеш-функцию.
Ну и в текущей реализации dict в CPython сначала сравниваются указатели на объекты, а не сразу объекты. Но это корректно так как словарь владеет ключами своих объектов и ABA там невозможна. Кеш же владеть объектами не должен (иначе это больше боли принесёт чем пользы), weakref из кеша тоже не всегда возможен (нет же слабых ссылок на int, например).
Так что тут разве что выиграть на времени прохода по корзинам хеш-таблицы можно. Впрочем, в CPython стоит достаточно низкий порог заполнения таблицы, и просматривается обычно не так уж много корзин — и даже среди просматриваемых не для каждой вызывается функция сравнения объектов (так как в хеш-таблице с открытой адресацией часть вторичных коллизий разрешается по сравнению значений хеш-функций, а не самих объектов).
В общем, сделать такую оптимизацию можно. Но вот этот пример с ABA-подобным поведением не даст ей работать эффективно. Но попробовать можно, либо найди кто уже пробовал :)
А так, кажется, что всех уже приучили в таких ситуациях использовать .get(key, None), или .setdefault, или defaultdict, что в общем-то работает не особо плохо. Хотя,согласен, что это всё же не идеально, так как переносит проблему с интерпретатора на программиста.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, IROV.., Вы писали:
IRO>>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время W>В комментариях к реализации (см. dictnotes) CPython2 есть такой абзац. В CPython3 уже нет. Ну и в коде вообще нет. Возможно проверили и оптимизация не зажгла. Возможно и не проверяли.
IRO>>(проверять только на is то есть указатели) IRO>>что я упустил? W>Знаешь про ABA? W>Проверять указатели можно, но их равенство не говорит об том, что это тот же объект, что и был до этого. Пример:[python]
Ты прав, но только в том случае если я хранил бы PyObject * как кеш, в данном случае я буду сравнивать два корректных указателя которые живут в данной системе. И таких проблем не должно быть, ибо они указывают на живые объекты(объект).
W>А так, кажется, что всех уже приучили в таких ситуациях использовать .get(key, None), или .setdefault, или defaultdict, что в общем-то работает не особо плохо. Хотя,согласен, что это всё же не идеально, так как переносит проблему с интерпретатора на программиста.
Вот и говорю, что решать на уровне интерпретатора, особенно скриптового языка основной задачей которого упростить написание кода (без задней мысли про оптимизацию)
Здравствуйте, IROV.., Вы писали:
W>>Проверять указатели можно, но их равенство не говорит об том, что это тот же объект, что и был до этого. Пример: IRO> но только в том случае если я хранил бы PyObject * как кеш, в данном случае я буду сравнивать два корректных указателя которые живут в данной системе. И таких проблем не должно быть, ибо они указывают на живые объекты(объект).
Приведи пример реализации на псевдокоде такой проверки. Сдаётся мне, что-то тут у тебя не учтено
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, IROV.., Вы писали:
W>>>Проверять указатели можно, но их равенство не говорит об том, что это тот же объект, что и был до этого. Пример: IRO>> но только в том случае если я хранил бы PyObject * как кеш, в данном случае я буду сравнивать два корректных указателя которые живут в данной системе. И таких проблем не должно быть, ибо они указывают на живые объекты(объект). W>Приведи пример реализации на псевдокоде такой проверки. Сдаётся мне, что-то тут у тебя не учтено
struct dict
{
int index;
field m[8];
}
object * find( dict * d, object * key )
{
if d->m[d->index].key == key : return d->m[d->index].value
....
}
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, IROV.., Вы писали:
W>>>Приведи пример реализации на псевдокоде такой проверки. W>
IRO>> if d->m[d->index].key == key : return d->m[d->index].value
W>
W>Где оптимизация-то? Почему этому коду не хватает миллиарда итераций чтобы вышеприведённая строчка начала срабатывать?
W>key = 'abc'
W>d = {''.join(key): "Hello"}
W>assert key in d # True
W>for i in xrange(10**9):
W> if key in d:
W> print(d[key])
W>
Потому что, ты сам знаешь почему вот это уже серьезная причина, буду думать.
Но в случае если мы ключ даже туже строку возьмем общую то все будет хорошо
