有效地找到列表的最大值索引

Question

编辑:我不能说得足够清楚,但我正在寻找一个类似下面的功能,但不完全是这样.

给定一个列表,我希望能够找到列表中最大元素的索引
(所以,list !! (indexOfMaximum list) == maximum list)
我写了一些看似非常有效的代码,虽然我觉得我正在重新发明轮子.

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

现在我想返回列表中最大n个数字的索引列表.

我唯一的解决方案是将前n个元素存储在列表中,并替换(head list') > highestVal为n个最大的列表中的比较.

感觉就像必须有一个更有效的办法,而不是这样做,我也觉得我利用不足和前奏的Data.List模块.有什么建议？

Answer 1

最短的方法找到最大元素的最后一个索引,

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

如果你想要第一个索引,

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

缺点是,maximum而且maximumBy太懒了,所以这些可能会构成大量的风暴.为了避免这种情况,要么使用手动递归(就像你做的那样,但可能需要一些严格的注释)或者使用严格的左侧折叠和严格的累加器类型,元组对此不利,因为foldl'只评估弱头正常形式,这里是最外层的构造函数,因此你在元组组件中构建thunk.

Answer 2

此解决方案将每个元素与其索引相关联,对列表进行排序,因此最小元素是第一个,反转它,因此最大元素是第一个,获取前n个元素,然后提取索引.

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