On 29.08.2012 10:19, Karl Voelker wrote:
Data.Map.lookup has better asymptotic time complexity than Prelude.lookup, but the relevant measures of efficiency depend on the situation.
On Wed, Aug 29, 2012 at 2:25 AM, Dmitry Vyal
Can you please elaborate a bit? I suspect lists better when there are just a few elements, but how much is a "few"?
I believe that Prelude.lookup looks through the list until it finds the thing you're looking for or exhausts the list [this is something like O(n)]. Data.Map performs a binary search over its tree [this is something like O(log n)]
And what's about storage efficiency? How big is (Data.Map.fromList [1])?
A map associates keys and values, so your example doesn't actually work. As for space efficiency, I'm sure that an association tree and an association list are simple enough that both grow linearly with the number of elements. Prelude> :m +Data.Map Prelude Data.Map> let x = fromList [("banana", ["yellow"]), ("apple", ["green", "red"]), ("tomato", ["red"])] Prelude Data.Map> x Prelude Data.Map> Data.Map.lookup "apple" x Just ["green","red"] Prelude Data.Map> Data.Map.lookup "fish" x Nothing