起步
對(duì)于子串搜索，python提供了多種實(shí)現(xiàn)方式:in, find, index, __contains__，對(duì)其進(jìn)行性能比較:
|
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 timeitdef in_(s, other): return other in sdef contains(s, other): return s.__contains__(other)def find(s, other): return s.find(other) != -1def index(s, other): try: s.index(other) except valueerror: return false return trueperf_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) |
得到結(jié)果:
{
'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
}
從結(jié)果上 in 的搜索方式性能上最好。
知其然也要之其所以然，下面就對(duì)于這個(gè)結(jié)果進(jìn)行比較與分析。
in 與 __contains__ 比較
了解 python 中協(xié)議的應(yīng)該知道，in 操作其實(shí)也是調(diào)用 __contains__ ，但為什么 in 比 __contains__ 明顯快了很多，明明它們最終調(diào)用的c語言函數(shù)是一樣的。
在 cpython 中，in 屬于操作符，它直接指向了 sq_contains 中的c級(jí)函數(shù)指針，而在 str 中的 sq_contains 直接指向了最終調(diào)用的c層函數(shù)。而 __contains__ 的調(diào)用方式，則需要先在 str 屬性中進(jìn)行 load_attr 查找，然后再為 call_function 創(chuàng)建函數(shù)調(diào)用所需的空間。
也就是說，in 直接指向了最終的c層函數(shù)，一步到位，也不走python虛擬機(jī)的函數(shù)調(diào)用，而 __contains__ 調(diào)用方式先屬性查找和python函數(shù)調(diào)用的開銷；所以 str.__contains__(other) 的形式要慢得多。
一般來說，in 方式更快只使用 python 內(nèi)置的c實(shí)現(xiàn)的類。對(duì)于用戶自定義類，因?yàn)樽罱K調(diào)用都是python級(jí)的，所以兩種方式都要對(duì)函數(shù)調(diào)用所需的空間的。
find 與 index 的比較
find 與 index 的查找方式的區(qū)別僅僅只是 index 在子串不存在時(shí)會(huì)拋出異常。從源碼來看:
|
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);} |
實(shí)現(xiàn)方式基本相同，所以在子串存在的時(shí)候，兩者的性能一致；而當(dāng)子串不存在時(shí)，index 會(huì)設(shè)置異常，因此涉及異常棧的空間等異常機(jī)制，速度上也就慢了一些。
總結(jié)
in 的搜索方式性能最佳，可讀性也最好，屬最佳實(shí)踐。
好了，以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)服務(wù)器之家的支持。
擴(kuò)展閱讀
原文鏈接：http://www.hongweipeng.com/index.php/archives/1805/
