您能否詳細說明您是如何計算查找時間的指數?
如果它確實是指數的,也許你可以加快速度通過在你的鑰匙(配置)使用Hash
,然後存儲鍵值對像{{key1,value1},{key2,value2}}
列表,不停地通過key
排序,然後使用二進制搜索(這應該記錄時間)。這應該是非常快速的編碼,但在速度方面不是最佳的。
如果這還不夠快,可以考慮設置一個合適的哈希表實現(我認爲這是f[{0,1,0,1}]=3
方法做的,沒有檢查)。
但放緩的一些玩具例子是進一步進行有益的......
編輯:我只是想
test[length_] := Block[{f},
Do[
f[RandomInteger[{0, 10}, 100]] = RandomInteger[0, 10];,
{i, 1, length}
];
f[{0, 0, 0, 0, 1, 7, 0, 3, 7, 8, 0, 4, 5, 8, 0, 8, 6, 7, 7, 0, 1, 6,
3, 9, 6, 9, 2, 7, 2, 8, 1, 1, 8, 4, 0, 5, 2, 9, 9, 10, 6, 3, 6,
8, 10, 0, 7, 1, 2, 8, 4, 4, 9, 5, 1, 10, 4, 1, 1, 3, 0, 3, 6, 5,
4, 0, 9, 5, 4, 6, 9, 6, 10, 6, 2, 4, 9, 2, 9, 8, 10, 0, 8, 4, 9,
5, 5, 9, 7, 2, 7, 4, 0, 2, 0, 10, 2, 4, 10, 1}] // timeIt
]
與timeIt
定義以準確的時間,即使短期運行如下:
timeIt::usage = "timeIt[expr] gives the time taken to execute expr,
repeating as many times as necessary to achieve a total time of \
1s";
SetAttributes[timeIt, HoldAll]
timeIt[expr_] := Module[{t = Timing[expr;][[1]], tries = 1},
While[t < 1.,
tries *= 2;
t = Timing[Do[expr, {tries}];][[1]];
];
Return[t/tries]]
然後
out = {#, test[#]} & /@ {10, 100, 1000, 10000, 100000, 100000};
[email protected]
![enter image description here](https://i.stack.imgur.com/AFliB.png)
(也適用於較大的運行)。所以在這裏似乎不變。
無模式DownValue查找使用哈希,並分攤和適當的內存限制,恆定的時間。不管是什麼導致你的速度問題,它本身不可能是單獨的查找時間。 –