CODEWITHSUNDEEP
python
carl
carl

Reputation: 4426

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

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:

Output:

Code:

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

Upvotes: 1

Views: 76

Answers (4)

martineau
martineau

Reputation: 123463

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)]

Upvotes: 0

Paul Panzer
Paul Panzer

Reputation: 53029

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

Upvotes: 0

Stepan Snigirev
Stepan Snigirev

Reputation: 956

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'}]

Upvotes: 1

bgse
bgse

Reputation: 8587

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.

Upvotes: 3

Related Questions