.jpg)
探究原始數(shù)據(jù)順序?qū)θ闅v效率的影響
在構(gòu)建測(cè)試數(shù)據(jù)生成器時(shí)，我發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象：對(duì)test_strings進(jìn)行排序后，數(shù)據(jù)生成時(shí)間顯著增加。這令人費(fèi)解，因?yàn)槔碚撋希瑹o(wú)論數(shù)據(jù)是否排序，時(shí)間復(fù)雜度都應(yīng)為O(n)。
以下是我的代碼：
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))])) # test_strings = tuple(test_strings) # 原代碼 test_strings = tuple(sorted(test_strings)) # 修改后的代碼 print('隨機(jī)字符串生成完畢，大小為:', humanize.naturalsize(sys.getsizeof(test_strings))) data: list = [] print('開(kāi)始生成測(cè)試數(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('測(cè)試數(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)改為test_strings = tuple(sorted(test_strings))后，生成時(shí)間從2.5小時(shí)激增到5.5小時(shí)。排序本身耗時(shí)并不多，因此這并非排序?qū)е碌摹?/p>
經(jīng)過(guò)測(cè)試和分析，我發(fā)現(xiàn)問(wèn)題并非排序本身，而是與大型字符串?dāng)?shù)組的內(nèi)存訪問(wèn)效率有關(guān)：
-
并非排序?qū)е?/strong>: 無(wú)論使用sorted()、random.shuffle()，還是random.sample()打亂順序，都會(huì)導(dǎo)致遍歷速度變慢。關(guān)鍵在于破壞了原始數(shù)據(jù)的內(nèi)存地址連續(xù)性。
-
與迭代內(nèi)部操作無(wú)關(guān): 即使將內(nèi)部循環(huán)替換為空循環(huán)，for j in test_strings: pass，仍然能觀察到順序變化帶來(lái)的性能差異。
我的推測(cè)如下：
-
初始狀態(tài): test_strings中的字符串在創(chuàng)建時(shí)按順序添加到列表中，因此它們的內(nèi)存地址大致連續(xù)。
-
CPU緩存命中: CPU緩存利用內(nèi)存地址連續(xù)性來(lái)提高訪問(wèn)速度。當(dāng)訪問(wèn)順序與內(nèi)存地址順序一致時(shí)，緩存命中率高，訪問(wèn)速度快；反之，緩存命中率低，需要頻繁訪問(wèn)主存，速度慢。
-
頁(yè)面調(diào)度: test_strings可能跨越多個(gè)內(nèi)存頁(yè)。當(dāng)內(nèi)存地址連續(xù)時(shí)，頁(yè)面調(diào)度次數(shù)少；當(dāng)順序被打亂后，頁(yè)面調(diào)度次數(shù)增多，導(dǎo)致性能下降。
為了驗(yàn)證推測(cè)，可以嘗試反向排序test_strings：test_strings = tuple(reversed(test_strings))。這有助于進(jìn)一步理解性能差異的根源，即內(nèi)存訪問(wèn)模式對(duì)性能的影響遠(yuǎn)大于排序算法本身。 關(guān)鍵在于理解內(nèi)存訪問(wèn)局部性原理，以及如何利用它來(lái)優(yōu)化代碼性能。
.png)
