尋找一個通用的「平分」功能

我正在尋找在類似於Python的bisect_left()和朋友的Haskell中的bisect操作。輸入是一個下限，一個上限，一個非遞減函數（Ord a）=>（Int-> a），它必須爲所有下限和上限之間的整數以及一個搜索值定義。返回值是最高整數i，其中lower <= i <= upper和f(i) < search_term。性能應該是O（log（n））。尋找一個通用的「平分」功能

Hoogling此：

(Ord a)=>(Int->a)->Int->Int->a->Int

不會產生任何結果。

庫中是否有標準的通用二元搜索運算符？

來源

2012-03-24 gcbenison

是對'INT - > A'函數假定爲單調增加/非減？ – jwodder 2012-03-24 23:05:11

@jwodder該函數應該是非遞減的 - 編輯以添加約束 – gcbenison 2012-03-24 23:42:27

您可能還喜歡手指樹，它們被設計爲有效搜索單調謂詞。 – 2012-03-25 03:30:55

羅斯帕特森的binary-search包在Hackage做你正在尋找。具體而言，請參閱searchFromTo，其類型爲簽名

searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a

作爲吉洪所指出的，在[a] Haskell是一個鏈表而不是陣列。由於鏈表僅支持順序訪問，因此無法在[a]數據結構上進行對數時間搜索。相反，您應該使用真正的陣列數據結構 - 請參閱vector庫以獲取陣列的首選實現。

丹Doel寫了一個家族的二進制搜索功能在矢量包可變載體：看到他vector-algorithms庫Data.Vector.Algorithms.Search。與提供純API的Ross Paterson的庫不同，Data.Vector.Algorithms.Search中的API是monadic（即，它必須在ST monad或IO monad中運行）。

來源

2012-03-25 00:00:29 reinerp

像bisect_left這樣的函數（假設我正確地閱讀了它的文檔）對列表來說並不存在。因爲你沒有在列表中的O（1）中的隨機訪問（記住Haskell列表是鏈接列表，而Python使用的東西更像是一個向量），所以你不能真正獲得一個O（logn）二進制搜索。

特別是，剛到列表中間需要O（n/2）（這只是O（n））個步驟，所以涉及列表中間的算法（如二分搜索）必須以Ω（n）爲單位。

總之 - 二元搜索在列表上沒有意義。如果您正在進行大量搜索，則可能需要不同的數據結構。特別是，看看在內部使用二叉樹的Data.Set。

來源

2012-03-24 22:49:28

他說數組不是列表。 – alternative 2012-03-24 23:16:25

@monadic但他的類型簽名說的名單。他的術語很混亂。 – bitbucket 2012-03-24 23:18:38

@bitbucket確實 - C編程太多讓我把[]與單詞「數組」聯繫起來，而且我很sl。。然而，我真正想要的是一種二進制搜索，可以與任何非遞減函數一起使用，而不僅僅是一個有序列表或數組。所以我編輯了關於列表/數組的句子，因爲他們只是混淆了這個問題。 – gcbenison 2012-03-24 23:53:50

binary_search :: Ord a, Integral b => (b -> a) -> b -> b -> a -> b 
binary_search f low hi a = go low hi 
    where 
     go low hi | low + 1 == hi = low 
     go low hi = go low' hi' 
      where 
       mid = (low + hi) `div` 2 
       (low',hi') = if f mid < a then (mid,hi) else (low, mid)

（這可具有差一錯誤。）

來源

2012-03-25 00:08:08 huon

尋找一個通用的「平分」功能

回答

相關問題