トップページ⇒tech
431コメント122KB

いいアルゴリズムっていうか小技を教えて

■ このスレッドは過去ログ倉庫に格納されています
00011 ◆UbLWewsM NGNG
たとえばaとbを入れ替えるとき、
普通は
　tmp = a;
　a = b;
　b = tmp;
みたいにやるところを、
　a = a + b;
　b = a - b;
　a = a - b;
ってやれば余計な変数を使わずに実現する！
みたいなちょっとした小技を教えてください。

見た人が「なるほど」って感動するようなやつを。
0002デフォルトの名無しさんNGNG
発作的に2ゲットずざー
0003デフォルトの名無しさんNGNG
>>1はトリップまで用意してスレを…
ウッウッ
0004デフォルトの名無しさんNGNG
N88BASICでは、コメントを付けないほうが速くなる。
0005デフォルトの名無しさんNGNG
>>3
そのわりに名前は1か
0006デフォルトの名無しさんNGNG
>>4
コンパイルしないスクリプト言語はぜんぶ
そうなんですかね？
0007名無しさん＠揚げ足NGNG
かわいそうな>>１に乾杯
0008デフォルトの名無しさんNGNG

つか、

トリッキーなコード
http://pc.2ch.net/test/read.cgi/tech/983191866/

じゃだめなの？

a ^= b ^= a ^= b;
とかあるよ。
0009デフォルトの名無しさんNGNG
>>6
最近のやつは内部で中間コードに落としたりしてるから、
関係ないんじゃねーの?
00106NGNG
>>9
じゃ中間コードに落とす時点での
速度差があるってことですかね？
0011デフォルトの名無しさんNGNG
ソースに ギガバイト単位の のコメントとか入れてるなら
遅くなるだろーけど、普通のソースだったら殆ど差なんか出ないだろ。
0012デフォルトの名無しさんNGNG
N88BASICは最近の言語じゃないし。
0013デフォルトの名無しさんNGNG
>>1のは実用的じゃない。
0014デフォルトの名無しさんNGNG
>>13　確かに。でもちょっと感動した。
a b cの中身を指定した順番に簡単に入れ替えれるやつないかな
漏れも今から考えてみるけど。
0015デフォルトの名無しさんNGNG

a = ( a - ( b = ( a = a + b ) - b ) );
0016デフォルトの名無しさんNGNG
>>15
>>1を横にしただけだけだけど面白いと思う
0017デフォルトの名無しさんNGNG
>>16
だけが１個多いだけだけだけど面白いと思う
0018デフォルトの名無しさんNGNG
【俺】　俺語でプログラミング　【語】
http://pc.2ch.net/test/read.cgi/tech/1016815283/6-9

のソースが意味不明なんだけど....
動かなかったし
0019デフォルトの名無しさんNGNG
まず眼科へ >>18
http://pc.2ch.net/test/read.cgi/tech/1016815283/10
0020デフォルトの名無しさんNGNG
>>19
すいません。見てなかった。
つか、Cのソースだったのか....

ﾊｧ...耳(外耳炎)の次は目か...
0021デフォルトの名無しさんNGNG
>>1
それは面白いが、良いアルゴリズムではないよ。
00221NGNG
>>13>>21やっぱtmp使ったほうがいいですかね？
0023デフォルトの名無しさんNGNG
そこまで小技は知らんが「珠玉のプログラミング」はまともにおもろいよ。
0024デフォルトの名無しさんNGNG
>>22　そっちがいいとは限らないけど　
　多くの CPU は b=a-bは１命令に落ちないから　XOR の方がいいんだよ
0025デフォルトの名無しさんNGNG
じゃあ　除算命令が無いとして7で割った余りを求めるコード　は知ってる？
0026デフォルトの名無しさんNGNG
a = ???;
b = 7;
while(a > b){a=a-b;}

aに最初の数を入れれば、
最後にはaに余りが入るんじゃないかな。

bは7以外でも可かな？試してないから自信ないけど。
0027デフォルトの名無しさんNGNG
>>26　それはけど 実行時間が a に比例してしまうよ LOG(a)程度で済む方法を考えて

ヒント a mod 8 なら a and -8 で代用出来る。
　　　 -8 は ２の補数表現として 8bitなら 11111000　ね
002826NGNG
そんなに難しいこと考えてよかったんだ。
可能な限り誰でもわかるようにわざわざ書いたのに。

待ってて書き直す。
002927NGNG
あ　やっちゃった ミス

