better-orderedmultidict 0.2.0

Ordered Multivalue Dictionary

Better OrderedMultiDict

Overview

Better OrderedMultiDict provides OrderedMultiDict, a fast*, ordered multivalued dictionary.

OrderedMultiDict is multivalued, which means that there can be multiple items with the same key:

from better_orderedmultidict import OrderedMultiDict
dictionary = OrderedMultiDict()
dictionary.add("umfahren", "to drive around")
dictionary.add("umfahren", "to drive over, to knock sth. over")
print(dictionary.getall("umfahren"))  # ["to drive around", "to drive over, to knock sth. over"]

OrderedMultiDict retains the insertion order of all keys and values:

from better_orderedmultidict import OrderedMultiDict
dictionary = OrderedMultiDict()
dictionary.add('a', 'A1')
dictionary.add('b', 'B')
dictionary.add('a', 'A2')
print(', '.join(dictionary.values()))      # A1, B, A2
print(', '.join(dictionary.unique_keys())) # a, b

dictionary.popfirstitem()
print(', '.join(dictionary.values()))      # B, A2
print(', '.join(dictionary.unique_keys())) # b, a

Better OrderedMultiDict requires Python 3.12+ and is fully type annotated.

Performance Comparison

Creating / iterating over dictionary with 500'000 entries with all keys being different:

	OrderedMultiDict	omdict	speedup		bolton OrderedMultiDict	speedup
create	164.3 ms	548.0 ms	3.2x		304.1 ms	1.9x
addall / addlist	82.3 ms	311.7 ms	3.8x		139.6 ms	1.7x
update / updateall1)	262.2 ms	531.5 ms	2.0x		325.5 ms	1.2x
extend / update_extend	156.4 ms	--	--		285.5 ms	1.8x
copy	100.1 ms	646.7 ms	6.5x		350.7 ms	3.4x
iterate over items	11.2 ms	97.0 ms	8.6x		81.0 ms	7.2x
iterate over values	12.3 ms	77.3 ms	6.3x		81.3 ms	6.3x
iterate over keys	12.6 ms	78.6 ms	6.2x		53.0 ms	4.2x
iterate over unique keys	42.4 ms	23.7 ms	slower		94.1 ms	2.2x
pop last item until empty	268.7 ms	501.3 ms	1.9x		884.3 ms	3.2x

Creating / iterating over dictionary with 500'000 entries, but only 100 unique keys distributed randomly:

	OrderedMultiDict	omdict	speedup		bolton OrderedMultiDict	speedup
create	89.7 ms	484.5 ms	5.4x		258.8 ms	2.7x
addall / addlist	84.7 ms	317.1 ms	3.7x		137.5 ms	1.6x
update / updateall1)	110.8 ms	491.8 ms	4.4x		278.2 ms	2.5x
extend / update_extend	91.3 ms	--	--		257.3 ms	2.7x
copy	24.0 ms	595.8 ms	24.8x		307.8 ms	12.4x
iterate over items	11.2 ms	102.5 ms	9.2x		77.4 ms	6.8x
iterate over values	17.0 ms	81.0 ms	4.8x		80.1 ms	4.8x
iterate over keys	16.9 ms	78.3 ms	4.6x		50.5 ms	3.0x
iterate over unique keys	18.8 ms	< 0.1 ms	slower		36.0 ms	1.9x
pop last item until empty	235.7 ms	484.8 ms	2.1x		401.8 ms	1.7x

1): omdict. updateall() has slightly different behavior: omdict keeps the positions for already existing keys, but OrderedMultiDict and bolton's OrderedMultiDict do not:

from better_orderedmultidict import OrderedMultiDict
from orderedmultidict import omdict
omd1 = OrderedMultiDict([(1,1), (2,2), (1,11), (2, 22), (3,3)])
omd2 = omdict([(1,1), (2,2), (1,11), (2, 22), (3,3)])
omd1.update([(1, '1'), (3, '3'), (1, '11')])
omd2.updateall([(1, '1'), (3, '3'), (1, '11')])
print(list(omd1.items()))         # prints [(2, 2), (2, 22), (1, '1'), (3, '3'), (1, '11')]
print(list(omd2.iterallitems()))  # prints [(1, '1'), (2, 2), (1, '11'), (2, 22), (3, '3')]

Examples

OrderedMultiDict can have multiple values per key:

from better_orderedmultidict import OrderedMultiDict
omd = OrderedMultiDict()
omd[1] = 1
print(omd[1])   # prints: 1

omd.add(1, 11)
print(omd[1])           # prints: 11
print(omd.get(1))       # prints: 11
print(omd.getlast(1))   # prints: 11
print(omd.getfirst(1))  # prints: 1
print(omd.getall(1))    # prints: [1, 11]

# adding multiple values at once:
omd.addall(2, [2, 22])
print(omd.getall(2))    # prints: [2, 22]

