配列の上手な使い方について

質問

int d[100];

while(0)
{
i++;
d[i] = input;
if(i=>99)
{
i=0;
}
}

で、データを取っているとして、
ある瞬間d[edg]±20のデータがほしい時

for(j=-20;j<=20;j++)
{
x[j-20] = d[edg+j];
}
で、ほしいデータが取れる。
しかし、edg=90の時等はd[]が100を超えることがあり、データが取れない。

なので、少し修正して
for(j=-20;j<=20;j++)
{
if((edg+j) < 100)
{
x[j+20] = d[edg+j];
}
else
{
x[j+20] = d[edg-100+j];
}
}
とすると、毎回IFを通るので、実行速度が遅くなってしまう。

もう少しマシな方法はありますか？

回答No.1

rinkun · ベストアンサー

方法として思いつくのは2つ。
1.バッファサイズを2の冪にする
例えばdのサイズが256なら0xffでマスクする(&0xff)だけで0～255に収められるので分岐するより速い。
バッファサイズを変えないと剰余演算になるので非効率だろう。

2.ループを2つに分割しておく
最初に境界条件をチェックして範囲を越えない分と越えて0からやる分の2つにループを分割してしまう。後のループは0回実行の可能性もあり。
ループ内で無意味な判定を繰り返す必要がなくなって速い。

お礼

１、
int d[0x7f];
…
for(j=-20;j<=20;j++)
{
x[j+20] = d[0x7F & (edg+j)];
}

２、
loop = 100 - edg;
for(j=-20;j<=loop;j++)
{
x[j+20] = d[edg+j];
}
for(j=loop;j<=20;j++)
{
x[j+20] = d[edg-100+j];
}

こんな感じですか。
かなりマシになりそうです
ありがとうございます。

回答No.12

matyrcry

>アルゴリズム・レベルでの最適化

確かにそうですね。
何人かで語られていますし、さほどの妙手も浮かばないんですが、
自分だとd[100]を前後に２０個づつ拡張しておいて、
データ取りの処理で
d[i] = input;
if( i < 20 ){ d[i+100] = input; }
if( i >= 80 ){ d[i-100] = input; }
としておけば抽出時にちょっと楽になるかなと。
ただデータ取り処理があまり短周期で実行されると恒常的に負荷
がかかるのでどうかなあとか。

お礼

何度もありがとうございます
とりあえずNo1さんの言っていた方法を使いつつ、ポインタも使いつつ、なるべく早くなるようにしようと思います。

で、動かしてみて余裕が無さそうだったらもう少し削ってみようかと思います。
（削り方、方法を沢山聞いたので、色々な部分で応用できそうで）

色々勉強になりました。
ありがとうございます。

回答No.11

rinkun

なんか生成するマシン語を予測してCソースを書く世界にいってますが……(^_^;)

・if(a>2) と if(a-2>0)
ちゃんとしたコンパイラならどちらも同じ命令を生成するでしょうね。それが比較命令になるか減算命令になるかは後でa-2の値を使うかどうかに掛かってくるでしょう。実際、比較と減算の違いは演算結果を保存するかどうかだけですし。RISCやDSPだと比較命令を持たないのもあるかな。

ただ最適化を考えるなら生成コードを予測して書くだけでなく、コンパイラにアセンブラ・ソースを生成させて確認しながら書いた方が良いよ。アセンブラが読めなければ評価できないので無理はしない方が良い。
それにアセンブラ・レベルでの最適化は最後の手段で、アルゴリズム・レベルでの最適化を極限までやって足りない部分だけにしておかないと後のメンテナンスで困るよ。

お礼

速度とファイルのサイズとソースの見易さのバランスと言うことですよね。

ほどほどに、出来る限りがんばろうと思います。

ありがとうございました

回答No.10

matyrcry

説明不備も多いと思いますんで、不明な部分はそう言ってくれると助かります。

