通常的說法是，在檢查密碼或哈希等內(nèi)容時(shí)，必須在恒定時(shí)間內(nèi)進(jìn)行字符串比較，因此建議避免使用a == b. 但是，我運(yùn)行了以下腳本，結(jié)果不支持a==b第一個(gè)不相同字符短路的假設(shè)。from time import perf_counter_nsimport randomdef timed_cmp(a, b): start = perf_counter_ns() a == b end = perf_counter_ns() return end - startdef n_timed_cmp(n, a, b): "average time for a==b done n times" ts = [timed_cmp(a, b) for _ in range(n)] return sum(ts) / len(ts)def check_cmp_time(): random.seed(123) # generate a random string of n characters n = 2 ** 8 s = "".join([chr(random.randint(ord("a"), ord("z"))) for _ in range(n)]) # generate a list of strings, which all differs from the original string # by one character, at a different position # only do that for the first 50 char, it's enough to get data diffs = [s[:i] + "A" + s[i+1:] for i in range(min(50, n))] timed = [(i, n_timed_cmp(10000, s, d)) for (i, d) in enumerate(diffs)] sorted_timed = sorted(timed, key=lambda t: t[1]) # print the 10 fastest for x in sorted_timed[:10]: i, t = x print("{}\t{:3f}".format(i, t)) print("---") i, t = timed[0] print("{}\t{:3f}".format(i, t)) i, t = timed[1] print("{}\t{:3f}".format(i, t))if __name__ == "__main__": check_cmp_time()這是運(yùn)行的結(jié)果，重新運(yùn)行腳本給出的結(jié)果略有不同，但都不令人滿意。# ran with cpython 3.8.36 78.0517001 78.20320015 78.22270014 78.38480011 78.39630012 78.4418009 78.47690013 78.5190008 78.5862003 78.631500---0 80.6911001 78.203200我原以為最快的比較是第一個(gè)不同字符位于字符串開頭的位置，但這不是我得到的。知道發(fā)生了什么事嗎？？？
2 回答
30秒到達(dá)戰(zhàn)場(chǎng)
TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超6個(gè)贊
有區(qū)別，您只是在這么小的弦上看不到它。這是一個(gè)適用于您的代碼的小補(bǔ)丁，所以我使用更長(zhǎng)的字符串，我通過將 A 放在一個(gè)位置來進(jìn)行 10 次檢查，從頭到尾在原始字符串中均勻分布，我的意思是，像這樣：
A_______________________________________________________________
______A_________________________________________________________
____________A___________________________________________________
__________________A_____________________________________________
________________________A_______________________________________
______________________________A_________________________________
____________________________________A___________________________
__________________________________________A_____________________
________________________________________________A_______________
______________________________________________________A_________
____________________________________________________________A___
@@ -15,13 +15,13 @@ def n_timed_cmp(n, a, b):
def check_cmp_time():
random.seed(123)
# generate a random string of n characters
- n = 2 ** 8
+ n = 2 ** 16
s = "".join([chr(random.randint(ord("a"), ord("z"))) for _ in range(n)])
# generate a list of strings, which all differs from the original string
# by one character, at a different position
# only do that for the first 50 char, it's enough to get data
- diffs = [s[:i] + "A" + s[i+1:] for i in range(min(50, n))]
+ diffs = [s[:i] + "A" + s[i+1:] for i in range(0, n, n // 10)]
timed = [(i, n_timed_cmp(10000, s, d)) for (i, d) in enumerate(diffs)]
sorted_timed = sorted(timed, key=lambda t: t[1])
你會(huì)得到：
0 122.621000
1 213.465700
2 380.214100
3 460.422000
5 694.278700
4 722.010000
7 894.630300
6 1020.722100
9 1149.473000
8 1341.754500
---
0 122.621000
1 213.465700
請(qǐng)注意，在您的示例中，只有2**8字符，它已經(jīng)很明顯，請(qǐng)應(yīng)用此補(bǔ)?。?/p>
@@ -21,7 +21,7 @@ def check_cmp_time():
# generate a list of strings, which all differs from the original string
# by one character, at a different position
# only do that for the first 50 char, it's enough to get data
- diffs = [s[:i] + "A" + s[i+1:] for i in range(min(50, n))]
+ diffs = [s[:i] + "A" + s[i+1:] for i in [0, n - 1]]
timed = [(i, n_timed_cmp(10000, s, d)) for (i, d) in enumerate(diffs)]
sorted_timed = sorted(timed, key=lambda t: t[1])
只保留兩種極端情況（第一個(gè)字母變化與最后一個(gè)字母變化），你會(huì)得到：
$ python3 cmp.py
0 124.131800
1 135.566000
數(shù)字可能會(huì)有所不同，但大多數(shù)時(shí)候 test0比 test 快一點(diǎn)1。
為了更精確地隔離修改了哪個(gè)字符，只要 memcmp 一個(gè)字符一個(gè)字符地執(zhí)行它就可以，只要它不使用整數(shù)比較，通常是在最后一個(gè)字符未對(duì)齊時(shí)，或者在非常短的字符串上，比如8 個(gè)字符的字符串，正如我在這里演示的那樣：
from time import perf_counter_ns
from statistics import median
import random
def check_cmp_time():
random.seed(123)
# generate a random string of n characters
n = 8
s = "".join([chr(random.randint(ord("a"), ord("z"))) for _ in range(n)])
# generate a list of strings, which all differs from the original string
# by one character, at a different position
# only do that for the first 50 char, it's enough to get data
diffs = [s[:i] + "A" + s[i + 1 :] for i in range(n)]
values = {x: [] for x in range(n)}
for _ in range(10_000_000):
for i, diff in enumerate(diffs):
start = perf_counter_ns()
s == diff
values[i].append(perf_counter_ns() - start)
timed = [[k, median(v)] for k, v in values.items()]
sorted_timed = sorted(timed, key=lambda t: t[1])
# print the 10 fastest
for x in sorted_timed[:10]:
i, t = x
print("{}\t{:3f}".format(i, t))
print("---")
i, t = timed[0]
print("{}\t{:3f}".format(i, t))
i, t = timed[1]
print("{}\t{:3f}".format(i, t))
if __name__ == "__main__":
check_cmp_time()
這給了我：
1 221.000000
2 222.000000
3 223.000000
4 223.000000
5 223.000000
6 223.000000
7 223.000000
0 241.000000
差異是如此之小，Python 和 perf_counter_ns 可能不再是這里的正確工具。
揚(yáng)帆大魚
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超9個(gè)贊
看，要知道它為什么不短路，您必須進(jìn)行一些挖掘。簡(jiǎn)單的答案當(dāng)然是它不會(huì)短路，因?yàn)闃?biāo)準(zhǔn)沒有這樣規(guī)定。但是您可能會(huì)想，“為什么實(shí)現(xiàn)不選擇短路？當(dāng)然，它必須更快！”。不完全的。
出于顯而易見的原因，讓我們來看看cpython。查看中定義的函數(shù)的代碼unicode_compare_equnicodeobject.c
static int
unicode_compare_eq(PyObject *str1, PyObject *str2)
{
int kind;
void *data1, *data2;
Py_ssize_t len;
int cmp;
len = PyUnicode_GET_LENGTH(str1);
if (PyUnicode_GET_LENGTH(str2) != len)
return 0;
kind = PyUnicode_KIND(str1);
if (PyUnicode_KIND(str2) != kind)
return 0;
data1 = PyUnicode_DATA(str1);
data2 = PyUnicode_DATA(str2);
cmp = memcmp(data1, data2, len * kind);
return (cmp == 0);
}
（注意：這個(gè)函數(shù)實(shí)際上是在推導(dǎo)之后調(diào)用的，str1并且str2不是同一個(gè)對(duì)象 - 如果它們是 - 那么這只是一個(gè)簡(jiǎn)單的True立即）
特別關(guān)注這一行-
cmp = memcmp(data1, data2, len * kind);
啊，我們又回到了另一個(gè)十字路口。是否memcmp短路？C標(biāo)準(zhǔn)沒有規(guī)定這樣的要求。如opengroup 文檔和C 標(biāo)準(zhǔn)草案的第 7.24.4.1 節(jié)所示
7.24.4.1 memcmp 函數(shù)
概要
#include <string.h>
int memcmp(const void *s1, const void *s2, size_t n);
描述
memcmp 函數(shù)將 s1 指向的對(duì)象的前 n 個(gè)字符與 s2 指向的對(duì)象的前 n 個(gè)字符進(jìn)行比較。
退貨
memcmp 函數(shù)返回一個(gè)大于、等于或小于零的整數(shù)，對(duì)應(yīng)于 s1 指向的對(duì)象大于、等于或小于 s2 指向的對(duì)象。
大多數(shù)C 實(shí)現(xiàn)（包括glibc）選擇不短路。但為什么？我們是不是漏掉了什么，你為什么不短路？
因?yàn)樗麄兪褂玫谋容^可能不像逐字節(jié)檢查那樣天真。該標(biāo)準(zhǔn)不要求逐字節(jié)比較對(duì)象。這就是優(yōu)化的機(jī)會(huì)。
它的作用glibc是比較類型的元素，unsigned long int而不僅僅是unsigned char. 檢查實(shí)施
幕后還有很多事情要做——討論遠(yuǎn)遠(yuǎn)超出了這個(gè)問題的范圍，畢竟這甚至沒有被標(biāo)記為問題C；）。雖然我發(fā)現(xiàn)這個(gè)答案可能值得一看。但要知道，優(yōu)化就在那里，只是形式與乍一看可能想到的方法大不相同。
添加回答
舉報(bào)
0/150
提交
取消