Collections.OrderedDict: примеры (PYTHON)

Простые примеры использования

Создание OrderedDict

from collections import OrderedDict

# Пустой OrderedDict
d1 = OrderedDict()
print(d1)

# Из списка кортежей
d2 = OrderedDict([('apple', 3), ('banana', 2), ('orange', 5)])
print(d2)

# Из другого словаря (порядок может быть произвольным в Python <3.7)
d3 = OrderedDict({'apple': 3, 'banana': 2, 'orange': 5})
print(d3)

# С использованием ключевых аргументов (Python >=3.8 сохраняет порядок)
d4 = OrderedDict(apple=3, banana=2, orange=5)
print(d4)

OrderedDict()
OrderedDict([('apple', 3), ('banana', 2), ('orange', 5)])
OrderedDict([('apple', 3), ('banana', 2), ('orange', 5)])
OrderedDict([('apple', 3), ('banana', 2), ('orange', 5)])

Метод popitem

od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
print('Исходный:', od)

# Удаление с конца (по умолчанию)
item = od.popitem()
print('Удалённый элемент:', item)
print('После popitem():', od)

# Удаление с начала
item = od.popitem(last=False)
print('Удалённый элемент (last=False):', item)
print('После popitem(last=False):', od)

Исходный: OrderedDict([('a', 1), ('b', 2), ('c', 3)])
Удалённый элемент: ('c', 3)
После popitem(): OrderedDict([('a', 1), ('b', 2)])
Удалённый элемент (last=False): ('a', 1)
После popitem(last=False): OrderedDict([('b', 2)])

Метод move_to_end

od = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])
print('Исходный:', od)

# Перемещение в конец
od.move_to_end('b')
print('После move_to_end(\'b\'):', od)

# Перемещение в начало
od.move_to_end('c', last=False)
print('После move_to_end(\'c\', last=False):', od)

Исходный: OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])
После move_to_end('b'): OrderedDict([('a', 1), ('c', 3), ('d', 4), ('b', 2)])
После move_to_end('c', last=False): OrderedDict([('c', 3), ('a', 1), ('d', 4), ('b', 2)])

Альтернативы в Python

В Python существуют несколько структур данных, которые могут рассматриваться как альтернативы OrderedDict в определённых сценариях.

Обычный dict

Начиная с Python 3.7, обычные словари гарантируют сохранение порядка вставки. Для большинства задач обычный dict предпочтительнее из-за меньшего потребления памяти и более высокой производительности. OrderedDict стоит использовать при необходимости специфичных операций (move_to_end, popitem с last=False) или при работе с кодом, который должен выполняться на более ранних версиях Python.

collections.ChainMap

Класс ChainMap группирует несколько словарей в одно представление. Он сохраняет порядок словарей, но не гарантирует порядок внутри каждого. Используется для поиска по нескольким словарям, а не для сохранения порядка элементов.

types.MappingProxyType

Создаёт неизменяемую обёртку вокруг словаря. Не предоставляет возможности управления порядком, но полезен для создания read-only представлений словарей, включая OrderedDict.

Пользовательские классы

При необходимости сложной логики упорядочивания иногда создают пользовательские классы, комбинирующие словарь и двусвязный список. Однако OrderedDict уже реализует такую структуру эффективно.

Распространённые ошибки

Неизменяемость порядка при сравнении

Сравнение OrderedDict с обычным словарём не учитывает порядок, что может привести к неожиданным результатам.

from collections import OrderedDict

od = OrderedDict([('a', 1), ('b', 2)])
d = {'b': 2, 'a': 1}

print('OrderedDict:', od)
print('dict:', d)
print('Равны ли?', od == d)

# В Python 3.7+ порядок в dict сохраняется, но сравнение всё равно игнорирует порядок
d2 = {'a': 1, 'b': 2}
print('Сравнение OrderedDict с dict в другом порядке:', od == d2)

OrderedDict: OrderedDict([('a', 1), ('b', 2)])
dict: {'b': 2, 'a': 1}
Равны ли? True
Сравнение OrderedDict с dict в другом порядке: True

