Эффективно найти индексы максимумов списка

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-крупнейших на данный момент.

Такое ощущение, что должен быть более эффективный способ, чем сделать это, и я также чувствую, что недостаточно использую Prelude и 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' оценивает только нормальную форму со слабой головой, то есть для самого внешнего конструктора, и, таким образом, вы создаете блоки в компонентах кортежа.

Answer 2

Это решение связывает каждый элемент с его индексом, сортирует список, так что наименьший элемент является первым, переворачивает его так, чтобы наибольший элемент был первым, берет первые n элементов и затем извлекает индекс.

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

Answer 3

Ну, простым способом было бы использовать maximum, чтобы найти самый большой элемент, а затем использовать findIndices, чтобы найти каждое его вхождение. Что-то вроде:

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

Однако, это не идеально, потому что maximum является частичной функцией и будет ужасно раздражать, если ей дан пустой список. Вы можете легко избежать этого, добавив [] чехол:

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

Настоящий трюк с этим ответом заключается в том, как я понял это. Я даже не знал о findIndices до сих пор! Однако GHCi имеет аккуратную команду под названием :browse.

Prelude> :browse Data.List

Здесь перечислены все функции, экспортируемые с помощью Data.List. Используя это, я просто ищу сначала maximum, а затем index, чтобы увидеть, какие были варианты. И прямо к findIndex было findIndecies, что было идеально.

Наконец, я не стал бы беспокоиться об эффективности, если вы на самом деле не видите, что код работает медленно. GHC может - и выполняет - некоторые очень агрессивные оптимизации, потому что язык чистый, и он может сойти с рук. Поэтому единственное время, когда вам нужно беспокоиться о производительности, это когда - после компиляции с -O2 - вы видите, что это проблема.

РЕДАКТИРОВАТЬ: Если вы хотите найти индексы n верхних элементов, вот простая идея: отсортируйте список по убыванию, возьмите первые n уникальные элементы, получите их индексы с помощью elemIndices и возьмите первые n индексы из этого. Я надеюсь, что это относительно ясно.

Вот краткая версия моей идеи:

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