if( a > 2 )だと分岐条件のフラグを作るために( a - 2 )で２の固定値減算
が行われ、x[j]だと配列先頭からのオフセット位置を求めるために、j*4の
乗算（*4は2bitシフトに置換されますが）とアドレス加算が行われます。
変数jは実際にはインクリメントしているだけであっても、x[j]は前回のアド
レスを残しておいてインクリメントするわけではなく、毎回jの値を参照して
算出し直すのが普通です。
頭の良いコンパイラならうまく処理してくれる可能性もありますが、かなり
期待薄ですから明示的に指示してやった方がいいです。

追求しすぎると人間向きでなくなるので妥協は必要ですが、明示的な演算記号
以外にも見えない演算記号が多々あるので、そこを狙ってみてください。

お礼

一つ目が微妙なんですけど、
if(a>2)と書いてもif(a-2>0)と内部で計算してるって事でしょうか？？

２個目は多分
ポインタを使ってアドレスに加算するとアドレスを直接参照する。
配列の場合はx[0]から何アドレスずれているかを毎回計算してから参照するから、一手間多くなる。
って事ですよね。

なんか、今まで見易い（作り易い？）ソースばかり書いてたので、実行速度とか後回しにしてたんですが、やはりかなり奥が深そうですね＾＾；

回答No.9

matyrcry

>*p1++=*p2++;
>はポインタを使わずに
>x[j]=d[i];j++;
>と書くよりも速度が速いのでしょうか？

x[j]だと、
１）&x[0]をアドレスレジスタに入れる
２）j * sizeof(int)をアドレスレジスタに加える加算処理が毎回行われます。
p1++だとアドレスレジスタを４（固定値）加算で、１バイト定数のレジスタ加算は
たいていのＣＰＵで専用命令がサポートされているので、加算演算より高速に処理
されます。

>フラグの比較と言うのはコンパイラが自動でやってくれる物なのでしょうか？
フラグはロード、演算、転送などの処理の度にＣＰＵが勝手に立てるもので、分岐
処理は、フラグ条件付きのジャンプ命令として表現されます。
たとえば、
if( a > 0 ){処理Ａ}else{処理Ｂ}
と記述すれば、
１）変数ａをレジスタにロード
２）ＺかＳフラグが立っていれば処理Ｂにジャンプ
３）処理Ａ
４）おわりにジャンプ
５）処理Ｂ
６）おわり
という機械語に翻訳されます。

回答No.8

matyrcry

コーディングするとこんな感じでしょうか。
int j,k1,k2,max1,max2,*p1;*p2;
p1 = x;
k1 = edg - 20;
k2 = edg + 20;
if( (k1 >= 0)&&(k2 < 100) ){
　p2 = &d[k1];
　for(j=40;j>=0;j--){ *p1++ = *p2++; }
}else{
　if( k1 < 0 ){
　　max1 = k2; max2 = k1 + 100;
　}else{
　　max1 = k2 - 100; max2 = k1;
　}
　p2 = &d[max2];
　for(;max2<100;max2++){ *p1++ = *p2++; }
　p2 = d;
　for(;max1>=0;max1--){ *p1++ = *p2++; }
}

補足

わざわざソースまで書いてくださってありがとうございます。
ちょっと理解するのに時間がかかりましたが、なんとなく理解しました。

k1 = edg - 20;
k2 = edg + 20;
if((k1>=0)&&(k2<100)){
for(j=0;j<40;j++) {x[j]=d[k1];k1++;}
}else{
if(k1<0){
max1=k2;max2=k1+100;
}else {
max1=k2-100;max2=k1;
}
j=0;
for(i=max2;i<100;i++){x[j]=d[i];j++;}
for(i=0;i<=max1;max1++){x[j]=d[i];j++;}
}
大体コレと同じですよね。
まだポインタの良さがイマイチ判らないのですが、
*p1++=*p2++;
はポインタを使わずに
x[j]=d[i];j++;
と書くよりも速度が速いのでしょうか？

今見てるだけでごちゃごちゃしたので、実際に書く場合には多分相当やる気出さないとポインタ使えなさそうなので、聞いてみました。
結構違うのであれば相当やる気出そうと思っています。

