具有任意長度數據作爲鍵的功能性地圖數據結構？

很可能這個問題的答案是一個明顯的和響亮的「沒有這樣的事情」，但我會給它一個鏡頭：是否有一個功能性地圖樣數據結構比標準更有效當鑰匙具有任意的，通常很大的尺寸時，如何繪製地圖？具有任意長度數據作爲鍵的功能性地圖數據結構？

爲了具體起見，考慮哈斯克爾類型

(Ord k) => Map [k] v

，其中，如果列表需要比較下來到了深層次的查詢可能需要很長的時間。由於列表的任意長度，我猜哈希也不存在。我仍然不禁想到，那裏可能會有一個聰明的數據結構。

來源

2011-04-12 gspr

我懷疑使用矢量（矢量包）而不是列表作爲關鍵將是一個巨大的勝利，爲此目的。 – 2011-04-12 16:45:38

哈希出了問題嗎？沒有可以有效計算的關鍵結構的前綴？

如果不是，散列表怎麼樣？採用非常大的密鑰，將其減小到非常小的值，並將其用作結構的索引。

hashmap on Hackage。
Johan Tibbel's talk on hash tree structures

來源

2011-04-12 16:44:19

啊，你是對的。我想我是在錯誤地考慮任意大數據的散列衝突。謝謝。 – gspr 2011-04-13 07:24:25

特里樹？

如果你有兩個幾乎相同的長鍵，一個Map會從頭開始比較它們，但是一個trie只會比較以前比較還沒有消除的後綴（如果你明白我的意思）。因此，在這種情況下，系統會更節省時間。

嘗試可以通過各種方式進行優化，並且您可能還想要查看三元樹。

來源

2011-04-12 17:17:51

這裏有一個：

module ListMap where 
import Data.Map as M 

data ListMap k v = ListMap { ifEmpty :: Maybe v, ifFull :: Maybe k (ListMap k v) } 

empty :: ListMap k v 
empty = ListMap Nothing M.empty 

singleton :: [k] -> v -> ListMap k v 
singleton [] v = ListMap.empty { ifEmpty = Just v } 
singleton (k:ks) v = ListMap.empty { ifFull = M.singleton k (ListMap.singleton ks v) } 

lookup :: Ord k => [k] -> ListMap k v -> Maybe v 
lookup [] lm = ifEmpty lm 
lookup (k:ks) lm = M.lookup k (ifFull lm) >>= ListMap.lookup ks 

insert :: Ord k => [k] -> v -> ListMap k v -> ListMap k v 
insert [] v lm = lm { ifEmpty = Just v } 
insert (k:ks) v lm = lm { ifFull = M.alter (Just . insertion) k (ifFull lm) } 
    where insertion = maybe (ListMap.singleton ks v) (ListMap.insert ks v)

它本質上創建的列表元素前綴樹，所以你只需要比較遠。

來源

2011-04-12 17:43:42 rampion

具有任意長度數據作爲鍵的功能性地圖數據結構？

回答

相關問題