How to order a list of objects using a list of object attributes

Question

I have a list of objects with ids (object.id) and a list of ids. What is the most efficient way to use the list of ids to order the object list? I have the following solution... just wondering whether there is a faster one?

Input:

result = list of user objects with user ids (user.id)
list_of_ids = list of user ids e.g. [3, 2, 5, 8, 9]

Output:

list of user objects ordered according to list_of_ids

Code:

ordered_result = []
for user_id in list_of_ids:
    for user in result:
        if user_id == user.id:
            ordered_result.append(user)
            break

@martineau I'm pretty sure it's not a duplicate at least not of the Q you reference. Observe how here the desired order is given by an _unsorted_ list which makes it quite a different problem. In particular, just sorting with the attribute as key is _not_ a solution. — Paul Panzer, Nov 18 '17 at 02:20

score 3 · Accepted Answer · answered Nov 17 '17 at 23:47

You could first put the users in a dict:

usrdict = {}
for user in result:
    usrdict[user.id] = user

And then you'd have a few options, based on looking up the users by their id, for example:

ordered_result = [usrdict[x] for x in list_of_ids]

Edit: I'd probably, unless you have a very large list or have perform the operation many times, not worry about efficiency that much, but rather focus on having it clear and readable.

score 1 · Answer 2 · answered Nov 17 '17 at 23:59

You can use sorted function with custom sorting function. In this case returning index in the ids list.

def order_by(objects, ids):
    def fn(obj):
        return ids.index(obj["id"])

    return sorted(objects, key=fn)

print(order_by(objects_list, id_list))

Example:

objects_list = [
{ "id": 3, "name": "penny"},
{ "id": 5, "name": "adam"},
{ "id": 9, "name": "meh"},
{ "id": 1, "name": "john"},
{ "id": 3, "name": "archibald"},
]
id_list = [9,1,3,5,6,4]

print(order_by(objects_list, id_list))

Results in:

[{'id': 9, 'name': 'meh'}, {'id': 1, 'name': 'john'}, {'id': 3, 'name': 'penny'}, {'id': 3, 'name': 'archibald'}, {'id': 5, 'name': 'adam'}]

watch out, here. Using `ids.index(obj["id"])` is an O(N) operation, making the sorting operation in total O(n^2logn) — juanpa.arrivillaga, Nov 18 '17 at 00:52

score 0 · Answer 3 · answered Nov 18 '17 at 01:04

Here is an O(n log(n)) solution. It requires the ids in both lists to be exactly the same. It sorts the object list by id and does an indirect sort of the id list yielding an index list containing the positions of ids in order. This is then used to move the sorted objects to the right positions.

import operator

class know_who_you_are:
    def __init__(self, id_):
        self.id = id_

def argsort(L):
    "returns sorted, order"
    return zip(*sorted(zip(L, range(len(L)))))

ids = [3, 2, 4, 5, 1]
objs = [know_who_you_are(id_) for id_ in [1, 5, 3, 2, 4]]

sid, oid = argsort(ids)
sobj = sorted(objs, key=operator.attrgetter('id'))
result = len(objs) * [None]
for dest, src in zip(oid, sobj):
    result[dest] = src

# check
print(all(id_==obj.id for id_, obj in zip(ids, result)))

Prints:

True

score 0 · Answer 4 · answered Nov 18 '17 at 03:47

Here's a variation of the scheme using the built-in sorted() function with a custom comparison function. (It may seem like a lot of code, but a significant portion of it is only there for setting up a somewhat realistic test case.)

from functools import cmp_to_key
import random

random.seed(13)  # Gets consistent "random" ordering during testing.

class User:
    def __init__(self, name, id):
        self.name = name
        self.id = id

    def __repr__(self):
        return '{}({!r}, id={!r})'.format(self.__class__.__name__, self.name, self.id)

@cmp_to_key  # Converts cmp function to a key function.
def cmp(x, y):
    """ Return -1 if the position of User x in list_of_ids < index of User y
        otherwise return 1.
    """
    p1, p2 = -1, -1
    try:
        p1 = list_of_ids.index(x.id)
        p2 = list_of_ids.index(y.id)
    except ValueError:
        pass
    return -1 if p1 < p2 else 1

list_of_ids = [3, 2, 5, 8, 9]
# Create a random list of users with these ids.
shuffled_ids = random.sample(list_of_ids, k=len(list_of_ids))
users = [User(name, id) for name, id in zip(['Andy', 'Simon', 'Nick', 'John',
                                             'Roger'], shuffled_ids)]

print('Desired id order:', list_of_ids)
print()
print(' Before:', users)
ordered_result = sorted(users, key=cmp)
print('Ordered:', ordered_result)

Output:

Desired id order: [3, 2, 5, 8, 9]

 Before: [User('Andy', id=5), User('Simon', id=9), User('Nick', id=8), User('John', id=3), User('Roger', id=2)]
Ordered: [User('John', id=3), User('Roger', id=2), User('Andy', id=5), User('Nick', id=8), User('Simon', id=9)]

How to order a list of objects using a list of object attributes

4 Answers4