起步
对于子串搜索,python提供了多种实现方式:in, find, index, __contains__,对其进行性能比较:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
import timeit
def in_(s, other):
return other in s
def contains(s, other):
return s.__contains__(other)
def find(s, other):
return s.find(other) ! = - 1
def index(s, other):
try :
s.index(other)
except valueerror:
return false
return true
perf_dict = {
'in:true' : min (timeit.repeat( lambda : in_( 'superstring' , 'str' ))),
'in:false' : min (timeit.repeat( lambda : in_( 'superstring' , 'not' ))),
'__contains__:true' : min (timeit.repeat( lambda : contains( 'superstring' , 'str' ))),
'__contains__:false' : min (timeit.repeat( lambda : contains( 'superstring' , 'not' ))),
'find:true' : min (timeit.repeat( lambda : find( 'superstring' , 'str' ))),
'find:false' : min (timeit.repeat( lambda : find( 'superstring' , 'not' ))),
'index:true' : min (timeit.repeat( lambda : index( 'superstring' , 'str' ))),
'index:false' : min (timeit.repeat( lambda : index( 'superstring' , 'not' ))),
}
print (perf_dict)
|
得到结果:
{
'in:true': 0.2763608000000001,
'in:false': 0.2794432,
'__contains__:true': 0.40546490000000013,
'__contains__:false': 0.4122471000000001,
'find:true': 0.497128,
'find:false': 0.4951530000000002,
'index:true': 0.5243821999999998,
'index:false': 0.8693923999999988
}
从结果上 in 的搜索方式性能上最好。
知其然也要之其所以然,下面就对于这个结果进行比较与分析。
in 与 __contains__ 比较
了解 python 中协议的应该知道,in 操作其实也是调用 __contains__ ,但为什么 in 比 __contains__ 明显快了很多,明明它们最终调用的c语言函数是一样的。
在 cpython 中,in 属于操作符,它直接指向了 sq_contains 中的c级函数指针,而在 str 中的 sq_contains 直接指向了最终调用的c层函数。而 __contains__ 的调用方式,则需要先在 str 属性中进行 load_attr 查找,然后再为 call_function 创建函数调用所需的空间。
也就是说,in 直接指向了最终的c层函数,一步到位,也不走python虚拟机的函数调用,而 __contains__ 调用方式先属性查找和python函数调用的开销;所以 str.__contains__(other) 的形式要慢得多。
一般来说,in 方式更快只使用 python 内置的c实现的类。对于用户自定义类,因为最终调用都是python级的,所以两种方式都要对函数调用所需的空间的。
find 与 index 的比较
find 与 index 的查找方式的区别仅仅只是 index 在子串不存在时会抛出异常。从源码来看:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
static pyobject *
unicode_find(pyobject * self , pyobject * args)
{
/ * initialize variables to prevent gcc warning * /
pyobject * substring = null;
py_ssize_t start = 0 ;
py_ssize_t end = 0 ;
py_ssize_t result;
if (!parse_args_finds_unicode( "find" , args, &substring, &start, &end))
return null;
if (pyunicode_ready( self ) = = - 1 )
return null;
result = any_find_slice( self , substring, start, end, 1 );
if (result = = - 2 )
return null;
return pylong_fromssize_t(result);
}
static pyobject *
unicode_index(pyobject * self , pyobject * args)
{
/ * initialize variables to prevent gcc warning * /
py_ssize_t result;
pyobject * substring = null;
py_ssize_t start = 0 ;
py_ssize_t end = 0 ;
if (!parse_args_finds_unicode( "index" , args, &substring, &start, &end))
return null;
if (pyunicode_ready( self ) = = - 1 )
return null;
result = any_find_slice( self , substring, start, end, 1 );
if (result = = - 2 )
return null;
if (result < 0 ) {
pyerr_setstring(pyexc_valueerror, "substring not found" );
return null;
}
return pylong_fromssize_t(result);
}
|
实现方式基本相同,所以在子串存在的时候,两者的性能一致;而当子串不存在时,index 会设置异常,因此涉及异常栈的空间等异常机制,速度上也就慢了一些。
总结
in 的搜索方式性能最佳,可读性也最好,属最佳实践。
好了,以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。
扩展阅读
原文链接:http://www.hongweipeng.com/index.php/archives/1805/