CODEWITHSUNDEEP
python
i_trope
i_trope

Reputation: 1604

Python - append to list of dicts while keeping order

I have a python list that contains dicts of personal information like so:

entries = [
    {
        "first_name": "philip",
        "last_name": "fry"
    },
    {
        "first_name": "john",
        "last_name": "zoidberg"
    }
]

I would like to add entries to this list, in such as way that ascending (last name, first name) order is maintained. The bisect module looks promising, but it does not seem to support this.

Any help is appreciated!

Upvotes: 3

Views: 735

Answers (4)

Ben Beirut
Ben Beirut

Reputation: 763

A less simple but more efficient approach is to use the sortedcontainers module (which uses bisect as you suspected).

You have to extend dict to make it sortable.

class Person(dict):
    def __lt__(self, other):
        return '{}{}'.format(self['last_name'], self['first_name']) <
               '{}{}'.format(other['last_name'], other['first_name'])

Then add Person objects to a sorted list:

from sortedcontainers import SortedList
sorted_list = SortedList()
p = Person()
p['first_name'] = 'philip'
p['last_name']  = 'fry'
sorted_list.append(p)

Upvotes: 1

Roland Smith
Roland Smith

Reputation: 43495

If the list is homogeneous, i.e. all entries are a pair of names, you could use tuples instead of dicts since the keys don't add much value in this case.

And if you kept the tuples in last name, first name order you could use bisect:

In [1]: entries = [("fry", "philip"), ("zoidberg", "john")]

In [2]: entries.sort()

In [3]: entries
Out[3]: [('fry', 'philip'), ('zoidberg', 'john')]

In [4]: import bisect

In [5]: bisect.insort(entries, ("turanga", "leela"))

In [6]: entries
Out[6]: [('fry', 'philip'), ('turanga', 'leela'), ('zoidberg', 'john')]

Upvotes: 2

Martin Evans
Martin Evans

Reputation: 46759

You are right in thinking the bisect module would do what you need, and it is quite efficient. As it does not have a key function, you simply build your own key list prior to calling it. It will then return the correct insert point for you to use in your list:

import bisect

entries = [
    {"first_name": "philip", "last_name": "fry"},
    {"first_name": "john", "last_name": "zoidberg"}]

new_entry = {'first_name': 'anne', 'last_name': 'bedford'}

keys = [(d['last_name'], d['first_name']) for d in entries]
entries.insert(bisect.bisect_left(keys, (new_entry['last_name'], new_entry['first_name'])), new_entry)
print entries

This would give you the following output:

[{'first_name': 'anne', 'last_name': 'bedford'}, {'first_name': 'philip', 'last_name': 'fry'}, {'first_name': 'john', 'last_name': 'zoidberg'}]

Upvotes: 1

MikeTwo
MikeTwo

Reputation: 1327

Depending on how performant you need it to be, you can just resort after each addition. Something like (untested code):

def add(item, aList):
    aList.append(item)
    return sorted(aList, key=lambda entry:"{}{}".format(entry['last_name'], entry['first_name'])

It's not efficient, but if you have the flexibility, it's simple.

Upvotes: 3

Related Questions