ヒント a mod 8 なら a and 8-1 で代用出来る。
　　　 8-1 は ２の補数表現として0000 0111　ね
0030デフォルトの名無しさんNGNG
b = 7 << 28; //28は適当
while( a != 0){
　if( a >= b ) a-=b;
　b = b >>1;
}
0031デフォルトの名無しさんNGNG
>>1
自ら宣言する余計な変数は減るかもしれないけど
明らかに遅くなるよ。a = a+bの時点で　
a+bを格納するための変数のコンストラクタが呼ばれているから。
わざわざ加算・減算のための関数をよんでるからオーバーヘッド
が発生する。
たとえaもbもただの32bit int 型だったとしてもオーバーフローする
可能性があるしバグ探しで見つかりにくい。
条件式なんかつけたらそれこそ投機実行で死んでくれるからね。
それよりも、値が早く、でるような、よい関数を、考えましょう。
テイラー展開。

003227NGNG
>>30
　その方が汎用的だね　用意していた答えは

while( a>7 ) a=(a>>3)+(a&7) ; if( a>=7 )a-=7;

このwhile をバイナリ展開すれば　もっと早くなるけど
0033デフォルトの名無しさんNGNG
>>30
とまってないよ…
それってどんな値でも 0にならないか？
0034デフォルトの名無しさんNGNG
http://www.dd.iij4u.or.jp/~okuyamak/Information/xor_fixed_swapping.html
0035間違ってたしNGNG
b = 7 << 28; //28は適当
while( a < 7){
　if( a >= b ) a-=b;
　b = b >>1;
}
0036また間違ってたしNGNG
a>7ね
0037デフォルトの名無しさんNGNG
>>31
整数演算ならマトモなコンパイラは関数呼び出しなんてやりません

そして整数演算ならオーバーフローしてもこの演算は必ず復帰しますよ

ってもしかして縦読み？
003831NGNG
>>37
復帰するんだ。考えんかった。
0039デフォルトの名無しさんNGNG
>>38 ２次フィルターなんか (1-2Z+Z^2)/(略)、みたいな
感じだから途中オーバフローする訳だけど、結果さえ収まっていれば正しく計算出来るよ
0040デフォルトの名無しさんNGNG
>>34
単独なら意味ないかもしれないけど

ttp://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm

小さい方の絶対値を 1/2にして大きい方に足して返すらしい

ihypot(int a,int b)
{
a=abs(a);
b=abs(b);
{ register w=( ( a-b ) >> 31 ) & ( a^b ); /* a>bなら w=0 */
return ( a^w )+( b^w )/2;
}
}
0041デフォルトの名無しさんNGNG
なるべく短い行数でソートプログラム書いて
実行速度よりも行数優先で。

５個の変数（配列でも可）を昇順で。

どの言語でも簡単に応用できる程度にね。
0042仕様書無しさんNGNG
>>41がエラそうだけどやってみよっと
0043デフォルトの名無しさんNGNG
>>41　動かんかな？
void SortIntArray(int n, int dt[])
{int i,j:
　for(j=0;j<n;j++)
　for(i=1;i<n;i++)
　{ int w=(dt[i] ^ int[i-1]) & ((dt[i]>int[i-1])*-1) ; //確か 条件式の結果は１か0だったよね？
　dt[i]^=w;
　dt[i-1]^=w;
　}
}
0044デフォルトの名無しさんNGNG
>>41
まっ課題としては面白いんだけど、実用的じゃないんだよな。
004543NGNG
手元にあった Delphi6パーソナルで検証したコード

procedure SortIntArray(var dt:array of Integer);
var i,j,w:Integer;
begin
for j:=0 to High(dt)-1 do
for i:=j+1 to High(dt) do begin
　 w:=(dt[i] xor dt[j]) and ( ord(dt[i]>dt[j])*-1 );
　 dt[i]:=dt[i] xor w;
　 dt[j]:=dt[j] xor w;
end;
end;

ord(dt[i]>dt[j])*-1 を　減算してボローを見るアセンブラコードにすれば分岐無しソートになるぞ
0046デフォルトの名無しさんNGNG
やっぱ行数優先だったらバブルソートとXORの値交換だよな
その他のアイディアは無しか。
一応私も
#include <stdio.h>
#define sw(a,b) (a^=b,b^=a,a^=b)
int d[5]={42,11,56,34,22};
int main(){
int i,j;
for(i=4;i>0;i--)for(j=0;j<i;j++)if(d[j]>d[j+1])sw(d[j],d[j+1]);
for (i=0;i<5;i++)printf("%d\n",d[i]);
}
gccで検証
0047デフォルトの名無しさんNGNG
じゃ　速度優先だと？

void SortIntArray5(iint dt[5])

配列サイズは固定で
0048デフォルトの名無しさんNGNG
>>47　環境によって違うからねえ
　メモリアクセスコストが大きいなら比較して 5!=120通りに分岐するのが最速だし
　そんなコード見たい？
0049デフォルトの名無しさんNGNG
key = dt[0]&0xffff +
( (dt[1]<<16)&0xffff0000 )+
( (dt[2]<<16)&0xffff00000000 )+
( (dt[3]<<16)&0xffff000000000000 )+
( (dt[4]<<16)&0xffff0000000000000000 );

