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]

可以假设第一个参数已排序，但第二个参数不会排序。

ifn是要搜索的所有列表中的项目总数（在这种特殊情况下为 7，因为一旦找到一个项目，搜索就会停止）并且k是要搜索的项目数，我相信这个函数的运行时间将是O(n * k). 然而，这对大k时n是不利的。

如果可能的话，我希望运行时更像O(n * log k) + O(k * log k)或更好。最好的方法是什么？

Answer 1

粘贴items在 a 中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 xs将需要O(k log k)一次，每个find都将O(log k)在最坏的情况下进行。因此，n 个元素的总时间 =O(n log k) + O(k log k)最坏情况。