回答No.7

麻野 なぎ（@AsanoNagi）

No.6 です。
なるほど、DSP ですか。それなら、そういう考慮もありですね。失礼しました。

でも、DSP なら、リングバッファーのコピーなどが関数の形でついている可能性もあるかもしれません。

回答No.6

麻野 なぎ（@AsanoNagi）

No.1 の方も触れられていますが……

for(j=-20;j<=20;j++)
{
x[j+20] = d[(edg+j) % 100];
}

あたりがわかりやすいのではと思います。
もちろん、「遅い」ですが。

ぜひ、if なしのものと（edg をあふれないような数値にして）毎回 if を実行するものと処理時間を比べてみてください。

そして、あなたが「速い」と思ったソースを他の人に見せて、その人が処理を理解できるまでの時間を計ってみてください。

処理時間を稼ぐより、わかりやすいソースだと思いますが。たとえ数秒速くしたとしても、トリッキーなソースでバグをもぐり込ませたら、本末転倒なのではと思います。

補足

数秒も違うと困っちゃいます（汗
実は、PCで実行するプログラムではなく、DSPで実行するプログラムを作っています。（初DSP）
で、サンプリング周波数が50KHｚ、DSPのクロックが150MHｚなので、forの中にifなんてとてもかけないかな？と思いまして質問しました。
アセンブラで書けば早いと思うのですが、アセンブラは書けないのでcでどうにかと思っています。
今のところNo1の方のやり方が一番しっくり来てるのですが、リングバッファという言葉を調べたところ、そっちの方もよさそうかな？と思って今試行錯誤中です。
ポインタもほとんど使ったことが無いので、リングバッファを理解できるか微妙なんですけど（汗

回答No.5

matyrcry

もうひとつ考えてみました。^^;
連続４１（２Ｎ＋１）個の抽出と決まっているなら、基準点は中央に
とるよりもどちらかの端点にとったほうが比較の都合がいいです。
まずリングバファの端にかかるかどうかを比較して、かかる場合は
ループ変数を２つに分けて別々に回せば毎回比較は回避できます。
コーディング量は増えますが処理時間は減るわけです。
自動変数のロード、ストアは演算と比べるとかなり速いので、演算
付きの配列表現を単にポインタ変数の実体として記せば、関連変数
を増やして初期演算が増えても結果的には短縮になると思います。

回答No.4

matyrcry

比較文は零との比較ならＺ，Ｓフラグを見るだけで速いので、
k=edg+j-100;とでも置いて零との比較にしたほうが、（そのために
変数を増やしてインクリメントしたとしても）速くなると思います。
ループ回数が十分に大きいなら毎回既知の加算処理があるよりは
別の変数を置いてインクリメントにした方が速いです。
単に配列の抽出なら比較文を使って分岐してもmemcpy()で転送を
かけたほうが速くなるかもしれません。

補足

返事が遅くなってスイマセン。
初めて聞く言葉が色々出てまして。
Z,Sフラグって言うのは調べたところマイナスのフラグとゼロのフラグと言う事が分かりました。
フラグの比較と言うのはコンパイラが自動でやってくれる物なのでしょうか？
もし自動で無いとすると、その方法がサッパリ分からなくて、困っています。

ループの処理は別の変数でインクリメントが早いと言うのはなるほどと思いました。
毎回２回足すよりは１回計算しておいて毎回計算するのは１回ずつの方がいいと言うことですよね。
勉強になりました。

回答No.3

ttyp03

もうひとつ考えてみました。
前回のと似ているのですが、バッファとは別にバッファの添え字を格納する配列を用意します。

int p[200];

今回はこれをバッファの倍用意します。
処理に入る前、事前にこの配列に添え字を格納しておきます。

for(i=0;i<100;i++){
p[i] = i;
p[i+100] = i;
}

あとはわかると思いますが、dを参照するときにpを介して参照します。

d[p[edg+j]]

ご参考までに。