LINUX.ORG.RU

[Python] Великая загадка словарей

 


0

0

Давно знаю про этот момент, ибо узнал на опыте. Однако всегда было лень заниматься этим. Сейчас вот столкнулся так что пришлось готовить костыли, а не хочется. Суть проблемы видна в данном дампе:

>>> a = dict()
>>> a
{}
>>> a['a'] = '+'
>>> a
{'a': '+'}
>>> a['b'] = '+'
>>> a
{'a': '+', 'b': '+'}
>>> a['c'] = '-'
>>> a
{'a': '+', 'c': '-', 'b': '+'}
Сначала создаём словарь, забиваем в него 2 пары: a+,b+. Стоит заметить что они отсортированы как нужно, т.е. по тому как я их добавил и по алфавиту. Далее добавляется пара c-. Что мы видим? Она ломает всю логику - встаёт между предыдущими парами. Вопрос на засыпку: почему?


Dictionaries have no concept of order among elements. It is incorrect to say that the elements are “out of order”; they are simply unordered. This is an important distinction which will annoy you when you want to access the elements of a dictionary in a specific, repeatable order (like alphabetical order by key). There are ways of doing this, they're just not built into the dictionary.

http://diveintopython.org/getting_to_know_python/dictionaries.html

fluorite ★★★★★
()

Просто пиши на TCL

naryl ★★★★★
()
Ответ на: комментарий от fluorite

Спасибо, я в курсе этого, но хотелось бы узнать подробнее сам принцип.

Просто пиши на TCL.

Не Ъ :3
Сейчас весь стартап делается на Pylons, по сему не могу йути на что-то иное. Да и на пайтоне уж очень приятно кодить.
Вот неделю почти не садился за проект, сейчас сел и даже нет привычного чувства «лень». А такого я не встречал ни в одном языке..

tia
() автор топика

afaik раз каждый элемент может содержать и ключом и значением разные типы объектов, считается хеш этого элемента и надо смотреть конкретную реализацию встроенной функции dict.__hash__. поправляйте если неправ.

volh ★★
()
Ответ на: комментарий от volh

Вообще да.
Есть предположение что считается хеш вывода функции __repr__ у объекта-ключа.

[code=python]

'a'.__repr__().__hash__()

489403480

'b'.__repr__().__hash__()

492403553

'c'.__repr__().__hash__()

491403558

[/code]

tia
() автор топика

В Python dict реализован через Хэш-таблицу, которая может сохранять, а может и не сохранять порядок и «отсортировать» значения по козрастанию ключа невозможно. В tcl dict реализован так же через хэш-тааблицу, но в дополнение к этому указатели на все элементы хранятся в списке. Для реализации контракта, налагаемого на все пользовательские структуры данных в tcl:

set var "key1 val1 key2 val2"
expr {$var == [to-string [datatype create {*}$var]]}
где to-string (которая на самом деле не нужна) форсит восстановление строкового представления, а datatype - это команда, определяющая любой пользовательский тип данных, напримр, dict. Иными словами, любая структура данных созданная из строки должна преобразовываться обратно в ту же самую строку.

naryl ★★★★★
()
Ответ на: комментарий от naryl

Дык оно очевидно что только дурак будет юзать __cmp__ у каждого объекта для поиска его по списку. Хеши все юзают.
Но в данном случае интересно то что хеши то пропорциональны кодам символов.
Однако, как я сказал выше, у каждого типа в пайтоне есть метод __repr__, который интерпритирует объект как строчку. Логично предположить что по строке проще всего искать хеш, а раз есть такая функция, то сначала вызывается она и из её результата считается хеш.
Результаты показывают что оно так и есть, ибо получается что хеши как-раз рсттавляются в таком порядке, как в первом посте.
Такие дела.

tia
() автор топика

Значения словаря хранятся в не-отсортированном порядке, более того, ключи могут храниться не в том порядке, в котором они добавляются.

юзай списки

kto_tama ★★★★★
()
Ответ на: комментарий от kto_tama

Спасибо, К.О.
И да, никто не говорит что оно сортируется, но также никто и не говорит что сортируется, но по хешу результата __repr__()

tia
() автор топика
Ответ на: комментарий от volh

на TCL нет ORM! на нем нельзя писать веб!

паника! паника!

jtootf ★★★★★
()

вот поузнавать теорию того как работает хэшмапы лениво :) обязательно на грабли наступить и поругаться?

qnikst ★★★★★
()
Ответ на: комментарий от tia

