排序Data.Map並得到所有最大的價值

我有Data.Map，看起來像這樣：排序Data.Map並得到所有最大的價值

fromList [("eso",1),("mes",1),("ome",2),("som",2)]

我需要從這個地圖，值是最大的獲取密鑰的列表：

["ome","som"]

這裏是我的解決方案：

get_max_from_map m = map fst (filter is_biggest sorted) 
    where sorted = List.sortBy (\(k1, v1) (k2, v2) -> v2 `compare` v1) $ Map.toList m 
      max_v = snd $ head sorted 
      is_biggest (key, value) = value == max_v

我轉換地圖列出，對它們進行排序，得到第一值最大和篩選器列表。

我只是想知道是否有更優化和美麗的解決方案這項任務？

謝謝。

來源

2013-11-01 demas

如果沒有理由進行快速查找，則可能需要考慮使用堆而不是地圖。有了堆，最大的元素總是最頂層的元素，因此很容易訪問。 – kqr

這不比什麼是你原來的職位的任何簡單，但它的是一個線性時間，一個通解決方案的優勢（您版本是O（n日誌n），因爲它對列表進行排序，至今發佈的其他答案都是雙通解決方案）。

getMaxFromMap m = go [] Nothing (Map.toList m) 
    where 
    go ks _  []   = ks 
    go ks Nothing ((k,v):rest) = go (k:ks) (Just v) rest 
    go ks (Just u) ((k,v):rest) 
     | v < u  = go ks  (Just u) rest 
     | v > u  = go [k] (Just v) rest 
     | otherwise = go (k:ks) (Just v) rest

來源

2013-11-01 09:32:13

您可以使用Data.Map中的函數在Maybe monad中處理此問題。

編輯：這是一個使用lens導入的工作版本。

import Control.Lens 
import Data.Map (Map) 
import qualified Data.Map as Map 

getYourKeys :: Eq a => Map k a -> Maybe [k] 
getYourKeys m = do 
    maxValue <- maximumOf traverse m 
    return . Map.keys . Map.filter (== maxValue) $ m

來源

2013-11-01 09:10:47 jtobin

錯誤，這實際上是不正確的，只是恰好適用於您的特定用例。 'Map.maxView'在鍵上工作，而不是值。我會在一兩分鐘內修復/刪除它。（更新：固定） – jtobin

你需要做2個任務 - 找到最大，過濾

get_max_from_lst xs = map fst $ filter ((== m) . snd) xs 
    where m = maximum $ map snd xs

這是清單。

如果我們有地圖的話：

import Data.Map.Lazy as M 

get_max_from_map xs = M.keys $ M.filter (== m) xs 
    where m = maximum $ M.elems xs

來源

2013-11-01 09:12:48 viorior

我想你需要首先將參數轉換爲列表。 –

@ChrisTaylor，謝謝！也爲Map完成 – viorior

排序Data.Map並得到所有最大的價值

回答

相關問題