假設我有兩個向量:如何根據haskell中另一個向量的排序順序重新排序向量值?
let x = V.fromList ["foo", "bar", "baz"]
let y = V.fromList [1,3,2]
我想定義一個矢量y'
這是y
排序的版本,但我也希望這是基於y
排序順序(有序定義的重新排序x'
x'
應該看起來像["foo", "baz", "bar"]
)。
這樣做的最佳功能是什麼?理想情況下,我想避免從頭開始編寫排序功能。
假設我有兩個向量:如何根據haskell中另一個向量的排序順序重新排序向量值?
let x = V.fromList ["foo", "bar", "baz"]
let y = V.fromList [1,3,2]
我想定義一個矢量y'
這是y
排序的版本,但我也希望這是基於y
排序順序(有序定義的重新排序x'
x'
應該看起來像["foo", "baz", "bar"]
)。
這樣做的最佳功能是什麼?理想情況下,我想避免從頭開始編寫排序功能。
下面是一個基於列表的方式:
> 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")]
然後列表,字典順序,從而使第一部分更重要。
最後,我們丟棄第一個組件。
你應該能夠適應這個向量。
是否有Data.List(排序)的前往式替代?大多數矢量分類功能似乎是針對可變/盒裝變體的。 – daj
我想你正在尋找backpermute
backpermute :: Vector a -> Vector Int -> Vector a
O(n)的產率通過
xs!i
替換索引向量中的每個元素i
獲得的矢量。這相當於map (xs!)
是但通常效率更高。
排序向量索引比較索引值;然後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])
'V.fromList $ sortOn SND(V.toList(V.zip XY))' – pdexter
@pdexter,不會使用來自'矢量algorithms'排序與'Data.Vector.Modify'一起比轉換爲列表,排序和轉換回來還快? – dfeuer
@dfeuer,是的,最有可能的 – pdexter