3
\$\begingroup\$

I have a function that I use to convert a list of dictionaries into a list of tuples, similar to itertools.groupby() would do in an ideal world. The goal is to make a list of {unique-dict} => [list of values]. I'm having a hard time explaining it, so I hope the example makes it clear.

I couldn't find a thing on google, so I wrote it pretty quickly, and I am wondering if there is a better way to do this (or a standard library even)

  • Naming things is hard... what is a better one?
  • This is a task I performed fairly often when receiving user input
  • The keys in each dict may not be consistent (some may be missing)
  • It is OK to destroy or mangle the original input list & items
  • Validation is done before calling, so 'key_field' is always present
  • It is expected that values can be duplicated in the list.
    • { status: 1 } => [1,2,3,4,1,2] is ok, if the values are actually present twice.

Simple little python function:

def group_by_excluding_key(list_of_dicts, key_field):
    """
    Takes a list of `dict` items and groups by ALL KEYS in the dict EXCEPT the key_field.
    :param list_of_dicts: List of dicts to group
    :param key_field: key field in dict which should be excluded from the grouping
    """

    output = []

    for item in list_of_dicts:
        found = False
        item_key = item.pop(key_field)

        for existing_group, found_keys in output:
            if existing_group.viewitems() == item.viewitems():
                found_keys.append(item_key)
                found = True
                break

        if not found:
            output.append((item, [item_key]))

    return output

Example Input/Output

from pprint import pprint

data = [
    {'id': 1, 'status': 1, 'product': 1},
    {'id': 2, 'status': 1, 'product': 1},
    {'id': 7, 'status': 1, 'product': 2},
    {'id': 9, 'status': 1, 'product': 2},
    {'id': 3, 'status': 1, 'product': 1},
    {'id': 4, 'status': 1, 'product': 1},
    {'id': 8, 'status': 1, 'product': 2},
    {'id': 1, 'status': 1, 'product': 1},
]

results = group_by_excluding_key(data, 'id')

pprint(results)

# [({u'product': 1, u'status': 1}, [1, 2, 3, 4, 1]),
#  ({u'product': 2, u'status': 1}, [7, 9, 8])]
\$\endgroup\$
0

1 Answer 1

4
\$\begingroup\$

Your code is pretty good, there is one thing that I would add, the for-else keyword, as this gets rid of the found variable. Which honestly is just noise. This is as if a for loop runs completely without breaking then the else will run too. But if it breaks then it won't run the else. This can leave you with:

def group_by_excluding_key(list_of_dicts, key_field):
    """
    Takes a list of `dict` items and groups by ALL KEYS in the dict EXCEPT the key_field.
    :param list_of_dicts: List of dicts to group
    :param key_field: key field in dict which should be excluded from the grouping
    """
    output = []
    for item in list_of_dicts:
        item_key = item.pop(key_field)
        for existing_group, found_keys in output:
            if existing_group.viewitems() == item.viewitems():
                found_keys.append(item_key)
                break
        else:
            output.append((item, [item_key]))
    return output

Other than that your code is good.


But if I were to were to write this, I'd prefer a very small solution. Lets say dicts are hash able, what you want is a dictionary that has the modified item as the key, and the popped item_key as the value. This obviously has two down-sides, it's not ordered, and dicts aren't hash able. Both easily solved with collections.OrderedDict and tuple(dict.items()). And so can result in:

from collections import OrderedDict

def group_by_excluding_key(list_of_dicts, key_field):
    """
    Takes a list of `dict` items and groups by ALL KEYS in the dict EXCEPT the key_field.
    :param list_of_dicts: List of dicts to group
    :param key_field: key field in dict which should be excluded from the grouping
    """
    output = OrderedDict()
    for item in list_of_dicts:
        key = item.pop(key_field)
        output.setdefault(tuple(item.items()), []).append(key)
    return [(dict(key), value) for key, value in output.items()]

This has the benefit of moving the for loop into the OrderedDict, and possibly getting \$O(1)\$ key lookup, but requires you to change the type of all the keys, twice.

I know you didn't ask for a performance review, but the performance difference between my code and your code can be tested with the following. The comments are my functions run time over yours as a percentage, so if mine took 0.8s and yours 3.3s then it'll be 24%, followed by how long it took my function to run.

from timeit import timeit
from itertools import count

# 240%, 0.1s
c = count(1)
l = [{'status': 1, 'product': i, 'id': next(c)} for i in range(10)]
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key_dict as fn', number=1000))
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key as fn', number=1000))

# 25%, 0.8s
c = count(1)
l = [{'status': 1, 'product': i, 'id': next(c)} for i in range(100)]
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key_dict as fn', number=1000))
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key as fn', number=1000))

# 28%, 0.8s
c = count(1)
l = [{'status': i, 'product': j, 'id': next(c)} for i in range(10) for j in range(10)]
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key_dict as fn', number=1000))
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key as fn', number=1000))

# 0.4%, 0.9s
c = count(1)
l = [{'status': i, 'product': j, 'id': next(c)} for i in range(100) for j in range(100)]
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key_dict as fn', number=10))
print(timeit('fn({!r}, "id")'.format(l), 'from __main__ import group_by_excluding_key as fn', number=10))
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the kind words. I never think of using for...else, but now I've changed to it at least for here. I think its an odd construct and confusing, though. Would using setdefault and reconstructing the dictionary cause excessive allocations in this case? I also feel its possibly more confusing, so I will stick with the loop & viewitems() for now. \$\endgroup\$
    – Andrew
    Sep 23, 2016 at 2:05
  • \$\begingroup\$ @AndrewBacker I thought my review was quite small, so I added the bottom part purely as an example on how I'd do it, I meant to reinforce my point it's not meant to better nor worse than your code. To answer your question, it allocates more memory for the new objects, but allocates the same amount as you otherwise. It's also a lot faster than yours, on medium to large input, I'll add the timings I used to my answer. \$\endgroup\$
    – Peilonrayz
    Sep 23, 2016 at 8:58
  • \$\begingroup\$ Oh wow... thanks for the amazing update, I had no idea the performance difference was so huge; i was only considering readability to a new coder (and myself!). With the performance so much different I will switch. Even though we batch in 100s and the DB transaction takes 99% of the time, the performance for some future use case is worth the readability tradeoff, I think. \$\endgroup\$
    – Andrew
    Sep 23, 2016 at 11:08
  • 1
    \$\begingroup\$ @AndrewBacker Just remember everything's a trade off, only do it if you need it, :) (Also I didn't know about the performance difference till I tested it when I made that comment.) \$\endgroup\$
    – Peilonrayz
    Sep 23, 2016 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.