dt[0]=kotae[key][0];
dt[1]=kotae[key][1];
dt[2]=kotae[key][2];
dt[3]=kotae[key][3];
dt[4]=kotae[key][4];

kotae_table[100000000000000000000][5]={
.....
};



0050デフォルトの名無しさんNGNG
( (dt[1]<<16)&0xffff0000 )+
( (dt[2]<<32)&0xffff00000000 )+
( (dt[3]<<48)&0xffff000000000000 )+
( (dt[4]<<64)&0xffff0000000000000000 );
に訂正
0051デフォルトの名無しさんNGNG
(´Д`)・・・
0052デフォルトの名無しさん 　NGNG
うまい棒１０本買うときに、
レジ１０回通れば消費税がかからないよ。
0053デフォルトの名無しさんNGNG
>>52
示唆に富んでるなぁ…

葉書10枚を送れば500円かかるけど、
その葉書10枚を封筒に詰めて送れば500円はかからないよ。
0054デフォルトの名無しさんNGNG
>>53
某クロスワードの雑誌にはその方法を使うとよいと書かれているね。
0055デフォルトの名無しさんNGNG
普通はがき10枚はそれぞれ別の宛先に送るんじゃ…
0056デフォルトの名無しさんNGNG
>>55
懸賞とか。
0057デフォルトの名無しさんNGNG
じゃ>>29 のように a % n を a and(n-1) で代用出来るかどうか　
　つまり n が２のベキかどうかを高速に判定する方法

・・・これはスレも立ったことある問題だから知ってる人は多いかな？
0058デフォルトの名無しさんNGNG
官製はがき１０枚を封筒に入れて送ると５００円以上かかるという罠
0059デフォルトの名無しさんNGNG
BOOL IsBeki( int a ){
　int b=0;
　while( a!=0 ){
　　if( a&1 ) b+=1;
　　a = a >>1;
　}
return( b==1 ); //BOOLで返すの作ったこと無いので間違ってるかも
}
0060デフォルトの名無しさんNGNG
ああ、もっと速いアルゴリズムあるね。
0061デフォルトの名無しさんNGNG
送り主のところに宛先を書き、切手を貼らずにポストに投函するとどうなりますか?
0062デフォルトの名無しさんNGNG
サンタクロースに届けられます
0063デフォルトの名無しさんNGNG
良すれあげ。
0064デフォルトの名無しさんNGNG
BOOL IsBeki( int a ){
　int b=a;
　a |= (a>>16);b += (b>>16);
　a |= (a>>8);b += (b>>8);
　a |= (a>>4);b += (b>>4);
　a |= (a>>2);b += (b>>2);
　a |= (a>>1);b += (b>>1);
　return( (a==b) || (a==0) );
}
0065デフォルトの名無しさんNGNG
　return( (a==b) || (a!=0) );
0066もーわけわからんNGNG
return( (a==b) && (a!=0) );
0067デフォルトの名無しさんNGNG
>>64 苦労してるね　答えは　たった1行で判定出来る

じつは >>57 そのものがヒントになってるよ

もっとヒント出すと　逆に a% n == a &(n-1) になる nが必ず２のベキであるaの値は？
0068ひよこNGNG
このスレずっとみてたけどぜんぜんわからん。
>>1のですら実験してみるまでわけわかんなかった。

a^=b^=a^=bもやっと意味わかった程度。

ビット演算なんかぜんぜんわからん。

みんなどーやって考えてるの。
よいページあったら教えてー。
0069デフォルトの名無しさんNGNG
そんなサイトあったらこんんあスレ立たないよ
つーか分からないんだったら素直に普通のコーディングしてれ。
007067NGNG
さらにヒント a% n == a &(n-1) で a=n　と代入してみよう
0071デフォルトの名無しさんNGNG
なんか素直にやったら一行になった。

return (a > 0 && (a | (a - 1)) == (a + (a - 1))) ? 1 : 0 ;

答えはもっと簡単？
007267NGNG
>>71
　違う答え用意してたけど　それでいいよ

用意してたのは
＝＞ (a>0) && ( 0 == (a&(a - 1) )

0073デフォルトの名無しさんNGNG
そっちの方が簡単だねえ。
a & (a - 1)は、他にも0になる値がありそうな気がして、
何となく避けてしもた。んなこたない
0074デフォルトの名無しさんNGNG
このネタスレみておもいついたんですけど、
多倍長計算のクラスをC++で組むときには
void Change(HOGE hoge1,HOGE hoge2);
みたいのを作っとくと後々便利ですかね？
hoge1 = temp;hoge1 = hoge2;hoge2 = temp;とかやると
メモリ確保とメモリコピーに無駄に時間がかかりそうなので。

0075デフォルトの名無しさんNGNG
std::swap を使って書いておいて、必要なら多倍長数クラス用に特殊化すれば良いのでは。
スレの趣旨とは違うｶﾞﾅｰ
0076デフォルトの名無しさんNGNG
sqrt() を使わずに hypot() を実装する方法 :
ttp://research.microsoft.com/~hollasch/cgindex/math/pythag-root.txt
0077デフォルトの名無しさんNGNG
>>74
多倍長というかある程度のサイズのオブジェクトはポインタで管理し、インスタンスは動かさないのが基本
0078デフォルトの名無しさんNGNG
しかし交換のつもりでchangeなんて命名するか…
007974NGNG
ボクドキュソなんで英語わかんないんです。
Commutation(HOGE hoge1,HOGE hoge2);
でかまいませんか？
0080デフォルトの名無しさんNGNG
しかし交換のつもりでCommutationなんて命名するか…
0081デフォルトの名無しさんNGNG
交換は swap か exchange が普通。
commutation にも確かに交換という意味はあるけど、
プログラムで使ってるの見たことない。
0082デフォルトの名無しさんNGNG
>>74
自力でそういうことを考えたのは偉いと思う。
だけど、C++の良書にはそういうテクニックは普通に
載ってる。買って読もうな（推薦図書スレに行くべし）。

ちなみに、ホントに交換したいなら、

void Hoge::swap(const HOGE& hoge);

というメンバ関数にするのが一般的。
0083デフォルトの名無しさんNGNG
>>82
const相手のswapできるのかと
008482NGNG
>>83
マジボケだ。すまん。
0085デフォルトの名無しさんNGNG
RGB565 形式の　アルファブレンドってのは　ありきたりすぎ？

MSB　　　LSB
　R:5 G:6: B:5

でR,G,Bのそれぞれ平均を求める計算
0086デフォルトの名無しさんNGNG
つか、今時のカードって殆ど555でないの？
0087デフォルトの名無しさんNGNG
>>86　そうなの？
ttp://www.geocities.co.jp/SiliconValley-PaloAlto/5989/trans01.html

とかで565でやってたから 565が多いのかと思った

じゃ 555で
0088デフォルトの名無しさんNGNG
>>1へ
a=a xor b
b=a xor b
a=a xor b
オーバーフローしない処理
0089デフォルトの名無しさんNGNG
DirectX8が動くのなら555がないのはあっても565がないものはない
0090デフォルトの名無しさんNGNG
>>85
それってアルファブレンドじゃなくて単なる半透明
0091デフォルトの名無しさんNGNG
じゃあ 565 で　アルファブレンドと　半透明の両方を
0092デフォルトの名無しさんNGNG
あのさ、 565とか555とか関係なんだよ

R,G,Bを その2^ビット位置として

　r1*R+g1*G+b1*B　が１ワードだとすると0<=α<=1の範囲なら

(r1*R+g1*G+b1*B)*α+(r2*R+g2*G+b2*B)*(1-α)

つまり、ビット位置に関係なく一つのワードとして処理すればいいんだよ
009392NGNG
なんか判り難いな

つまり
int HarfBlend(int a, int b){ return ((long)a+(long)b)/(long)2;}

と書いておけば 565でも555でも888でも正しく動くという事
0094デフォルトの名無しさんNGNG
>>92
桁上がりが起きたら破綻するから駄目
0095デフォルトの名無しさんNGNG
桁上がりじゃなくて 　余りが下位に入ってしまうからダメ
0096デフォルトの名無しさんNGNG
余りの問題を解決する為に LSBが片方だけ1の時だけ事前に各LSBゼロにしておくというのがセオリー

論理演算でやるなら
888なら mask=(not ((a xor b) and $010101)) とマスクビットを用意して

return ( (mask and a)+(mask and b) )>>1;

0097デフォルトの名無しさんNGNG
ｵｵｳ　ﾌｧﾝﾀｽﾃｨｸ!
0098デフォルトの名無しさんNGNG
この人が　そういう手法の元祖だと主張しております

ttp://www.emit.jp/prog/prog_b.html
009996NGNG
>>98
＞v2 = (v0 & v1) + (((v0 ^ v1) & 0xfefefefe) >> 1);

すごいね５演算か 　>>96のは7演算・・・完全に負けた
0100デフォルトの名無しさんNGNG
>>92の頭のほうがﾌｧﾝﾀｽﾃｨｯｸだ。
0101デフォルトの名無しさんNGNG
まさか特許とか取られてないよな。
■ このスレッドは過去ログ倉庫に格納されています