10

ステータス:これまでのところ、最良の回答のプログラムは元のプログラムの 33% の時間で実行されています! しかし、おそらくそれを最適化する他の方法がまだあるでしょう。

Lua は現在、最速のスクリプト言語ですが、C/C++ に対するいくつかのベンチマークでは、Lua のスコアが非常に低くなっています。

それらの 1 つは、マンデルブロ テスト (マンデルブロ セット ポータブル ビットマップ ファイル N=16,000 を生成) で、1:109 (マルチ コア) または 1:28 (シングル コア) という恐ろしいスコアを付けます。

速度のデルタが非常に大きいため、これは最適化の良い候補です。また、Mike Pall が誰であるかを知っている人は、これ以上最適化することはできないと考えるかもしれませんが、それは明らかに間違っています。最適化を行ったことがある人なら誰でも、常に改善できることを知っています。それに加えて、いくつかの微調整で追加のパフォーマンスを得ることができたので、それが可能であることを知っています:)

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

write("P4\n", width, " ", height, "\n")

for y=0,height-1 do
  local Ci = 2*y / height - 1
  for xb=0,width-1,8 do
    local bits = 0
    local xbb = xb+7
    for x=xb,xbb < width and xbb or width-1 do
      bits = bits + bits
      local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
      local Cr = x * wscale - 1.5
      for i=1,m do
        local Zri = Zr*Zi
        Zr = Zrq - Ziq + Cr
        Zi = Zri + Zri + Ci
        Zrq = Zr*Zr
        Ziq = Zi*Zi
        if Zrq + Ziq > limit2 then
          bits = bits + 1
          break
        end
      end
    end
    if xbb >= width then
      for x=width,xbb do bits = bits + bits + 1 end
    end
    write(char(255-bits))
  end
end

では、これをどのように最適化できますか (もちろん、他の最適化と同様に、より高速であることを確認するために実装を測定する必要があります)。また、Lua の C コアを変更したり、LuaJit を使用したりすることは許可されていません。それは、Lua の弱点の 1 つを最適化する方法を見つけることです。

編集:チャレンジをより楽しくするために、これに賞金をかけます。

4

9 に答える 9

7

パス 2、以前より (私のマシンで) 約 30% 優れています。主な節約は、オーバーヘッドを償却するために内側のループをアンロールしたことによるものです。

また、中央のカーディオイドで立ち往生しているときに早期に終了する (およびピクセルを黒に設定する) ことで時間を節約するための試み (コメントアウト) も含まれています (コメントアウトされています)。動作しますが、どのように動かしても遅くなります。

私は走らなければなりませんが、別れの提案を残します。結果をランレングス エンコーディングすることで、ある程度の最適化が可能になる場合があります (したがって、一連のビットをいじった文字を保存する代わりに、リスト (白点の数、黒点の数、白点の数など) を保存します)。 ）。これは次のようになります。

  1. ストレージ/GC のオーバーヘッドを削減する
  2. 出力生成でいくつかの最適化を許可します (数値が >> 8 の場合)
  3. いくつかの軌道検出を許可します。

飛ぶのに十分なほどタイトにコード化できるかどうかはわかりませんが、時間があれば次に試してみたいところです.

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall
-- with optimizations by Markus J. Q. (MarkusQ) Roberts

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

local h2 = math.floor(height/2)
local hm = height - h2*2
local top_half = {}

for y=0,h2+hm do
    local Ci = 2*y / height - 1
    local line = {""}
    for xb=0,width-1,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width-1 do
            bits = bits + bits
            local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
            local Cr = x * wscale - 1.5
            local Zri = Zr*Zi
            for i=1,m/5 do
                Zr = Zrq - Ziq + Cr
                Zi = Zri + Zri + Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zrq = Zr*Zr
                Ziq = Zi*Zi
                Zri = Zr*Zi
                if Zrq + Ziq > limit2 then
                    bits = bits + 1
                    break
                    end
                -- if i == 1 then
                --    local ar,ai       = 1-4*Zr,-4*Zi
                --    local a_r         = math.sqrt(ar*ar+ai*ai)
                --    local k           = math.sqrt(2)/2
                --    local br,bi2      = math.sqrt(a_r+ar)*k,(a_r-ar)/2
                --    if (br+1)*(br+1) + bi2 < 1 then
                --        break
                --        end
                --    end
                end
            end
        for x=width,xbb do 
            bits = bits + bits + 1 
            end
        table.insert(line,char(255-bits))
        end
    line = table.concat(line) 
    table.insert(top_half,line)
    end

write("P4\n", width, " ", height, "\n")
for y=1,h2+hm do
    write(top_half[y])
    end
for y=h2,1,-1 do
    write(top_half[y])
   end
于 2009-03-03T19:07:21.377 に答える
3

したがって、ここに開始用の ~40% があります。

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

function addChar (line, c)
    table.insert(line, c)
    for i=table.getn(line)-1, 1, -1 do
        if string.len(line[i]) > string.len(line[i+1]) then
            break
            end
        line[i] = line[i] .. table.remove(line)
        end
    end

local h2 = math.floor(height/2)
local hm = height - h2*2
local top_half = {}
for y=0,h2+hm do
    local Ci = 2*y / height - 1
    local line = {""}
    for xb=0,width-1,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width-1 do
            bits = bits + bits
            local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
            local Cr = x * wscale - 1.5
            for i=1,m do
                local Zri = Zr*Zi
                Zr = Zrq - Ziq + Cr
                Zi = Zri + Zri + Ci
                Zrq = Zr*Zr
                Ziq = Zi*Zi
                if Zrq + Ziq > limit2 then
                    bits = bits + 1
                    break
                    end
                end
            end
        for x=width,xbb do 
            bits = bits + bits + 1 
            end
        addChar(line,char(255-bits))
        end
    line = table.concat(line) 
    table.insert(top_half,line)
    end

