CODEWITHSUNDEEP
listhaskellfunctional-programming
amindfv
amindfv

Reputation: 8448

Efficiently find indices of maxima of a list

Edit: I must not have worded it clearly enough, but I'm looking for a function like the one below, but not exactly it.

Given a list, I wanted to be able to find the index of the largest element in the list
(So, list !! (indexOfMaximum list) == maximum list)
I wrote some code that seems pretty efficient, although I feel I'm reinventing the wheel somewhere. 

indexOfMaximum :: (Ord n, Num n) => [n] -> Int
indexOfMaximum list =
   let indexOfMaximum' :: (Ord n, Num n) => [n] -> Int -> n -> Int -> Int
       indexOfMaximum' list' currIndex highestVal highestIndex
          | null list'                = highestIndex
          | (head list') > highestVal = 
               indexOfMaximum' (tail list') (1 + currIndex) (head list') currIndex
          | otherwise                 = 
               indexOfMaximum' (tail list') (1 + currIndex) highestVal highestIndex
   in indexOfMaximum' list 0 0 0

Now I want to return a list of the indices of the largest n numbers in the list.

My only solution is to store the top n elements in a list and replace (head list') > highestVal with a comparison across the n-largest-so-far list.

It feels like there has to be a more efficient way than to do this, and I also feel I'm making insufficient use of Prelude and Data.List. Any suggestions?

Upvotes: 1

Views: 3306

Answers (3)

pat
pat

Reputation: 12749

This solution associates each element with its index, sorts the list, so the smallest element is first, reverses it so the largest element is first, takes the first n elements, and then extracts the index.

maxn n xs = map snd . take n . reverse . sort $ zip xs [0..]

Upvotes: 5

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

Well, a simple way would be to use maximum to find the largest element and then use findIndices to find each occurrence of it. Something like:

largestIndices :: Ord a => [a] -> [Int]
largestIndices ls = findIndices (== maximum ls) ls

However, this is not perfect because maximum is a partial function and will barf horribly if given an empty list. You can easily avoid this by adding a [] case:

largestIndices :: Ord a => [a] -> [Int]
largestIndices [] = []
largestIndices ls = findIndices (== maximum ls) ls

The real trick to this answer is how I figured it out. I didn't even know about findIndices before now! However, GHCi has a neat command called :browse.

Prelude> :browse Data.List

This lists every single function exported by Data.List. Using this, I just search first for maximum and then for index to see what the options were. And, right by findIndex, there was findIndecies, which was perfect.

Finally, I would not worry about efficiency unless you actually see that code is running slowly. GHC can--and does--perform some very aggressive optimizations because the language is pure and it can get away with it. So the only time you need to worry about performance is when--after compiling with -O2--you see that it's a problem.

EDIT: If you want to find the n top elements' indices, here's an easy idea: sort the list in descending order, grab the first n unique elements, get their indices with elemIndices and take the first n indices from that. I hope this is relatively clear.

Here's a quick version of my idea:

nLargestInices n ls = take n $ concatMap (`elemIndices` ls) nums
  where nums = take n . reverse . nub $ sort ls

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183888

The shortest way finds the last index of a maximum element,

maxIndex list = snd . maximum $ zip list [0 .. ]

If you want the first index,

maxIndex list = snd . maximumBy cmp $ zip list [0 .. ]
  where
    cmp (v,i) (w,j) = case compare v w of
                        EQ -> compare j i
                        ne -> ne

The downside is that maximum and maximumBy are too lazy, so these may build large thunks. To avoid that, either use a manual recursion (like you did, but some strictness annotations may be necessary) or use a strict left fold with a strict accumulator type, tuples are not good for that because foldl' only evaluates to weak head normal form, that is to the outermost constructor here, and thus you build thunks in the tuple components.

Upvotes: 5

Related Questions