＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズ ..

2:デフォルトの名無しさん
04/06/03 23:18
( ´∇｀)y-~~~ ﾍｪ...

3:デフォルトの名無しさん
04/06/03 23:20
2GETTER用のプログラム作ってみました。要りますか？

4:デフォルトの名無しさん
04/06/03 23:20
いるいる

5:デフォルトの名無しさん
04/06/03 23:23
URLﾘﾝｸ(www2.famille.ne.jp)

6:デフォルトの名無しさん
04/06/03 23:27
↑↑概論↑↑

7:デフォルトの名無しさん
04/06/03 23:37
pc5鯖を潰すｱﾙｺﾞﾘｽﾞﾑ募集してます

8:デフォルトの名無しさん
04/06/04 01:19
奥村先生のアルゴリズム事典はぼろぼろになるまで読んでたな。

9:デフォルトの名無しさん
04/06/04 19:33
>>8
僕のは、まだ新品同然です。
この本の内容を、あらかた覚えるにはどれくらいの月日がかかったのでしょうか？

10:デフォルトの名無しさん
04/06/04 20:04
アルゴリズムといえばコーマン

11:デフォルトの名無しさん
04/06/04 21:24
>>9
あの本は事典ですよ？

12:デフォルトの名無しさん
04/06/05 11:48
ｱﾙｺﾞﾘｽﾞﾑって何ですか？

13:デフォルトの名無しさん
04/06/05 13:40
>>12
ゴリズム氏が考え出したとある手法の一つです。

14:デフォルトの名無しさん
04/06/05 14:15
>>13
ちがうよ。
１６世紀、オーストリアのディマン＝アルゴが提唱した基礎的な音楽のリズムだよ。

15:デフォルトの名無しさん
04/06/05 14:36
違うよ、ギタリスト　アル・ディメオラの弟ゴリズムが生み出した新しいリズムだよ、

