5

是否有等效于 NumPyargsort函数的标准 Haskell？

我正在使用HMatrix，因此，想要一个与之兼容的函数，Vector R它是Data.Vector.Storable.Vector Double. 下面的argSort函数是我目前正在使用的实现：

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

我使用显式限定import的 s 只是为了清楚每种类型和函数的来源。

这种实现并不是非常有效，因为它将输入向量转换为列表，并将结果转换回向量。这样的东西（但更有效）是否存在于某处？

更新

@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

这更直接可用，Numeric.LinearAlgebra因为数据向量是 a Storable。这对索引使用未装箱的向量。

4

2 回答 2

5

使用向量算法：

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可以往返于可存储的向量。

于 2016-11-13T20:06:46.963 回答
0

对我来说更好的方法是使用 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

但是，这仅适用于定期列表，例如：

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]
于 2017-11-23T11:39:16.020 回答