>Сейчас весь стартап

Попахивает быдлохабром.

Siado ★★★★★
()
Ответ на: комментарий от volh

> на TCL нет ORM! на нем нельзя писать веб!

Фигасе, значит несколько лет я делал невозможное. Но Ты открыл мне Свет, я лузер, нет смысла дальше жить, пойду отравлюсь йадом.

anonymous
()
Ответ на: комментарий от anonymous

Записал в self-upgrade блокнот: довести уровень сарказма до абсурда.

А вообще да, надо наконец намочить руки в этом TCL, сколько можно откладывать..

volh ★★
()
Ответ на: комментарий от Kpoxman

ну так метапрограммирование же, только строки вместо списков как в лиспах? мне просто любопытно.

volh ★★
()
Ответ на: комментарий от Kpoxman

Ну ребята. Сравнивать пайтон с тиклем по популярности немного глупо. У них разные ниши.
Пайтон не самый лучший язык для встраиваемых систем, однако тикль здесь король, как и в обработке текста. А вот для больших задач больше подходит пайтон с его простым кодом(синтаксисом), в котором можно разобраться даже не заглядывая несколько недель.

tia
() автор топика
Ответ на: комментарий от tia

> А вот для больших задач больше подходит пайтон с его простым кодом(синтаксисом), в котором можно разобраться даже не заглядывая несколько недель.

ну тогда бы для больших задач больше подошел CL или Scheme с полным отсутствием синтаксиса как такового.

anonymous
()
Ответ на: комментарий от tia

> Пайтон не самый лучший язык для встраиваемых систем, однако тикль здесь король

Бгг. Весь встраиваемый тикль - это наследие 80-х, когда ничего дргугого просто не было %)

tailgunner ★★★★★
()

Не знаю как в пилонсе, но в джанге есть реализации упорядоченных словарей...

chicane
()
Ответ на: комментарий от anonymous

Перечитайте что вы написали. Вы предложили юзать язык в котором адский синтаксис(а точнее код, написанный с его использованием) вместо языка, чей синтаксис так красив.
Буэ. Троллинг, я вижу, да. Не нужно отвечать, прошу вас.

Бгг. Весь встраиваемый тикль - это наследие 80-х, когда ничего дргугого просто не было %)

Ну да, луа теперь здесь король. Хотя тикль тоже ничего так.

Не знаю как в пилонсе, но в джанге есть реализации упорядоченных словарей...

Не люблю я когда такие простые вещи реализуются дополнительными библиотеками, скриптами, костылями. Увы.
Да и зависимость никому не нужна.

OrderedDict же: http://docs.python.org/3.1/library/collections.html#collections.OrderedDict

Это хорошо, спасибо за информацию, но нужен даже не 3.0, а 3.1.

Портов в python 2 навалом (гугл: python SortedDict).

Боюсь я оверхедов. Да и все Sorted/OrderedDict'ы-костыли делают тоже что и я сейчас, по сути. Уныло.

В общем, вопрос треда был не в этом. Нужную информацию я нашёл, и, надеюсь, все кто не знал - узнали тоже.

tia
() автор топика
Ответ на: комментарий от tia

пайтон с его простым кодом(синтаксисом), в котором можно разобраться даже не заглядывая несколько недель

в Tcl синтаксических сущностей меньше ;)

jtootf ★★★★★
()
Ответ на: комментарий от tailgunner

наследие 80-х

скорей, всё же, 90-х. впрочем, сейчас он по-прежнему активно используется, хоть и потерял монополию (что, в общем-то, даже и хорошо)

jtootf ★★★★★
()
Ответ на: комментарий от vasily_pupkin

У меня в кеноне lua, tcl нет вроде ^_^

практически прямой потомок, кстати говоря. язык-deja-vu

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

Что проще:
(+ a b)
или
a+b
м? Вот и ответ. В лиспе динамический, программируемый язык. Но! Это не фича, это единственный выход. В лиспе нет иного способа объявить функцию(или я не прав?).

К логопеду билда!

И тебя тем-же туда-же

tia
() автор топика
Ответ на: комментарий от tia

Ну смысл понятен, думаю a.__repr__().__hash__() < c.__repr__().__hash__() < b.__repr__().__hash__() Вопрос решён.

Ты ведь не собираешься этим потом пользоваться на практике? ))

ei-grad ★★★★★
()
Ответ на: комментарий от ei-grad

