80

パフォーマンスをRと比較するJuliaの例は、特に複雑に見えます。 https://github.com/JuliaLang/julia/blob/master/test/perf/perf.R

以下の2つのアルゴリズムから得られる最速のパフォーマンスはどれくらいですか（できれば、よりRに似たものにするために何を変更したかについての説明があります）。

## mandel

mandel = function(z) {
    c = z
    maxiter = 80
    for (n in 1:maxiter) {
        if (Mod(z) > 2) return(n-1)
        z = z^2+c
    }
    return(maxiter)
}

mandelperf = function() {
    re = seq(-2,0.5,.1)
    im = seq(-1,1,.1)
    M = matrix(0.0,nrow=length(re),ncol=length(im))
    count = 1
    for (r in re) {
        for (i in im) {
            M[count] = mandel(complex(real=r,imag=i))
            count = count + 1
        }
    }
    return(M)
}

assert(sum(mandelperf()) == 14791)

## quicksort ##

qsort_kernel = function(a, lo, hi) {
    i = lo
    j = hi
    while (i < hi) {
        pivot = a[floor((lo+hi)/2)]
        while (i <= j) {
            while (a[i] < pivot) i = i + 1
            while (a[j] > pivot) j = j - 1
            if (i <= j) {
                t = a[i]
                a[i] = a[j]
                a[j] = t
            }
            i = i + 1;
            j = j - 1;
        }
        if (lo < j) qsort_kernel(a, lo, j)
        lo = i
        j = hi
    }
    return(a)
}

qsort = function(a) {
  return(qsort_kernel(a, 1, length(a)))
}

sortperf = function(n) {
    v = runif(n)
    return(qsort(v))
}

sortperf(5000)
4

2 に答える 2

107

この質問のキーワードは「アルゴリズム」です。

以下の2つのアルゴリズムから得られる最速のパフォーマンスはどれくらいですか（できれば、よりRに似たものにするために何を変更したかについての説明があります）。

「 Rでこれらのアルゴリズムをどれだけ速く作成できますか？」のように。ここで問題となるアルゴリズムは、標準のマンデルブロ複合ループ反復アルゴリズムと標準の再帰的クイックソートカーネルです。

これらのベンチマークで提起された問題に対する答えを計算するためのより速い方法は確かにありますが、同じアルゴリズムを使用することはありません。再帰を回避し、反復を回避し、Rが得意でないものを回避することができます。しかし、同じアルゴリズムを比較することはもうありません。

マンデルブロ集合をRで計算したり、数値を並べ替えたりしたい場合は、そうです。これは、コードの記述方法ではありません。可能な限りベクトル化して、すべての作業を事前定義されたCカーネルにプッシュするか、カスタムC拡張機能を記述してそこで計算を実行します。いずれにせよ、結論は、Rはそれ自体で本当に良いパフォーマンスを得るのに十分な速さではないということです。良いパフォーマンスを得るには、Cにほとんどの作業を行わせる必要があります。

そして、それがまさにこれらのベンチマークのポイントです。Juliaでは、優れたパフォーマンスを得るためにCコードに依存する必要はありません。やりたいことを純粋なジュリアで書くだけで、パフォーマンスが良くなります。反復スカラーループアルゴリズムがやりたいことを行う最も自然な方法である場合は、それを実行してください。再帰が問題を解決する最も自然な方法である場合、それも問題ありません。不自然なベクトル化によるものであれ、カスタムC拡張機能の作成によるものであれ、パフォーマンスをCに依存することを余儀なくされることはありません。もちろん、線形代数であることが多いので、自然なときにベクトル化されたコードを書くことができます。必要なことを実行するライブラリがすでにある場合は、Cを呼び出すことができます。しかし、そうする必要はありません。

言語間で同じアルゴリズムを可能な限り公平に比較​​したいと考えています。

  1. 同じアルゴリズムを使用するRの高速バージョンを誰かが持っている場合は、パッチを送信してください。
  2. ジュリアサイトのRベンチマークはすでにバイトコンパイルされていると思いますが、間違っていてRとの比較が不公平な場合は、お知らせください。修正してベンチマークを更新します。
于 2012-05-23T01:00:27.583 に答える
47

うーん、マンデルブロの例では、行列Mの次元が転置されています

M = matrix(0.0,nrow=length(im), ncol=length(re))

count内側のループ（の連続する値）でインクリメントすることで埋められるためimです。私の実装では、複素数のベクトルを作成し、mandelperf.1すべての要素を操作します。インデックスとサブセットを使用して、ベクトルのどの要素がまだ条件を満たしていないかを追跡します。Mod(z) <= 2

mandel.1 = function(z, maxiter=80L) {
    c <- z
    result <- integer(length(z))
    i <- seq_along(z)
    n <- 0L
    while (n < maxiter && length(z)) {
        j <- Mod(z) <= 2
        if (!all(j)) {
            result[i[!j]] <- n
            i <- i[j]
            z <- z[j]
            c <- c[j]
        }
        z <- z^2 + c
        n <- n + 1L
    }
    result[i] <- maxiter
    result
}

mandelperf.1 = function() {
    re = seq(-2,0.5,.1)
    im = seq(-1,1,.1)
    mandel.1(complex(real=rep(re, each=length(im)),
                     imaginary=im))
}

13倍のスピードアップの場合（元の値は整数値ではなく数値を返すため、結果は同じですが同一ではありません）。

> library(rbenchmark)
> benchmark(mandelperf(), mandelperf.1(),
+           columns=c("test", "elapsed", "relative"),
+           order="relative")
            test elapsed relative
2 mandelperf.1()   0.412  1.00000
1   mandelperf()   5.705 13.84709

> all.equal(sum(mandelperf()), sum(mandelperf.1()))
[1] TRUE

クイックソートの例は実際にはソートしません

> set.seed(123L); qsort(sample(5))
[1] 2 4 1 3 5

しかし、私の主なスピードアップは、ピボットの周りのパーティションをベクトル化することでした

qsort_kernel.1 = function(a) {
    if (length(a) < 2L)
        return(a)
    pivot <- a[floor(length(a) / 2)]
    c(qsort_kernel.1(a[a < pivot]), a[a == pivot], qsort_kernel.1(a[a > pivot]))
}

qsort.1 = function(a) {
    qsort_kernel.1(a)
}

sortperf.1 = function(n) {
    v = runif(n)
    return(qsort.1(v))
}

7倍のスピードアップ（未修正のオリジナルと比較して）

> benchmark(sortperf(5000), sortperf.1(5000),
+           columns=c("test", "elapsed", "relative"),
+           order="relative")
              test elapsed relative
2 sortperf.1(5000)    6.60 1.000000
1   sortperf(5000)   47.73 7.231818

元の比較では、ジュリアはマンデルのRよりも約30倍高速であり、クイックソートの場合は500倍高速であるため、上記の実装はまだ実際には競争力がありません。

于 2012-04-02T00:17:13.613 に答える