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

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

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

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

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

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

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

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

[code=python]

'a'.__repr__().__hash__()

489403480

'b'.__repr__().__hash__()

492403553

'c'.__repr__().__hash__()

491403558

[/code]

Ну смысл понятен, думаю

a.__repr__().__hash__() < c.__repr__().__hash__() < b.__repr__().__hash__()

Вопрос решён.

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

set var "key1 val1 key2 val2"
expr {$var == [to-string [datatype create {*}$var]]}

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

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

юзай списки

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

Не Ъ :3

ещё как Ъ!

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

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

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

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

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

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

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

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

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

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

В чем Ъ TCL по сравнению с Python? Та же самая хрень. Только в 100 раз менее популярная.

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

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

> пришлось готовить костыли, а не хочется

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

наследие 80-х

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

И что с того? Пайтон всё-равно легче благодаря его синтаксису.

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

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

И что с того? Пайтон всё-равно легче благодаря его синтаксису.

порошок, уходи

>пайтон

Пайтон

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

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

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

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

я не прав?

ты читать не умеешь ;)

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

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

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

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

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

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

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

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

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

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

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

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

>>> 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

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

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

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

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

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

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

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

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

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

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

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

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

[code=python]

for key in a:

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

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

>>> 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}

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

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