ループを29000,000回繰り返します。より速いです。

Question

申し訳ありませんので、データを処理するプログラムを作成しましたが、この関数を文字列で実行する必要があり、データは29,000,000文字以上です。私は

for x = 1, 29000000, 1 do 
end 
print("Done") 

それが今、私は即座にこの仕上げをしようとして作るために誰かを求めていないよ、即座に終了しますが、どのように私はそれが現在入手し3+時間がかかるので、それはより速く仕上げることができますのようなループを実行する場合行って10％に、その基本的に多分プログラムを実行するために時間と時間を要した場合、それは似ていないとき、LUAは（より多くのCPUを使用するか、多分

local function interpret(action, input, key) 
    local byte, char, decrypt, encrypt, input, output, sub = string.byte, string.char, key.decrypt, key.encrypt, input, '', string.sub 
    if (action == "decrypt") then 
     for x = 1, (#input), 1 do 
      output = (output .. (char(((byte(decrypt[sub(input, x, x)]) - (x + 2)) + 1) % 256))) 
      if x % 10000 == 0 then print(x) end 
     end 
    else 
     for x = 1, (#input), 1 do 
      output = output .. (encrypt[char(((byte(sub(input, x, x)) + x) + 1) % 256)]) 
      if x % 10000 == 0 then print(x) end 
     end 
    end 
    return (output); 
end 

Answer 1

私の機能をより効率的にできるようにする方法がありますその場合）は、あなたが悪い漸近的な時間の複雑さを持つアルゴリズムを使用している可能性があります。いくつかの実験を実行し、アルゴリズムを実行するのにかかる時間が入力文字列の長さによってどのように異なるかを確認してください。

この問題では、サイズ入力に合わせて直線的に成長することが理想的です。入力文字列のサイズを2倍にすると、計算時間が2倍になるはずです。しかし、あなたの場合（コメントが示唆しているように）私はあなたのアルゴリズムが二次的であると思われます。入力サイズを2倍にすると、おそらく計算時間が4倍になります。入力を10倍に増やすと、おそらく計算時間が100倍になるでしょう。

アルゴリズムが2次の場合、長い入力に対して妥当な時間にアルゴリズムを実行させる唯一の方法は、アルゴリズムをより漸近的な複雑さを持つ別のアルゴリズムに置き換えることです。どんなにあなたのプログラムを微調整しても、使用するコンピュータハードウェアがどれくらいのものであっても、漸近的な複雑さはあなたに追いつきます。たとえば、アルゴリズムが10000倍速く実行されるようにアルゴリズムを微調整したとしても、以前の100倍の大きさの入力を処理できるのはその場合だけです。あなたの特定のプログラムで

---

問題のソースは、一度に大きな文字列の文字を構築するために..演算子を使用しています。 Luaでは、..に入力された文字列の長さに比例した時間が、..に入力されます。これは、入力を新しい文字列にコピーすることによって機能します。

最も一般的な回避策は、文字列の一部をテーブルに格納し、table.concatを使用して最後に一緒に結合することです。

local result = {} 
for i = 1, (#input), 1 do 
    result[i] = char(((byte(decrypt[sub(input, i, i)]) - (i + 2)) + 1) % 256) 
end 
return table.concat(result)