1

简介：我想用相应的 TEX 代码替换数学百科全书上大约 280,000 张数学公式的图像。为此，我将所有这些图像（或者更好的是：它们的 URL）分类到一个包含 100'000 个列表的列表中。

每个“子列表”都包含 url 字符串，这样子列表中的每个 url 都链接到同一个图像。该列表看起来像[["https://www.encyclopediaofmath.org/legacyimages/a/a130/a130010/a1300105.png", "https://www.encyclopediaofmath.org/legacyimages/a/a010/a010080/a01008021.png", ...], ["https://www.encyclopediaofmath.org/legacyimages/w/w130/w130080/w1300801.png", "https://www.encyclopediaofmath.org/legacyimages/w/w130/w130080/w130080211.png"], ...].

对于每个子列表，我已经（或仍在处理中）为该子列表的一个图像确定了相应的 TEX 代码。由于每个子列表中的图像都是相同的，我已经（或仍然）确定了整个列表中每个图像 url 的 TEX 代码。

现在我想用已知的 TEX 代码替换每篇文章中的图片（比如这篇文章） 。这导致我不得不在这个子列表列表中索引每篇文章的图像 URL。

我的问题：您是否知道比上述任务的列表列表更好的数据结构？

示例代码：

dups = [[i, i+1] for i in range(100000)]
for i in range(10000):
    for j in range(100000):
        if i in dups[j]:
            print(f"Found number {i} in {j}-th list")
            break

在上面的示例中，dups是我的列表列表的简化版本（我使用数字而不是字符串。）如您所见，上述程序需要一些时间才能完成。我想改进 dups，以便可以更快地完成类似类型的索引。

备注 1：如果 dups 的长度为 n，则上述代码本质上会进行 1 + 2 + 3 + ... + n 次比较。这导致 n * (n+1)/2 次比较。由于在我的情况下 n = 100'000，这已经是很多比较了。

备注 2：一个明显的改进是将每个子列表转换为 Python 集合并考虑集合列表。但是，我的大多数子列表包含少于 3 张图像，所以我怀疑这会大大提高运行时间。

备注3：请注意，我几乎无法控制“传入”图像的顺序（基本上我必须遵循文章结构）并且我无法在列表列表中构建完整的顺序（因为我无法将子列表分开.) 因此，我还没有找到实现二进制搜索的方法。

4

1 回答 1

1

虽然它可能会引入数据冗余，但我建议使用二叉搜索树。您的列表列表是索引的好主意，但它有一个重要问题，确实是运行时。

您对树的度量可能只是链接的字母比较（a < z、aa > z 等）。因此，基本上你有二进制搜索和一些冗余数据。如果我们算一下，您有 280,000 张图像，这意味着 BST 中的平均搜索时间为log[2](280,000)，大约为 18 步。考虑到速度的提高，你有大约三个相同的 TEX 代码真的没关系，只需存储 3 次即可。将其视为键值对。在您的 BST 中，关键是您的链接，相应的值只是与它一起存储（您可以使用您的列表列表）。您也可以将您的配对值作为它所在的子列表的索引。但我的一般建议是在搜索时忽略您的子列表，并在完成后再次使用它们。

一棵树看起来像这样：

                                (link, code/index)
                              /                     \
                      (link,code/index)       (link, code/index)
                            / \                      / \
                            etc.                     etc.

如果您想或必须坚持您的子列表想法，那么我唯一的建议是dictionary根据您的列表创建一个。请参阅此处了解其时间复杂度。

虽然如果可能的话，我会用一种有指针的语言来实现它，或者以这样一种方式来实现它，即每个链接的代码都是同一个对象以节省空间。

于 2019-04-15T15:39:46.333 回答