В Python, как перебрать словарь в порядке сортировки ключей?

211

Существует существующая функция, которая заканчивается следующим d: словарь:

return d.iteritems()

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

Майк
источник

Ответы:

171

Я не тестировал это очень подробно, но работает в Python 2.5.2.

>>> d = {"x":2, "h":15, "a":2222}
>>> it = iter(sorted(d.iteritems()))
>>> it.next()
('a', 2222)
>>> it.next()
('h', 15)
>>> it.next()
('x', 2)
>>>

Если вы привыкли делать for key, value in d.iteritems(): ...вместо итераторов, это все равно будет работать с решением выше

>>> d = {"x":2, "h":15, "a":2222}
>>> for key, value in sorted(d.iteritems()):
>>>     print(key, value)
('a', 2222)
('h', 15)
('x', 2)
>>>

В Python 3.x используйте d.items()вместо того, d.iteritems()чтобы возвращать итератор.

JPP
источник
29
используйте .items()вместо iteritems(): как сказал @Claudiu, iteritems не работает для Python 3.x, но items()доступен из Python 2.6.
Remi
40
Это не очевидно. Фактически, items()создает список и, следовательно, использует память, тогда как по iteritems()существу не использует память. Что использовать в основном зависит от размера словаря. Кроме того, автоматический инструмент преобразования Python 2 в Python 3 ( 2to3) автоматически выполняет преобразование из iteritems()в items(), поэтому об этом не нужно беспокоиться.
Эрик О Лебиго
5
@HowerHell используйте collections.OrderedDictтогда, вы сортируете один раз и получаете элементы в отсортированном порядке всегда.
Марк Харвистон
9
Но @EOL, даже если iteritems()не использует память, все должно быть сохранено в памяти sorted(), так что нет никакой разницы между использованием items()и iteritems()здесь в отношении памяти.
Ричард
8
@Richard: Хотя верно, что все элементы должны быть извлечены в память, они хранятся дважды с items()(в списке, возвращенном items()и в отсортированном списке) и только один раз с iteritems()(только в отсортированном списке).
Эрик О Лебигот
83

Используйте sorted()функцию:

return sorted(dict.iteritems())

Если вам нужен реальный итератор для отсортированных результатов, поскольку он sorted()возвращает список, используйте:

return iter(sorted(dict.iteritems()))
Грег Хьюгилл
источник
Это не сработало для меня: <type 'exceptions.TypeError'>: iter () вернул не итератор типа 'list'
Майк
Это, вероятно, потому что вы используете «dict» в качестве имени переменной. «dict» - это на самом деле имя типа словарей. Просто используйте другое имя, как «mydict» здесь и вуаля.
utku_karatas
1
Все еще не работает. Вы уверены, что sorted () возвращает другой итератор, в отличие от обычного списка?
Майк
когда и где происходит это исключение? Вы можете перебирать список без проблем
1
Договорились, хоп. Я не думаю, что когда-либо вызываю .next () напрямую, за исключением случаев пропуска строк в файлах. Наше решение iter (sorted (dict.iteritems ())) в конечном итоге делает копию всего dict в памяти на этапе «sorted (»), поэтому основное преимущество итератора кажется утраченным :)
39

Ключи диктовки хранятся в хеш-таблице, так что это их «естественный порядок», то есть псевдослучайный. Любой другой заказ - это концепция потребителя диктата.

sorted () всегда возвращает список, а не диктат. Если вы передадите ему dict.items () (который создает список кортежей), он вернет список кортежей [(k1, v1), (k2, v2), ...], которые можно использовать в цикле в некотором смысле очень похоже на диктовку, но в любом случае это не диктат !

foo = {
    'a':    1,
    'b':    2,
    'c':    3,
    }

print foo
>>> {'a': 1, 'c': 3, 'b': 2}

print foo.items()
>>> [('a', 1), ('c', 3), ('b', 2)]

print sorted(foo.items())
>>> [('a', 1), ('b', 2), ('c', 3)]

Следующее выглядит как диктовка в цикле, но это не так, это список кортежей, распаковываемых в k, v:

for k,v in sorted(foo.items()):
    print k, v

Примерно эквивалентно:

for k in sorted(foo.keys()):
    print k, foo[k]
