7

一部のデータのフィッシャー・イェーツ・シャッフルを実装しようとしています。このアルゴリズムは、1 次元配列に対して簡単に実装できます。ただし、2 次元行列でデータをシャッフルできる必要があります。

高次元配列にうまく一般化できると思うアプローチは、任意の次元の行列をインデックスの 1 次元配列に変換し、それらをシャッフルしてから、このインデックス配列の各インデックスの要素を要素と交換して行列を再編成することです。インデックス配列の要素のインデックス。つまり、次のような 2x2 行列を取得するには:

1  2
3  4

これをこの「配列」に変換します。

[(0, (0,0)),  (1, (0,1)),  (2, ((1,0)),  (3, (1,1))]

これを通常どおりにスクランブルして、たとえば、

[(0, (1,0)),  (1, (0,1)),  (2, ((1,1)),  (3, (0,0))]

再編成すると、元のマトリックスは次のようになります。

2  3
4  1

ここでの私の基本的なアプローチは、次のような型クラスが必要だということです。

class Shufflable a where
  indices    :: a -> Array Int b
  reorganize :: a -> Array Int b -> a

次に、次のようなシャッフルを実行する関数を用意します。

fisherYates :: (RandomGen g) => g -> Array Int b -> (Array Int b, g)

考え方は、（RandomGen配管を除いて）シャッフル可能なものを次のようにシャッフルできるはずだということです：

shuffle :: (Shufflable a, RandomGen g) => a -> g -> (a, g)
shuffle array = reorganize array (fisherYates (indices array))

これが私がこれまでに持っているものです：

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances  #-}

module Shuffle where

import Data.Array hiding (indices)
import System.Random         

fisherYates :: (RandomGen g) => Array Int e -> g -> (Array Int e, g)
fisherYates arr gen = go max gen arr
    where
      (_, max) = bounds arr

      go 0 g arr = (arr, g)
      go i g arr = go (i-1) g' (swap arr i j)
          where
            (j, g') = randomR (0, i) g

class Shuffle a b | a -> b where
  indices    :: a -> Array Int b
  reorganize :: a -> Array Int b -> a

shuffle :: (Shuffle a b, RandomGen g) => a -> g -> (a, g)
shuffle a gen = (reorganize a indexes, gen')
  where
    (indexes, gen') = fisherYates (indices a) gen

instance (Ix ix) => Shuffle (Array ix e) ix where
  reorganize a = undefined
  indices a    = array (0, maxIdx) (zip [0..maxIdx] (range bound))
      where
        bound = bounds a
        maxIdx = rangeSize bound - 1

swap :: Ix i => Array i e -> i -> i -> Array i e
swap arr i j = arr // [ (i, i'), (j, j') ]
    where
      i' = arr!j
      j' = arr!i

私の問題:

  1. これは、単純な問題を解決するための言語拡張が多いように感じます。別の書き方や書き方が分かりやすいでしょうか？
  2. コミュニティは、関数の依存関係よりも型ファミリーに移行しているように感じます。この問題を解決する代わりにそれを使用する方法はありますか?
  3. 私の一部は、fisherYates関数を何らかの形で型クラスに移動できるかどうか疑問にShuffle思っています。と の両方を実装shuffleまたは実装するように、これを設定することは可能ですか、または行う価値がありますか?indicesreorganize

ありがとう！

4

1 に答える 1

5

n次元配列を提供するrepaを調べて、その形状(次元) を型にエンコードすることをお勧めします。それを使用して、任意の形状の配列で機能する一般的な操作をコーディングできます。

backpermuteorを使用して配列を構築し、インデックスを変換することで、型クラスを完全に回避できると思いますfromFunction（強制するとボックス化されていない配列に変換されるため、見た目よりも効率的です。実際には、ボンネットbackpermuteの下で実装されていますfromFunction）。

repa 自体はかなりの数の言語拡張機能を使用しますが、パフォーマンス (repa の配列はボックス化されておらず、提供される標準操作は自動並列化などの優れた機能を提供します) と利便性 (IMO repa には標準の配列よりも優れた API)。

これは repaの良い紹介です。

確かに、これはコードを直接単純化するものではありません。しかし、repa の配列が適切である場合、最終的に得られるコードは、おそらく現在のソリューションの複雑さの多くを回避するでしょう。

とはいえ、機能依存関係の使用を型ファミリーに変えるのは非常に簡単です。Shuffleクラスは

class Shuffle a where
  type Elt a
  indices    :: a -> Array Int (Elt a)
  reorganize :: a -> Array Int (Elt a) -> a

インスタンスは

instance (Ix ix) => Shuffle (Array ix e) where
  type Elt (Array ix e) = ix
  ...

となり、Shuffle a b制約は になりShuffle aます。

于 2011-12-22T00:26:02.570 に答える