8

リストを取り、存在する場合は一意の要素を返し、存在しない場合は [] を返す関数が必要です。一意の要素が多数存在する場合は、最初の要素を返す必要があります (他の要素を見つけるために時間を無駄にすることはありません)。さらに、リスト内のすべての要素が (小さくて既知の) セット A に由来することを知っています。たとえば、この関数は Ints の仕事をします:

unique :: Ord a => [a] -> [a]
unique li = first $ filter ((==1).length) ((group.sort) li)
    where first [] = []
          first (x:xs) = x

ghci> unique [3,5,6,8,3,9,3,5,6,9,3,5,6,9,1,5,6,8,9,5,6,8,9]
ghci> [1]

ただし、これは線形時間で実行できますが (A が小さいため)、並べ替え (n log n) を伴うため、十分ではありません。さらに、リスト要素のタイプが Ord である必要がありますが、必要なのは式 (1) だけです。比較の量ができるだけ少ない場合もいいでしょう (つまり、リストをトラバースして要素 el に 2 回遭遇した場合、後続の要素が el と等しいかどうかをテストしません)。

これが、たとえば次の理由です。リスト内の一意の要素を数えても問題は解決しません。すべての回答には、リスト全体をソートまたはトラバースして、すべての要素の数を見つけることが含まれます。

問題は、Haskell で正しく効率的に行う方法です。

4

6 に答える 6

6

だけでこれを効率的に行う方法は本当にありませんEq。等しい要素のグループを構築するには、はるかに効率の悪い方法を使用する必要があり、リスト全体をスキャンしないと、特定の要素の 1 つだけが存在することを知ることはできません。

また、無駄な比較を避けるために、要素が以前に遭遇したかどうかを確認する方法が必要になることに注意してください。これを行う唯一の方法は、複数の出現があることが知られている要素のリストを持つことです。現在の要素がそのリストにあるかどうかを確認する方法は...それぞれと等しいかどうかを比較することです。

これを O (本当に恐ろしいもの) よりも速く動作させたい場合は、そのOrd制約が必要です。

わかりました、コメントの説明に基づいて、ここにあなたが探していると思うものの簡単で汚い例があります:

unique [] _ _ = Nothing
unique _ [] [] = Nothing
unique _ (r:_) [] = Just r
unique candidates results (x:xs)
    | x `notElem` candidates = unique candidates results xs
    | x `elem` results       = unique (delete x candidates) (delete x results) xs
    | otherwise              = unique candidates (x:results) xs

最初の引数は候補のリストで、最初は可能なすべての要素である必要があります。2 番目の引数は可能な結果のリストで、最初は空である必要があります。3 番目の引数は、調べるリストです。

候補がなくなるか、リストの最後に到達しても結果がない場合は、 を返しますNothing。結果がリストの最後に到達すると、結果リストの先頭にあるものを返します。

それ以外の場合は、次の入力要素を調べます。候補でない場合は、無視して続行します。結果リストにある場合は、2 回見たことがあるので、結果リストと候補リストから削除して続行します。それ以外の場合は、結果に追加して続行します。

残念ながら、結果が実際に一意であることを確認する唯一の方法であるため、1 つの結果でもリスト全体をスキャンする必要があります。

于 2013-04-17T22:42:30.780 に答える
2

他の人が言ったように、追加の制約がなければ、要素について何かを知らなければ、それらを合理的なデータ構造に保つことができないため、これを二次時間未満で行うことはできません。

要素を比較できる場合、最初に要素の数を計算し、次に数が 1 に等しい最初の要素を見つけるという明白なO(n log n)ソリューション:

import Data.List (foldl', find)
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe (fromMaybe)

count :: (Ord a) => Map a Int -> a -> Int
count m x = fromMaybe 0 $ Map.lookup x m

add :: (Ord a) => Map a Int -> a -> Map a Int
add m x = Map.insertWith (+) x 1 m

uniq :: (Ord a) => [a] -> Maybe a
uniq xs = find (\x -> count cs x == 1) xs
  where
    cs = foldl' add Map.empty xs

log nMap係数は、サイズnの a を操作する必要があるという事実に由来することに注意してください。リストにk 個の一意の要素しかない場合、マップのサイズは最大でkになるため、全体的な複雑さはO(n log k)になります。

しかし、もっとうまくやることができます -マップの代わりにハッシュ テーブルを使用して、 O(n)ソリューションを取得できます。このためには、STモナドがハッシュマップ上で変更可能な操作を実行する必要があり、要素はHashableでなければなりません。ST解決策は基本的に以前と同じですが、モナド内で作業するために少しだけ複雑です:

import Control.Monad
import Control.Monad.ST
import Data.Hashable
import qualified Data.HashTable.ST.Basic as HT
import Data.Maybe (fromMaybe)

count :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s Int
count ht x = liftM (fromMaybe 0) (HT.lookup ht x)

add :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s ()
add ht x = count ht x >>= HT.insert ht x . (+ 1)

uniq :: (Eq a, Hashable a) => [a] -> Maybe a
uniq xs = runST $ do
    -- Count all elements into a hash table:
    ht <- HT.newSized (length xs)
    forM_ xs (add ht)
    -- Find the first one with count 1
    first (\x -> liftM (== 1) (count ht x)) xs


-- Monadic variant of find which exists once an element is found.
first :: (Monad m) => (a -> m Bool) -> [a] -> m (Maybe a)
first p = f
  where
    f []        = return Nothing
    f (x:xs')   = do
        b <- p x
        if b then return (Just x)
             else f xs'

ノート：

  • リストに少数の異なる要素しかないことがわかっている場合は、HT.new代わりに を使用できますHT.newSized (length xs)。これにより、メモリと 1 回のパス オーバーが節約されますxsが、多くの異なる要素の場合、ハッシュ テーブルのサイズを数回変更する必要があります。
于 2013-04-18T07:52:02.260 に答える