Sort list of objects by a number of attributes using a generator

user_1199464 0
Viewed 165

I've got a list of objects which will number somewhere between the thousands & tens of thousands. These objects could be thought of as people which I'm looking to rank based on a score they have.

So first of all they're split into groups by age, then gender etc. At each point a ranking is provided corresponding to that age/gender category. The fields on the objects are age_group and gender. So you'd first collect everybody that's got the 30-39 age group, then all the men (M) and all women (W) from that age group.

Creating a new list at each of these points is very memory intensive so I'm attempting to use a generator & itertools to group using the original list. So I've got a function to do that;

def group_standings(_standings, field):
    """ sort list of standings by a given field """
    getter = operator.attrgetter(field)
    for k, g in itertools.groupby(_standings, getter):
        yield list(g)


def calculate_positions(standings):
    """
    sort standings by age_group then gender & set position based on point value 
    """
    for age_group in group_standings(standings, 'age_group'):

        for gender_group in group_standings(age_group, 'gender'):

            set_positions(
                standings=gender_group,
                point_field='points',
                position_field='position',
            )

For set_positions to function correctly it needs the whole group so that it can sort by the point_field value then set the position_field value.

Debugging the generator, groupby isn't collecting all objects matching the key as I'd expected. The output is something like;

DEBUG generating k 30-39
DEBUG generating g [<Standing object at 0x7fc86fedbe10>, <Standing object at 0x7fc86fedbe50>, <Standing object at 0x7fc86fedbe90>]

DEBUG generating k 20-29
DEBUG generating g [<Standing object at 0x7fc86fedbed0>]

DEBUG generating k 30-39
DEBUG generating g [<Standing object at 0x7fc86fedbf10>]

DEBUG generating k 20-29
DEBUG generating g [<Standing object at 0x7fc86fedbf50>, <Standing object at 0x7fc86fedbf90>, <Standing object at 0x7fc86fedbfd0>, <Standing object at 0x7fc856ecc050>, <Standing object at 0x7fc856ecc090>, <Standing object at 0x7fc856ecc0d0>, <Standing object at 0x7fc856ecc110>, <Standing object at 0x7fc856ecc150>, <Standing object at 0x7fc856ecc190>, <Standing object at 0x7fc856ecc1d0>]

To confirm, for set_positions to function, the list provided by the generator would need to contain all objects in the 20-29 age group, but as above, objects from that group are being found on multiple iterations of the list.

itertools generator python
2 Answers

It happens because groupby function assumes that the input iterable is already sorted by key (see documentation). It's made for performance but is confusing. Also, I wouldn't cast g to a list in group_standings function but applied it only when you pass gender_group to set_positions.

user_52458930

groupby works on adjacent elements

As per @MikhailBerlinkov's answer, groupby aggregates consecutive items only which are the same, optionally using a key argument for comparison.

It may help to see an example:

from itertools import groupby

L = [1, 1, 1, 2, 2, 2, 1, 1]

res = [list(j) for _, j in groupby(L)]

[[1, 1, 1], [2, 2, 2], [1, 1]]

As you can see, the groups of 1 values are split into two separate lists.

Sort before grouping

Instead, you can sort your list of objects before grouping. For a large list of objects, say of length n, this takes O(n log n) time. Here's an example (using same L as before):

L_sorted = sorted(L)

res = [list(j) for i, j in groupby(L_sorted)]

[[1, 1, 1, 1, 1], [2, 2, 2]]
user_92095460
Related