TA貢獻1812條經(jīng)驗 獲得超5個贊
只用一個比較/分支就可以做到這一點。它是否能真正提高速度可能會受到質(zhì)疑，即使它確實如此，它可能太少注意或不關心，但當你只是開始兩次比較時，巨大改進的可能性非常小。代碼如下：
// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
// upper-lower, simply add + 1 to upper-lower and use the < operator.
if ((unsigned)(number-lower) <= (upper-lower))
in_range(number);
對于典型的現(xiàn)代計算機（即使用二進制補碼的任何東西），轉(zhuǎn)換為無符號實際上是一個不必要的 - 只是改變了相同位的查看方式。
請注意，在典型情況下，您可以upper-lower在（假定的）循環(huán)之外預先計算，因此通常不會貢獻任何重要時間。隨著減少分支指令的數(shù)量，這也（通常）改進了分支預測。在這種情況下，無論數(shù)字是低于底端還是高于范圍的頂端，都會采用相同的分支。
至于它是如何工作的，基本思路非常簡單：當被視為無符號數(shù)時，負數(shù)將大于以正數(shù)開頭的任何數(shù)字。
在實踐中，此方法將number間隔轉(zhuǎn)換為原點，并檢查是否number在區(qū)間中[0, D]，在哪里D = upper - lower。如果number低于下限：負，如果高于上限：大于D。
TA貢獻1836條經(jīng)驗 獲得超4個贊
能夠?qū)θ绱诵∫?guī)模的代碼進行重要優(yōu)化是很少見的。從更高級別觀察和修改代碼可以獲得巨大的性能提升。您可以完全消除對范圍測試的需要，或者僅執(zhí)行O（n）而不是O（n ^ 2）。您可以重新排序測試，以便始終隱含不平等的一面。即使算法是理想的，當您看到此代碼如何進行1000萬次范圍測試并且您找到一種方法來批量處理并使用SSE并行執(zhí)行多個測試時，更有可能獲得增益。
TA貢獻1836條經(jīng)驗 獲得超13個贊
這取決于您希望對同一數(shù)據(jù)執(zhí)行測試的次數(shù)。
如果您一次執(zhí)行測試，可能沒有一種有意義的方法來加速算法。
如果您為一組非常有限的值執(zhí)行此操作，則可以創(chuàng)建查找表。執(zhí)行索引可能會更昂貴，但如果您可以將整個表放在緩存中，那么您可以從代碼中刪除所有分支，這樣可以加快速度。
對于您的數(shù)據(jù)，查找表將是128 ^ 3 = 2,097,152。如果您可以控制三個變量中的一個，那么您可以同時考慮所有實例start = N，那么工作集的大小將下降到128^2 = 16432字節(jié)，這應該適合大多數(shù)現(xiàn)代緩存。
您仍然需要對實際代碼進行基準測試，以查看無分支查找表是否比明顯的比較快得多。
舉報