高效的Haskell相当于NumPy的argsort [英] Efficient Haskell equivalent to NumPy's argsort

问题描述

是否有与NumPy相同的标准Haskell argsort 函数？

我正在使用 HMatrix ，所以需要一个兼容 Vector R 的函数，它是<$ c的别名$ c> Data.Vector.Storable.Vector Double 。下面的 argSort 函数是我目前使用的实现：

  { - ＃LANGUAGE NoImplicitPrelude＃ - } 
 
模块Main其中
 
将限定的Data.List导入为L 
将限定的Data.Vector导入为V 
导入（$，Double，IO，Int，compare，print，snd）
 $ b :: 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  -  yield [2,3,1,0] 
  

我使用显式限定 import s来制作它清楚每个类型和函数来自哪里。

这个实现并不是非常高效，因为它将输入向量转换为列表并将结果转换回向量。是否有这样的（但更高效的）存在的地方？

更新

@leftaroundabout有一个很好的解决方案。这是我最终得到的解决方案：

  module LAUtil.Sorting 
（IndexVector 
，argSort 
）
其中
 
导入Control.Monad 
导入Control.Monad.ST 
导入Data.Ord 
导入限定的Data.Vector.Algorithms .Intro as VAI 
将合格的Data.Vector.Storable导入为VS 
将合格的Data.Vector.Unboxed导入为VU 
将合格的Data.Vector.Unboxed.Mutable导入为VUM 
 import Numeric.Linear代数
 
类型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（比较snd）t0 
 t1 < -  VUM.new l 
 forM_ [0..l -  1] $ 
 \i  - > VUM.unsafeRead t0 i>> = \（x，_） - > VUM.unsafeWrite t1 ix 
 VU.freeze t1 
  

这可以直接用于 Numeric.LinearAlgebra ，因为数据向量是 Storable 。这为索引使用了unboxed向量。

解决方案

使用 vector-algorithms ：


$ b

 导入Data.Ord（比较）
 
将合格的Data.Vector.Unboxed导入为VU 
将合格的Data.Vector.Algorithms.Intro导入为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（比较snd）xsi 
 return xsi 
  

注意这些是 Unboxed 而不是可存储向量。后者需要做一些折衷以允许不纯净的C FFI操作，并且不能正确处理异构元组。您当然可以始终 convert 到可存储向量中。

Is there a standard Haskell equivalent to NumPy's argsort function?

I'm using HMatrix and, so, would like a function compatible with Vector R which is an alias for Data.Vector.Storable.Vector Double. The argSort function below is the implementation I'm currently using:

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

I'm using explicit qualified imports just to make it clear where every type and function is coming from.

This implementation is not terribly efficient since it converts the input vector to a list and the result back to a vector. Does something like this (but more efficient) exist somewhere?

Update

@leftaroundabout had a good solution. This is the solution I ended up with:

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

This is more directly usable with Numeric.LinearAlgebra since the data vector is a Storable. This uses an unboxed vector for the indices.

解决方案

Use 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

Note these are Unboxed rather than Storable vectors. The latter need to make some tradeoffs to allow impure C FFI operations and can't properly handle heterogeneous tuples. You can of course always convert to and from storable vectors.

这篇关于高效的Haskell相当于NumPy的argsort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！