いくつかの文と条件を持つ単一のループは、いくつかの単純なループよりも優れていますか？

Question

私は貪欲アルゴリズムを使ってクライアントに変更を返すために必要なコインの数を決定する非常に簡単なプログラムを作成していました。 アルゴリズムは本当に明白です。あなたが使用できる大きなコインを決定し、その値を変更から減算し、コインカウンタを更新する必要があります。

私は2つの本当に似た実装を考えました。

注：changeIntは変更を100倍して整数に変換したものです。

1）シングル "複雑な" ループ

while(changeInt != 0) { 
     if(changeInt - 25 >= 0){ 
      changeInt -= 25; 
      coins++; 
     } 
     else if(changeInt - 10 >= 0){ 
      changeInt -= 10; 
      coins++; 
     } 
     else if(changeInt - 5 >= 0){ 
      changeInt -= 5; 
      coins++; 
     } 
     else if(changeInt - 1 >= 0){ 
      changeInt -= 1; 
      coins++; 
     } 

    } 

2）複数の単純なループ今

while(changeInt - 25 >= 0) 
    { 
     changeInt -= 25; 
     coins++; 
    } 
    while(changeInt - 10 >= 0) 
    { 
     changeInt -= 10; 
     coins++; 
    } 

    while(changeInt - 5 >= 0) 
    { 
     changeInt -= 5; 
     coins++; 
    } 

    while(changeInt - 1 >= 0) 
    { 
     changeInt -= 1; 
     coins++; 
    } 

、私はパフォーマンスはおそらくアルゴリズムいるので、どちらの場合も、同様のになります知っています同じですが、私はどちらのアプローチが良いのだろうと思っていました。

私が思いついた最初のアイデアは、最初のアイデアでした。そして、私は2番目の方法を考えました。それは直感的に私にとっては良いようです。

が、私は本当に私の正確なシナリオを気にしない、私は一般的なもので、より興味が（いくつかのより複雑なループ対いくつかの単純なループ）

1）パフォーマンスの面で優れているアプローチは？

2）少なくとも巨大な数値で作業する場合は、違いが目立っていますか？

3）1つのアプローチは、他のアプローチよりもかなり読みやすいですか？ （私がここでそれを聞くことができるか分からない）

ありがとう！

Answer 1

説明したループの手法の中から選択する必要がある場合は、2番目の方法が推奨されます（わずかなバリエーションがあります）。それはよりクリーンで、ほとんどの場合、不必要なテストを避けます。 「 - X changeIntは」決してラップアラウンドしない

はここで、これは提供しています

while(changeInt >= 25) { 
    changeInt -= 25; 
    coins++; 
} 

while(changeInt >= 10) { 
    changeInt -= 10; 
    coins++; 
} 

while(changeInt >= 5) { 
    changeInt -= 5; 
    coins++; 
} 

while(changeInt > 0) { 
    changeInt -= 1; 
    coins++; 
} 

主な利点は、それがいることを保証するのに役立つということです...わずかな変化です。あなたの記事に書かれていることから、それが問題になることはまずありませんが、型が符号付き整数から符号なし整数に変更された場合は、バグの場所を特定しようとしている可能性があります。

また、除算とモジュラス演算子の組み合わせを使用して変更を計算し、ループを回避することもできます。

これが役に立ちます。

Answer 2

あなたが言ったように、両方ともかなり似ています。私が最初のものを好む読みやすさについて話しているのですが（それは主観的意見です）。

私たちがパフォーマンスで考えると、IMHOは前のモデルより少し速いです。

1）シングル "複雑な" ループ（およそ10mlの液体フッ化水素を圧入ASM用のx86-64）

jmp 
mov 
sub 
test 
js 
sub 
add 
jmp 
mov 
sub 
test 
js 
sub 
add 
jmp 
mov 
sub 
test 
js 
sub 
add 
jmp 
mov 
sub 
test 
js 
sub 
add 
cmp 
jne 

2）複数の単純なループ（およそ10mlの液体フッ化水素を圧入ASMのx86-64で）：私たちは、詳細な比較のためにASMにtraslateしようとすることができます

jmp 
sub 
add 
mov 
sub 
test 
jns 
jmp 
sub 
add 
mov 
sub 
test 
jns 
jmp 
sub 
add 
mov 
sub 
test 
jns 
jmp 
sub 
add 
mov 
sub 
test 
jns 

我々はx86-64でのASM命令数える場合：

jmp: 4 
mov: 4 
sub: 8 
test: 4 
add: 4 
js: 4 
cmp: 1 
jne: 1 

対

0123をそして、総括する

jmp: 4 
mov: 4 
sub: 8 
test: 4 
add: 4 
jns: 4 

：

jns 4 

対

js 4 
cmp 1 
jne 1 

そして "jsが" "JNS" に似ています。

しかし、これは他のコンパイラやアーキテクチャーでも変わる可能性があります。それでも、第2のものは最初のものより少し速いと思います。

Answer 3

他にも言及したように、第2のアプローチは、比較が少ないので好ましい。

クリーナー、より簡潔な方法は、除算およびモジュラスを使用することです：

int current = changeInt; 
coins += current/25; 
current %= 25; 
coins += current/10; 
current %= 10; 
coins += current/5; 
current %= 5; 
coins += current; 

DIVとMOD演算子は、減算よりも高価ですが、changeIntの大きな値のために高速になりそうだし、そこにあります枝はありません。

Answer 4

なぜこのようなループが必要なのかわかりません。

int tempChangeInt; 

tempChangeInt = changeInt; 
coins = changeInt/25; 
tempChangeInt = changeInt % 25; 
if (tempChangeInt != 0) 
{ 
    coins += tempChangeInt/10; 
    tempChangeInt = tempChangeInt % 10; 
} 
if (tempChangeInt != 0) 
{ 
    if (tempChangeInt >= 5) 
     coins += (tempChangeInt - 5) + 1; 
    else 
     coins += tempChangeInt; 
}