快速查找遭遇浮點不準確

假設我有等間距雙打（64位浮點數）x0,x1,...,xn。等間隔意味着對於所有i,x(i+1) - xi是恆定的;寬度爲w。快速查找遭遇浮點不準確

給定y的範圍[x0,xn]我想找到最大的i這樣的xi <= y。

一個幼稚的方法將依次訪問每個i（O(n)）。更好的方法是使用二分查找（O(log n)）。

恆定時間查找將計算(y-x0)/w並將其轉換爲整數。但是，由於浮點不準確，這偶爾會給出錯誤的結果。例如。假設有寬0.01 100個間隔從0開始。

(int)(0.29/0.01) = 28 //want 29 here

我能保持恆定的時間查找，但確保結果總是相同的二進制搜索？使用小數進行計算而不是雙倍計算'w'和'x0'似乎可以在這裏工作，但它會一直工作嗎？我總是可以跟隨直接查找並與x進行比較，但這看起來很醜並且效率低下。

澄清 - 我得到xi和價值y作爲雙打 - 我不能改變這一點。但是在返回整數索引之前執行的任何中間計算都可以使用我喜歡的任何數據類型。此外，我可以執行一次性「準備」工作，以便更快地運行計算。

編輯：道歉 - 事實證明，我沒有正確檢查「等間隔」 - 當它們的差異是使用浮點算法計算時，這些數字通常不是「等距」。

來源

2015-02-11 Rob

'（int）（0.29/0.01 + 0.5）= 28'如果你想四捨五入，而不是截斷。（0.289999/0.01 = 28.999999，在截斷時給出28） – kiwixz 2015-02-11 12:11:19

1）舍入而不是截斷將減少需要調整的可能性。 '（int）Math.Round（0.29/0.01）'2）我會使用索引計算，然後是一個循環，通過向上/向下進行調整，直到您處於正確的位置。對於充分的病理情況，通過一步調整可能是不夠的。 3）C＃的浮點規範非常邪惡，除非你在正確的位置將double放置到double（強制精度降低爲double），否則上述算法可能不會總是工作。 – CodesInChaos 2015-02-11 12:11:24

@iKiWiXz更好的是明確和使用Math.Round，Math.Floor，Math.Ceiling比試圖強制演員做到這一點 – 2015-02-11 12:12:31

執行以下操作

計算(int)(0.29/0.01) = 28 //want 29 here

接下來，計算i和28 + 1之間28-1回i * 0.01，拿起一個是正確的。

來源

2015-02-11 12:12:50 Tarik

是的，這基本上是我在提到比較x的任何一方時暗示的。如果可能，我想避免這種情況。 – Rob 2015-02-11 12:45:22

你說過：「我可以保留恆定時間查找，但要確保結果始終與二進制搜索相同嗎？」 - 這似乎回答你的問題的肯定。 – AakashM 2015-02-11 13:21:41

你只需要看看3個值。這是不變的時間。 – Tarik 2015-02-11 16:31:44

你是什麼意思equally spaced？例如，如果可以對數字進行一些假設 - 例如它們在一個時間間隔內增加，那麼實際上可以使用最佳情況下的O（1）和最差情況下的O（log2（N））。

來源

2015-02-11 13:27:07

等間隔意味着計算爲x（i + 1） - xi'的double不論「i」如何都是恆定的。 – Rob 2015-02-11 13:32:23

快速查找遭遇浮點不準確

回答

相關問題