python - 列表中的“列表中”与列表中的“手动搜索”

Question

我在 Python 中的代码读取列表中的下一个元素并检查它之前是否已经出现在列表中。如果是，则它将列表的左边界移动到先前出现的后面（其余代码无关紧要）：

while k<len(lst):
    if lst[k] in lst[a:k]: #a is a left bound
       i = lst.index(lst[k],a) #could be done more effeciently with exception handling
       a = i+1
    k += 1

我试图在不使用高级技巧（in/index）的情况下重写它：

    while k<len(lst):
      for i in range(a,k+1):
        if lst[i] == lst[k]:
            break
      if i != k: #different indices, same values
        a = i+1
      k += 1

这似乎比代码 #1 慢 3.5 倍。但如果我正确理解了“in”命令，我认为代码 #2 的效率不会很低。

go through all elements in list
compare to the searched element
if they are equal, stop and return True
if at end of the list, return False

（并且函数索引可能以相同的方式工作，您只需要记住索引）。

我的猜测是 Python 解释器将“in”解释为代码 #2 中 for 循环的低级版本。但是在代码 #2 中，每次我增加 i 的值时它都必须解释我的比较，这使得代码整体运行缓慢。我是对的吗？

顺便说一句，该列表是非重复数字的有序列表（不一定是，因此不建议使用二进制搜索），这导致该算法的最坏情况复杂度为 n^2/2。

标签： pythonindexing