在Python列表中高效搜索部分字符串

Question

我可以帮忙翻译关于IT技术的中文内容。以下是需要翻译的内容：

寻找在Python(3.6+)列表中高效搜索部分字符串的方法。

我有两个列表。 listA是一个包含路径名和唯一文件名的字符串列表：

['/pathname/uniquestring.ext', '/pathname/uniquestring.ext', '/pathname/uniquestring.ext' ...]

(使用glob()创建，文件名已给出且存在)

listB是一个字典列表。每个字典都有相同的键集，但具有唯一的值。

[{key1:value1, key2:value2}, {key1:value3, key2:value4}, ...]

在列表B中，每个字典中的一个键值对将具有一个值，该值“包含于”列表A中的一个唯一项中。

但是，该值在列表A的每个项中出现的位置是不确定的。

我需要的是：对于列表B中的每个项，找到包含与字典中k:v对匹配的子字符串的列表A中的项，并创建一个新的字典（或元组列表）作为“查找表”（目标是纠正一组图像文件中损坏的exif创建日期）。

例如：

listA = ['/pathname/abdce_654321.ext', '/pathname/a3b4c5_123456.ext', '/pathname/cbeebie_645321_abcde.ext', ...]

listB = [{"id": "123456", "create_date": "23/05/2014"}, ...]

new_dict = {"/pathname/a3b4c5_123456.ext": "23/05/2014, ...}

以下是我从字典推导式中得到的准确结果：

{j:i['create_date'] for j in listA for i in listB  if i['id'] in j}

但是，即使对于我的非常小的文件（~5500个项目），这在我的（尽管有些陈旧）笔记本电脑上需要12秒。

这可能是因为我必须使用我的方法迭代整个listB约5500次。

在Python中是否有更有效的方法？

（注：我不是寻求如何用Python纠正exif数据的建议；这是关于列表中字符串查找的广义问题。）

更正和澄清：

1. 我忽略了在我的示例中将值“123456”括在引号中，当然意味着它是一个整数；在实际数据中，它不是，也不是我处理的任何等效值。
2. 作为listA项中出现的子字符串，“id”几乎总是由下划线分隔的，但出现在整个字符串中的位置并不总是相同的；因此，对每个项目执行split（'_ '）并不总是将“id”字符串放置在位置[-1]或[-2]或[-3]，尽管[-1]会处理大约80％的情况。
3. 所有“id”都是唯一的，在列表中不会重复出现； listA中的每个文件名都是唯一的； 每个“id”从不出现在多个字典中。

顺便说一句，感谢大家的兴趣。

- redacted code

---

字典中的ID是否可以在其他字典中重复？ - Dani Mesejo

你的样本中 'id' 的值为 123456 是一个整数，所以在这里 i['id'] in j 的测试会失败。文件名中的 id 部分是否总是由下划线或 _ 分隔的？ - Martijn Pieters

listB中是否可以有多个条目与listA中的文件名匹配？如果不行，您可以在找到给定文件名的匹配项时从（副本）listB中弹出找到的元素。 - AKX

@MartijnPieters - 嗯，是的，但你得原谅我没有将123456转换为字符串；在实际情况中，“id”值是一个字符串，代码完美运行。 - redacted code

Answer 1

我能理解这两个评论的意思。重要问题是：我们需要使用in吗？只有当我们不知道id在路径字符串中出现的位置时才需要使用它吗？如果它总是出现在特定的位置，我们可以提取它并使用常数时间查找：

def extract_id(path):
    # todo
ids = {item['id']: item['create_date'] for item in listB}
new_dict = {path: ids[extract_id(path)] for path in listA}

相对于您当前的 O(N**2)，这个只有 O(N) 的时间复杂度。

- FHTMitchell

Answer 2

首先，这里是一些通用列表，可帮助进行测试：

listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

运行这个程序，使用 10,000 个值，在我的机器上平均需要 8.8 秒（如果在之后打印字典，则需要 9.5 秒）。

现在，如果我们将该代码编译为 Cython（一种在 C 上运行的 Python 超集），我这里的时间缩短到了 4.4 秒。

请参见下面的代码：

cpdef dict main():
    cdef int x
    cdef int number
    cdef char j
    cdef dict i

    listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

    listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

    hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

    return hello

- hegash

Answer 3

我写了一个小测试台，生成类似于你的随机数据，并尝试使用你的原始字典推导式和一个具有优化功能的版本，例如在找到匹配项时提前退出并删除已使用的标记。

无论是match（你的原始版本）还是match2（我的版本），都会打印出结果数量，以确保它们的工作效果相同。

结果非常明显...希望这可以帮助你。

我的MBP上5000/10000个项目的数字：

• 原始版本：1.771 / 7.391
• 优化版本：0.054 / 0.203
• 如果不删除已使用的标记（如果这不是可接受的业务规则）：0.917 / 3.789

---

import random
import timeit
import string

random.seed(42)


def genrand(n):
    return "".join(
        random.choice(string.ascii_lowercase + string.digits) for x in range(n)
    )


filenames = []
tags = []

for x in range(5000):
    id = genrand(8)
    filenames.append("/pathname/%s_%s.ext" % (genrand(6), id))
    if random.random() < 0.95:
        tags.append({"id": id, "date": "date for %s" % id})


def match():
    x = {j: i["date"] for j in filenames for i in tags if i["id"] in j}
    print(len(x))


def match2():
    x = {}
    available_tags = tags[:]
    for filename in filenames:
        for tag in available_tags:
            if tag["id"] in filename:
                x[filename] = tag
                available_tags.remove(tag)  # we've used this tag, remove it
                break
    print(len(x))


print(timeit.timeit(match, number=1))
print(timeit.timeit(match2, number=1))

- AKX

---

你的回答有和 @Martijn Pieters 指出的原始代码中相同的错误。 - martineau

@martineau 实际上并不会，因为生成的 id 是一个字符串。 - AKX