# __setitem__ overrides all existing entries for the given key:
omd[1] = 111
print(list(omd.values()))  # prints: [2, 22, 111]

OrderedMultiDict retains insertion order:

from better_orderedmultidict import OrderedMultiDict
omd = OrderedMultiDict()
omd.addall(1, [1, 11])
omd.add(2, 2)
omd.add(3, 3)
omd.add(2, 22)
omd.add(3, 33)
omd.add(1, 111)

print(omd.getall(1))    # prints: [1, 11, 111]
print(list(omd.values()))  # prints: [1, 11, 2, 3, 22, 33, 111]

del omd[2]
print(list(omd.values()))  # prints: [1, 11, 3, 33, 111]
omd.popfirst(3)
print(list(omd.values()))  # prints: [1, 11, 33, 111]
omd.poplast(1)
print(list(omd.values()))  # prints: [1, 11, 33]
omd.poplast(1)
print(list(omd.values()))  # prints: [1, 33]

Method parity with dict is only somewhat retained

from better_orderedmultidict import OrderedMultiDict
d, omd = dict(), OrderedMultiDict()
d.update([(1,1), (1,11), (2,2), (2,22)])
omd.update([(1,1), (1,11), (2,2), (2,22)])

print(d[1], omd[1])  # prints: (11, 11)
d[3] = omd[3] = 3
print(d[3], omd[3])  # prints: (3, 3)

d[3] = omd[3] = 33
print(d[3], omd[3])  # prints: (33, 33)

# But there are differences:
print(len(d), len(omd))  # prints: (3, 5)
d.pop(2)
omd.pop(2)
print(d.get(2), omd.get(2))  # prints: (None, 2)

Iterating over unique keys

from better_orderedmultidict import OrderedMultiDict
omd = OrderedMultiDict([(1,1), (2,2), (1,11), (2,22)])

print(len(omd.keys()))  # prints: 4
print(len(omd.unique_keys()))  # prints: 2

for key in reversed(omd.unique_keys()):
    print(f"{key}: {omd.getall(key)}")
# prints:
# 1: [1, 11]
# 2: [2, 22]

Installation

Installation is simple:

$ pip install better_orderedmultidict

Detailed performance comparison

Creating / iterating over dictionary with 500'000 entries with all keys being different:

	OrderedMultiDict	DeOrderedMultiDict	omdict	bolton OrderedMultiDict	bolton FastIterOrderedMultiDict
create	161.4 ms	369.3 ms	551.6 ms	277.3 ms	361.1 ms
addall / addlist	82.5 ms	118.7 ms	305.2 ms	137.2 ms	184.7 ms
update / updateall1)	260.7 ms	449.2 ms	547.7 ms	315.9 ms	373.0 ms
extend / update_extend	156.4 ms	351.7 ms	--	289.4 ms	327.7 ms
copy	108.7 ms	402.4 ms	639.5 ms	382.4 ms	430.8 ms
iterate over items	11.2 ms	23.9 ms	95.6 ms	82.9 ms	77.0 ms
iterate over values	12.4 ms	27.8 ms	75.6 ms	83.5 ms	79.7 ms
iterate over keys	12.5 ms	27.8 ms	77.9 ms	56.3 ms	53.1 ms
iterate over unique keys	45.8 ms	61.3 ms	23.2 ms	104.4 ms	59.9 ms
pop first item until empty	--	461.3 ms	478.8 ms	--	--
pop last item until empty	266.8 ms	379.5 ms	499.4 ms	865.8 ms	944.8 ms

Creating / iterating over dictionary with 500'000 entries, but only 100 unique keys distributed randomly:

	OrderedMultiDict	DeOrderedMultiDict	omdict	bolton OrderedMultiDict	bolton FastIterOrderedMultiDict
create	93.9 ms	137.5 ms	463.3 ms	250.9 ms	296.2 ms
addall / addlist	83.8 ms	119.2 ms	307.7 ms	133.0 ms	179.1 ms
update / updateall1)	104.3 ms	153.1 ms	464.3 ms	260.3 ms	307.3 ms
extend / update_extend	91.3 ms	135.1 ms	--	242.7 ms	290.5 ms
copy	23.6 ms	91.7 ms	560.6 ms	291.5 ms	338.5 ms
iterate over items	11.4 ms	23.7 ms	96.5 ms	76.7 ms	69.0 ms
iterate over values	16.7 ms	30.7 ms	77.8 ms	80.7 ms	74.7 ms
iterate over keys	16.4 ms	30.6 ms	77.6 ms	52.8 ms	48.0 ms
iterate over unique keys	19.1 ms	37.4 ms	< 0.1 ms	36.6 ms	< 0.1 ms
pop first item until empty	--	294.2 ms	721.6 ms	--	--
pop last item until empty	232.3 ms	261.1 ms	471.5 ms	390.0 ms	428.6 ms