write("P4\n", width, " ", height, "\n")
for y=1,h2+hm do
    write(top_half[y])
    end
for y=h2,1,-1 do
    write(top_half[y])
    end

-- マーカスQ

于 2009-03-03T06:10:39.200 に答える
2

Lua が動作するコードを生成するのにそれほど適しているかどうかはわかりませんが、いくつかの数学のトリックを使用することで、マンデルブロのパフォーマンスを大幅に向上させることができるはずです。対称性を使用して高速化することについての提案がありましたが、この最適化を使用して別の大きな改善を行うことができます。

マンデルブロ部分の長方形座標を使用する再帰関数を使用します。次に、長方形の境界線と中央で分割された 2 つの線の値を計算します。この後、4 つのサブ長方形があります。そのうちの 1 つがすべて同じ境界ピクセルの色を持っている場合は、単純にこの色で塗りつぶすことができます。そうでない場合は、この部分で関数を再帰的に呼び出します。

このアルゴリズムの別の説明を検索したところ、ここで見つかりました - 素敵な視覚化とともに。古い DOS プログラム FRACTINT は、この最適化を「テッセラル モード」と呼んでいます。

于 2009-03-04T10:22:29.867 に答える
2

私のソリューションよりも速い回答が少なくとも1つあるので、回答を投稿します

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char
local insert = table.insert
local results={}
write("P4\n", width, " ", height, "\n")

for y=0,height-1 do
  local Ci = 2*y / height - 1
  for xb=0,width-1,8 do
    local bits = 0
    local xbb = xb+7
    for x=xb,xbb < width and xbb or width-1 do
      bits = bits + bits
      local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
      local Cr = x * wscale - 1.5
      for i=1,m do
        local Zri = Zr*Zi
        Zr = Zrq - Ziq + Cr
        Zi = Zri + Zri + Ci
        Zrq = Zr*Zr
        Ziq = Zi*Zi
        if Zrq + Ziq > limit2 then
          bits = bits + 1
          break
        end
      end
    end
    if xbb >= width then
      for x=width,xbb do bits = bits + bits + 1 end
    end
    insert(results,(char(255-bits)))
  end
end
write(table.concat(results))

秘訣は、値を出力に送信する前にテーブルに格納することです。このような単純なことで、実行時間が 58% に短縮されました。

于 2009-03-03T07:37:06.933 に答える
1

ローカル変数 Zri を使用する理由 次の 2 つのステートメントを並べ替えることで、その使用を避けることができます。

Zi = 2*Zr*Zi + Ci Zr = Zrq - Ziq + Cr

単純な周期性チェックを使用することも可能ですが、高速化は m に依存します。"m" が大きいほど、周期性チェックによる高速化が向上します。

于 2009-05-19T11:19:58.567 に答える
0

ロバート・グールド>そのうちの1つは、マンデルブロ検定（マンデルブロ集合ポータブルビットマップファイルN = 16,000を生成）で、恐ろしい1：109を記録します。

ベンチマークゲームの数字を引用するときは、読者がある程度の文脈を理解できるように、それらの数字がどこから来ているのかを示してください。

この場合、複数のコアを利用するために最速のプログラムが書き直されたクアッドコアマシンで測定された数値を取得したようです。経過時間をCPU時間で並べ替えると、比率が1:28に低下することがわかります。

または、中央値と四分位数を調べて、C++測定値のセットがLua測定値のセットとどのように比較されるかをよりよく理解します。

または、プログラムが1つのコア（C ++と比較したLua ）のみを使用するように強制される一連の測定値があります。これらのLua pi-digitsプログラムを見ると、C言語のGNUGMPライブラリが使用されていることがわかります。

于 2009-02-20T22:13:55.887 に答える
0

これは別の試みでしたが、変数のローカル アクセスよりも遅いことが判明しました (クリーンな環境を使用すると変数を見つけるのが速くなると想像しましたが、そうではありませんでした。ローカルの仮想レジスタはわずかに高速です)。実行時間は 41% に減少しました。

local env={}
env.width = tonumber(arg and arg[1]) or 100
env.height = env.width
env.wscale = 2/env.width
env.m = 50
env.limit2 = 4.0
env.write = io.write
env.char = string.char
env.results={}
env.height_minus_one = env.height - 1
env.width_minus_one = env.width -1
env.insert = table.insert

setfenv(function()
    write("P4\n", env.width, " ", env.height, "\n")
    for y=0,height_minus_one do
      local Ci = 2*y / height_minus_one
      for xb=0,width_minus_one,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width_minus_one do
          bits = bits *2
          local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
          local Cr = x * wscale - 1.5
          for i=1,m do
            local Zri = Zr*Zi
            Zr = Zrq - Ziq + Cr
            Zi = Zri + Zri + Ci
            Zrq = Zr*Zr
            Ziq = Zi*Zi
            if Zrq + Ziq > limit2 then
              bits = bits + 1
              break
            end
          end
        end
        if xbb >= width then
          for x=width,xbb do bits = bits *2 + 1 end
        end
        insert(results,(char(255-bits)))
      end
    end
end,env)()

io.write(table.concat(env.results))
于 2009-03-03T08:11:18.897 に答える