NumPyのargsortに相当する効率的なHaskell

Question

NumPyのargsort関数に相当する標準的なHaskellはありますか？

私はHMatrixを使用していますので、Data.Vector.Storable.Vector Doubleの別名であるVector Rと互換性のある機能を望みます。私はすべてのタイプと機能がどこから来ているだけで、それを明確にするために、明示的な資格import Sを使用してい

{-# 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] 

：以下argSort機能は、私が現在使用している実装です。

この実装は、入力ベクトルをリストに変換し、結果をベクトルに変換するため、非常に効率的ではありません。このような（より効率的な）何かがどこかに存在しますか？

更新

@leftaroundaboutは良い解決策を持っていました。これは私がなってしまったソリューションです：

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 

データベクトルがStorableあるので、これは、より直接的に使用可能Numeric.LinearAlgebraです。これは、インデックスにボックス化されていないベクトルを使用します。

Answer 1

使用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 

注これらはUnboxedいうよりStorableベクトルです。後者は、不純なC FFI操作を可能にするためにいくつかのトレードオフを行う必要があり、異種タプルを適切に処理できません。もちろん、保存可能なベクターとの間には、常にconvertを入れることができます。

Answer 2

リスト融合の対象となるData.mapを使用すると、速度が上がりました。ここでn =長さ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 

しかし、これはよう、定期的なリストのための唯一のaplicableです：

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]