Python 中的快速数据结构，用于将一堆图像索引为重复项
Fast data structure in Python for indexing a bunch of images as duplicates
简介： 我想用相应的 TEX 代码替换 Encyclopedia of Mathematics 上大约 280'000 个数学公式图像。为此，我将所有这些图像（或更好：它们的 URL）分类到一个包含 100'000 个列表的列表中。
每个 "sublist" 包含 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 代码。由于每个子列表中的图像都是相同的，我已经（或仍然）确定了整个列表中每个图像的 TEX 代码 url。
现在我想用已知的TEX代码替换每篇文章中的图像（例如this one）。这导致我必须在这个子列表列表中索引每篇文章的图像 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：注意我很难控制"incoming"图片的顺序（基本上我得按照文章结构）而且我无法构造列表列表中的完整顺序（因为我无法将子列表分开。）因此我还没有找到实现二进制搜索的方法。
虽然它可能会引入数据冗余，但我建议使用二叉搜索树。您的列表列表是索引的好主意，但它有一个重要问题，确实是运行时。
树的指标可以简单地按字母顺序比较 link（a < z、aa > z 等）。因此，本质上你有二进制搜索和一些冗余数据。如果我们进行数学计算，您有 280,000 张图像，这意味着 BST 中的平均搜索时间为 log[2](280,000)，大约为 18 步。考虑到速度的提高，你有大约三个相同的 TEX 代码真的无关紧要，只需存储 3 次即可。将其视为键值对。在你的 BST 中，键是你的 link，相应的值只是与它一起存储（你可以使用你的列表列表）。你也可以让你的对的值是它所在的子列表的索引。但我的一般建议是在搜索时忽略你的子列表，并在你完成后再次使用它们。
一棵树看起来像这样：
(link, code/index)
/ \
(link,code/index) (link, code/index)
/ \ / \
etc. etc.
如果您想要或必须坚持您的子列表想法，那么我唯一的建议是根据您的列表创建一个 dictionary。请参阅此处了解其中的 time complexity。
虽然如果可能的话我会实现这个 in a language which has pointers 或以这样的方式实现每个 link 的代码是同一个对象来保存 space.
简介： 我想用相应的 TEX 代码替换 Encyclopedia of Mathematics 上大约 280'000 个数学公式图像。为此，我将所有这些图像（或更好：它们的 URL）分类到一个包含 100'000 个列表的列表中。
每个 "sublist" 包含 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 代码。由于每个子列表中的图像都是相同的，我已经（或仍然）确定了整个列表中每个图像的 TEX 代码 url。
现在我想用已知的TEX代码替换每篇文章中的图像（例如this one）。这导致我必须在这个子列表列表中索引每篇文章的图像 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：注意我很难控制"incoming"图片的顺序（基本上我得按照文章结构）而且我无法构造列表列表中的完整顺序（因为我无法将子列表分开。）因此我还没有找到实现二进制搜索的方法。
虽然它可能会引入数据冗余，但我建议使用二叉搜索树。您的列表列表是索引的好主意，但它有一个重要问题，确实是运行时。
树的指标可以简单地按字母顺序比较 link（a < z、aa > z 等）。因此，本质上你有二进制搜索和一些冗余数据。如果我们进行数学计算，您有 280,000 张图像，这意味着 BST 中的平均搜索时间为 log[2](280,000)，大约为 18 步。考虑到速度的提高，你有大约三个相同的 TEX 代码真的无关紧要，只需存储 3 次即可。将其视为键值对。在你的 BST 中，键是你的 link，相应的值只是与它一起存储（你可以使用你的列表列表）。你也可以让你的对的值是它所在的子列表的索引。但我的一般建议是在搜索时忽略你的子列表，并在你完成后再次使用它们。
一棵树看起来像这样：
(link, code/index)
/ \
(link,code/index) (link, code/index)
/ \ / \
etc. etc.
如果您想要或必须坚持您的子列表想法，那么我唯一的建议是根据您的列表创建一个 dictionary。请参阅此处了解其中的 time complexity。
虽然如果可能的话我会实现这个 in a language which has pointers 或以这样的方式实现每个 link 的代码是同一个对象来保存 space.