CODEWITHSUNDEEP
pythondata-structures
fdisk
fdisk

Reputation: 233

Most efficient pair-value data structure in Python with support for duplicates and sorting?

What is the most efficient pair-value data structure in Python with support for duplicates and sorting?

I need a dictionary like structure but it must support duplicates, I am looking a solution that could be sorted fast based in the first value of each pair.

Upvotes: 3

Views: 5991

Answers (1)

PaulMcG
PaulMcG

Reputation: 63739

Keep a sorted list using the bisect module. With a list data, for each new pair (a,b), data.insert at the index returned by bisect(data,(a,LARGE_NUMBER)) to add a new entry after all existing entries starting with a. The list is always maintained in sorted order, so you don't worry about "sorting fast".

>>> from bisect import bisect
>>> from random import randint
>>> data = []
>>> for x in range(20):
...   a,b = randint(1,10),randint(1,100)
...   data.insert(bisect(data,(a,1000)),(a,b))
...
>>> for d in data: print (d)
...
(1, 67)
(1, 85)
(1, 38)
(2, 78)
(3, 57)
(3, 37)
(4, 76)
(4, 74)
(5, 47)
(5, 24)
(5, 59)
(5, 91)
(6, 85)
(6, 41)
(7, 18)
(7, 41)
(7, 24)
(9, 48)
(9, 77)
(9, 82)
(10, 80)

Upvotes: 2

Related Questions