Python字典，其中多个键以内存有效方式指向同一列表

Question

我有这个独特的要求，可以用这段代码来解释。这是工作代码，但内存效率不高。

data = [[
        "A 5408599",
        "B 8126880",
        "A 2003529",
    ],
    [
        "C 9925336",
        "C 3705674",
        "A 823678571",
        "C 3205170186",
    ],
    [
        "C 9772980",
        "B 8960327",
        "C 4185139021",
        "D 1226285245",
        "C 2523866271",
        "D 2940954504",
        "D 5083193",
    ]]

temp_dict = {
    item: index for index, sublist in enumerate(data)
        for item in sublist
}

print(data[temp_dict["A 2003529"]])

out: ['A 5408599', 'B 8126880', 'A 2003529']

简而言之，我希望子列表的每个项目都可索引，并应返回子列表。

上面的方法有效，但是当数据很大时会占用大量内存。有没有更好的，内存和CPU友好的方法？数据存储为JSON文件。

编辑 我尝试了最大可能的用例场景的答案（1000个子列表，每个子列表100个项目，100万个查询），这是结果（10次运行的平均值）：

Method,    Time (seconds),    Extra Memory used
my,        0.637              40 Mb
deceze,    0.63               40 Mb
James,     0.78               200 kb
Pant,      > 300              0 kb
mcsoini,   forever            0 kb

Answer 1

您实际上处于生成字典所需的时间/内存与扫描即时方法的整个数据所需的时间之间的权衡空间。

如果您想要一个低内存方法，您可以使用一个在每个子列表中搜索该值的函数。使用生成器可以更快地向用户提供初始结果，但对于大型数据集，返回之间的速度会很慢。

data = [[
        "A 5408599",
        "B 8126880",
        "A 2003529",
    ],
    [
        "C 9925336",
        "C 3705674",
        "A 823678571",
        "C 3205170186",
    ],
    [
        "C 9772980",
        "B 8960327",
        "C 4185139021",
        "D 1226285245",
        "C 2523866271",
        "D 2940954504",
        "D 5083193",
    ]]


def find_list_by_value(v, data):
    for sublist in data:
        if v in sublist:
            yield sublist

for s in find_list_by_value("C 9772980", data):
    print(s)

正如评论中提到的，仅根据第一个字母或前 2 或 3 个字符构建哈希表可能是一个不错的起点。这将允许您构建子列表的候选列表，然后扫描这些子列表以查看该值是否在子列表中。

from collections import defaultdict

def get_key(v, size=3):
    return v[:size]

def get_keys(sublist, size=3):
    return set(get_key(v, size) for v in sublist)

def find_list_by_hash(v, data, hash_table, size=3):
    key = get_key(v, size)
    candidate_indices = hash_table.get(key, set())
    for ix in candidates:
        if v in data[ix]:
            yield data[ix]

# generate the small hash table
quick_hash = defaultdict(set)
for i, sublist in enumerate(data):
    for k in get_keys(sublist, 3):
        quick_hash[k].add(i)

# lookup a value by the small hash
for s in find_list_by_hash("C 9772980", data, quick_hash, 3):
    print(s)

在此代码quick_hash中将需要一些时间来构建，因为您正在扫描您的整个数据结构。然而，内存占用会小得多。调整性能的主要参数是size。较小的大小将具有较小的内存占用量，但运行时会花费更长的时间，find_list_by_hash因为您的候选池会更大。size您可以做一些测试来看看您的数据应该有什么权利。请注意，您的所有值至少与一样长size。