Resolving items in list that also are grouped

Viewed 103

I have a dict that looks like this:

{
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}

The dict is big, but fits fine in memory (a couple of thousand items).

I am trying to resolve the groups, so that each group got the list of all it's members.

So in this case, the "solution"-dict would be:

{
    "group-1": ["a.b", "c.d", "e.f"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["a.b", "c.d", "e.f"],
}

because each group

  • have a list of all it's members
  • have resolved the group-in-group problem
  • Groups does not contain ., but items always does..

I'm not sure how to go about this, without being incredible inefficient.


Something like this is what I got so far, doesnt work, and is probably the wrong direction:

from pprint import pprint
from collections import defaultdict

def normalize(data):
    group_map = defaultdict(set)

    found_some = True
    while found_some:
        found_some = False
        for k, v in data.items():
            for i in v:
                if "." in i:
                    if i not in group_map[k]:
                        group_map[k].add(i)
                        found_some = True
                else:
                    ....

    return group_map
4 Answers

You could try a recursive function to keep resolving elements:

def resolve(d, key):
    for x in d[key]:
        if x in d:
            yield from resolve(d, x)
        else:
            yield x

Or in a single line:

def resolve(d, key):
    return (y for x in d[key] for y in (resolve(d, x) if x in d else [x]))

Applied to your example:

d = {
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}
r = {k: sorted(set(resolve(d, k))) for k in d}
# {'group-1': ['a.b', 'c.d', 'e.f'],
#  'group-2': ['c.d', 'e.f'],
#  'group-3': ['a.b', 'c.d', 'e.f']}

Note that if your dict is very big, you should probably add the @functools.lru_cache(None) decorator to add memoization to the function. In this case, you will have to remove the non-hashable d parameter (and use the d from the surrounding score instead). Depending on the "depth" of the references you might also have to increase the recursion limit. And of course, this will not work if there are cyclic dependencies (but I think the same will be true for any other appraoch).

What about something like this?

def normalize(mapping):
    result = {}
    for k, v in mapping.items():
        new_v = []
        for x in v:
            if x in mapping:
                for y in mapping[x]:
                    if y not in v and y not in new_v:
                        new_v.append(y)
            else:
                new_v.append(x)
        result[k] = new_v
    return result
src = {
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}
print(src)
# {'group-1': ['a.b', 'c.d', 'group-2'], 'group-2': ['e.f', 'c.d'], 'group-3': ['group-1', 'group-2']}

tgt = {
    "group-1": ["a.b", "c.d", "e.f"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["a.b", "c.d", "e.f"],
}
print(tgt)
# {'group-1': ['a.b', 'c.d', 'e.f'], 'group-2': ['e.f', 'c.d'], 'group-3': ['a.b', 'c.d', 'e.f']}


print(normalize(src))
# {'group-1': ['a.b', 'c.d', 'e.f'], 'group-2': ['e.f', 'c.d'], 'group-3': ['a.b', 'c.d', 'e.f']}
print(tgt == normalize(src))
# True

Beware that this may (will?) break for nesting levels beyond 1 and for circular dependencies.


EDIT

A more general, order-preserving approach, overcoming the depth limitation, but also slower (at least for the provided input) is:

def resolve(mapping, key):
    for k in mapping[key]:
        if k in mapping:
            yield from resolve(mapping, k)
        else:
            yield k


def normalize_r(mapping):
    result = {}
    for k, v in mapping.items():
        new_v = []
        for item in resolve(mapping, k):
            if item not in new_v:
                new_v.append(item)
        result[k] = new_v
    return result
src = {
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}
print(src)
# {'group-1': ['a.b', 'c.d', 'group-2'], 'group-2': ['e.f', 'c.d'], 'group-3': ['group-1', 'group-2']}

tgt = {
    "group-1": ["a.b", "c.d", "e.f"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["a.b", "c.d", "e.f"],
}
print(tgt)
# {'group-1': ['a.b', 'c.d', 'e.f'], 'group-2': ['e.f', 'c.d'], 'group-3': ['a.b', 'c.d', 'e.f']}


print(normalize_r(src))
# {'group-1': ['a.b', 'c.d', 'e.f'], 'group-2': ['e.f', 'c.d'], 'group-3': ['a.b', 'c.d', 'e.f']}
print(tgt == normalize_r(src))
# True


%timeit normalize_r(src)
# 100000 loops, best of 3: 4.3 µs per loop

The resolve() function is from @tobias_k. Compared to the approach proposed there, this would keep the order of appearance. Note that normalize_r() cannot be one-lined because new_v is actually needed to determine whether to expand itself in order to ensure unique inclusion. The price of doing this with set() is that you loose ordering.

The following works and might be more efficient. However, the order is lost due to the use of set. Ordered set implementation do exist if the order is relevant.

d = {"group-1": ["a.b", "c.d", "group-2"],
     "group-2": ["e.f", "c.d"],
     "group-3": ["group-1", "group-2"]}

for key, value in d.items():
    value_copy = list(value)

    for i, v in enumerate(value):
        try:
            value_copy.extend(d[v])
            value_copy.remove(v)
        except:
            pass

    d[key] = list(set(value_copy))

I would encourage you to test different approach with %timeit to determine the most optimal one. On this example, this approach took:

4.87 µs ± 201 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

But as this example doesn't seems very similar to your large data, I think you should test it on a larger chunk of your data.

If you want to preserve order, before adding any element check if it doesn't exist first:

from collections import defaultdict


def resolve(data):

    def add_if_not_exist(element_list, element):
        """ add element if not exist."""
        if element not in element_list:
            element_list.append(element)

    def get_elements(key):
        """ check all element in data to extract them in one set."""
        values = data[key]
        for value in values:
            if value in data:
                yield from get_elements(value)
            else:
                yield value

    result = defaultdict(list)
    for dk, dd in data.items():
        for item in dd:
            if item in data:
                for subitem in get_elements(item):
                   add_if_not_exist(result[dk], subitem)
            else:
                add_if_not_exist(result[dk], item)

    return result

data1 = {
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
    "group4": ["group-3"],
}
print(resolve(data1))
# defaultdict(<class 'list'>, {'group-1': ['a.b', 'c.d', 'e.f'], 'group-2': ['e.f', 'c.d'], 'group-3': ['a.b', 'c.d', 'e.f'], 'group4': ['a.b', 'c.d', 'e.f']})
Related