Изменение размера во время итерации

Удаление или добавление элементов во время итерации вызывает RuntimeError, как и в случае с обычным словарём.

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

for key in od:
    if key == 'b':
        od.pop('a')  # Пытаемся удалить другой ключ

RuntimeError: dictionary changed size during iteration

Использование move_to_end с отсутствующим ключом

Метод move_to_end вызывает KeyError, если ключ отсутствует в словаре.

od = OrderedDict([('a', 1), ('b', 2)])
od.move_to_end('c')

KeyError: 'c'

Передача нескольких позиционных аргументов

Конструктор OrderedDict принимает только один позиционный аргумент.

od = OrderedDict([('a', 1)], [('b', 2)])

TypeError: OrderedDict expected at most 1 argument, got 2

Изменения в последних версиях Python

Python 3.8

Добавлена поддержка обратного порядка итерации через встроенную функцию reversed(). Теперь OrderedDict поддерживает обратную итерацию аналогично обычным словарям.

from collections import OrderedDict

od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
for key in reversed(od):
    print(key, od[key])

c 3
b 2
a 1

Python 3.9

Добавлены операторы объединения (| и |=) для словарей. OrderedDict также поддерживает эти операторы, сохраняя порядок: сначала элементы из левого операнда, затем из правого.

from collections import OrderedDict

od1 = OrderedDict([('a', 1), ('b', 2)])
od2 = OrderedDict([('c', 3), ('d', 4)])
result = od1 | od2
print(result)

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

Python 3.10

Добавлен метод OrderedDict.__reversed__(), который явно реализует обратную итерацию. Это улучшение внутренней реализации, не меняющее публичный API.

Будущие изменения

В Python 3.12 планируется дальнейшая оптимизация внутренней структуры OrderedDict для уменьшения потребления памяти. Также рассматривается возможность добавления метода OrderedDict.__ror__ для обратного объединения.

Расширенные примеры применения

Реализация LRU-кэша

OrderedDict эффективно используется для создания кэша с вытеснением давно не используемых элементов.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# Использование
cache = LRUCache(2)
cache.put(1, 'a')
cache.put(2, 'b')
print(cache.get(1))  # 'a'
cache.put(3, 'c')    # Вытеснит ключ 2
print(cache.get(2))  # -1 (не найден)
print(cache.cache)

a
-1
OrderedDict([(1, 'a'), (3, 'c')])

Обработка конфигураций с сохранением порядка

Чтение конфигурационных файлов с сохранением порядка секций и параметров.

from collections import OrderedDict
import configparser

config = configparser.ConfigParser(dict_type=OrderedDict)
config.read_string("""
[Database]
host = localhost
port = 5432

[Server]
port = 8080
host = 0.0.0.0
""")

for section in config.sections():
    print(f'[{section}]')
    for key, value in config[section].items():
        print(f'{key} = {value}')

[Database]
host = localhost
port = 5432
[Server]
port = 8080
host = 0.0.0.0

Слияние словарей с сохранением порядка

Объединение нескольких источников данных с приоритетом и сохранением последовательности.

from collections import OrderedDict

def merge_ordered_dicts(*dicts):
    result = OrderedDict()
    for d in dicts:
        for key, value in d.items():
            if key not in result:
                result[key] = value
    return result

od1 = OrderedDict([('a', 1), ('b', 2)])
od2 = OrderedDict([('c', 3), ('a', 999)])  # 'a' уже есть
od3 = OrderedDict([('d', 4), ('b', 888)])  # 'b' уже есть

merged = merge_ordered_dicts(od1, od2, od3)
print(merged)

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

Сортировка с учётом порядка

Сортировка OrderedDict с сохранением порядка равных элементов (стабильная сортировка).

from collections import OrderedDict

od = OrderedDict([('banana', 3), ('apple', 2), ('orange', 5), ('grape', 2)])

