Geek asks and answers

Faster `elem` Using binary search in Haskell

I have a list of Texts and they are in sorted order. It seems to me that I can write a much faster version elemby implementing it as a binary search instead of a linear search. Is there such a version already?

+3
source share
3 answers

Haskell lists are implemented as linked lists, which means that access to an arbitrary i-th element is in O(i). In normal mode, the binary search version elemfor lists will take longer than the standard version (see @DanielFischer Note below).

You might want to use another container, for example, Data.Set or Data.Map , which are implemented as a balanced binary tree that gives you O(log n)access time (where nis the number of elements in the map / set).

+12
source

Binary search requires random access. Since the haskell list does not provide random access (accessing an element in the middle takes linear time), a binary search would not help.

If your data was in Arraythat provides random access, a binary search will be doable.

+6
source

, .

, ( ).

Haskell, ( , ).

If you use, for example, a heap or a tree to store your text, you can implement O (log (n)) elem trivially. You can take advantage of the fact that they are sorted for faster insertion.

+1
source

More articles:


All Articles