它值得轉換爲集？

我正在處理程序中的列表，並且希望能夠快速檢查兩個列表是否相交。我在執行嘗試它值得轉換爲集？

commonEle :: (Eq a) => [a] -> [a] -> Bool 
commonEle _ [] = False 
commonEle [] _ = False 
commonEle (x:xs) ys 
    |x `elem` ys = True 
    |otherwise = commonEle xs ys

這工作，但我想小心效率，使事情不炸燬。 This SO question在其中一個答案中解釋，使用集合來快速檢查交叉點會更有效率。我的列表將自動具有不同的元素，所以使用集合可能是一個好主意，但構建數據的自然方式是列表理解，所以我必須使用fromList函數將其變爲集合。你如何判斷哪個實現更高效？

爲了記錄，我將不得不檢查很多相當小的列表（大小爲< 100的〜10^5）。

來源

2015-08-16 Daniel Littlewood

我認爲找出最好的方法就是嘗試它（測量它） - 這只是我的直覺，但我認爲*列表<100您可能會更快通過使用列表（可能首先排序） – Carsten

「爲了記錄，我將不得不檢查大量相當小的列表（大小小於100的〜10^5）「 - 您是否要針對單個列表檢查所有列表，還是需要測試所有列表可能的配對？ – duplode

注意：你**不能**使用Set並獲得一個嚴格等價的函數。使用'Set's意味着有'Ord a'約束，而你的函數只有'Eq a'。如果你允許'Ord a'，一個等效的方法可以是對這兩個列表進行排序，然後使用類似'group'的東西，然後比較「線性」（不需要使用elem來檢查頭部）。事實上，我相信這個問題*如果只允許'Eq a'需要* O（n^2）... – Bakuriu

你打算檢查所有的列表是否對單個列表，或者你需要測試所有可能的配對嗎？

我會檢查很多非常小的名單對一個。

我問，因爲一個問題將不得不轉換太多的小列表與fromList。由於其中一個列表是固定的，您可以通過轉換固定列表來避免大部分成本。

import qualified Data.Set as S 
import Data.Set (Set) 

-- There is probably a better name for this modified version. 
commonEle :: (Ord a) => Set a -> [a] -> Bool 
commonEle xs ys = any (`S.member` xs) ys

如果你正在寫一個益智遊戲，你可以考慮永久保持拼圖的狀態，這部分爲Set，這樣你就不必重新創建一舉一動集。（如果事實證明您需要保留與職位相關的額外信息，那麼Data.Map/Data.Map.Strict/Data.HashMap也有Map類型）。

然而，在任何情況下，都要遵循Carsten的建議：「找出最好的方法就是嘗試（測量它）」。另外，請務必檢查您計劃在相關模塊的文檔中使用的功能的承諾性能特徵。

來源

2015-08-16 21:42:24 duplode

您在評論中提到，您的套件將全部爲座標對(Int,Int)，其中每個座標的範圍爲[1..10]。

在這種情況下，您應該使用「位集」，以便您可以使用處理器的按位AND和OR操作來設置交集和聯合。

模塊Data.BitSet.Dynamic可以用於這一目的：

import qualified Data.BitSet.Dynamic as B 

type Bset = B.BitSet B.FasterInteger 

-- convert a list of points into a bit set 
toSet :: [(Int,Int)] -> Bset 
toSet points = B.fromList [ fromIntegral (r*10+c) | (r,c) <- points ] 

-- do two bit sets have common elements? 
commonElements :: Bset -> Bset -> Bool 
commonElements a b = not $ B.null $ B.intersection a b 

-- add a point to a bit set 
addPoint :: Bset -> (Int,Int) -> Bset 
addPoint a (r,c) = B.insert (fromIntegral $ r*10+c) a 

-- convert a bit set to a list of points 
toPoints :: Bset -> [(Int,Int)] 
toPoints a = [ (q,r) | x <- B.toList a, let (q,r) = divMod (fromIntegral x) 10 ] 

-- does a set have a point? 
hasPoint :: Bset -> (Int,Int) -> Bool 
hasPoint a (r,c) = B.member (fromIntegral $ r*10+c) a

檢測是否兩套有任何共同的元件或點是否在一組是非常快的。

來源

2015-08-16 21:56:29 ErikR

它值得轉換爲集？

回答

相關問題