# Сортировка по значению с сохранением порядка равных элементов
sorted_items = sorted(od.items(), key=lambda x: x[1])
sorted_od = OrderedDict(sorted_items)
print(sorted_od)

# Проверка стабильности: элементы с одинаковым значением сохраняют порядок
print('Элементы со значением 2 в исходном порядке:')
for k, v in od.items():
    if v == 2:
        print(k, v)

OrderedDict([('apple', 2), ('grape', 2), ('banana', 3), ('orange', 5)])
Элементы со значением 2 в исходном порядке:
apple 2
grape 2

Работа с JSON

Сериализация и десериализация OrderedDict в JSON с сохранением порядка.

import json
from collections import OrderedDict

# Python 3.7+ сохраняет порядок при загрузке JSON в OrderedDict
data = '{"z": 1, "a": 2, "c": 3}'
od = json.loads(data, object_pairs_hook=OrderedDict)
print('Загруженный OrderedDict:', od)

# Сохранение порядка при сериализации
serialized = json.dumps(od, indent=2)
print('Сериализованный JSON:')
print(serialized)

Загруженный OrderedDict: OrderedDict([('z', 1), ('a', 2), ('c', 3)])
Сериализованный JSON:
{
  "z": 1,
  "a": 2,
  "c": 3
}

Реализации в других языках

JavaScript: Map

Объект Map сохраняет порядок вставки элементов и предоставляет методы для управления коллекцией.

const map = new Map([
  ['apple', 3],
  ['banana', 2],
  ['orange', 5]
]);

// Порядок сохраняется при итерации
for (let [key, value] of map) {
  console.log(key, value);
}

// Добавление элемента сохраняет порядок
map.set('grape', 4);
console.log([...map]);

apple 3
banana 2
orange 5
[ ['apple', 3], ['banana', 2], ['orange', 5], ['grape', 4] ]

Java: LinkedHashMap

Класс LinkedHashMap расширяет HashMap, сохраняя порядок вставки или порядок доступа (в режиме LRU).

import java.util.LinkedHashMap;

LinkedHashMap map = new LinkedHashMap<>();
map.put("apple", 3);
map.put("banana", 2);
map.put("orange", 5);

// Порядок сохраняется
System.out.println(map);

// Удаление первого элемента
String firstKey = map.keySet().iterator().next();
map.remove(firstKey);
System.out.println(map);

{apple=3, banana=2, orange=5}
{banana=2, orange=5}

C#: OrderedDictionary и SortedDictionary

OrderedDictionary в пространстве имён System.Collections.Specialized сохраняет порядок вставки. SortedDictionary в System.Collections.Generic сортирует элементы по ключам.

using System.Collections.Specialized;

var orderedDict = new OrderedDictionary
{
    { "apple", 3 },
    { "banana", 2 },
    { "orange", 5 }
};

foreach (DictionaryEntry entry in orderedDict)
{
    Console.WriteLine($"{entry.Key}: {entry.Value}");
}

apple: 3
banana: 2
orange: 5

PHP: SplObjectStorage и ArrayObject

В PHP нет встроенного упорядоченного словаря, но ArrayObject сохраняет порядок элементов, а SplObjectStorage обеспечивает хранение объектов с сохранением порядка.

$arrayObject = new ArrayObject([
    'apple' => 3,
    'banana' => 2,
    'orange' => 5
]);

foreach ($arrayObject as $key => $value) {
    echo "$key: $value\n";
}

apple: 3
banana: 2
orange: 5

Golang: map и упорядочивание

В Go map не сохраняет порядок элементов. Для сохранения порядка используют дополнительный срез ключей или пакеты вроде github.com/elliotchance/orderedmap.

package main

import (
    "fmt"
    "github.com/elliotchance/orderedmap"
)

func main() {
    m := orderedmap.NewOrderedMap()
    m.Set("apple", 3)
    m.Set("banana", 2)
    m.Set("orange", 5)

    for el := m.Front(); el != nil; el = el.Next() {
        fmt.Println(el.Key, el.Value)
    }
}

apple 3
banana 2
orange 5