2016-06-07 44 views
2

假設我有兩個向量:如何根據haskell中另一個向量的排序順序重新排序向量值?

let x = V.fromList ["foo", "bar", "baz"] 
    let y = V.fromList [1,3,2] 

我想定義一個矢量y'這是y排序的版本,但我也希望這是基於y排序順序(有序定義的重新排序x'x'應該看起來像["foo", "baz", "bar"])。

這樣做的最佳功能是什麼?理想情況下,我想避免從頭開始編寫排序功能。

+0

'V.fromList $ sortOn SND(V.toList(V.zip XY))' – pdexter

+1

@pdexter,不會使用來自'矢量algorithms'排序與'Data.Vector.Modify'一起比轉換爲列表,排序和轉換回來還快? – dfeuer

+0

@dfeuer,是的,最有可能的 – pdexter

回答

3

下面是一個基於列表的方式:

> import Data.List 
> let x = ["foo", "bar", "baz"] 
> let y = [1,3,2] 
> map snd . sort $ zip y x 
["foo","baz","bar"] 

基本上,我們拉鍊所以獲得我們對它進行排序對

[(1,"foo"),(3,"bar"),(2,"baz")] 

然後列表,字典順序,從而使第一部分更重要。

最後,我們丟棄第一個組件。

你應該能夠適應這個向量。

+0

是否有Data.List(排序)的前往式替代?大多數矢量分類功能似乎是針對可變/盒裝變體的。 – daj

5

我想你正在尋找backpermute

backpermute :: Vector a -> Vector Int -> Vector a 

O(n)的產率通過xs!i替換索引向量中的每個元素i獲得的矢量。這相當於map (xs!)是但通常效率更高。

1

排序向量索引比較索引值;然後permute這兩個向量基於排序的索引。 Data.Vector.Algorithms.Intro提供 introsort爲可變載體和modify提供安全破壞性更新使用ST Monad

import Data.Ord (comparing) 
import Data.Vector.Algorithms.Intro (sortBy) 
import Data.Vector.Unboxed (generate, modify) 
import Data.Vector (Vector, unsafeIndex, backpermute, convert, fromList) 
import qualified Data.Vector as V 

reorder :: (Ord b) => Vector a -> Vector b -> (Vector a, Vector b) 
reorder a b = (backpermute a idx, backpermute b idx) 
    where 
    idx = convert $ modify (sortBy comp) init 
    comp = comparing $ unsafeIndex b -- comparing function 
    init = generate (V.length b) id -- [0..size - 1] 

然後,

\> reorder (fromList ["foo", "bar", "baz"]) $ fromList [1, 3, 2] 
(["foo","baz","bar"],[1,2,3])