CODEWITHSUNDEEP
algorithmhaskell
Clinton
Clinton

Reputation: 23135

Fast find in list of lists

Consider the following function:

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

Which can be called like so with the following result:

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

The first argument can be assumed to be sorted, but the second argument will not be sorted.

If n is the total number of items in all lists to be searched (in this particular case, 7, as the search stops once an item is found) and k is the number of items to search for, I believe the runtime of this function will be O(n * k). However, this is bad for large k when n is also large.

I would like the runtime to be more like O(n * log k) + O(k * log k) or better if possible. What's the best way to do this?

Upvotes: 3

Views: 169

Answers (2)

Satvik
Satvik

Reputation: 11208

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 will take O(k log k) one time and each find will take O(log k) in worst case. So total time for n elements = O(n log k) + O(k log k) worst case.

Upvotes: 6

Daniel Wagner
Daniel Wagner

Reputation: 152947

Stick the items in a Set and use member.

Upvotes: 6

Related Questions