16:デフォルトの名無しさん
04/06/05 15:08
(#ﾟДﾟ) ムズリ、ｺﾞﾙｧ!!! .←ムズリ（タンザニア出身）

17:デフォルトの名無しさん
04/06/05 19:40
>>11
事典として使うものですか。。。
どうりでいっぱいある訳だ

18:デフォルトの名無しさん
04/06/05 23:38
>>8
あれのJava版についてはどう思うよ？
アルゴリズムが増えて改良されてなかなかのもんだと思うが。
しかしあの本のソースコード書いた香具師は
クラス継承の合理的な使い方を分かってない感じだな。

19:デフォルトの名無しさん
04/06/05 23:51
いや、アルゴリズムとはアル　ゴア元副大統領の異名のことだよ　

20:デフォルトの名無しさん
04/06/06 00:05
ある御リズム

21:デフォルトの名無しさん
04/06/06 00:12
アルゴリ＝ズム＝ダイクン

22:デフォルトの名無しさん
04/06/06 02:04
>>18
Java版出てるの知らんかったよ。今度買ってみる。

23:デフォルトの名無しさん
04/06/06 03:49
くぬーすセンセが新刊だされるのが遅すぎるのでmitので我慢してね♪

24:デフォルトの名無しさん
04/06/06 18:30
いまだにバブルソートをバルブソートと言い間違えてる奴大杉

25:デフォルトの名無しさん
04/06/06 19:18
どんなソートだ

26:デフォルトの名無しさん
04/06/06 19:22
イング兵衛のバンドに昔いた奴か

27:デフォルトの名無しさん
04/06/06 19:49
URLﾘﾝｸ(www.google.co.jp)

そんなに多くないよ

28:デフォルトの名無しさん
04/06/06 20:40
奇特なひとだねぇ

29:デフォルトの名無しさん
04/06/06 23:20
>>1
そんなに暇ならコードの一つぐらい覚えろ
他力本願野郎がｗ

30:デフォルトの名無しさん
04/06/06 23:35
なんてねｗ

31:デフォルトの名無しさん
04/06/19 11:05
>>25
ブルーベレーちゃんが手作業で並べ替えてくれまつ。
URLﾘﾝｸ(valve.kubota.co.jp)

32:デフォルトの名無しさん
04/07/06 13:04
強固なスレだね。

33:デフォルトの名無しさん
04/07/06 13:10
ビリーフプロパゲーション（Belief Propagation）
計算確率アルゴリズムについて、知っている人、または
説明があるサイトをご存知の方は教えてください
お願いします。

34:デフォルトの名無しさん
04/07/06 14:21
ファイルをパースして読みこむプログラムを教えてください

35:デフォルトの名無しさん
04/07/07 17:22
>>34
どうやってファイルに遠近感を付けるというのだ！

36:デフォルトの名無しさん
04/07/07 17:30
言いたいことはメール欄に書けばいいと思ったら大間違いだぼけ
と言ってみるﾃｽﾄ

37:デフォルトの名無しさん
04/07/07 17:47
parse

38:デフォルトの名無しさん
04/07/08 23:04
あの本は聖典なんだけど、それが何か？

39:デフォルトの名無しさん
04/07/08 23:05
アルゴリズムを使って、　まそこん　を造りたいのですが

40:デフォルトの名無しさん
04/07/08 23:15
何がひつようでしか？ΛΛ
　　　　　　　　　・　・
　　　　　　　　　　△
　　　　　　　　　　ЦЦ　　

41:デフォルトの名無しさん
04/07/09 22:21
多次元配列をソートするのに、いいアルゴリズムはないですか？

42:デフォルトの名無しさん
04/07/09 22:25
多次元だろうが1次元だろうがソートアルゴリズムは殆ど一緒だろ。
それともキーが多次元でランダムなのか？

43:ケンや
04/07/09 22:39
俺にウィルスちょうだい。
パソコン買い換えるので何とか壊してください。
happy-days1989@zpost.plala.or.jp

44:デフォルトの名無しさん
04/07/24 16:07
□□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□
□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□

45:デフォルトの名無しさん
04/07/24 18:54
>44

46:1
04/07/25 11:06
ｽﾚﾘﾝｸ(tech板:1番)
ついに強固なスレが現れました

47:1
04/07/25 11:08
□□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□
□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□です。

48:デフォルトの名無しさん
04/10/01 11:12:36
バブルソートってどんなときに使うの？

49:デフォルトの名無しさん
04/10/01 12:08:21
>>48
教育用？

クレオソートってどんなときに使うの？

50:デフォルトの名無しさん
04/10/01 12:58:46
>>49
> クレオソートってどんなときに使うの？
下痢止めの薬を作るとき、かな。

51:デフォルトの名無しさん
04/11/08 22:59:22
>>48
使うときほぼないけど、学習用によく使われるみたい。

52:1
04/11/08 23:05:17
おいっ！おまいら！大変です！
バルブソートでググったら、なんとこのスレが２番目にあったよ

53:デフォルトの名無しさん
04/11/09 17:05:25
#include <algorithm>

54:デフォルトの名無しさん
05/01/30 17:56:48
age

55:デフォルトの名無しさん
05/03/08 22:07:30
自前で簡単なオーディオミキサを作りたいのですが、どんなアルゴリズムにすれば良いのでしょうか。

サンプリングレートは8000。
チャンネルは1つ(モノラル)。
ビット数は16。
音声データは160バイト(20[ms])に細かく切られている。

これが複数の音源からやって来ます。
複数の音源の同期は取りません。取り敢えずタイミングは無視してミックスします。
同期よりも遅延の方を問題に思っていますので。

こんな感じで良いのでしょうか？
for( int i = 0; i != 160; i++ )
　　if( buffer_1[i] < buffer_2[i] )
　　　　buffer_o[i] = buffer_2;
　　else
　　　　buffer_o[i] = buffer_1;

その後でDirectXでストリーミング再生します。

56:55: 訂正
05/03/08 22:08:24
for( int i = 0; i != 160; i++ )
　　if( buffer_1[i] < buffer_2[i] )
　　　　buffer_o[i] = buffer_2[i];
　　else
　　　　buffer_o[i] = buffer_1[i];

57:デフォルトの名無しさん
05/03/09 00:07:52
アルゴリズムと言うよりも、スレッドとかノンブロッキングとかデバイスの扱いでは？
DirectXとかよくわからんけど

58:55
05/03/09 00:37:21
すみません。要点がはっきりしてませんでした。

ポイントは、音源Aと音源Bのデータをミックスする時にどの様にすべきかです。

例えば以下の様な事が単純に思い付きます。

1.AとBの平均を取る。
out=(A+B)/2

2.AとBを単純に足す。最大値を越えた場合(65535<(A+B))は最大値(==65535)とする。
out=max(65535, A+B)

3.AとBを比較して、大きい方の値とする。(>>56の内容に等しい)
out=max(A, B)

良く分かりませんが、他にもっとインテリジェンスなやり方が有ったら教えて頂きたいなあと思った次第です。

59:デフォルトの名無しさん
05/03/09 00:51:31
out=a*A+b*Bでいいんじゃないの？
(a, bは入力レベル。通常は1でいいと思うけど、音割れするようだったら絞ればいい)

60:55
05/03/09 01:03:55
ありがとうございました。

実はRTPもどきを使って3人以上で会話するってプログラムを作ってました。
会話の場合は、1人が喋っていても他の2人は無音の場合が多く、>>59のやり
方で問題無いと思います。

61:デフォルトの名無しさん
05/04/04 15:57:46
ええとね。
サウンドプログラミング2
ｽﾚﾘﾝｸ(tech板)
で聞いてくれれば良かったかもな。

問題は、複数の音源の場合、サンプリングレートが微妙に違う点にあると思うよ。
まあ、無音の間に適当に入れたり出したりして誤魔化すんだろうけど

62:デフォルトの名無しさん
05/04/04 16:01:51
で、そいう場合は
out = r*(A+B);
if( abs(out)>=0x7fFF) r = r*0.95 else r=min(1.0, r+1/8000);

こんな感じで、合成音がクリッピングしたら、出力を絞るような方式がいいと思うよ。

63:デフォルトの名無しさん
05/04/30 22:21:53
よく、テキストの機能とかにある無限アンドゥってどんなアルゴリズムなんでしょうか？教えてください

64:デフォルトの名無しさん
05/04/30 22:25:14
ユーザーが入力した内容のログを全部取っておくだけの事。

65:デフォルトの名無しさん
05/04/30 22:37:29
安藤がきたら、挿入なら削除というようにログの逆を辿る。
Redoはログからもう一度ユーザーの内容を再現していく。
うまく動くと面白いし、何かを編集するアプリなら必須機能の１つ。
がんばって作ってくれ。

66:デフォルトの名無しさん
05/04/30 22:56:45
クリックやキー入力のイベントが起こったとき
現在の状態を全部ファイルにバックアップする

67:63
05/04/30 23:00:56
とりあえず処理の検討はつきました。どうもです

68:デフォルトの名無しさん
05/05/01 12:54:00
クヌース先生のアルゴリズムのバイブルを買うと馬鹿にされますか？

69:デフォルトの名無しさん
05/05/01 13:11:04
>>64,66

70:デフォルトの名無しさん
05/05/01 13:15:15
保管するだけでも場所とって大変だから、
図書館から借りてくることをオススメする

71:デフォルトの名無しさん
05/05/02 01:03:58
>>68
されません

72:デフォルトの名無しさん
05/05/02 19:34:01
マインスイーパーで裏返したセルが0だったときのアルゴリズムおせーて

73:デフォルトの名無しさん
05/05/02 19:47:56
>>72
m_buttonHogeを用意しといて
if(stCell == 0)
　　m_buttonHoge(FALSE);
else
　　m_buttonHoge(TRUE);

ってな感じでは？

74:デフォルトの名無しさん
05/05/02 19:49:54
ﾌﾟ(AA略

75:デフォルトの名無しさん
05/05/02 19:53:44
マインスイーパーって裏返したのが0だったら周りの0も連鎖して裏返るんだよね
そこが難しいんです

76:デフォルトの名無しさん
05/05/02 19:56:24
>>73
m_buttonHogeを用意しといて
if(stCell[x][y] == 0)
　　m_buttonHoge.ShowWindow(FALSE);
else
　　m_buttonHoge.ShowWindow(TRUE);
のまちがいだろ

77:デフォルトの名無しさん
05/05/02 20:03:22
BOOL reverse(int x, int y)
{
　　if(stCell[x-1][y-1]
　　　　m_buttonHoge[x-1][y-1].ShowWindow(FALSE);
　　else
　　　　m_buttonHoge[x-1][y-1].ShowWindow(TURE);
　　if(stCell[x][y-1]
　　　　m_buttonHoge[x][y-1].ShowWindow(FALSE);
　　else
　　　　m_buttonHoge[x][y-1].ShowWindow(TURE);

　　if(stCell[x][y-1]
　　　　m_buttonHoge[x][y-1].ShowWindow(FALSE);
　　else
　　　　m_buttonHoge[x][y-1].ShowWindow(TURE);

　　if(stCell[x+1][y-1]
　　　　m_buttonHoge[x+1][y-1].ShowWindow(FALSE);
　　else
　　　　m_buttonHoge[x+1][y-1].ShowWindow(TURE);

以下略
　　return TRUE;
}

78:デフォルトの名無しさん
05/05/02 20:09:35
裏返す
↓
０だ
↓
周りを探す
↓
また０だ
↓
周りを探す
↓
・・・・・・元の場所わかんねぇ('A`)

79:デフォルトの名無しさん
05/05/02 20:18:10
>>77
reverse(0, 0);
は大丈夫なのかな？

80:デフォルトの名無しさん
05/05/02 20:25:38
77ですが
>>79
TRY CATCHでくくって例外は処理しないようにすれば？

81:デフォルトの名無しさん
05/05/02 20:32:24
>>80
TUREって何よ？

82:デフォルトの名無しさん
05/05/02 20:33:16
>>81
つまんねーレスすんなよ。

83:デフォルトの名無しさん
05/05/02 20:41:59
http://から始まる文字列があった場合に<a href="hoge">hoge</a>に痴漢するアルゴリズム教えてください。
アドレスと文字列の区別は・・・どうするのが一般的？
2バイト文字にぶち当たったらとかかな。

84:デフォルトの名無しさん
05/05/02 20:44:22
>>81
"つれ"た、ってことなんじゃ？

85:デフォルトの名無しさん
05/05/02 22:39:55
>>83
sedでよければｗ

86:デフォルトの名無しさん
05/05/02 22:47:57
>>・・・・・・元の場所わかんねぇ('A`)　
そこで再帰関数ですよ。

こんな感じだったけなぁー。
なんせ3年前位に作ったやつだから忘れちゃってる。
間違ってる可能性大
int　hoge(int　x,int　y){
　　　　int　b=0;
　　　　if(table[x][y]　==　BOME){
　　　　　　　　　return　BOME;
　　　　　}
　　　　　for(int　i=0;i<9;i++){
　　　　　　　if(table[pos[i].x+x][pos[i].y+y]==BOME){
　　　　　　　　　　b++;
　　　　　　　　}
　　　　　　}
　　　　　　if(b==0){
　　　　　　　　　for(int　i=0;i<9;i++){
　　　　　　　　　　　hoge(pos[i].x+x,pos[i].y+y)
　　　　　　　　　}
　　　　　　}
　　　　　　return　0;
}

87:デフォルトの名無しさん
05/05/04 21:48:03
コムソートってどんなソートなのでしょうか？
ググってもでてきません。よろしくお願いします。

88:デフォルトの名無しさん
05/05/04 21:50:41
>>87
検索が下手。

URLﾘﾝｸ(www.google.co.jp)

89:デフォルトの名無しさん
05/05/04 23:06:09
>>87
URLﾘﾝｸ(www.ffortune.net)

90:デフォルトの名無しさん
05/05/04 23:52:38
>>89
ありがとうございます。
でもできたら参考文献とかあったらうれしいな、なんて

91:デフォルトの名無しさん
05/05/05 00:02:29
参考文献などない！

92:デフォルトの名無しさん
05/05/05 00:12:42
コムソートの利点はリソース消費しないってとこだね。

Comb sort algorithm
URLﾘﾝｸ(www.google.co.jp)

93:デフォルトの名無しさん
05/05/05 04:30:23
学生の宿題を手伝うスレｗ

94:デフォルトの名無しさん
05/05/07 20:38:46
数値を格納した二つの配列があり、
その二つの配列に共通する数値のみを選び出す効率的なアルゴリズムって何かありますか？

95:デフォルトの名無しさん
05/05/07 21:17:43
>二つの配列に共通する数値
a.格納位置も一緒
b.格納位置が違っていてもＯＫ

b.だとすると数値がダブっている場合どう考えるんだ？

96:デフォルトの名無しさん
05/05/08 05:15:32
ハッシュテーブルかな
衝突がなければO(1)

97:デフォルトの名無しさん
05/05/08 07:11:44
>>96 でいいとおもうけど、別案

片方で分布数えソートの前段階（分布だけ調べる）まで行い、
もう片方をスキャンすれば、重複する値がわかる

98:デフォルトの名無しさん
05/05/08 12:50:16
>>96
配列に格納されている数値が何かのハッシュだったら、どうするの？

99:デフォルトの名無しさん
05/05/08 15:42:48
>>98
内容がなんであっても、ハッシュで問題ないと思うがどうだろう？

100:デフォルトの名無しさん
05/05/13 13:47:35
ユーザーがマウスを用いてフリーハンドで引いた線を、
複数のベジェ曲線へと変換するアルゴリズムって何かありますか？

URLﾘﾝｸ(www.simdesign.nl)
上記のような有料のライブラリは見つかったのですが・・・。

101:デフォルトの名無しさん
05/05/13 15:56:51
>>100
そのサンプリング点を端点に、
端点の微分が一致するという条件で解いたらどう？

102:デフォルトの名無しさん
05/05/13 16:00:58
>>100
URLﾘﾝｸ(www.tensyo.com)
ここの折れ線から滑らかな曲線にという所に、点を与えながら処理する方法が

103:デフォルトの名無しさん
05/05/15 19:46:06
コンドーム

104:デフォルトの名無しさん
05/05/17 09:09:03
URLﾘﾝｸ(www.tensyo.com)
ここの　折れ線から滑らかな曲線に　以外に
複数のベジェ曲線へと変換するアルゴリズムって何かありますか？

105:デフォルトの名無しさん
05/05/17 23:45:00
手書き

106:デフォルトの名無しさん
05/05/18 07:29:50
>>104
それ以外にと聞かれるならば
１、３次スプライン補間法で解いてからベジェに変換する
２、混合スプライン、ベーススプライン等で解いてからベジェに変換する

という方法が考えられます

107:デフォルトの名無しさん
05/05/20 09:14:39
ベジェ曲線を描くときにマウスが拾ったすべての点において
ベジェ曲線を描くのではなく、点を間引いて描きたいのですが、
どのように点を間引いたらいいかがわかりません。
何か良いアイデアはありませんか？

108:デフォルトの名無しさん
05/05/20 23:32:01
3点支持

109:デフォルトの名無しさん
05/05/21 08:38:54
どのように間引くかと聞かれても、　どうしたいのか判らないので困ってしまう

たとえば、直線的に引いた通過点を間引きたいならそうすればいい
　前２点の延長線からの誤差が一定いないなら、その前の点を除くとかさ

110:デフォルトの名無しさん
05/05/21 19:06:48
XMLデータの検索プログラムを作ろうと思っているのですが、
単純な検索はBtree*を用いて作成しましたが、XMLのある部分が合致するような
検索をする場合どのような手法があるのでしょうか？

111:デフォルトの名無しさん
05/05/21 19:44:10
基本的には文字列の検索と同じ方法になるだろうけど、それでは満足出来ないんだろうね。

となると、その部分をB木の検索キーに入れておくしかないかもな

112:デフォルトの名無しさん
05/05/21 20:40:13
そっかぁBtreeかRTreeで何とかするしかないようだな。どもです。
後差分を取る方法って今主流な方法でどのような方法があるのでしょうか？
XMLデータの差分を取ってみたいと思うのですがそっち方面は何もわかりません。

113:デフォルトの名無しさん
05/06/15 08:29:58
立っているビットの位置を調べるアルゴリズムで以下の物より高速な物はあるでしょうか？
int i=1;調べるビット列 bits;
while(i<sizeof(調べるビット列)*8+1){
if(bits%2){
cout << i << ",";
}
bits >> 1;
i++;
}
cout << endl;

114:デフォルトの名無しさん
05/06/15 11:51:50
>>113
while(bits!=0)
{
　　if(bits&1!=0)
　　{
　　　　cout << i << ",";
　　}
　　i++;
　　bits=bits>>1;
}
cout << endl;
上位がゼロになればそれ以上調べなくてもよい。
ビットが1つしか立ってないなら、二分探索が使えるが。

115:デフォルトの名無しさん
05/06/15 15:49:29
MSBだけ知りたい場合でもバイナリ検索が使えるよ

116:デフォルトの名無しさん
05/06/15 22:55:01
こういう小手先テクはトリッキースレにあった気がする

117:デフォルトの名無しさん
05/06/16 07:05:10
テーブル検索という方法もあるね。

118:デフォルトの名無しさん
05/06/16 09:34:53
>>110 XMLを一旦Prologの項に変換してassertして、
Prologの述語呼び出しや、述語定義の参照述語を使って
部分構造の検索をする。

119:デフォルトの名無しさん
05/06/24 07:20:01
m/123 * 100/101 < x1 < m/123 * 100/99
m/456 * 100/101 < x2 < m/456 * 100/99
m/789 * 100/101 < x3 < m/789 * 100/99

x1, x2, x3 に正の整数が含まれるm > 0の条件は？

120:デフォルトの名無しさん
05/07/09 20:48:02
>>110
全文検索系のアルゴリズムが参考になるんじゃない？
suffix tree とか suffix array とか。
ってもう一月以上前か。

121:デフォルトの名無しさん
05/08/26 11:16:09
ここでいいのかな。
パトリシアトライ木とハッシュテーブルを比較したら、
ハッシュの方が速い事が多いんですが、
こんなものでしょうか？（特に検索はハッシュが倍以上速い）

なんかパトリシアは苦労して作ったのにこれではちょっと納得いかなかったので。
パトリシアの枝を平衡木にすればマシになるのかな？

122:デフォルトの名無しさん
05/08/26 13:38:29
なんていうか、苦労と成果は単純に比例する物ではないと思いますハイ。

123:デフォルトの名無しさん
05/08/26 22:16:26
参考までにベンチ結果を載せておきます。
msは挿入、検索で、検索の速い順に並んでます。
データの種類にもよるでしょうが、自分が対象とするデータはほぼこの順位です。
検索ではTernary Search Trieが健闘してます。
でもtstとtrieはメモリ食います。

>tst (Ternary Search Trie)
55040 件辞書に登録しました。
1268ms
81ms

>hash
55040 件辞書に登録しました。
1224ms
82ms

>pat (Patricia)
55040 件辞書に登録しました。
1444ms
158ms

>trie (Trie)
55040 件辞書に登録しました。
1285ms
224ms

124:デフォルトの名無しさん
05/08/26 22:25:10
>>1
かまいたちの夜２のネタバレｷﾀ━━━(ﾟ∀ﾟ)━━━ !!

125:デフォルトの名無しさん
05/08/27 03:16:43
二次元座標に三点を直線状にならないようにとった。それらがなす三角形が、鈍角か鋭角かを座標情報を使って計算により判定する手続きを述べよ。

126:デフォルトの名無しさん
05/08/27 03:58:42
>>121
patriciaは辞書データ構造に使うんだよ
圧縮が効くしインクリメンタルサーチもできるという特性がある
hashはキーがまるごと必要でしょ

127:デフォルトの名無しさん
05/08/27 04:05:02
>>125
中学生か？

128:デフォルトの名無しさん
05/08/27 04:28:18
>>127
条件分岐は一回以下とする。

129:デフォルトの名無しさん
05/08/27 06:49:06
>>128
普通のパターンだと、条件分岐1回では直角三角形を分離できない（はずだ）けどいいの？
トリッキーにすれば、条件分岐を使わずにできるけど

130:デフォルトの名無しさん
05/08/27 07:26:28
>>125
は宿題の丸投げか？
自分で考えろよ

131:デフォルトの名無しさん
05/08/27 10:06:02
>>125
こんなものも自分ひとりで解決できないようじゃ先が思いやられるな

132:デフォルトの名無しさん
05/08/27 10:41:25
わかったー
cosA・cosB・cosC ＜ 0
なら鈍角だー

133:121
05/08/28 06:19:01
コード見直しでそれぞれ多少縮まりました。
tstがこれぐらい差が付くとhashの３倍はメモリ食っても使ってみたくなる。

>tst
57260 件辞書に登録しました。
1275ms
63ms

>hash
57260 件辞書に登録しました。
1284ms
78ms

>pat
57260 件辞書に登録しました。
1450ms
106ms

134:デフォルトの名無しさん
05/08/28 07:01:14
>>129
ピーキーなのきぼん

135:デフォルトの名無しさん
05/09/16 09:46:27
簡単なプログラムだと思うんですが、
なかなかいい方法が浮かばないんで、何かいい方法があれば
教えてください。

二次元配列のデータ
dat[i][j]

という200x200くらいのデータ（モノクロ画像データ）があります。
そのデータに対して、i,j面でスムージングをして、new_dat[i][j]
を作りたいのですが、どうするのが簡単で良い方法でしょうか？
簡単にスムージング（もどき）が出来るアルゴリズムをご存知の方が
居られれば教えてください。

136:デフォルトの名無しさん
05/09/16 10:01:42
スムージングって、ローパスとかノイズ除去する奴よね？
線形のローパスフィルタかけるか、中央値フィルタかけたら？

137:デフォルトの名無しさん
05/09/16 10:09:32
a00 = 4
a01 = 1
a11 = 1

{lon w
　w = a00*dat[i][j];
　w+= a01*dat[i][j+1]+a01*dat[i][j-1];
　w+= a10*dat[i+1][j]+a01*dat[i-1][j];
new_data[i][j] =w /(a00+2*a01+2*a10);
};
ってな所から始めたら?

138:デフォルトの名無しさん
05/10/22 08:57:26
アルゴリズムを勉強するのにいい本があったら教えてください

139:デフォルトの名無しさん
05/10/22 10:44:17
xって値を決める時に
if (x < 0) x = 0;
と
x = max(x, 0);
はどっちが優れてるの？

140:デフォルトの名無しさん
05/10/22 18:50:57
>>139
コンパイラによるだろmax関数の解釈とかは、
とりあえずアセンブラの出力を比べてみては。

141:デフォルトの名無しさん
05/10/22 19:23:39
>>139
最上位ビットを0にするのがいいんじゃないの？

142:デフォルトの名無しさん
05/10/22 19:45:38
>>139
if (x < 0) x = 0;

143:デフォルトの名無しさん
05/10/23 14:00:30
>140
アセンブラ読めない、頑張ってみた

---if(x<0) x=0;
+++x=max(x,0)

　　movl $1, -4(%ebp)
- cmpl $0, -4(%ebp)
- jns L2
- movl $0, -4(%ebp)
-L2:
+ movl $0, 4(%esp)
+ movl -4(%ebp), %eax
+ movl %eax, (%esp)
+ call _max
+ movl %eax, -4(%ebp)
　　movl $0, %eax

左の列が言わんとしてる事はわかるんですが、他は字に見えません
movlとjnsとcmplとcallがどれだけの奴か知らないので臨場感が伝わってきませんでした。

>142
おすすめのポイントはcallの有無？

>141
おー！と思ったけどビット演算は自分の脳に負荷がかかりました

とりあえず右の列
グーグルと一緒にとっつかまえてくる

144:デフォルトの名無しさん
05/10/23 20:02:39
>>143
max()自体が最適化されてcallがなくなる処理系もある。
>>142 は記述形式がアセンブラに一番近い、つまり

最適化の有無に因らず、どのような処理系でも
「一番速いコード」が生成される「はず」

が根拠だ。

145:デフォルトの名無しさん
05/10/23 20:54:55
計ってみればいいんじゃない

146:デフォルトの名無しさん
05/10/27 07:56:09
if (x < 0) x = 0;
つまり、ｘが負数ならゼロにするという事は、　２の補数表現であれば
xの最上位ビットが１の時に、xを0にすればいい。

よって x := x and (not (x asr 31) ) という計算と等価となる

　・符号拡張命令
　・バレルシフタ
　のどちらかを持っているCPU（x86は両方持ってる）なら
　符号拡張
　NOT
　AND
の３ステップで実現出来る

147:デフォルトの名無しさん
05/10/28 03:24:19
>>146
計算マンセーの前時代的思考方法だな。
xが整数型であると、どこに書いてある？
という、無駄な突っ込みは別として、その手の置き換えは
「必ず計算が実行される」と言う面から考えると、速くも、
また、美しくもない。

if (x < 0) x = 0;

は、しなくとも良い計算や代入は発生しない。
そう言った意味で

x := x and (not (x asr 31) )

は、問題外。

148:デフォルトの名無しさん
05/10/28 06:29:38
浮動小数点型でも符号ビットは最初にあるから同じ方式でいけるぞ。
だからもし突っ込むなら、　２の補数の方だろう

149:デフォルトの名無しさん
05/10/28 07:31:16
２の補数表現でも１の補数でも　if (x < 0) x = 0; という演算なら問題ない。
つまり >>147の前半の突っ込みは無駄ではなくて、無知なツッコミ。

後半もちょっと変
if (x < 0) x = 0; 　は表現であって、実際に分岐を指示しているわけではない。

この計算は賢いコンパイラなら
最近のX86に対応しているなら条件付代入命令に変換される可能性が高い
CMP
CMOVS
となる。
ちなみに、浮動小数点命令にも条件付代入命令はある

さて、分岐と演算命令のどちらが高速という話なら、
分岐命令は並列演算の妨げとなるが
演算命令は並列化可能な部分は並列化される故に
命令数が多少多くても現在でも分岐より演算が速く、将来はもっと高速になる可能性が大

並列処理のことを言わず、一昔前のCPUや現在のH8やSHでは
分岐命令は演算命令２～４つ分のコストを支払わされるのが普通

なお、この部分　x := x and (not (x asr 31) )　も　条件代入も並列化出来ないが
その次に同じような演算があれば先読み実行される可能性があるという事

150:デフォルトの名無しさん
05/10/28 16:21:10
どちらにしろ、ｘが32bitだという前提がないと成立しない
x := x and (not (x asr 31) )
は、問題外ということでよろしかったですか？

151:デフォルトの名無しさん
05/10/28 17:14:49
>>150
それがそのまま通る言語がそもそもないだろう。　あほか？

152:デフォルトの名無しさん
05/10/28 17:23:32
もともと>>139のような比較自体に意味がないし、
(x and (not (x asr 31))) が格別優れているわけでもなかろが、
>>150
ええと、>>147はまったく意味の無い記述とされてるし、
32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、
ようするにalgorithmなり記述を評価する能力無し、という告白でよろしいか?

153:デフォルトの名無しさん
05/10/28 17:30:27
まあ、少なくとも
x := x and (not (x asr 31) )
は、アルゴリズムじゃなくて「技」だしなあ。

154:デフォルトの名無しさん
05/10/28 17:38:39

x := x and (not (x asr　sizeof(x) )

155:デフォルトの名無しさん
05/10/28 17:48:12
という事で、C言語なら3項演算子を使え。　バカなコンパイラならインラインでCMOVを使えと

156:デフォルトの名無しさん
05/10/28 17:50:29
ABS　マクロなんかは、論理演算に変換されるね

覚えてないけど、符号拡張＋XORだったかな？

157:デフォルトの名無しさん
05/10/28 18:41:28
>>152
＞ 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、
さすがに、そんなコンパイラは使いもんにならないと思う。
31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する
となると、マジヤバイ。

>>154
えーと、１年生ですか？w

158:デフォルトの名無しさん
05/10/28 18:54:11
>>157
>31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する
!!!? バカ、マジヤバス。低脳乙www 終了。

159:デフォルトの名無しさん
05/10/28 18:54:21
x := x and (not (x asr BitSizeOf(x) )

160:デフォルトの名無しさん
05/10/28 18:55:31
x := x and (not (x asr log2(INT_MAX) )

161:デフォルトの名無しさん
05/10/28 18:56:51
x := x and (not (x asr ∞ ) )

162:デフォルトの名無しさん
05/10/28 19:14:01
x =( abs(x) + x ) /2

163:デフォルトの名無しさん
05/10/28 23:28:42
>>158
えーと、幼稚園ですか？w

164:デフォルトの名無しさん
05/10/29 00:12:48
>>157,163
おまえがなwww

165:デフォルトの名無しさん
05/11/03 23:15:11
( ´∇｀)y-~~~ へぇ

166:デフォルトの名無しさん
05/11/08 00:13:18
B-Treeを自分で書いて理解したいのですが、難しくてよくわからん。
アホ向けに解説してあるサイトか書籍ないでしょうか。

167:デフォルトの名無しさん
05/11/08 00:33:13
>>166
URLﾘﾝｸ(unit.aist.go.jp)

168:デフォルトの名無しさん
05/11/08 01:55:08
>>167
クノッピでBtreeが理解できるの?

169:デフォルトの名無しさん
05/11/08 05:05:57
>>164あたりまで

ともかくそんな高度な話題を論じれる貴方達を尊敬する。
俺にはついていけないよ。

170:デフォルトの名無しさん
05/11/09 00:00:21
>>166
読み辛いのなら、デバッガを使って変数の値を追っていくといい

171:デフォルトの名無しさん
05/11/10 01:14:30
すいません、「Universal hashing」について教えてくだせぇ。

URLﾘﾝｸ(lecture-wiki.ecc.u-tokyo.ac.jp)
このページにもその部分だけ書かれてなくて困ってます。
「平方採中法」とは違うものなんでしょうか？

172:171
05/11/10 04:11:50
自己解決しました

173:デフォルトの名無しさん
05/11/13 19:12:43
平衡木のAVL木において，バランスが崩れた場合に，単一回転と二重回転
によってバランスを保つことを勉強しました．

単一回転と二重回転の選択の判断ってどうしてるんですか?

174:デフォルトの名無しさん
05/11/13 20:25:30
>>173
その勉強した内容は、隅から隅まで読んでみたのかな？
たとえば次のページみたいに、普通は書いてあるよ。
URLﾘﾝｸ(lecture.ecc.u-tokyo.ac.jp)

175:& ◆i.twkzJbf.
05/11/13 21:41:13
>>174

大変，ありがとうございます!
図書館にあるアルゴリズムの本をあさり，「こういうパターン
の時は単一回転」という図は掲載されていたのですが，明確に
文章で書かかれているものが，無かったんです．

上記のURL には明確に文章で記載されていたので，理解できました．
ありがとうございました．

176:デフォルトの名無しさん
06/02/05 09:40:09
2

177:デフォルトの名無しさん
06/02/05 09:41:09
今春、情報処理試験受けてきます

178:デフォルトの名無しさん
06/02/15 22:05:35
誰かイージスシステムのアルゴリズムうｐしてよ。

できればCASL2形式のソースコードで頼む。

179:デフォルトの名無しさん
06/03/06 23:50:20
GDIのArcToってどういうアルゴリズムで実装されているかご存知の方いませんか？
また、ArcToを実装する場合、Google等でそのアルゴリズムの名前を検索するとヒット
するようなメジャーなアルゴリズムってあるのでしょうか？

今、DirectXを使用してVRAMに直接弧を描画する関数を作っています。
楕円描画のアルゴリズムを使用して、弧を描く関数自体はできたのですが、問題点として、

①　条件分岐が多くスパゲッチーなコードになる
②　○○のアルゴリズム、とかの名前で、世間一般に知られているかが分からず、
　　　スパゲッチーなコードでも、その内容を見た人が調べて把握できるかが不安。

今後の保守性に不安があるので、弧の描画に用いられている一般的な
アルゴリズムがあるなら、そちらに揃えたいです。
ないなら、多少速度を犠牲にしてもGDIのArcToを使ってしまおうかと悩みちゅうです。

180:デフォルトの名無しさん
06/03/08 11:31:54
DDA を使ってるなら、Bresenham　アルゴリズムとでも書いておけば判るだろう

181:デフォルトの名無しさん
06/04/05 02:28:16
ヒープを使えば最小値（もしくは最大値）を迅速に取り出すことができます。
しかし、ある条件を満たしている間は最小値を、
そうでない場合は最大値を取り出すとなると、効率のいい方法が思いつきません。
線形探索で最大値を探し出すことになってしまいます。

（ソースコードは以下のURL）
URLﾘﾝｸ(anotherred.hp.infoseek.co.jp)

なにかいい方法は無いものなのでしょうか。

182:デフォルトの名無しさん
06/04/05 02:32:24
(181の続き）
某ソフトのある部分と流れがそっくりですが・・・
そっくりそのままコピペしたわけではないので、
そこらへんは目をつぶっていただけるとありがたいです。

183:デフォルトの名無しさん
06/04/05 05:54:32
>>181
ようするに、最大値と最小値の両方を高速に取り出せるデータ構造か。

両方 O(1) で出来るものはしらんが、両方 O(log n) でできるものならB木の類。

184:デフォルトの名無しさん
06/04/05 12:56:41
あとは、データを最初にソートしておくか。

185:デフォルトの名無しさん
06/04/05 13:19:15
>>183
木構造ですか・・・
たしか、木構造を使用したデーターベース関連のソースがあるので、
速度のことさえ気にしなければいけそうですね。
ちょっとベンチマークを取ってることにします。
わざわざ答えてくださりありがとうございました。

>184
二分ソートを使うとなると、かえって遅くなりそう・・・
適切な位置を探すのにO(log n)
データの移動に最悪でO(n)
平均はいくらぐらいか知らないけど。

186:デフォルトの名無しさん
06/04/23 23:18:33
質問です。
0<= x < N までの値を巡回する式を作りたいのです。

用途としては、選択肢を指すカーソルが一番下まで行った時、さらに下ボタンを押すと一番上を指すように。
一番上まで行った時にさらに上ボタンを押すと、一番下を指すように。
という使い方です。

x = (x + N) % N;
でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
Nが2の乗数なら、マスクをとるという方法も思いつくのですが…。

何か定型的な方法はありますでしょうか？
x = ((x % N) + N) % N;
でもとりあえず良いのですが、かなり冗長に見えます。

187:デフォルトの名無しさん
06/04/23 23:39:39
>>186
> でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
つか、xが-N未満になりうる時点でバグってると思うが？
0<= x < N なんでしょ？

188:デフォルトの名無しさん
06/04/23 23:51:29
もう面倒だから素直に分岐つかえば
x　%　n　+　(x　<　0　?　n　:　0)

189:デフォルトの名無しさん
06/04/24 00:08:33
>>187
説明が下手ですいません。
xになにかしらの数が代入され、それをうまく 0<=x<N に丸め込みたいのです。

int hoge(int x)
{
while(x < 0) x += N;
x %= N;
return x;
}
とお考えください。

>>188
その式だと、ちょっとやりたいこととは違うようです。
whileやifを使わずに綺麗にやる式があれば…と思っているのですが

190:デフォルトの名無しさん
06/04/24 00:46:26
>>188 それ負のとき0が5になる

191:デフォルトの名無しさん
06/04/24 00:50:35
188のもあってるが、
＞x = ((x % N) + N) % N;
のほうが分岐無いだけ速くねーか

192:デフォルトの名無しさん
06/04/24 06:33:35
xは負数としてもそんな極端な負数にはならないんでしょ？

NM=INT_MAX/N;
として
x = (x + NM) % N;
でいいんじゃないの？

193:デフォルトの名無しさん
06/04/24 16:25:32
いまいちやりたいことがわからんが、
UIなら計算量をケチる必要性はないので多少冗長でもかまわないのでは。

xの初期値として
x = (x + N) % N;
が計算できて、xは以降、0<=y<N、という値が足されたり引かれたりするだけという状況を仮定すると、
(>>186だとそういう状況ですよね。xに乗除算は入ってこない)

x-yを行うときはx<yならばNを足してからyを引くでいいんでないかい。
除算よりも比較の方が圧倒的に速いから。

194:デフォルトの名無しさん
06/04/24 16:36:30
いや、それなら基本的に　
xが-N未満になど、普通はなりようがないのだ。
x <-Nになる事はないのだから用途的には
x = (x + N) % N; で何の問題もない。
過剰仕様といえよう。

もし、xがEPROMとかに保存されてる間にゴミと化しても変な事にならないようにという事なら
x を　符号無数とすればいい

195:デフォルトの名無しさん
06/04/25 00:18:10
360度 0～4095の値をとる円の時に、この問題に悩むな。
-500000とか入れられたときに、0～4095に直すとどうなるか。みたいな。
DWORDにする手もあるんだが、Javaだと符号intしかないからなぁ・・

196:デフォルトの名無しさん
06/04/25 06:36:53
0～4095なら　4095とのand でいいんだから、悩まないぞ

197:デフォルトの名無しさん
06/05/16 22:52:10
テキストの類似度を判定するアルゴリズムって、なんかいいのないかな。

leveshteinとかsimilar_textだと、"abcdefgh"と"hgfedcba"の類似性を
かなり低く見積もってくれたりするんだけど、人間の直感にマッチするような
アルゴリズムってないもんですかね。

198:デフォルトの名無しさん
06/05/17 10:17:58
人の直感がそれぞれだからねぇ

199:デフォルトの名無しさん
06/05/17 16:01:49
>>197
俺の直感だと、その2つは似てない

200:デフォルトの名無しさん
06/05/20 21:35:30
Oliver [1993] とか。
similar_text
URLﾘﾝｸ(jp2.php.net)

201:デフォルトの名無しさん
06/05/23 17:06:12
SoundEx　とかはどうなの？

202:デフォルトの名無しさん
06/05/30 16:49:01
複数の候補からランダムに選択させたいんですが、
そこに重み付けを導入する場合って、どんなアルゴリズムがあります?

203:デフォルトの名無しさん
06/06/08 07:54:15
誰か解答を求む！

C で文字列を比較するのは
(*(int *)s1) == (*(int *)s2)
これのほうが早い？

204:デフォルトの名無しさん
06/06/08 07:57:42
>>203
ここで聞く前に試したほうが早いし確実だと思うのは気のせいでしょうか

205:デフォルトの名無しさん
06/06/08 09:25:22
速いっつーか，間違ってねえか？

206:203
06/06/08 09:29:08
すいません、ミスです

207:デフォルトの名無しさん
06/06/08 10:42:46
切れ目探しで鬱になったけど早い事は早かった
間違ってるの？

208:207
06/06/08 10:47:38
ミスｗ

209:デフォルトの名無しさん
06/06/08 13:58:46
なるほど、疾いよ、strcmpの1/10になれる
これどのCPUでもいけるの？

210:デフォルトの名無しさん
06/06/08 15:47:53
まだ続けるのか？

211:デフォルトの名無しさん
06/06/22 15:26:03
奥村先生は放送大学に出演している。

212:デフォルトの名無しさん
06/06/22 15:47:54
>>211
ナイス情報サンクス｡
LATEXとＪＡＶＡかー｡
アルゴリズムキボンヌだなぁ｡

213:デフォルトの名無しさん
06/06/22 16:02:00
>>212
「JAVAによるアルゴリズム事典」はpLaTeXで書いたとちゃっかり宣伝していた。

214:デフォルトの名無しさん
06/06/25 00:14:43
B+-treeに関して説明してあるお薦めサイトか、
理解しやすいオープンソースプログラムってあります？

215:デフォルトの名無しさん
06/07/06 08:08:55
B木までは説明してるサイトでもB+やB*は名前がでてくるかどうかって感じだな

216:デフォルトの名無しさん
06/07/06 15:40:55
奥村先生はJAVAが出て来たとき世界は統一されたと思ったらしい。

217:デフォルトの名無しさん
06/08/06 13:40:04
さすが学者先生だな。
何かで世界統一されることなんてないよ。

218:デフォルトの名無しさん
06/08/06 17:01:29
>>216
ソースは？
解釈が間違っている可能性がある。

219:デフォルトの名無しさん
06/08/06 20:40:34
>>218
放送大学で言っていた。

220:デフォルトの名無しさん
06/08/12 09:04:26
遺伝的アルゴリズムは？

221:デフォルトの名無しさん
06/09/02 16:52:02
　　（　・∀・）　　　|　|　ｶﾞｯ
　　と　　　　）　　 |　|
　　　Ｙ　/ノ　　　人
　　　　 /　）　　 < 　>__Λ∩
　　＿/し'　／／. Ｖ｀Д´）/
　　（＿フ彡　　　　　　　/

222:デフォルトの名無しさん
06/09/14 01:08:00
GA ってこと?

223:デフォルトの名無しさん
06/09/17 22:57:32
格子点を、原点からの距離が小さい順に数え上げていくアルゴリズムをしりませんか？

簡単の為、問題を２次元にします。
この時、
(0,0)
(1,0)
(0,1)
(1,1)
(2,0)
(2,1)
(1,2)
(2,2)
・・・・・・・
という配列を得たいのです。

思いついた単純な方法は、
for(i =1; i < N ; i++)
for(j = 1 ; j < N; j++){
d = i**2 + j**2
arry.push([i,j],d)
}
sort arry by d
aryy.each { a
printt a
}
という方法ですが、あまりスマートとはいえないし、
同じ距離d (= 1)をもつ点(1,0),(0,1)がこの順で並ぶとは限らないという欠点があります。
（同じ距離を持つ(x,y)なら　x>=yというを満足する点からで並んで欲しい)

224:デフォルトの名無しさん
06/09/17 23:03:57
>>223
「安定なソート」でぐぐれ。若しくはC++のstd:stable_:sortで関数オブジェクトに
x>=yという条件を含めれば簡単。

225:デフォルトの名無しさん
06/09/17 23:04:27
×std:stable_:sort
○std::stable_sort

226:デフォルトの名無しさん
06/09/17 23:33:51
おもしろいな
群論とか使えばいけそうだが。。。
俺の知識では無理ｗ

227:デフォルトの名無しさん
06/09/17 23:42:44
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

struct MyComp {
bool operator()(const std::pair<double, double>& p1, const std::pair<double, double>& p2)
{
double d1 = p1.first * p1.first + p1.second * p1.second;
double d2 = p2.first * p2.first + p2.second * p2.second;

if (d1 < d2)
return true;
else if (d1 > d2)
return false;
else { // d1 == d2
if (p1.first < p1.second && p2.first > p2.second)
return false;
else return true;
}
}
};

struct MyOut {
void operator()(const std::pair<double, double>& p)
{
std::cout << '(' << p.first << ',' << p.second << ')' << std::endl;
}
};

次ページ