CODEWITHSUNDEEP
listfunctionhaskell
Sir DK
Sir DK

Reputation: 179

Haskell :: Slower Function as List Getting Bigger

I'm working with finding a maximum value of a list (by using maximum) and I know that this function need to process the entire list to reach its goal and this obviously gets slower as the list gets bigger. Unfortunately, my list is huge (hundreds of million).

Is this the only way? Or there are faster ways to do this? I found that Haskell is fast but at this point (getting slower), I'm wondering is there any other option to find the maximum.

Upvotes: 2

Views: 135

Answers (2)

madnight
madnight

Reputation: 418

Since you need to "look" at each value and pick the highest O(n) is the best solution (without any other information that could be used). If you have to perform the function multiple times, then you might want to sort your list (ascending or descending) and use the function head or last, that have a time complexity of O(1), while haskells sort is a mergesort with O(n log n) worst-case and average-case performance.

Upvotes: 0

user8174234
user8174234

Reputation:

I know that this function need to process the entire list to reach its goal and this obviously gets slower as the list gets bigger.

Finding a maximum is O(n) in Haskell (and presumably every other language as well). Unless you have some concrete benchmarks and code this seems totally expected.

Upvotes: 1

Related Questions