你如何做一个在Haskell就地快速排序 [英] How do you do an in-place quicksort in Haskell

问题描述

有人可以提供一个就地quicksort haskell函数吗？即它返回一个新的排序列表，但输入列表被复制到一个可变数组或其他东西。

我想看看如何做到这一点，因为我有一个关键性能程序，我需要模拟比赛和理货比分。如果我为此使用了不可变数据结构，每次竞赛都会花费O（log（numRaces）+ numRunners）时间，而如果我使用可变数组等，每次竞赛都会花费O（log（numRaces））时间。 b
$ b

哦，顺便说一下，我实际上并不需要做快速排序，我只是想要一个例子来看看如何有效地使用可变数组。

解决方案

这是一个版本，只是为了证明您可以将维基百科中的代码几乎完全转换为Haskell;）

  import Control.Monad.ST 
 import Data.Array.ST 
 import Data.Foldable 
 import Control.Monad 
 
  - 维基复制代码从这里开始
 partition arr left right pivotIndex = do 
 pivotValue<  -  readArray arr pivotIndex 
 swap arr pivotIndex right 
 storeIndex<  -  foreachWith [left..right-1] left（\i storeIndex  - > do 
 val<  -  readArray arr i 
 if（val< = pivotValue）
然后执行
交换arr i storeIndex 
 return（storeIndex + 1）
 else do 
 return storeIndex）
 swap arr storeIndex right 
 return storeIndex 
 
 qsort arr left right = when（right>左）$ do 
让pivotIndex = left +（（right-left）`div` 2）
 newPivot<  -  partition arr left right pivotIndex 
 
 qsort arr left（newPivot -  1）
 qsort arr（newPivot + 1）right 
 
  - 将列表排序为数组
 sortList xs = runST $ do 
 let lastIndex =长度xs  -  1 
 arr<  -  newListArray（0，lastIndex）xs :: ST s（STUArray s Int Int）
 qsort arr 0 lastIndex 
 newXs<  -  getElems arr 
返回newXs 
 
  - 测试示例
 main = print $ sortList [212498,127,5981,2749812,74879,126,4,51,2412] 
 
  - 帮助者
交换arr左边的右边=做
 leftVal<  -  readArray arr左边
 rightVal<  -  readArray arr右边
 writeArray arr左边右边
 writeArray arr right leftVal 
 
  -  foreachWith获取一个列表和一个可以被该函数修改的值，
  - 它将函数映射到列表后返回修改后的值。 
 foreachWith xs v f = foldlM（flip f）v xs 
  

Could somebody provide an in-place quicksort haskell function? I.e. it returns a new sorted list, but the input list is copied to a mutable array or something.

I want to see how to do this, because I have a performance critical program where i need to simulate races and tally scores. If I use immutable data structures for this, each race will take O(log(numRaces) + numRunners) time, whereas if I use mutable arrays etc, each race will take O(log(numRaces)) time.

oh by the way i didn't actually need to do quicksort, i just wanted an example to see how to use mutable arrays effectively

解决方案

Here's a version, just to prove you can convert code from Wikipedia almost exactly into Haskell ;)

import Control.Monad.ST
import Data.Array.ST
import Data.Foldable
import Control.Monad

-- wiki-copied code starts here
partition arr left right pivotIndex = do
    pivotValue <- readArray arr pivotIndex
    swap arr pivotIndex right
    storeIndex <- foreachWith [left..right-1] left (\i storeIndex -> do
        val <- readArray arr i
        if (val <= pivotValue)
            then do
                 swap arr i storeIndex
                 return (storeIndex + 1)
            else do
                 return storeIndex )
    swap arr storeIndex right
    return storeIndex

qsort arr left right = when (right > left) $ do
    let pivotIndex = left + ((right-left) `div` 2)
    newPivot <- partition arr left right pivotIndex

    qsort arr left (newPivot - 1)
    qsort arr (newPivot + 1) right

-- wrapper to sort a list as an array
sortList xs = runST $ do
    let lastIndex = length xs - 1
    arr <- newListArray (0,lastIndex) xs :: ST s (STUArray s Int Int)
    qsort arr 0 lastIndex
    newXs <- getElems arr
    return newXs

-- test example
main = print $ sortList [212498,127,5981,2749812,74879,126,4,51,2412]

-- helpers
swap arr left right = do
    leftVal <- readArray arr left
    rightVal <- readArray arr right
    writeArray arr left rightVal
    writeArray arr right leftVal

-- foreachWith takes a list, and a value that can be modified by the function, and
-- it returns the modified value after mapping the function over the list.  
foreachWith xs v f = foldlM (flip f) v xs

这篇关于你如何做一个在Haskell就地快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！