algorithm - リストのリストで高速検索

Question

次の関数を検討してください。

import Data.List (find)     
findInLists items = map $ find (`elem` items)

次の結果でそのように呼び出すことができます：

findInLists [2,3] [[1,2], [1,3,2], [4, -2, 8]] -> [Just 2, Just 3, Nothing]

最初の引数はソートされていると想定できますが、2 番目の引数はソートされません。

検索するすべてのリスト内nのアイテムの総数 (この特定のケースでは、アイテムが見つかると検索が停止するため、7) であり、 が検索するアイテムkの数である場合、この関数の実行時間は次のようになると思いますO(n * k). kしかし、これも大きいとダメですn。

O(n * log k) + O(k * log k)可能であれば、ランタイムをもっと似たものにしたいです。これを行う最善の方法は何ですか？

Answer 1

を貼り付けてitems使用Setしますmember。

Answer 2

import Data.Set (fromList,member)
import Data.List
findInLists :: Ord a => [a] -> [[a]] -> [Maybe a]
findInLists xs = map $ find $ flip member $ fromList xs

fromList xsO(k log k)1回かかり、最悪の場合はそれぞれにかかりますfind。O(log k)したがって、n 個の要素の合計時間 =O(n log k) + O(k log k)最悪の場合です。