在二维数组中搜索字符串的最快方法是什么

Question

我需要在一个二维数组的第一列中查找一个字符串。最简单的方法就是

for i in range (0, len(list)):
if list[i][0]==searchstring:
   list[i][4]=do_a_bunch_of_stuff

我需要知道“i”在哪里，这样我才能对同一行做很多事情。我需要遍历这个二维数组中的所有行。

速度是最重要的因素，不需要考虑代码的美观。有什么最快（CPU性能）的方法来做到这一点呢？

Answer 1

因为这列数据是无序的，所以线性搜索是你能用的最快的方法。线性搜索的意思就是你需要检查每一个元素，才能找到你想要的。

如果你需要重复进行这个搜索的过程，可以考虑用字典来创建一个索引：

index = {}
for i in range (0, len(list)):
    index[list[i]] = index.get(list[i], list()) + [i]

这样的话，你就可以很简单地查找任何你需要搜索的字符串的索引了：

rows = index[some_string]

不过，这样做会占用更多的内存，因为你需要存储第一列中的每个唯一值，还要存一个整数列表。

如果你不需要把数据保持在二维数组的格式，可能可以考虑把它重构成一个字典。你可以把你的搜索字符串当作键，映射到一个元组的列表中，每个元组里存放的是那一行其他列的数据。

Answer 2

其实没有更快的方法来做到这一点，你总是需要比较你要查找的字符串中每个内部列表的第一个元素。

下面的方法可能会稍微快一点，因为它避免了几次查找索引：

for x in lst:
    if x[0] == searchstring:
        x[4] = do_a_bunch_of_stuff