最快的列表索引搜索方法

Question

找到一个整数列表中某个元素的索引，最快的方法是什么？

现在我正在这样做：

if value in mylist:
    return mylist.index(value)

但是我觉得我在做同样的事情两次：要知道value是否在mylist中，我也知道它的索引位置。我还尝试了其他解决方案：

try:
    return mylist.index(value)
except ValueError:
    return None

或者

for i, x in enumerate(mylist):
    if x == value:
         return i
return None

但这些解决方案似乎都比较慢。

这个数组没有排序，只有4个元素。

Answer 1

单纯使用if-else语句虽然速度快，但如果你总是在同一个列表上查找（或者你的列表不经常变化），那么可以通过把元素和它们的索引关系存储在一个字典里来加快速度，然后进行字典查找。

所以你的代码应该看起来像这样：

# Precompute the mapping.
mapping = { index: value for value, index in enumerate(TEST_LIST) }

# Search function:
def lookup(value):
  return mapping.get(value, None)

我做了一些测试，把这个方法和其他方法进行了比较。以下是我的测试代码：

import timeit

TEST_LIST = [100, -2, 10007, 2**70 + 1]
mapping = { index: value for value, index in enumerate(TEST_LIST) }
NUM_TIMES = 10**6


def by_if_else(lst, value):
  if lst[0] == value:
    return 0
  elif lst[1] == value:
    return 1
  elif lst[2] == value:
    return 2
  elif lst[3] == value:
    return 3
  else:
    return None


def by_index(lst, value):
  for i in xrange(4):
    if lst[i] == value:
      return i
  return None


def by_exception(lst, value):
  try:
    lst.index(value)
  except ValueError:
    return None


def by_iter(lst, value):
  for index, element in enumerate(lst):
    if element == value:
      return value
  return None

def by_dict(lst, value):
  return mapping.get(value, None)


def TimeFunction(function_name, value):
  if 'dict' in function_name:
    return timeit.timeit(
        stmt = '%s(mapping, %d)' % (function_name, value),
        setup = 'from __main__ import %s, mapping' % function_name,
        number=NUM_TIMES)
  else:
    return timeit.timeit(
        stmt = '%s(TEST_LIST, %d)' % (function_name, value),
        setup = 'from __main__ import %s, TEST_LIST' % function_name,
        number=NUM_TIMES)


def RunTestsOn(value):
  print "Looking for %d in %s" % (value, str(TEST_LIST))
  function_names = [name for name in globals() if name.startswith('by_')]
  for function_name in function_names:
    print "Function: %s\nTime: %f" % (
        function_name, TimeFunction(function_name, value))



def main():
  values_to_look_for = TEST_LIST + [ -10**70 - 1, 55, 29]
  for value in values_to_look_for:
    RunTestsOn(value)


if __name__ == '__main__':
  main()

看起来，当要查找的值比较小并且在列表中存在时，if-else的方法更快（我把其他函数的运行时间去掉了）：

Looking for 10007 in [100, -2, 10007, 1180591620717411303425L]
Function: by_dict
Time: 0.213232
Function: by_if_else
Time: 0.181917

但如果值很大（也就是说比较的代价比较高），则会变慢：

Looking for 1180591620717411303425 in [100, -2, 10007, 1180591620717411303425L]
Function: by_dict
Time: 0.223594
Function: by_if_else
Time: 0.380222

或者，当值根本不在列表中时（即使这个值很小）：

Looking for 29 in [100, -2, 10007, 1180591620717411303425L]
Function: by_dict
Time: 0.195733
Function: by_if_else
Time: 0.267689

虽然使用字典应该更快，因为在字典上的查询是O(1)，而其他方法是O(n)，但对于这么小的列表，解释器可能会为if-else版本生成优化过的字节码，而通过哈希表进行指针查找的开销抵消了字典的速度优势。不过大多数情况下，它似乎还是稍微快一点。我建议你在自己的数据上测试一下这个方法，看看哪个效果更好。

Answer 2

你可以使用集合来检查某个元素是否在里面，这比用列表来检查要更有效率。不过，最大的开销在于索引的部分：

In [54]: l = [1,2,3,4]

In [55]: s = set([1,2,3,4])

In [56]: timeit l.index(6)  if 6 in s else False
10000000 loops, best of 3: 79.9 ns per loop

In [57]: timeit l.index(6)  if 6 in l else False
10000000 loops, best of 3: 141 ns per loop

In [58]: timeit l.index(4)  if 4 in l else False

1000000 loops, best of 3: 381 ns per loop

In [59]: timeit l.index(4)  if 4 in s else False
1000000 loops, best of 3: 333 ns per loop

Answer 3

因为你只有四个项目，你也可以试试这个：

 if value == mylist[0]:
   return 0
 elif value == mylist[1]:
   return 1
 elif value == mylist[2]:
   return 2
 elif value == mylist [3]:
   return 3

告诉我这个在你那边效果怎么样。我很好奇。:)