最快的列表索引搜索

Python 2018-04-18

起步

这个问题来自 https://stackoverflow.com/questions/25476179/fastest-list-index-searching/ 。大致意思是一个只有 4 个整数元素的数组搜索性能不理想。

可选方案

方法一

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

这个方案搜索两次,多余了。

方法二

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

这段代码没有了条件检查。

方法三

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

这是最 pythonic 的写法了。

方法四

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

这个方法最为粗暴,仅针对很小的数组。

测试

我的测试脚本:

#coding: utf-8
import time
import random

def fun1(value, mylist):
    if value in mylist:
        return mylist.index(value)

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

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

def fun4(value, arr):
    if value == arr[0]:
        return 0
    elif value == arr[1]:
        return 1
    elif value == arr[2]:
        return 2
    elif value == arr[3]:
        return 3
    return None

target_list = [x for x in range(4)]

# 100w 的测试数据,按二八原则来,有 80% 的概率命中
test_data = [random.randint(1, 4) for _ in range(800000)] + [random.randint(10, 1000) for _ in range(200000)]
random.shuffle(test_data)  # 乱序

start_time = time.time()
for item in test_data:
    fun1(item, target_list)
end_time = time.time()
print("fun1 use time:", end_time - start_time)

start_time = time.time()
for item in test_data:
    fun2(item, target_list)
end_time = time.time()
print("fun2 use time:", end_time - start_time)

start_time = time.time()
for item in test_data:
    fun3(item, target_list)
end_time = time.time()
print("fun3 use time:", end_time - start_time)

start_time = time.time()
for item in test_data:
    fun4(item, target_list)
end_time = time.time()
print("fun4 use time:", end_time - start_time)

用了 100w 条的测试数据,按 80% 的命中率来进行测试。

测试结果:

fun1 use time: 0.2760157585144043
fun2 use time: 0.45302581787109375
fun3 use time: 0.48602795600891113
fun4 use time: 0.2590148448944092

没想到的是方法一会比方法二来的快,这应该是 try...except... 结构需要额外设置堆栈有关。当我把 mylist 长度调至 300 个时两个方法相当,再往上就是方法二更佳了。方法三的性能损失主要是不断的拆包和解包。尽管方法四最快,但显然这个方法并不推荐。


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!