Здравствуйте, 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, что в общем-то работает не особо плохо. Хотя,согласен, что это всё же не идеально, так как переносит проблему с интерпретатора на программиста.
Здравствуйте, IROV.., Вы писали:
IRO>Часто вижу такой код и сам грешу, да и вообще говорят что это ок! IRO>
IRO>if 'hello' in d:
IRO> print d['hello']
IRO>
IRO>Что смущает, два раза идет поиск по ключу сначала в "находиться" а другой раз в "дай"
IRO>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время(проверять только на is то есть указатели)
IRO>что я упустил?
Часто вижу такой код и сам грешу, да и вообще говорят что это ок!
if 'hello' in d:
print d['hello']
Что смущает, два раза идет поиск по ключу сначала в "находиться" а другой раз в "дай"
Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время(проверять только на is то есть указатели)
Здравствуйте, IROV.., Вы писали:
IRO>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время(проверять только на is то есть указатели)
IRO>что я упустил?
Ты упустил тот маленький факт, что "сэкономить время" и Python не очень сильно пересекающиеся между собой вещи. В принципе, оптимизации возможны, просто этим никто не парится, т.к. в целом язык довольно медленный.
Здравствуйте, savitar, Вы писали:
S>Может dict.get()? S>
S>v = d.get('hello')
S>if v is not None:
S> print v
S>
Это не совсем корректный путь, потому что ТС хочет вывести любое значение, соответствующее ключу, а в твоём коде на значение накладывается требование отличия от None.
Если очень хочется сократить обращения до одного, то можно так:
Здравствуйте, kaa.python, Вы писали:
KP>Ты упустил тот маленький факт, что "сэкономить время" и Python не очень сильно пересекающиеся между собой вещи. В принципе, оптимизации возможны, просто этим никто не парится, т.к. в целом язык довольно медленный.
Воспринимай это как академический вопрос ну и я бы не сказал что в CPython не делают всяких оптимизаций, кешей и тд.
keys = ['none', 'false', 'zero', 'empty', 'missed']
data = {'none':None, 'false':False, 'zero':0, 'empty':[], 'one':1}
def naive(k):
return data[k] if k in data else'missed'def smart(k):
v = data.get(k)
return v if v is not None else'missed'def stupid(k):
v = data.get(k)
return v if v else'missed'
unique_object = [] # объект глобальный только ради того, чтоб не тратиться на пересоздание на каждый вызовdef verysmart(k):
v = data.get(k,unique_object)
return v if v is not unique_object else'missed'def test(method):
print(method)
for k in keys:
print(k, method(k))
print()
test(naive) # медленно
test(stupid) # куча ложных пропусков
test(smart) # ложный пропуск на none
test(verysmart) # быстро
Замеры скорости не делал. Чтобы их сделать, надо нагенерить большие словари с большим количеством коллизий хеша, — а это писанина.
Здравствуйте, Кодт, Вы писали:
К>Замеры скорости не делал. Чтобы их сделать, надо нагенерить большие словари с большим количеством коллизий хеша, — а это писанина.
У тебя в verysmart есть один серьезный недостаток с точки зрения Python оптимизации – глобальная переменная. На ее использовании легко потерять порядка 10-20% скорости работы приложения/ Я тут как-то делал для себя небольшое исследование на этот счет.
Здравствуйте, kaa.python, Вы писали:
KP>У тебя в verysmart есть один серьезный недостаток с точки зрения Python оптимизации – глобальная переменная. На ее использовании легко потерять порядка 10-20% скорости работы приложения/ Я тут как-то делал для себя небольшое исследование на этот счет.
Не спорю. Может быть, выгоднее каждый раз создавать локальные объекты, чем заставлять питон искать по всему пространству имён.
Либо, есть ещё один трюк с однократным созданием
def verysmart(k, unique_object=[])
Значение дефолтного аргумента будет создано в момент объявления функции.
Кстати, это известная грабля: объект можно поменять, и в следующий раз там будет фигня http://ideone.com/pi3SAC
Поэтому вопрос: какой тип является объектом (передаваемым и идентифицируемым по адресу) и, одновременно, самым дешёвым в создании?
Кортеж () — это значение. None — это значение. [] — это объект, и, наверно, очень дешёвый.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, kaa.python, Вы писали:
KP>>У тебя в verysmart есть один серьезный недостаток с точки зрения Python оптимизации – глобальная переменная. На ее использовании легко потерять порядка 10-20% скорости работы приложения/ Я тут как-то делал для себя небольшое исследование на этот счет.
К>Не спорю. Может быть, выгоднее каждый раз создавать локальные объекты, чем заставлять питон искать по всему пространству имён. К>Либо, есть ещё один трюк с однократным созданием К>
К>def verysmart(k, unique_object=[])
К>
К>Значение дефолтного аргумента будет создано в момент объявления функции.
К>Кстати, это известная грабля: объект можно поменять, и в следующий раз там будет фигня http://ideone.com/pi3SAC К>
К>Поэтому вопрос: какой тип является объектом (передаваемым и идентифицируемым по адресу) и, одновременно, самым дешёвым в создании? К>Кортеж () — это значение. None — это значение. [] — это объект, и, наверно, очень дешёвый.
думаю самый дешевый это object()
Здравствуйте, IROV.., Вы писали:
IRO>думаю самый дешевый это object() IRO>Да и как всегда мы отошли все от вопроса)
Почему отошли? Ты спросил, как сделать быстрее и без двойного поиска, я предложил решение
Синтетический тест
import time
class X:
def __init__(self,i):
self.i = i
def __repr__(self):
return'X(%r)' % self.i
def __eq__(self, other):
return type(self) == type(other) and self.i == other.i
def __hash__(self):
return 0 # злодейски положим всех в одну корзину
N = 5000
ns = range(N)
xs = [ X(i) for i in ns ]
t = time.time()
xn = { X(i):i for i in ns } # квадратичная сложность, тупит 11сprint(time.time()-t)
t = time.time()
all(x in xn for x in xs) # True; квадратичная сложность, тупит 11сprint(time.time()-t)
# добавим для вредности в ту же корзину hash(X(_)) == hash(0) == 0
xn[0] = None
# добавим в проверочный список
xs += [0x7FFFFFFF] # hash == 0
# наивный
t = time.time()
for x in xs:
if x in xn: # тупим раз
v = xn[x] # тупим два (не будем тратиться на print)else:
print(x,'missed')
print(time.time()-t) # тупили дважды, 22с
# умный
t = time.time()
for x in xs:
o = object()
v = xn.get(x,o) # тупим разif v is not o:
pass
else:
print(x,'missed')
print(time.time()-t) # тупили единожды, 11с
Здравствуйте, Кодт, Вы писали:
К>Разница, как и ожидалось, двукратная.
Все замечательно, но это вводит "некрасивости кода" — так не далеко и до С++ можно дожиться)
Вопрос же был в модификации CPython >>но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время
то есть, в первый момент
'hello' in d
мы в словаре d, указываем index таблицы в котором произошел успешный поиск.
d['hello']
тут мы смотрим вначале по данному индексу, и проверяем указатели на PyObject *
typedef struct {
/* Cached hash code of me_key. Note that hash codes are C longs.
* We have to use Py_ssize_t instead because dict_popitem() abuses
* me_hash to hold a search finger.
*/
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
не проверяя даже хеши, эта копеечная операция, в многих программах даст те x2
Здравствуйте, IROV.., Вы писали:
IRO>Да поиск по хеш таблице идет довольно быстро, но все же почему не хранить "последний" проверяемый индекс в таблице и сначала проверить на него, я думаю это должно сэкономить время(проверять только на is то есть указатели)
IRO>что я упустил?
Упустил то, что ты предлагаешь объект (словарь) с состоянием, учитывая один из сценариев работы.
Теоретически, разнообразные MRU/MFU-коллекции могут давать заметное ускорение за счёт адаптации к популярным запросам (переупорядочивания элементов). Но мороки с ними многовато.
Также, теоретически, словарь мог бы возвращать узел (ключ,значение) либо None. Но это потребует раскрыть внутреннее устройство словаря; там ведь не кортежи хранятся. А конвертировать узел в кортеж тоже чего-то стоит.
Многим ли пользователям окажется недостаточно get(key,defvalue) / setdefault(key,initvalue) / pop(key,defvalue) / items()/iteritems(), чтобы ещё что-то хитрое изобретать?
Здравствуйте, Кодт, Вы писали:
К>Упустил то, что ты предлагаешь объект (словарь) с состоянием, учитывая один из сценариев работы.
В связи с рекомендацией писать на питоне именно так как "выше", то это уже не "рекомендуемый" сценарий и не плохо бы его "оптимизировать"
К>Теоретически, разнообразные MRU/MFU-коллекции могут давать заметное ускорение за счёт адаптации к популярным запросам (переупорядочивания элементов). Но мороки с ними многовато.
К>Также, теоретически, словарь мог бы возвращать узел (ключ,значение) либо None. Но это потребует раскрыть внутреннее устройство словаря; там ведь не кортежи хранятся. А конвертировать узел в кортеж тоже чего-то стоит.
К>Многим ли пользователям окажется недостаточно get(key,defvalue) / setdefault(key,initvalue) / pop(key,defvalue) / items()/iteritems(), чтобы ещё что-то хитрое изобретать?
поясни, я же ничего не изобретаю, это я бы сказал оптимизация
Здравствуйте, IROV.., Вы писали:
К>>Также, теоретически, словарь мог бы возвращать узел (ключ,значение) либо None. Но это потребует раскрыть внутреннее устройство словаря; там ведь не кортежи хранятся. А конвертировать узел в кортеж тоже чего-то стоит. IRO>
Это здесь при чём?
Как питон хранит хеш-таблицу в двоичном дереве поиска?
К>>Многим ли пользователям окажется недостаточно get(key,defvalue) / setdefault(key,initvalue) / pop(key,defvalue) / items()/iteritems(), чтобы ещё что-то хитрое изобретать? IRO>поясни, я же ничего не изобретаю, это я бы сказал оптимизация
Т.е. нужно было бы завести хэндл и вот такое апи к нему?
h = d.lookup(k) # хэндлif h:
d.item_at(h) # (k,v)
d.value_at(h) # v
d.pop_at(h) # удаляет элемент
И протащить в питон все горести и печали голых указателей — с их протуханием, стрельбой по памяти, и прочая, и прочая?
Кому надо такое, биндите питон к сям и стреляйте в ногу. А в скриптовый апи это нафиг-нафиг. Я так думаю...
Здравствуйте, Кодт, Вы писали:
К>Это здесь при чём? К>Как питон хранит хеш-таблицу в двоичном дереве поиска?
сорри комментарий к вот этому. >>Теоретически, разнообразные 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) бывают очень разные
Здравствуйте, 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>
Потому что, ты сам знаешь почему вот это уже серьезная причина, буду думать.
Но в случае если мы ключ даже туже строку возьмем общую то все будет хорошо