通常的說法是，在檢查密碼或哈希等內容時，必須在恒定時間內進行字符串比較，因此建議避免使用a == b. 但是，我運行了以下腳本，結果不支持a==b第一個不相同字符短路的假設。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()這是運行的結果，重新運行腳本給出的結果略有不同，但都不令人滿意。# 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我原以為最快的比較是第一個不同字符位于字符串開頭的位置，但這不是我得到的。知道發生了什么事嗎？？？
2 回答
30秒到達戰場
TA貢獻1828條經驗 獲得超6個贊
有區別，您只是在這么小的弦上看不到它。這是一個適用于您的代碼的小補丁，所以我使用更長的字符串，我通過將 A 放在一個位置來進行 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])
你會得到：
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
請注意，在您的示例中，只有2**8字符，它已經很明顯，請應用此補?。?/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])
只保留兩種極端情況（第一個字母變化與最后一個字母變化），你會得到：
$ python3 cmp.py
0 124.131800
1 135.566000
數字可能會有所不同，但大多數時候 test0比 test 快一點1。
為了更精確地隔離修改了哪個字符，只要 memcmp 一個字符一個字符地執行它就可以，只要它不使用整數比較，通常是在最后一個字符未對齊時，或者在非常短的字符串上，比如8 個字符的字符串，正如我在這里演示的那樣：
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 可能不再是這里的正確工具。
揚帆大魚
TA貢獻1799條經驗 獲得超9個贊
看，要知道它為什么不短路，您必須進行一些挖掘。簡單的答案當然是它不會短路，因為標準沒有這樣規定。但是您可能會想，“為什么實現不選擇短路？當然，它必須更快！”。不完全的。
出于顯而易見的原因，讓我們來看看cpython。查看中定義的函數的代碼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);
}
（注意：這個函數實際上是在推導之后調用的，str1并且str2不是同一個對象 - 如果它們是 - 那么這只是一個簡單的True立即）
特別關注這一行-
cmp = memcmp(data1, data2, len * kind);
啊，我們又回到了另一個十字路口。是否memcmp短路？C標準沒有規定這樣的要求。如opengroup 文檔和C 標準草案的第 7.24.4.1 節所示
7.24.4.1 memcmp 函數
概要
#include <string.h>
int memcmp(const void *s1, const void *s2, size_t n);
描述
memcmp 函數將 s1 指向的對象的前 n 個字符與 s2 指向的對象的前 n 個字符進行比較。
退貨
memcmp 函數返回一個大于、等于或小于零的整數，對應于 s1 指向的對象大于、等于或小于 s2 指向的對象。
大多數C 實現（包括glibc）選擇不短路。但為什么？我們是不是漏掉了什么，你為什么不短路？
因為他們使用的比較可能不像逐字節檢查那樣天真。該標準不要求逐字節比較對象。這就是優化的機會。
它的作用glibc是比較類型的元素，unsigned long int而不僅僅是unsigned char. 檢查實施
幕后還有很多事情要做——討論遠遠超出了這個問題的范圍，畢竟這甚至沒有被標記為問題C；）。雖然我發現這個答案可能值得一看。但要知道，優化就在那里，只是形式與乍一看可能想到的方法大不相同。
添加回答
舉報
0/150
提交
取消