Питер Роуэлл
источник
Хорошо, но я не хочу Dict или List, я хочу итератор. Как заставить его стать Итератором?
Майк
2
sorted(foo.keys())лучше в качестве эквивалента sorted(foo), так как словари возвращают свои ключи при повторной итерации (с преимуществом не необходимости создавать foo.keys()промежуточный список, может быть - в зависимости от того, как sorted()реализовано для итерируемых элементов).
Эрик О Лебиго
Интересно, что лучше для скорости и / или памяти, k in sorted(foo.keys()):которая тянет клавиши или for k,v in sorted(foo.items()):возвращает копию пар списка словаря, я бы предположилsorted(foo.keys())
CrandellWS
1
@CrandellWS: Лучший способ ответить на вопрос о времени - использовать модуль времени Python .
Питер Роуэлл
1
@frank - Короткий ответ: Нет. Дикт является массивом, в котором фактический ключ является хэшем значения предоставленного ключа. Хотя некоторые реализации могут быть довольно предсказуемыми, а некоторые могут даже заключить этот контракт, я ничего не рассчитываю, когда речь идет о порядке хеширования. Смотрите этот пост для более подробной информации о поведении 3.6+. В частности, обратите внимание на первый ответ.
Питер Роуэлл
31

Грег ответил правильно. Обратите внимание, что в Python 3.0 вам придется делать

sorted(dict.items())

как iteritemsуйдет.

Клаудиу
источник
Это не сработало для меня: <type 'exceptions.TypeError'>: iter () вернул не итератор типа 'list'
Майк
3
«Не пользуйтесь автомобилями, потому что в будущем у нас будут ховерборды»
JJ
7

Теперь вы можете использовать и OrderedDictв Python 2.7:

>>> from collections import OrderedDict
>>> d = OrderedDict([('first', 1),
...                  ('second', 2),
...                  ('third', 3)])
>>> d.items()
[('first', 1), ('second', 2), ('third', 3)]

Здесь у вас есть новая страница версии 2.7 и API OrderedDict .

Caumons
источник
Это вернет ключ, значения в том порядке, в котором они вставлены, а не в отсортированном порядке (то есть в алфавитном порядке).
Тони Саффолк 66
5

В общем, сортировку можно отсортировать так:

for k in sorted(d):
    print k, d[k]

Для конкретного случая в вопросе, имеющего «замену» для d.iteritems (), добавьте такую ​​функцию:

def sortdict(d, **opts):
    # **opts so any currently supported sorted() options can be passed
    for k in sorted(d, **opts):
        yield k, d[k]

и поэтому конечная строка меняется от

return dict.iteritems()

в

return sortdict(dict)

или

return sortdict(dict, reverse = True)
pythonlarry
источник
5
>>> import heapq
>>> d = {"c": 2, "b": 9, "a": 4, "d": 8}
>>> def iter_sorted(d):
        keys = list(d)
        heapq.heapify(keys) # Transforms to heap in O(N) time
        while keys:
            k = heapq.heappop(keys) # takes O(log n) time
            yield (k, d[k])


>>> i = iter_sorted(d)
>>> for x in i:
        print x


('a', 4)
('b', 9)
('c', 2)
('d', 8)

Этот метод все еще имеет сортировку O (N log N), однако после короткого линейного heapify он возвращает элементы в отсортированном порядке, что делает его теоретически более эффективным, когда вам не всегда нужен весь список.

jamylak
источник
4

Если вы хотите отсортировать по порядку, в который элементы были вставлены, а не по порядку ключей, вам следует взглянуть на коллекции Python.OrderedDict . (Только Python 3)

GECCO
источник
3

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

Я понятия не имею, каков более широкий контекст вашего кода, но вы можете попробовать добавить итератор в итоговый список. как это может быть?

return iter(sorted(dict.iteritems()))

конечно, теперь вы будете возвращать кортежи, потому что сортировка превратила ваш диктат в список кортежей

ex: скажем, ваш dict был: {'a':1,'c':3,'b':2} sorted превращает его в список:

[('a',1),('b',2),('c',3)]

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

PCN
источник
2

Предполагая, что вы используете CPython 2.x и имеете большой словарь mydict, использование sorted (mydict) будет медленным, потому что sorted создает отсортированный список ключей mydict.

В этом случае вы, возможно, захотите взглянуть на мой пакет orderdict, который включает реализацию C sorteddictна языке C. Особенно, если вам приходится просматривать отсортированный список ключей несколько раз на разных этапах (т. Е. Количество элементов) времени жизни словарей.

http://anthon.home.xs4all.nl/Python/ordereddict/

Энтон
источник