解析列表中也分组的项

Question

我有个白痴看起来是这样的：

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

dict很大，但在内存中很适合(几千项)。

我正在努力解决这些组，这样每个组都得到了所有成员的列表。

因此，在这种情况下，“解决方案”-dict应该是：

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

因为每一组

• 有一份所有成员的名单
• 解决了分组问题
• 组不包含.，但项总是包含。

我不知道如何做到这一点，除非是难以置信的低效。

这样的事情是我到目前为止所得到的，不起作用，而且可能是错误的方向：

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

Answer 1

您可以尝试使用递归函数来继续解析元素：

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

或者是单行：

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

适用于您的示例：

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

请注意，如果您的dict非常大，您可能应该添加@functools.lru_cache(None)装饰器来将回忆录添加到函数中。在这种情况下，您将不得不删除不可接受的d参数(而不是从周围的分数中使用d )。根据引用的“深度”，您可能还必须使用增加递归限制。当然，如果存在循环依赖(但我认为其他appraoch也是如此)，这是行不通的。

Answer 2

像这样的东西怎么样？

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

小心这可能会(威尔？)嵌套级别超过1和循环依赖的中断。

编辑

一种更一般的、保持顺序的方法克服了深度限制，但速度也较慢(至少对于提供的输入而言是这样)：

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

resolve()函数来自K。与提议的方法相比，这将保持外观的顺序。请注意，normalize_r()不能是一行行的，因为实际上需要new_v来决定是否展开自身，以确保惟一的包含。用set()做这件事的代价是你放松了订购。

Answer 3

下面的工作可能会更有效率。但是，由于使用set，订单丢失了。如果订单相关，则确实存在有序集实现。

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

我鼓励您用%timeit测试不同的方法，以确定最优的方法。在本例中，采用了以下方法：

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

但是，由于这个示例与您的大数据不太相似，所以我认为您应该在更大的数据块上测试它。