Effiziente Haskell-Entsprechung zu NumPys argsort

Question

Gibt es eine Standard-Haskell-Entsprechung zu NumPys argsort-Funktion?

Ich verwende HMatrix und möchte daher eine Funktion kompatibel mit Vector R, die ein Alias ​​für Data.Vector.Storable.Vector Double ist. Die argSort Funktion unten ist die Implementierung ich zur Zeit mit:

{-# LANGUAGE NoImplicitPrelude #-} 

module Main where 

import qualified Data.List as L 
import qualified Data.Vector as V 
import qualified Data.Vector.Storable as VS 
import   Prelude (($), Double, IO, Int, compare, print, snd) 

a :: VS.Vector Double 
a = VS.fromList [40.0, 20.0, 10.0, 11.0] 

argSort :: VS.Vector Double -> V.Vector Int 
argSort xs = V.fromList (L.map snd $ L.sortBy (\(x0, _) (x1, _) -> compare x0 x1) (L.zip (VS.toList xs) [0..])) 

main :: IO() 
main = print $ argSort a -- yields [2,3,1,0] 

ich es klar, nur explizit qualifizierten import s bin mit machen, wo jede Art und Funktion herkommt.

Diese Implementierung ist nicht besonders effizient, da sie den Eingabevektor in eine Liste und das Ergebnis zurück in einen Vektor konvertiert. Gibt es irgendwo etwas (aber effizienter)?

aktualisieren

@leftaroundabout hatte eine gute Lösung. Dies ist die Lösung, die ich am Ende mit:

module LAUtil.Sorting 
    (IndexVector 
    , argSort 
) 
    where 

import   Control.Monad 
import   Control.Monad.ST 
import   Data.Ord 
import qualified Data.Vector.Algorithms.Intro as VAI 
import qualified Data.Vector.Storable as VS 
import qualified Data.Vector.Unboxed as VU 
import qualified Data.Vector.Unboxed.Mutable as VUM 
import   Numeric.LinearAlgebra 

type IndexVector = VU.Vector Int 

argSort :: Vector R -> IndexVector 
argSort xs = runST $ do 
    let l = VS.length xs 
    t0 <- VUM.new l 
    forM_ [0..l - 1] $ 
     \i -> VUM.unsafeWrite t0 i (i, (VS.!) xs i) 
    VAI.sortBy (comparing snd) t0 
    t1 <- VUM.new l 
    forM_ [0..l - 1] $ 
     \i -> VUM.unsafeRead t0 i >>= \(x, _) -> VUM.unsafeWrite t1 i x 
    VU.freeze t1 

Das ist mehr direkt nutzbar mit Numeric.LinearAlgebra da der Datenvektor ist ein Storable. Dies verwendet einen ungepackten Vektor für die Indizes.

Answer 1

Verwendung vector-algorithms:

import Data.Ord (comparing) 

import qualified Data.Vector.Unboxed as VU 
import qualified Data.Vector.Algorithms.Intro as VAlgo 

argSort :: (Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int 
argSort xs = VU.map fst $ VU.create $ do 
    xsi <- VU.thaw $ VU.indexed xs 
    VAlgo.sortBy (comparing snd) xsi 
    return xsi 

Hinweis diese sind Unboxed statt Storable Vektoren. Letztere müssen einige Kompromisse eingehen, um unreine C-FFI-Operationen zuzulassen, und können nicht mit heterogenen Tupeln richtig umgehen. Sie können natürlich immer convert zu und von speicherbaren Vektoren.

Answer 2

Was für mich besser funktionierte, ist die Verwendung von Data.map, da es sich um eine Listenverschmelzung handelt. Hier n = Länge xs.

import Data.Map as M (toList, fromList, toAscList) 

    out :: Int -> [Double] -> [Int] 
    out n !xs = let !a= (M.toAscList (M.fromList $! (zip xs [0..n]))) 
        !res=a `seq` L.map snd a 
       in res 

Dies ist jedoch nur aplicable für periodische Listen, wie:

out 12 [1,2,3,4,1,2,3,4,1,2,3,4] == out 12 [1,2,3,4,1,3,2,4,1,2,3,4]