4

以下の関数searchは、ある関数で同じ出力を持つ 2 つの入力を検索します。検索中、入力リストxsを 2 回反復します。この入力リストは非常に大きくなる可能性があります[0..1000000000]。の要素を保存するのではなく、衝突によって作成された HashSet を保存するためにメモリを使用したいとxs思いxsますfind。

質問:

  • この理解は正しいですか？
  • それをリストとして保持xsする場合、それが渡された場合に再計算できる方法はありfindますか?
  • xs使用するスペースを制御できる代替データ構造はありますか? xsチェックする入力を指定するためにのみ使用されます。

型の制限がないことに注意してくださいxs。任意の型のコレクションにすることができます。

import Data.HashSet as Set
import Data.Hashable
import Data.List

search :: (Hashable b, Eq b) => (a->b) -> [a] -> Maybe (a,a)
search h xs =
  do x0 <- collision h xs
     let h0 = h x0
     x1 <- find (\x -> (h x) == h0) xs
     return (x0,x1)

collision :: (Hashable b, Eq b) => (a->b) -> [a] -> Maybe a
collision h xs = go Set.empty xs
  where
    go s [] = Nothing
    go s (x:xs) =
      if y `Set.member` s
        then Just x
        else go (Set.insert y s) xs
      where y = h x

main = print $ search (\x -> x `mod` 21)  ([10,20..2100] :: [Int])
4

1 に答える 1

6

私は基本的にここでこの質問に答えました: https://stackoverflow.com/a/6209279/371753

関連するコードは次のとおりです。

import Data.Stream.Branching(Stream(..))
import qualified Data.Stream.Branching as S
import Control.Arrow
import Control.Applicative
import Data.List

data UM s a = UM (s -> Maybe a) deriving Functor
type UStream s a = Stream (UM s) a

runUM s (UM f) = f s
liftUM x = UM $ const (Just x)
nullUM = UM $ const Nothing

buildUStream :: Int -> Int -> Stream (UM ()) Int
buildUStream start end = S.unfold (\x -> (x, go x)) start
    where go x
           | x < end = liftUM (x + 1)
           | otherwise = nullUM

usToList x = unfoldr (\um -> (S.head &&& S.tail) <$> runUM () um) x

簡単に言うと、リストを渡す代わりに、リストの生成方法を説明するデータ型を渡します。usToListこれで、ストリーム上に直接関数を記述したり、関数を使用して既に持っているリスト関数を使用したりできます。

于 2012-06-06T18:45:17.167 に答える