1

私は次のコードを書きました：

combinationsstring = "List of Combinations"
for a = 0, 65 do
    for b = 0, 52 do
        for c = 0, 40 do
            for d = 0, 28 do
                for e = 0, 19 do
                    for f = 0, 11 do
                        for g = 0, 4 do
                            if (((1.15^a)-1)+((20/3)*((1.15^b)-1))
                               +((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))
                               +((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))
                               +((40000/3)*((1.15^g)-1))) < 10000 then
                                combinationsstring = combinationsstring
                                    .."\n"..a..", "..b..", "..c..", "..d
                                    ..", "..e..", "..f..", "..g
                            end
                        end
                    end
                end
            end
        end
    end
end

local file = io.open("listOfCombinations.txt", "w")
file:write(combinationsstring)
file:close()

次の方程式に適合するすべてのデータセットを見つける必要があります

(((1.15^a)-1)+((20/3)*((1.15^b)-1))+
((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))+
((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))+
((40000/3)*((1.15^g)-1))) < 10000

各変数 (ag) は実数です。そこで、7 つのそれぞれの最大値を計算しました (各変数の最大値は、他のすべての値が 0 の場合です)。これらの最大値は、65、52、40、28、19、11、および 4 です (62 = a、52 = b など)。

そこで、ネストされた 7 つの for ループを作成し (上記のコードに示すように)、中央のブロックで 7 つの値をテストして、基準に適合するかどうかを確認しました。適合する場合は、文字列に追加されました。コードの最後で、プログラムはファイルを上書きし、可能なすべての組み合わせを含む最終文字列を配置します。

プログラムは正常に動作していますが、このシミュレーションの過程で 31 億回の計算が実行されており、いくつかのテストから、私のコンピューターは 1 秒あたり平均 3000 回の計算を行っていることがわかりました。これは、合計シミュレーション時間が約 12 日と 5 時間であることを意味します。今回はまったく時間がないので、テストする方程式を単純化し、不要なコードを削除するために午前中ずっと費やしていましたが、これが私の最終結果でした。

ネストされた for ループを使用して行ったこの方法は、ここで最も最適な方法ですか? もしそうなら、これをスピードアップできる他の方法はありますか? そうでない場合は、別の方法を教えてもらえますか?

PS Lua は私が最もよく知っている言語であるため、Lua を使用していますが、他の提案や例があれば、あなたの言語で使用してください。このプログラム用に最適化を試みることができます。

4

4 に答える 4

3

私は lua を話せませんが、ここにいくつかの提案があります。

  • でループを開始する前にb、 を計算して保存し1.15^a-1ます。たぶんそれを呼び出しますfooa。
  • 同様に、 でループを開始する前にc、 を計算しfooa+(20/3)*(1.15^b-1)ます。たぶんそれを呼び出しますfoob。
  • 各ループを開始する前に、同様のことを行います。
  • たとえばfoob、 が少なくとも である場合10000、ループから抜け出します。内部のものは結果を大きくするだけです。
  • これは lua では役に立たないか、さらに悪いことかもしれませんが、結果を文字列に累積する必要は本当にあるのでしょうか? lua が文字列をどのように表現し、連結を行うかはわかりませんが、連結があなたをひどく傷つけている可能性があります。代わりに、リストまたは配列データ構造を使用してみてください。

また、ネストされたループは完全に賢明なソリューションであり、上記の変更を加えれば、まさに私が行うことになることも付け加えておきます。

于 2013-09-23T03:08:09.993 に答える
2

この性質のブルート フォーシングには静的言語をお勧めします。Python の使用に問題があるという問題 ( this one ) がありましたが、C++ ブルート フォース 8-for-loop アプローチは 30 秒でソリューションを計算します。

于 2013-09-23T03:50:15.537 に答える
0

さまざまな言語での解決策も求められたので、@tmyklebu による提案も取り入れた C++ の簡単で汚いプログラムを次に示します。

#include <iostream>
#include <fstream>
#include <cmath>

int main()
{
    std::ofstream os( "listOfCombinations.txt" );
    using std::pow;
    for( double a = 0; a <= 65; ++a ) {
        double aa = (pow(1.15, a) - 1);
        if ( aa > 10000 ) break;
        for( double b = 0; b <= 52; ++b ) {
            double bb = aa + (20/3) * (pow(1.15, b) - 1);
            if ( bb > 10000 ) break;
            for( double c = 0; c <= 40; ++c ) {
                double cc = bb + (100/3) * (pow(1.15, c) - 1);
                if ( cc > 10000 ) break;
                // The following line provides some visual feedback for the
                // user about the progress (it prints current a, b, and c
                // values).
                std::cout << a << "   " << b << "   " << c << std::endl;
                for( double d = 0; d <= 28; ++d ) {
                    double dd = cc + 200 * ( pow(1.15, d) - 1);
                    if ( dd > 10000 ) break;
                    for( double e = 0; e <= 19; ++e ) {
                        double ee = dd + (2000/3) * (pow(1.15, e) - 1);
                        if ( ee > 10000 ) break;
                        for( double f = 0; f <= 11; ++f ) {
                            double ff = ee + (8000/3) * (pow(1.15, f) - 1);
                            if ( ff > 10000 ) break;
                            for( double g = 0; g <= 4; ++g ) {
                                double gg = ff + (40000/3) * (pow(1.15, g) - 1);
                                if ( gg >= 10000 ) break;
                                os << a << ", " << b << ", " 
                                    << c << ", " << d << ", " 
                                    << e << ", " << f << ", " 
                                    << g << "\n";
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}
于 2013-09-24T09:58:22.883 に答える
0 
local res={}
combinationsstring = "List of Combinations"
--for a = 0, 65 do
        a=0
    for b = 0, 52 do
        for c = 0, 40 do
            for d = 0, 28 do
                for e = 0, 19 do
                    for f = 0, 11 do
                        for g = 0, 4 do
                            if (((1.15^a)-1)+((20/3)*((1.15^b)-1))
                               +((100/3)*((1.15^c)-1))+(200*((1.15^d)-1))
                               +((2000/3)*((1.15^e)-1))+((8000/3)*((1.15^f)-1))
                               +((40000/3)*((1.15^g)-1))) < 10000 then
                                        res[#res+1]={a,b,c,d,e,f,g}
                            end
                        end
                    end
                end
            end
        end
    end
--end

私のマシンでは 30 秒で実行され、約 1 GB のメモリがいっぱいになります。32 ビットの Lua VM では 66 倍にすることはできません。また、64 ビットの LuaVM でも、テーブルの配列部分は 32 ビットの整数キーに制限されています。

一番外側のループについてコメントしたので、約 30 秒 * 66 = 33 分かかります。おそらく66個の異なるファイルにそれを書きます。結果は最初にテーブルに保持され、次に連結できます。チェックアウト：

local res={
    {1,2,3,4,5,6,7},
    {8,9,10,11,12,13,14}
}

for k,v in ipairs(res) do
    -- either concatenate each line and produce a huge string
    res[k]=table.concat(v,", ")
  -- or write each line to a file in this loop
end

local text=table.concat(res,"\n")
print(text)

印刷

1, 2, 3, 4, 5, 6, 7
8, 9, 10, 11, 12, 13, 14
于 2013-09-25T14:30:25.977 に答える