在特定范围内查找两个列表中的元素

Question

So I have two lists L1 is fomatted like this:

L1 = ['12:55:35.87', '12:55:35.70', ...]
L2 = ['12:55:35.53', '12:55:35.30', ...]

我正在尝试在两个列表中查找以相同的4个字符开头的配对，例如xx:x，并返回每个列表中这些配对的索引。

到目前为止，我有：

for pair1 in L1:
    for pair2 in L2:
        if pair1[:4] in pair2:
            print(L1.index(pair1))

这个似乎没有返回正确的索引，而且显然也没有返回第二个列表的索引。任何帮助将不胜感激。

- PIEAGE

---

ra_1和ra1分别是什么？ - rodgdor

这些时间或其他数据是否可以以数字形式存储？ - jpp

if语句应该是if pair1[:4] == pair2[:4]。此外，有一种更有效的解决方法。 - gidim

抱歉，我修复了 ra_1 的问题。 - PIEAGE

你还有更多的例子吗？所有这些字符串中都包含前4个数字。你只想要第一个索引吗？ - Jongware

Answer 1

以下是使您的代码正常工作的方法。请记住，这是一种天真的解决方案，如果您的列表很大，则有更快的解决方案可用。运行时间为O(n^2)，但可以在线性时间内解决。

for i,pair1 in enumerate(L1):
    for j,pair2 in enumerate(L2):
        if pair1[:4] == pair2[:4]:
            print("list1: %s , list2: %s" % (i,j))

更新：对于未来的访问者，这里提供一个平均线性时间解决方案：

from collections import defaultdict
l1_map = defaultdict([])

for i,val in enumerate(L1):
    prefix = val[:4]
    l1_map[prefix].append(i)


for j,val in enumerate(L2):
     prefix = val[:4]
     for l1 in l1_map[prefix]:
        print("list1: %s , list2: %s" % (l1,j))

- gidim

---

你如何在线性时间内解决这个问题？难道不需要检查每一对组合吗？ - pault

我们可以对两个列表进行排序，然后得到O(n logn)，但我也很好奇线性的情况。嗯，dd:d是有限的，所以我们可以使用一个有1000个条目的表格。 - Arndt Jonasson

@gidim，老兄，这个问题简直是一场军备竞赛！不过你比我们更快地解决了它，赞一个！ - Aaron N. Brock

@ArndtJonasson 添加了线性时间解决方案。 - gidim

@gidim 是的，我的错。 - rodgdor

Answer 2

由于OP列表中似乎有很多重复的“前4个字符”，因此我会采取以下措施：

indices = {}
for i, entry in enumerate(L1):
    indices.setdefault(entry[:4], [])
    indices[entry[:4]].append("L1-{}".format(i))
    if L2[i][:4] in indices:
        indices[L2[i][:4]].append("L2-{}".format(i))

然后您可以通过以下方式访问您的重复条目：

for key in indices:
    print(key, indices[key])

这比O(n^2)更好。

编辑: 正如评论中有人指出的那样，这是假设列表具有相同的长度。

如果它们不是，假设L2比L1更大，然后在执行上述操作后，您可以执行以下操作:

for j, entry in enumerate(L2[i+1:]):
    indices.setdefault(entry[:4], [])
    indices[entry[:4]].append("L2-{}".format(j))

如果L2比L1短，只需更改代码中的变量名称。

- rodgdor

---

假设这两个列表具有相同的长度。 - Oluwafemi Sule

@OluwafemiSule 确实如此，但很容易修复，参见编辑（仍然比O(n^2)更快）。 - rodgdor

Answer 3

你可以使用 itertools.product 来循环计算笛卡尔积。

from itertools import product

L1 = ['12:55:35.87', '12:55:35.70']
L2 = ['12:55:35.53', '12:45:35.30']

res = [(i, j) for (i, x), (j, y) in 
       product(enumerate(L1), enumerate(L2)) 
       if x[:4] == y[:4]]

# [(0, 0), (1, 0)]

- jpp

---

这并没有解决问题，他要求的是索引对的列表，而不是元素本身的对。 - Aaron N. Brock

不错，已点赞！但是我认为在那个点上，列表推导可能会影响可读性？ - Aaron N. Brock

是的，也许吧，我把它分成了三行。现在对我来说看起来很清晰，但可能不是每个人都喜欢这样。 - jpp

也有可能是我不太擅长一眼理解列表推导式，实际上没什么问题。 ¯\(ツ)/¯ - Aaron N. Brock

Answer 4

使用 range() 或 enumerate() 函数在 for 循环中提供循环索引。

例如，使用 range() 函数：

for x in range(len(L1)):
   for y in range(len(L2)):
       if L1[x][:4] == L2[y][:4]:
           print(x, y)

- Yuankun

---

这么多相似的答案如此接近，干得好！点个赞！ - Aaron N. Brock

Answer 5

枚举对于这种事情非常棒。

indexes = []
for index1, pair1 in enumerate(L1):
    pair1_slice = pair1[:4] 
    for index2, pair2 in enumerate(L2):        
        if pair1_slice == pair2[:4]:
            indexes.append([index1, index2])
            print(index1, index2)

- RandomBob

---

很好，你只执行了 len(L1) 次切片操作！ - Aaron N. Brock

Answer 6

我认为enumerate函数是你正在寻找的！

L1 = ['12:55:35.87', '12:55:35.70', 'spam']
L2 = ['12:55:35.53', 'eggs', '12:55:35.30']

idxs = []

for idx1, pair1 in enumerate(L1):
    for idx2, pair2 in enumerate(L2):
        if pair1[:4] == pair2[:4]:
            idxs.append((idx1, idx2))

print(idxs)

输出

[(0, 0), (0, 2), (1, 0), (1, 2)]

- Aaron N. Brock