數(shù)據(jù)排序對全遍歷性能的意外影響
在構(gòu)建測試數(shù)據(jù)生成器時，我觀察到一個有趣的現(xiàn)象：對原始數(shù)據(jù)排序后，數(shù)據(jù)生成時間顯著增加。這與預(yù)期的O(n)時間復(fù)雜度相悖。
以下是我的測試代碼片段：
import random import json import tqdm import sys import humanize num = 100000 test_data_num = 0 test_strings = [] print('生成隨機(jī)字符串...') for i in tqdm.tqdm(range(num * 10)): test_strings.append(''.join( [random.choice('abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz') for _ in range(random.randint(3, 10))])) # 關(guān)鍵行：修改此處觀察性能變化 test_strings = tuple(test_strings) # 原代碼 # test_strings = tuple(sorted(test_strings)) # 排序 # random.shuffle(test_strings) # 打亂順序 # test_strings = random.sample(test_strings, len(test_strings)) # 隨機(jī)采樣 print('隨機(jī)字符串生成完畢，大小為:', humanize.naturalsize(sys.getsizeof(test_strings))) data: list = [] print('開始生成測試數(shù)據(jù)...') for i in tqdm.tqdm(range(num)): test_data_str = ''.join( [random.choice('abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz') for _ in range(random.randint(3, 8))]) data.append((test_data_str, {j for j in test_strings if j.startswith(test_data_str)})) print('測試數(shù)據(jù)生成完畢，大小為:', humanize.naturalsize(sys.getsizeof(data))) json.dump({'num': num, 'test_strings': test_strings, 'data': data}, open(f'test_data_{test_data_num}.json', 'w'))
將 test_strings = tuple(test_strings) 替換為排序或打亂順序操作（如 tuple(sorted(test_strings))、random.shuffle(test_strings) 或 random.sample），生成時間從2.5小時飆升至5.5小時。即使簡單地將 tuple 替換為 list 也會導(dǎo)致時間增加。
性能分析與推測
-
排序并非罪魁禍?zhǔn)? 實驗表明，問題并非排序本身，而是破壞了原始數(shù)據(jù)的內(nèi)存地址連續(xù)性。排序、打亂或隨機(jī)采樣都會導(dǎo)致性能下降。
-
迭代操作無關(guān): 即使將迭代內(nèi)部操作簡化為 pass，性能差異依然顯著。
-
內(nèi)存尋址效率: 我推測性能瓶頸在于內(nèi)存訪問效率。初始狀態(tài)下，test_strings 中的字符串地址相對連續(xù)，有利于 CPU 緩存命中。排序或打亂后，地址變得離散，導(dǎo)致緩存失效率上升，頻繁訪問主內(nèi)存，從而拖慢速度。 這可能也涉及到分頁機(jī)制，順序訪問更少地觸發(fā)頁面置換。
為了驗證緩存命中率的影響，可以嘗試將 test_strings 反轉(zhuǎn)：
test_strings = list(reversed(test_strings))
觀察反轉(zhuǎn)操作是否也會影響性能。 這些實驗結(jié)果表明，數(shù)據(jù)在內(nèi)存中的布局對全遍歷性能有顯著影響，這與CPU緩存和內(nèi)存分頁機(jī)制密切相關(guān)。
.png)