А чем здесь пользоваться? Я только разжевал для всех схему работы и хранения пар в словаре пайтона. Это нужно только для того чтобы понять почему оно так а не иначе.

tia
() автор топика
Ответ на: комментарий от tia

А! Пошли в лоб вроде «ты х*й и всё!», так?

это на тебя питон так действует? :) я, как бы, робко намекнул, что мы сравниваем Tcl и Python. каким боком тут лисп, ммм?

Отдохни в игноре, оке?

валерьяночки попей

jtootf ★★★★★
()
Ответ на: комментарий от tia

>Я только разжевал для всех схему работы и хранения пар в словаре пайтона.

Только ты немножко неправ с тем выражением) Попробуй подставить например канонический пример, разжовываемый на питоновских форумах - {'day': 13, 'month': 01, 'year': 2010}

volh ★★
()
Ответ на: комментарий от tia

Я просто думал что там построенное по значениям элементов бинарное дерево используется для поиска, а не отсортированные хеш-значения. И соответственно что порядок скорее соответствует порядку обхода бинарного дерева с значениями самих элементов, чем по значениям хешей, но вообще наверно логичнее хеши сравнивать.

ei-grad ★★★★★
()
Ответ на: комментарий от volh

М? В чём я не прав? Ну могу и на таком примере.

>>> a = {'day': 13, 'month': 01, 'year': 2010}
>>> a
{'year': 2010, 'day': 13, 'month': 1}
>>> for key in a:
... print key, ' hash: ', key.__repr__().__hash__()
... 
year hash: 325294749
day hash: -224762289
month hash: -504742923
Для Ъ: 1) Мы создаём словарь, как сказано в примере 2) Выводим и видим что оно не так как хотелось бы 3) Выводим хеши каждого из ключей Мы видим что: у 'day' хеш - -22... у 'month' хеш - -50... у 'year' хеш - 32...

Как было сказано мной, массив сортируется по этому значению. Из этого мы видим что список должен быть вида: year, day, month, что мы и видим:

>>> a
{'year': 2010, 'day': 13, 'month': 1}
tia
() автор топика
Ответ на: комментарий от ei-grad

Бинарное дерево слишком сложно для данной реализации паттерна. Думаю гвидо не зря использовал именно поиск по хешам.

tia
() автор топика
Ответ на: комментарий от ei-grad

бинарное дерево там где автосортировка нужна и нечёткий поиск :) иначе поиск и добавление за O(ln(N)) это излишние трудозатраты. В отличии от O(1) хэш мапы, не считая моментов расширения хранилища.

Поэтому логичным образом реализовывать словари через хэшмапы.

qnikst ★★★★★
()
Ответ на: комментарий от tia

tia, зачем было ещё и Лисп упоминать? Здесь вроде была почти здоровая дискуссия на тему Python vs TCL.

naryl ★★★★★
()
Ответ на: комментарий от tia

И вообще, хватит сравнивать тёплое с мягким.
(+ a b) - это reduce двух элементов (a и b) по операции +.
a + b - это операция сложения, применяемая к операндам a и b.

naryl ★★★★★
()
Ответ на: комментарий от tia

Да и все Sorted/OrderedDict'ы-костыли делают тоже что и я сейчас, по сути. Уныло.

Если ты крутой прогер то напиши неунылую реализацию.

true_admin ★★★★★
()
Ответ на: комментарий от tia

> Как было сказано мной, массив сортируется по этому значению.

Бред. repr здесь вообще не влияет.

anonymous
()
Ответ на: комментарий от anonymous

Нет, бред несёт анонимус. А проверить свои мысли никак?

[code=python]

for key in a:

... print key, ' hash: ', key.__hash__()
...
year hash: -1799083369
day hash: 1538775645
month hash: -400412657
[/code]
=> day, year, month.
Но, как видно, оно сортируется не так, а так как сказал я. Нужны ещё пруфы?

tia
() автор топика
Ответ на: комментарий от tia

Ха-ха. Вот тебе пример:

>>> a = {'day': 13, 'month': 01, 'year': 2010}
>>> a
{'year': 2010, 'day': 13, 'month': 1}
>>> a = {'year': 13, 'month': 01, 'day': 2010}
>>> a
{'month': 1, 'day': 2010, 'year': 13}

Мне-то пруфы не нужны, я уже в исходниках посмотрел как все выводится. Смешно просто, как ты на основе двух примеров сделал «гениальный» вывод.

(тот анонимус это я).

mqspi
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.