計算アルゴリズム【Ⅱ】

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 2chのread.cgiへ]
Update time : 01/02 08:46 / Filesize : 251 KB / Number-of Response : 871
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

計算アルゴリズム【Ⅱ】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ]: 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉

>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。

前スレ↓
pc8.2ch.net/test/read.cgi/tech/1090227743/
644 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 09:27:07 ]: >>642
そのとおり．
ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて
解が存在しても，収束するとは限らない．

いつ収束するかの厳密なところ（必要十分条件）は，現在でも未解決問題．
645 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 16:48:12 ]: >>644
639のこれは?

。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
646 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 17:10:06 ]: >>644
SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている
ωの値によって収束が左右される　0に近づければガウスザイデル法で無理な場合も収束するのでは?
647 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 20:15:14 ]: ω=1はガウスザイデル法である
648 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:51:21 ]: グレースケール変換。こいつより高速アルゴキボンヌ。
条件：徐々にグレースケール変換できればvolumeの持たせ方は自由

// 【メソッド名】convGrayScale
// 【引数説明】
// srcRGB：変換元画像(0xRRGGBBのピクセル配列)
// pixel_num：ピクセル数
// volume 0(無変換)～255(完全変換)の範囲でグレースケールに変換
// dstRGB：変換先(0xRRGGBBのピクセル配列)
649 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:52:02 ]: public void convGrayScale(int[] srcRGB, int pixel_num, int volume, int[] dstRGB){
　　int red, green, blue, Y;
　　for(int i=0; i<pixel_num; i++){
　　　　red = srcRGB[i] >> 16;
　　　　green = (srcRGB[i] & 0xFF00) >> 8;
　　　　blue = srcRGB[i] & 0xFF;
　　　　Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
　　　　if(Y > red){　// R成分の調整
　　　　　　red += volume;
　　　　　　if(Y < red) red = Y;
　　　　}else if(Y < red){
　　　　　　red -= volume;
　　　　　　if(Y > red) red = Y;
　　　　}
　　　　if(Y > green){　// G成分の調整
　　　　　　green += volume;
　　　　　　if(Y < green) green = Y;
　　　　}else if(Y < green){
　　　　　　green -= volume;
　　　　　　if(Y > green) green = Y;
　　　　}
　　　　if(Y > blue){　// B成分の調整
　　　　　　blue += volume;
　　　　　　if(Y < blue) blue = Y;
　　　　}else if(Y < blue){
　　　　　　blue -= volume;
　　　　　　if(Y > blue) blue = Y;
　　　　}
　　　　dstRGB[i] = (red << 16) + (green << 8) + blue;　// 変換結果
　　}
}
650 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:54:17 ]: あ、一応JavaだけどCとかでもおｋ
651 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 02:10:24 ]: volumeって要は、グレイ化度合いみたいなものなのね。
処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
652 名前：648 mailto:sage [2008/04/25(金) 03:08:47 ]: volumeって要は、グレイ化度合い⇒そのとおり！
volumeを255まで振る前にグレイになってしまう
⇒それは思ったけど、取り得る範囲がわからんかった。。。
　r=0,g=0,b=255、r=255,g=255,b=0の場合で29.191890～225.808365の範囲で196.616475がMAXかなぁ
振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
⇒ちょっとわからんkwsk
　ちなみに自分の使い方としては元画像srcRGBはずっと変えずにvolumeを増やす感じ
　だから一度変換したdstRGBをsrcRGBに使うことはない
653 名前：648 mailto:sage [2008/04/25(金) 03:15:22 ]: ちなみに、volumeを0～100%として

dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
　　　　　　(((Y * volume + green * (100 - volume)) / 100)<<8) +
　　　　　　((Y * volume + blue * (100 - volume)) / 100);

としたてみたけど、遅くなったorz
654 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 06:45:23 ]: Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
これの意味を教えて
655 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 06:54:50 ]: >>654
YUV とか色空間あたりでググって見たら、、、
wikipedia の「色空間」だとか
ofo.jp/osakana/cgtips/grayscale.phtml の 2.NTSC ～
にある式を小数点の無い形にしたと考えたらいいんじゃない?
656 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 07:26:42 ]: こういう時は
Y = (red * 19589+ green * 38444+ blue * 7503) / 0x10000;
か、
Y = (red * 77 + green * 150+ blue * 29)/ 256 ;

と２のベキにしたらどうかな　/256 は >>8 に出来る
8bitにすれば rgbも8bitだから 16bitの入れ物で計算出来る

dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
　　　　　　(((Y * volume + green * (100 - volume)) / 100)<<8) +
　　　　　　((Y * volume + blue * (100 - volume)) / 100);
もvolumeを２のベキにして
Y*k + X*(1-k) = X+(Y-X)*k なので

dstRGB[i] = ((( red + (( (Y - red )*volume)>>8) )<<16) +
　　　　　　　　((( green+ (( (Y - green)*volume)>>8) )<<8) +
　　　　　　　　 (( blue + (( (Y - blue )*volume)>>8) );
としたら掛け算は減らせるよ
657 名前：648 mailto:sage [2008/04/25(金) 07:54:03 ]: >>656
なるほど！！さんくす
　Y = (red * 77 + green * 150 + blue * 29) >> 8;
　dstRGB[i] = (((red + (((Y - red) * volume) >> 8)) << 16) +
　　　　　　　((green + (((Y - green) * volume) >> 8)) << 8) +
　　　　　　　(blue + (((Y - blue) * volume) >> 8)));
今、これで自分の環境で試したら1000ms切った！(前は1100msくらい)
でも500くらいは欲しいorz
658 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 08:51:23 ]: >>657
distRGB の方は、
(red + (～)>>8)<<16 を red<<16 + (～)<<8 などど展開して
red<<16+green<<8+blue とまとめて、
*volume) << の部分を出して因数分解できれば良さげだよね。
>>8 の方もレジスタの H を取るような方法で早くなるかな。
だだ、新しいCPUだとシフト演算もテーブル化してあって
シフト回数がステート数に影響しないからなぁ。
あっ。もうすぐ9時なのでここまででカキコ。
659 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 10:12:30 ]: java　だから　割り算をシフトにするとかの最適化があんまり効かないのかもな

どの行が一番時間かかってるか　コメントアウトしては時間計って
一番時間かかってる行から順に工夫してゆくしかないと思うけど
cかDelphiでDLL作った方が早いんじゃないの？
660 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 10:20:09 ]: あとは
Y8 = Y<<8
v = 256-volume;

dstRGB[i] =(((( ( Y8 - ( (Y - red )*v) ) & 0xFF00 )<<8 +
　　　　　　((( ( Y8 - ( (Y - green)*v) ) & 0xFF00 ) +
　　　　　　 (( ( Y8 - ( (Y - blue )*v) )>>8 ;

くらいかなv = 256-volume は最初からそう使えば問題ない
でも半分は無理だろな
661 名前：デフォルトの名無しさん mailto:sage [2008/04/26(土) 10:06:56 ]: >>645
任意のパラメタωに対して、真の解に収束しない例が作れる．
662 名前：648 mailto:sage [2008/04/26(土) 13:27:23 ]: >>658-660
いろいろありがと。
今んとこ、volume調整計算を事前にしておくことで800ms切ることができた
volumeは10段階くらいあればよくて、グレースケールの精度もそこまで求めてない
この条件でまだいげねがな？

char[][][] g_gray_tbl = new char[256][256][10]; // グレースケール変換計算テーブル

// 事前計算処理
// src：変換前値 dst：変換後値 vol：度合い(0～9の10段階)
for(int src=0; src<256; src++){
　　for(int dst=0; dst<256; dst++){
　　　　for(int vol=0; vol<10; vol++){
　　　　　　g_gray_tbl[src][dst][vol] = (char)(src + (((dst - src) * vol) / 9));
　　　　}
　　}
}

dstRGB[i] = ((g_gray_tbl[red][Y][volume] << 16) +
　　　　　　(g_gray_tbl[green][Y][volume] << 8) +
　　　　　　g_gray_tbl[blue][Y][volume]);
663 名前：デフォルトの名無しさん [2008/06/12(木) 13:23:40 ]: 誰かクイックソートが挿入法よりなぜ早いのか教えてくれ

クイックソートのほうがめんどくさそうなのに最速とか理解できん・・・
664 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 14:07:54 ]: >>663
クイックソートがソートの中で最速ってわけではないが……
同じデータ数なら、挿入法よりもクイックソートの方が
ソートが完了するまでの比較回数やデータ位置の入れ替えの回数が
平均的に少ないアルゴリズムになっているから。
ソートは基本的にループや再帰呼び出しによる操作だけれど、
ループに入る前や出た後の準備や後始末、
それにループ内での操作が少しくらい複雑になっても、
ループや再帰の回数がそれを補って余るだけ減少する方法なら全体として速くなる。
665 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 15:26:15 ]: >>663
大まかな話、例えば10,000個のデータをソートする場合、データの比較や交換を行う平均的な操作回数は、
挿入法なら1回当たり2～10,000個のデータの操作を行うループを10,000回行うから50,000,000回程度の操作が必要。
クイックソートは10,000個のデータをピボットに対する大小で2グループに分けるということを行うのに10,000回の操作が必要。
さらに2つに分けたグループごとに同じことを行うので両方のグループ合わせてやはり10,000回の操作が必要。
この分割をどんどん進めて最終的にグループ内のデータ数が1個になるまで行うと分割回数はlog10,000/log2=13回程度。
つまり全部で約130,000回の操作が必要になる。
50,000,000回と130,000回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。
666 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 23:20:30 ]: エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)
667 名前：デフォルトの名無しさん mailto:sage [2008/07/27(日) 08:46:19 ]: >>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？
668 名前：デフォルトの名無しさん [2008/08/30(土) 18:14:43 ]: あげ
669 名前：デフォルトの名無しさん [2008/10/11(土) 22:27:10 ]: www.forest.impress.co.jp/article/2007/04/24/dfsupt.html
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）

この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか？
670 名前：669 mailto:sage [2008/10/11(土) 22:29:00 ]: 失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)

プログラミングの為の数学と算数 vol.3
pc11.2ch.net/test/read.cgi/tech/1197063023/
671 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 23:04:05 ]: >>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？
672 名前：669 mailto:sage [2008/10/11(土) 23:11:15 ]: >>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。
673 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 23:16:47 ]: >>669
手始めに ONP とか LCS とかでググレばいいんじゃね。

ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。
674 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 01:23:58 ]: どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。　いや、やりたいことはdiffなんだろうけど。
675 名前：669 mailto:sage [2008/10/12(日) 01:54:11 ]: >>674
オリジナルの文のうち、消えた部分を特定できれば十分です。

aaa　aaa
bbb　ccc
ccc　ddd

左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。
676 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 02:27:20 ]: >>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。

外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
２ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおｋ
677 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 07:27:56 ]: > 手軽にやりたくて、

今時 FC はないだろ。

って言うか、それなら DF 呼び出すようにするだろうし。

単に楽したいだけなら、C# で LCS の実装例とかも見つけられるでしょ。

参考 URL: d.hatena.ne.jp/siokoshou/20070308
678 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 12:10:51 ]: >>677
DFってそういう出力する方法あるのか？

わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

あとFCなら配布時に別途導入してもらう必要が無いし。

あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。
679 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 13:30:35 ]: > わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

FC 勧める理由がわからん。

比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。
680 名前：669 mailto:sage [2008/10/12(日) 14:19:04 ]: 動的計画法と配列アラインメント
ttp://www.ibm.com/developerworks/jp/java/library/j-seqalign/index.html

↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。
681 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 15:09:12 ]: >>679
勧めた理由はその次の行に書いたが？

ぶっちゃけそれ以上の理由は無い。

解析が大変だと思うのは同意。

>>680
>>677のソースをコピペでいいのに。
682 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 15:26:58 ]: >>681
> 勧めた理由はその次の行に書いたが？

配布の容易さと解析の容易さの比較は状況次第だから議論は避けるよ。

> >>677のソースをコピペでいいのに。

>>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
ペでは得られないものがあると思うよ。

頑張れ > >>669
683 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 16:11:41 ]: 確かにプログラム書くことが目的なのかアルゴリズム知ることが目的なのかもはっきりしてなかったね。

とはいえスレとしては後者として考えるべきだった。　ｽﾏﾝｶｯﾀ
684 名前：669 mailto:sage [2008/10/12(日) 16:18:39 ]: みなさん暖かい支援どうもですm(_ _)m

> >>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
> ペでは得られないものがあると思うよ。

はい、>>680のサイトでO(NM)の単純なアルゴリズムに関してはおおよそ把握することができました。

可能ならば
hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
で紹介されていますO(ND)アルゴリズムや、さらに進化したO(NP)アルゴリズムも
理解したいと思っています。

さっそくO(ND)とO(NP)を解説した原著論文をDLしてきたのですがなかなか全体像を
把握するのが難しいです(´･ω･｀)
もう少し優しくかみ砕いて説明してくれているサイト、できましたら日本語で、があれば
嬉しいのですがそういうサイトは無いでしょうか？
685 名前：669 mailto:sage [2008/10/12(日) 16:19:20 ]: >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
d.hatena.ne.jp/siokoshou/20070315

aaa　aaa
bbb　bbb
　　　 ccc
（左がオリジナル、右が比較対象）

早速この二つを比較してみたところ。
オリジナルの"aaa"はCommon（共通）と判断されたものの、オリジナルの"bbb"はModified（変更）
と判断されました。ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。
686 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 16:22:21 ]: >>685
もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?
687 名前：669 mailto:sage [2008/10/12(日) 16:35:39 ]: >>686
左のbbbには\nを付けましたが、やはりModifiedが返されるようです。

あと
aaa　aaa
bbb　ccc
　　　 bbb
だと

Common
Modified
Common

と返されるようです。
オリジナルが2行なのに返される行が3行だと後々の処理がちょっとややこしくなるかもしれません・・・
688 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 17:10:18 ]: > ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

C# のソースがあるんだから、ステップ実行しながら見てみればいいと思うんだが。

あと、それはそれとしてバイナリエディタを１つ使えるようになっておいた方がいいと思う。
テキストエディタ上では同じ改行に見えても片方は 0x0d のみで、もう一方は 0x0d 0x0a
なんてこともあるから。
689 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 17:48:14 ]: >>687
鈍らな比較ツールだと、「挿入された」ことを理解できないから>687のようなことになる。
逆に言えば、「挿入された」ことを考慮しないアルゴリズムでは、目的に合っていないと言うことだけ。
それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。
690 名前：669 mailto:sage [2008/10/12(日) 17:56:39 ]: >>689
> それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
> 意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

釣りとかでは無いです（；´∀｀）・・・

>>685も>>687もどちらもオリジナルが2行なのに対して
比較対象の文字列（どちらも3行）をいじるだけで出力が
2行になったり3行になったりと変わってしまうと後々の
処理がややこしくなるかなと思った次第です
691 名前：だから、無駄なことはやめておけと mailto:sage [2008/10/12(日) 18:14:36 ]: >>690
読解力のない間抜けだということはよく判りました。
692 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 18:47:39 ]: 何で>>690みたいなゴミみたいな奴がアルゴとかやってんの？
693 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 19:52:19 ]: >>685
> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> d.hatena.ne.jp/siokoshou/20070315

そこのコードは最長共通部分とか返してくれない。
「とにかくO(NP)の最速で動くdiffコードを作ってみました」
ということを実証するためのコードだからあまり実用的じゃないぞ。
あるいはコードに手を入れてちょっとした改造を施すか汁。
694 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 20:58:19 ]: >>689
>それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
なんか勘違いしてね？
その二つの例が別の話題だということは>>687が「あと」と言っていることから分かる
自分の読解力を過信して、ろくに理解せずに他人にいちゃもんを付けるのは格好悪いよ
695 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:04:24 ]: >>691
> 読解力のない間抜けだということはよく判りました。

読解力の無いマヌケはお前の方だったようだなｗ
696 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:07:15 ]: 面白そうだから黙ってたのに。
697 名前：デフォルトの名無しさん [2008/10/12(日) 21:07:29 ]: 頭おかしくなっちゃうと屁が出るんだよねｗ
698 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:17:48 ]: >>689
(ﾉ∀`)ｱﾁｬｰ
699 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 22:11:35 ]: basicのほうが早くね
700 名前：　 [2008/10/14(火) 00:07:37 ]: 文字列照合アルゴリズムでSIGMAてのがあるらしんですけど
詳しいアルゴリズムを解説したページありませんか？
なんか宣伝のようなページしか見つかりません。
701 名前：デフォルトの名無しさん mailto:sage [2008/10/14(火) 18:55:04 ]: ttp://hdl.handle.net/2324/3109
ここにたどり着いた
あってるかは知らん
702 名前：デフォルトの名無しさん mailto:sage [2008/10/14(火) 19:06:55 ]: management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？
703 名前： mailto:sage [2008/10/15(水) 18:43:09 ]: >>701
エラーがでます。

>>702
シュンサクとかいうデーターベースで使われてると読んだのです。
704 名前：アラフＯＯ.ｏ（笑） [2008/10/15(水) 23:21:58 ]: >>703
オモローな記事があるぞ。兄弟。

いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
ttp://www.atmarkit.co.jp/fcoding/articles/algorithm/01/algorithm01a.html
705 名前：デフォルトの名無しさん mailto:sage [2008/10/16(木) 20:09:11 ]: >>703
pr.fujitsu.com/jp/news/2006/12/15.html
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。

アルゴリズムじゃなくてシステムじゃないか。
人物から見ても >>701 であってるんだな。

あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。
706 名前： mailto:sage [2008/10/17(金) 03:43:42 ]: >>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。
707 名前：デフォルトの名無しさん [2008/10/18(土) 18:41:25 ]: 範囲のリストに新しい１つの範囲を追加するアルゴリズムをお願いします。
例えば、[1,2][5,7][8,15]という範囲のリストがあります。
上記のリストに[3,5]という範囲を追加すると
[1,2][3,5][5,7][8,15]に。

上記のリストに[1,6]という範囲を追加すると
新しく追加する範囲が常に優先されて、
[1,6][6,7][8,15]に。

上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
[1,2][5,7][8,10][10,13][13,15]。

リストは常にソートされているものとして、各範囲は重なって
はいけません。上記で範囲[Start,End]でEndは含まれません。

範囲のリストに1万件とか２万件を高速に連続追加できれば幸いです。

よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。
708 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 18:46:16 ]: あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。
709 名前：デフォルトの名無しさん [2008/10/18(土) 18:53:28 ]: 多めに確保して置いて、存在するところのビットを立てておけ。
710 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:08 ]: データ構造はリストでお願いします。聞きたいのはアルゴリズムです。
実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定？
んー。
711 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:40 ]: ふと思いついたもの。

範囲を示すインデックスにどの範囲に属するかという情報を持たせる。

上の例で実際にやってみる。
[1,2][5,7][8,15]に[3,5]を追加する。
範囲を示すインデックスがどの範囲に属するかという変数 = ID (0,1,0,0,0,2,2,0,3,3,3,3,3,3,3)
[3,5]を追加。(0,1,0,4,4,2,2,0,3,3,3,3,3,3,3)

[1,6]を追加。(0,4,4,4,4,4,2,0,3,3,3,3,3,3,3)

[10,13]を追加。(0,1,0,0,0,2,2,0,3,3,4,4,4,3,3)

以上。追加は高速だと思う。
範囲のリストへのアクセスはIDからリストを作るので、そこは作る処理の時間だけ遅くなる。
712 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:19:05 ]: そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？
713 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:24:57 ]: あー。すみません。データ構造とアルゴリズムは関係があるので、データ構造はリスト
でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。
714 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:39:07 ]: >>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。
715 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:13:16 ]: 範囲の列を、pより小さい部分とp以上の部分に分ける操作を考えて「値pによる分割」と呼ぶことにする
例えば[1,2][5,7][8,15]を3で分割すると[1,2]と[5,7][8,15]に、
10で分割すると[1,2][5,7][8,10]と[10,15]になる(このように列の分割が範囲そのものの分割を伴うことがある)

範囲の列Sに[start, end]を挿入するには、Sをstartで分割してS1とS2を得、S2をendで分割してS3とS4を得、
S1とS4の間に[start, end]を挟んだものを結果とすればいい

Sをpで分割するには、まずS中の範囲でendがpを越えるもののうち一番左にあるものを探す
そういうものがなければ、SはSと空列に分割される
あれば、それのbeginをpと比較して、それを分割するか全部右側に入れるか決める

多分この手順でいけるけど、これが高速に実行できるようなデータ構造は何があるだろう
2-3 Finger Treesとかならindexとappendとsplitが全部O(log n)だから、O((log n)^2)で挿入できるかな
716 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:47:34 ]: >>702 >>713
データ構造を弄ってよいなら，
できるべき操作をちゃんと指定してほしい．
たとえば

(1) 範囲の追加
(2) 範囲 [x,y] に含まれる全ての範囲を小さい順に出力
(3) 小さいほうから数えて k 番目の範囲の出力
(4) ある点を含む区間の有無の判定
(5) ...

みたいな感じで列挙してください．

あと，>>710 に関して質問なのだけど，
いまある区間が分割された場合（>>707 の [10,13] の例），
オブジェクトとしてはどうなっているの？

(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
(b) [8,10] と [13,15] は同じオブジェクトに対応する

どっち？
717 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:22:08 ]: >>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
　unsigned int StartIndex;
　unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。
718 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:25:14 ]: >挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？
719 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:17:17 ]: >>713,714
反応してくれてどうもです。

最近はあまりやらないんですけど、前はパズルを解くプログラムを作ったりしていました。
ポイントは簡単な問題を数多くこなす事だと思っています。
すると、どういう処理が効率がいいのか分かってきます。

こういう場合の為におすすめです。あまり無いと思いますが。。。
720 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:52:35 ]: ＞上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
＞[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの？　そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。
721 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:59:37 ]: >>720
想像力不足
722 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:38:10 ]: 俺は動画のフレーム編集を想像しながらスレを見てた
723 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:42:24 ]: だとしたら>>716のa,bはa？

あと>>721はどんなもの想像してたんかな？
724 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:05:09 ]: >>707です。
>>716
>(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
オブジェクトを複製して別物で管理します(範囲以外のプロパティをコピーして)
>できるべき操作をちゃんと指定してほしい．
外部に公開する機能は
・範囲の追加(1個ずつ)
・リストの先頭から末尾への連続アクセス
・リストの全削除
以上です。
>>717
なるほど、上で書いた外部に公開する機能みてもB-Treeでいいのかもしれませんね。
ちょっと実装してみます。
>>715
わ。ありがとうございます。すごいわかりやすいです。

もうちょっと色々もだえてみます。
725 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:12:56 ]: ・リストの先頭から末尾への連続アクセス
だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。
726 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 12:23:29 ]: >720
ttp://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。
727 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:08:31 ]: 8≦Nを満たす正の整数Nを3と5の和の組み合わせで表すにはどうすればいい？
3が何個、5が何個って分かればいいんだけど
あと表せない数はあるんだろうか

最初の5つはこんな感じ
8=5+3
9=3+3+3
10=5+5
11=5+3+3
12=3+3+3+3
13=5+5+3
728 名前：デフォルトの名無しさん [2008/10/22(水) 23:37:07 ]: N = 3m+5nでしょ。　互いに素ならいけるんではなかったか? m,nが整数なら
729 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:37:40 ]: 単に3と5の個数をデータとして持てばいいんじゃないの?

8,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。
730 名前：デフォルトの名無しさん [2008/10/22(水) 23:39:21 ]: ax+by=1を満たす整数x,yが存在する

d.hatena.ne.jp/gould2007/20071009
731 名前：デフォルトの名無しさん [2008/10/22(水) 23:41:50 ]: そしたら連続する3つ作れればそれ以降、全てつくれるってことだな
732 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:01:14 ]: その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました
733 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:50:53 ]: どうもおかしいと思った。

＞最初の5つはこんな感じ

6つあったのねw
734 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:09:36 ]: A Small and Fast IP Forwarding Table Using Hashing.
これ何度みても計算できねぇ助けて
735 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:53:54 ]: 一緒に考えてやるからその論文を見る方法を教えろ
736 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 02:07:20 ]: ttp://cial.csie.ncku.edu.tw/ppt/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.ppt
ttp://cial.csie.ncku.edu.tw/pdf/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.pdf
ぐぐった
合ってるかは知らん
737 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 11:10:39 ]: >>736
それっすそれっす
738 名前：しろうと [2008/10/26(日) 16:22:55 ]: 突然すみません。しろうとです。
バイナリーサーチの計算量はO(log n)ですが、その導き方について。
T(n)=O(1) n<=1
T(n)=T(n/2)+O(1) n>1

以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。
ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1
したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。
また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか？
739 名前：デフォルトの名無しさん [2008/10/26(日) 18:18:41 ]: アルゴリズムをよく考えてみ
k=１のとき、つまり1回分割したときはn/2
k=2のとき、つまり2回分割したときはn/4 = n/2^2
k=3のとき、つまり3回分割したときはn/8 =n/2^3
といって、求めたいのは、つまりnをk回分割したときの計算量だから
k=???のとき、つまりk回分割したときにn/2^k　→ ???を求める為には
数式頼みはよろしくないよ
740 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 18:49:12 ]: >>738
ひどい導出だ．O(1) の扱いが雑すぎる．
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述．

もし本当に本にこう書いてあるなら捨てたほうがいい．
741 名前：くまさん [2008/10/26(日) 18:59:21 ]: プログラムの初心者です。
アルゴリズムの流れ図について、自然数ｍ、ｎに対して、
ｍのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。
742 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 19:37:22 ]: 流れ図の問題なんだな？そうなんだよな？
ではまず、効率の良いアルゴリズムを言ってくれ。
743 名前：くまさん [2008/10/26(日) 22:23:58 ]: ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。

n＾２＊ｎ＾２＊ｎ＾２
これがヒントだそうです。
どうしたら、よろしいのでしょうか？
お願いします。
744 名前：くまさん [2008/10/26(日) 22:44:42 ]: ｎの４乗はｎの２乗×ｎの２乗です。　ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。

従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。
の2乗
これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。
745 名前：デフォルトの名無しさん [2008/10/26(日) 22:45:56 ]: よくわからんな、何だろ
ビット演算を絡ませたアセンブラ的な問題なのかな？
お前らどうする？これ放置していいん？
746 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 22:53:29 ]: 罠じゃねえの?

説明がデタラメだし。
747 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:18:56 ]: >>744
＞ｎの８乗はｎの２乗×ｎの４乗
ダウト。乗数は足し算です。

n^8
= n^(4+4)
= n^4 * n^4
= (n * n * n * n) * (n * n * n * n)
ね？

＞ｎの６４乗はｎの２乗×ｎの３２乗
同様に、ｎの３２乗×ｎの３２乗がｎの６４乗で
あえて言うなら（ｎの３２乗）の２乗がｎの６４乗

つまり
>>745
問題のヒントが出鱈目だから放置していい。
748 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:20:45 ]: >>736の問題助けてくれｗまじでｗ
749 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:27:51 ]: 要するに>>736を分かりやすく翻訳してくれって言ってる？
サマリー読む限り、別に問題提起ってわけではなさそうだけど……？
750 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:35:16 ]: >>749
4bitの集合を考え、具体例として以下で計算した場合
0000, 1100　0011, 0100, 0110, 0111, 1011, 0001.

1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね？
751 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:12:25 ]: ４ページのExample 1の話？
752 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:28:44 ]: うん
753 名前：デフォルトの名無しさん [2008/10/28(火) 20:57:21 ]: kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7885.txt
上記は疑似コードで書かれていますが、アルゴリズム１もアルゴリズム２も
配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム１の
０２行目では配列をどうやってtempにぶちこめるのでしょうか？配列Aが例えば
{2, 6, 3, 7}だとすると、tempには最初に何が入るのですか？再帰なので、
A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり
A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の２が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。
754 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 21:06:35 ]: >>753
リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。
755 名前：デフォルトの名無しさん [2008/10/29(水) 00:57:04 ]: 再帰の仕組みって勉強すればなんとかなるもんじゃないだろ
何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ

>>753
間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない
君の配列の書き方を使って書くと

A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方！
じゃあA[1,3]の最小値って何さ　→　同じやり方で済むじゃん

みたいな考え方を適用すべき
756 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 01:01:16 ]: LISP学んだり、フラクタル図形書いてみたり
だまし絵とか見に行くといいんじゃないかな
757 名前：755 [2008/10/29(水) 01:09:03 ]: >>753
おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。
758 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:22:29 ]: n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？

ソートして先頭3つでやるのはなんかもったいない気がして・・・
759 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:41:45 ]: 端から舐めて上位3個を取り出す方法だろうなぁ
760 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:47:31 ]: それだと比較回数3n？
761 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:50:26 ]: ヒープ
762 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:53:24 ]: 20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？
763 名前：デフォルトの名無しさん [2008/10/29(水) 15:30:41 ]: >>757
ありがとうございました。
764 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 15:31:13 ]: nth_element, partial_sort
765 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:05:02 ]: >>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．

実用的にはデータの分布に依存するので，実測しないと何とも．
766 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:16:37 ]: >>765
全体ソートするのとオーダーかわらんじゃん
767 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:31:52 ]: っ「選択アルゴリズム」
768 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:33:23 ]: 選択アルゴリズムはk番目の値しか探せないぞ
769 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:38:05 ]: >>768はまったくプログラミングの才能が無いな。
770 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:41:47 ]: partial_sort使うのがいいんじゃない？
771 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:43:47 ]: >>770
それ、なんのこと言ってるの? C++前提なの?
772 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:50:02 ]: 「部分ソート」と呟いておく。
773 名前：デフォルトの名無しさん [2008/10/29(水) 19:03:55 ]: たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして
93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。
774 名前：デフォルトの名無しさん [2008/10/29(水) 19:09:33 ]: もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。
次のループでそれ以上を選ぶ。
775 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 21:53:17 ]: v[0]が4にならねーよ
わからねー
776 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 06:19:01 ]: >>766
全体ソートは　O(n log n) だから log の値が違う
777 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 13:30:13 ]: Nは100～10000程度で、double x[N]; に適当な数が入っているとします。
任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、
あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。

ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、
任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。
（与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ）
このときに上の二分法のようなアルゴリズムはあるでしょうか？
普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。
778 名前：デフォルトの名無しさん [2008/10/30(木) 13:54:09 ]: ないな　O(N)で困る例はなんだよ
779 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 15:30:46 ]: >>778
ないこと証明できる？

困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり？
780 名前：デフォルトの名無しさん [2008/10/30(木) 15:43:21 ]: a,bの存在範囲毎に最小点を計算しておけば定数時間
781 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 16:07:07 ]: >>777
i11www.iti.uni-karlsruhe.de/~awolff/pub/dmsw-fpqgc-06.pdf
のイントロに書いてあるけど，
[CY84]: 前処理 O(n^2)，問い合わせ O(log n)
[LC85]: 前処理 O(n^2)，問い合わせ O(log n)
[MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね．

一通り目を通してみたけど，LC85 は特に簡単．双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して，点位置決定問題に帰着するだけ．
782 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:50:08 ]: >>781
あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。

追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか？
783 名前：デフォルトの名無しさん [2008/10/30(木) 19:16:37 ]: そもそも何に必要なんだよ?
784 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 19:34:27 ]: >>782
私の大学からだとCY84以外は契約論文誌なので，Webから取れた．
もし必要ならどっかにアップロードするよ．

Mu03はciteseerからも取れたので，論文名で検索してみると良い．
785 名前：デフォルトの名無しさん [2008/10/30(木) 19:47:13 ]: 前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では?
786 名前：デフォルトの名無しさん [2008/10/30(木) 19:50:29 ]: 最後のやつだとこの辺に関連情報あるぞ
scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr=
787 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:04:09 ]: >>784
Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。

>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。
788 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:29:11 ]: >>785
O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。

なので、クエリ時間を増やしても n^2 より安い手法が存在する。
789 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:28:46 ]: マス目に二種類の記号を置いていった時、

AAA　　　　ABA
ABB　　　　ABA
AAA　　　　AAA

というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？
790 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:43:56 ]: >>789
問題が不明瞭

マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ？
791 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:54:59 ]: 簡単な方法はない。
地道に全回転・反転パターン（8通り）を網羅してチェックする。

プログラムが見通しよくなるように工夫がひつようかも。
792 名前：デフォルトの名無しさん [2008/10/31(金) 18:21:54 ]: 行同値的を出してそれを比較すれば・・・駄目か
793 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 18:37:25 ]: トランザクションメモリの実装
ここでやる夫的に説明してくれよ
794 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 19:41:21 ]: 　　　 .　'　　　_ 二二 _ .､
　　　　　　／　　　 /´ -‐…‐- .｀＼
　　　　　　 /　　　　 /´　　　 i　　 !｀ヽﾄ､
.　　　 ,ﾍ　 ,' 　 i　　 !　 !　 |　|i　　|ﾊ　i　ヽ　ｷﾘｯ
　　　/　ゝ!　ﾉ|　　! !::__!::ノ ´　￣　 i::.i ｜!
　　　＼　 .|　.:i i :i　i |´　　＼　　／　｀!､ﾊ:!　　
　　　｀ヽi　从 i　i | ニﾆﾐ　　　 .ﾆニ !:::::|　　＜トランザクションメモリの実装
.　　　　　 | 　ＹﾊｉﾊN　 {r::ﾘ｀　　´{r::ﾘ '::::N　　　　ここでやる夫的に説明してくれよ
.　　　　　 |　　ヽゝ　　 ´´　　　　　｀｀ﾊ!｀　
.　　　　　 |∧ 　 Ⅵ!　　　　　 ′　,':::|
　　　　　ｊ/∧　 _!::｝　、　　 ⊂'　..ｲ:::::|
　　　　　 ///∧´ ∨　　｀　,.... ィ´ﾞY:::::|
.　　　　 /////∧　ヽ　　　　{ﾄ､∧　|::::::!
　　　　 ,＜￣￣∧　 } ｀ヽ　　＞''}　{￣｀ヽ
.　　　 / 　｀ヽ:::::::::Y´ヽ　　　　　 i´｀∨::::∧
　　　/　　　 ∨:::::| .:: !　　　　 i .:.: !::::/　i

　　　　　　　　　　　＿＿＿_
　　　　　　　 ,. :'´: :,.　-―‐-ミ:ヽ、
　　　　　　／: : : :厶ｨ': ´￣￣ヾ : :＼
　　　　　 /: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼　　　＜じゃっておｗｗｗ
　　　　　ｉ: : :.!: : : ﾚ‐'　｀￣⌒　⌒" ﾄﾍ:ﾊ!
　　　ﾄ--|: : :.!: : ､|　　ｰ‐'' ´ ｀'ｰ　　}: :.ﾄ
　　ﾐ　ﾐ　ﾐ : :!: : : :!　z=≡　　　≡z.{: :.ﾊ　　　　ﾐ　ﾐ　ﾐ
　/⌒)⌒)⌒.ﾊ :_Nとつ　＼＼＼ C VVﾘ　　/⌒)⌒)⌒)
　|　/　/　/:弋こ　＼ヽ　＿＿,.　　　}　(⌒)/　/ / /／
　|　:::::::::::(⌒) : :}＼　　/　　　1　／　　ゝ　　:::::::::::/
　|　　　　　ノくf⌒Y ｀　{_　　_,ﾉイ| 　　　/　　）　　/
　ヽ　　　　/　ヽ　ﾍ,､　　_｢　|::!:::::} 　　/　　　　／　　　　バ
　　|　　　　|　　 l||l　从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l　　バ　　ン
　　ヽ　　　 -一''''''"~~｀`'ー--､/:::::ｲ;　 -一'''''''ー-､　　　　ン
　　　ヽ＿＿＿＿(⌒)(⌒)⌒)　):::/}　 (⌒＿(⌒)⌒)⌒))
795 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 21:00:10 ]: かんなぎは評価されすぎ。
796 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 03:17:29 ]: 無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。
って意味のわかる人教えて下さい。
797 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 06:37:03 ]: 意味が分からんな。
「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。
798 名前：796 mailto:sage [2008/11/13(木) 06:40:40 ]: >>797
無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか？
799 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:13:30 ]: やはり意味不明。
今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。
800 名前：796 mailto:sage [2008/11/13(木) 07:25:04 ]: そうですか。失礼しました。忘れてもらって結構です。
801 名前：796 mailto:sage [2008/11/13(木) 07:31:12 ]: 別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは
例えばどういうときかわかりますか？
802 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:42:43 ]: >>801
G = (V,E) を 3点 a,b,c からなるグラフとし，
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し，
頂点 a から b への最短路を求めようとすると破綻する．
803 名前：796 mailto:sage [2008/11/13(木) 07:49:21 ]: なるほど。素早い回答ありがとうございます。
804 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 08:36:21 ]: >>802
その例では破綻しないぞ
805 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 11:31:33 ]: >>804
kwsk
806 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:00:49 ]: >>802の例だとd(a, b) = 0で探索終わらね？

正答が得られないって意味で破綻なんじゃね？
807 名前：デフォルトの名無しさん [2008/11/14(金) 22:07:03 ]: ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。
ぜひ解答お願いしたいです。
スレチでしたらすみません。。
808 名前：びぎなぁ mailto:sage [2008/11/16(日) 05:22:26 ]: アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。
（どの用語がどの用語の中に含まれているのかとか）
ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？

木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子
木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、
　　　　　　　　　　　　　　　　　　　　　　　　　（２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい
木構造--------二分木---------------ヒープ・・・二分ヒープと同義？
木構造--------多分木
809 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:29:55 ]: >>808
ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう．よって．一般の木上のヒープがありうる．
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし，
より一般の木上のヒープとしてはフィボナッチヒープが有名．

ただ，最もよく使われるヒープは完全二分木上のヒープで，
何も断らずにヒープと言ったときこれを指す場合も多い．

場合によっては配列実装まで含めてヒープと言う場合もあるけど，
フォーマルには構造と実装は別に考えるので，
>>808 の二分ヒープの説明は本当はちょっとよろしくない．
810 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:53:51 ]: >>807
どれくらいの精度で解析すればいいの？

あと，Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ？
それとも，フィボナッチ数で抑えること自体が禁止されるの？
811 名前：デフォルトの名無しさん [2008/11/16(日) 09:19:57 ]: >>810
どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。
812 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 11:41:06 ]: >>811
互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える．

補題．
a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する．
証明．
k = 1 のときは自明．k-1 まで正しいと仮定．
gcd(a,b) が k ステップで終わるとき，
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}．
系．
gcd(a,b) のステップ数は O(log min{a,b})．
証明．
a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため．
813 名前：811 mailto:sage [2008/11/16(日) 17:41:20 ]: ありがとうございます

a ≧ 1.1^{k+1}, b ≧ 1.1^k

この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。
814 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 20:51:27 ]: >>813
上：なんとなく．
1.1 に必然性はなくて，1.0001^k でも 1.0000000001^k でも何でもいい．
(1+ε)^k で示せれば系が示せるので，適当に不等式が成り立ちそうな値にした．

本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど，
この場合にギリギリに評価するとフィボナッチ数が出てしまうので，
わざとガバガバに評価しているという事情がある．

下：
> できるあたりがいまいちわかりません。
そういうときは具体的にここが分からないとか言うもんだよ．
ただ，補題が少し不十分な書き方だったね．補題は
「k (≧ 1) ステップ以上かかるならば」に置き換えてよい（同じ証明が動く）ので，
そう置き替えておいて，対偶を取ると
「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」になるので
b < 1.1^m なる m を見つけられれば m ステップ未満で終わる．
そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底)．
815 名前：811 mailto:sage [2008/11/16(日) 21:04:38 ]: ありがとうございます。
もう一度問題と向き合って理解を深めたいと思います。
816 名前：びぎなぁ mailto:sage [2008/11/19(水) 07:05:43 ]: >>809
返事が遅くなりました。ありがとうございました。

ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、
計算量のところがウェブ（ウィキとか）で調べてもよく理解できません。
（１）クラスカル法
グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに
なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V)

（２）プリム法
MSTに属する頂点とそうでないものの２グループに分け、まだMSTに属していない頂点から
最もコストの安く済む頂点をMSTに付け加えて行く。計算量は３種類あるみたい。
・隣接行列、探索→O(V^2)
・２分ヒープと隣接リスト→O(E log V)（←これはO((V+E)log(V))より）
・フィボナッチヒープと隣接リスト→O(E+V log (V))

ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです
817 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 08:22:57 ]: >>816
アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど，
あなたの説明だと，良く分からない部分が多い．
（もちろん「普通の実装」というのがあるのだけれど，
　それがあなたの理解しているものと違う可能性もある）

なので，あなたが理解している形で，For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな？
その計算量だったら評価するよ．
818 名前：びぎなぁ mailto:sage [2008/11/19(水) 16:22:32 ]: >>817
イントロダクショントゥアルゴリズム二版から抜粋です
---------------------------------------
MST-クラスカル（G, w）
A←0
for each vertex v∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u)≠FIND-SET(v)
then A←A∪{(u, v)}
UNION(u, v)
return A
---------------------------------------
MST-プリム(G, w, r)
for each u∈V[G]
do key[u]←∞
π[u]←NIL
key[r]←0
Q←V[G]
while Q≠0
do u ← EXTRACT-MIN(Q)
for each v∈Adj[u]
do if v∈Q and w(u, v) < key[v]
then π[v]←u
key[v]←w(u, v)
---------------------------------------
819 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:49:58 ]: >>818
その本に計算量の説明が懇切丁寧に書いてあるよ
820 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:54:24 ]: ならし解析ですね分かりません。
821 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 00:37:39 ]: LC-Treisってどんな木なのですかね？
822 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:42:41 ]: >>819
了解です！
823 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:46:49 ]: 「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が
正の数だった場合、ダイクストラ法は失敗することがあるか？」

あれば例を教えて欲しいです
824 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 21:21:36 ]: 「開始点から離れて行く辺」の定義が必要なんじゃね？
825 名前：びぎなぁ mailto:sage [2008/11/20(木) 23:44:17 ]: sourceのことだと思います
826 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 19:02:46 ]: バイナリ木関連のアルゴリズム
詳細に書いてる本ってありますか？
827 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 20:00:17 ]: >>826
詳細ってどの程度？
必要なトピックを具体的にいくつか挙げてください。
828 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 09:34:20 ]: トポロジカルソートはなぜグラフがDAGであることが前提なのですか？
サイクリックなグラフでもソート出来ると思うのですが。
829 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 10:13:52 ]: >>828
トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？
いくつか流儀があるから君の流儀が分からないと適切には答えられない．
830 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 13:40:19 ]: トポロジカルソート：
（１）DAGに対して、DFSを実行する。
（２）Finishing timeの大きい順に頂点を並べる。
というものですが、いかがでしょうか。
831 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 17:21:09 ]: >>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）

普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．
832 名前：デフォルトの名無しさん mailto:sage [2008/12/03(水) 04:53:21 ]: >>831
なるほど。わかったような気がします。
ありがとうございます。
833 名前：初心者プログラマ mailto:sage [2008/12/03(水) 16:31:24 ]: 突然すみません。これからプログラミングで一辺に対して指定した数分の円を正六角形の中に敷き詰めるプログラムを
書こうとしています。例えば１と指定した場合は六角形内に１個の円が描かれます。例として９を指定した場合の図を
添付します。
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8194.zip

聞きたいのは、nの辺の数に対してどのような法則性があるかということです。
１辺の長さを仮に１とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、
n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な
法則などあるのでしょうか。アホな質問だったらすみません。
834 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:19:45 ]: >>833
数学板へどうぞ。
835 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:48:43 ]: >>833
(√3/2)/n
836 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:08 ]: >>833
>>835は間違い。

(√3/2)/(1+n√3)
837 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:56 ]: >>836
さらに間違えてた。orz

(√3/2)/(1+ (n-1)√3)
838 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 14:49:49 ]: 有り難うございました。
839 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 04:37:19 ]: ビッグ・オー記法の問題ですが、
a(n)=n^(1/2)
b(n)=10*log[2]n
どちらが大きいですか？導き方を教えて下さい。
840 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 07:34:40 ]: >>839
十分大きな n に対しては n^{1/2} > 10 log n．

lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して
εδで書いてε = 1 にでも取れば良い．
841 名前：839 mailto:sage [2008/12/07(日) 13:57:54 ]: >>840
limがわかっていないのですが、limを使わずに導くことは可能でしょうか？
842 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 14:14:55 ]: δε論法
843 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 01:52:02 ]: わからないなら
a^n >> n^b >> log(n)
とでも暗記しておけ。
大概はこれだけ覚えてりゃ問題ない
844 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 03:53:27 ]: ノイズのある入力列の中から
A->B->C->A => 1
A->B->C->B => 2
A->C->C->C->D => 3
とかの並びが含まれていたら、それをパターンと識別して
=>の後の値に変換する処理を書いています。
今はパターンをトライ木に登録していて速度は問題ないのですが、
共通パターンが少ないとメモリを食うのが気になります。
もう少し効率の良い方法はあるでしょうか。
パターンの候補であるかはインクリメンタルに読み取れる必要があります。
845 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 04:41:33 ]: wiki見たら

基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、
トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。

だとか。もう少し見たら

HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。
時間計算量も領域計算量もハッシュテーブルに匹敵する。

とか。
846 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 06:33:09 ]: >>844
パトリシアではダメ？
847 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 08:28:21 ]: パトリシア木でもいいんですが、
何か別の方法がないか聞いて見ました。
HAT-trieは初めて聞きました。調べてみます。
848 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 12:02:22 ]: >>847
自分もかなり興味があるので調べているのですが、難しいです。。。

とりあえず、HAT-trieの発案者の一人であるDr. Nikolas Askitisのホームページを張っておきます。
goanna.cs.rmit.edu.au/~naskitis/

調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。
849 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 21:53:25 ]: 見た目はB-trieという(B木の変形の)変形で、ノードに該当するキーの
代わりに、キーの一部の文字そのものを使い、キーの残りに共通部が
なければ衝突のない小さな順序付きテーブルを作って葉に残りの
文字列を入れる。平衡木が深くなるのを避けつつ、
ハッシュ表と違い順序構造も維持できるって事でしょうかね。
テーブルの入れ方の指定とかチューニングとか書いてありますが、
実際に比較した実装も見せないで他のアルゴリズムとの比較グラフが
載ってるのは胡散臭いです。複雑さによる速度低下はありそうだし、
都合の良いデータなのかもしれません。
1つ言えることは、メモリは減るのかもしれないけど、
平衡木が絡んでくるだけでコード量は数倍に増えると思います。

今使ってるトライのコードは登録検索だけですが60行程度です。
パトリシアにするだけでコードは2倍以上に増えました。
メモリは半分以下になりますが速度は3割減ぐらいです。
850 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 02:43:00 ]: とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう)
間違いがあるかもしれませんが。。。

-----------------------------------------------------------
HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造

Nikolas Askitis Ranjan Sinha
School of Computer Science and Information Technology,
RMIT University, Melbourne 3001, Australia.
Email: {naskitis,rsinha}@cs.rmit.edu.au

概要

トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。
burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。
しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは
不十分なパフォーマンスにつながり得る。
この論文では、既存の手法とうまく組み合せたキャッシュを考慮した
トライベースのデータ構造であるHAT-trieを提案する。
いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。
ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの
実行時間とメモリ使用量の改善が見られた。
HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。
851 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:22:50 ]: 引き続き翻訳してみます。
初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。

----------------
3 The HAT-trie

現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。
852 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:24:46 ]: 最後の「原因」は「問題」の方が良さそうです。
853 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:03:11 ]: アクセス時にmove-to-frontする
ってどういう事？
854 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:08:11 ]: あ、文字列のMTFじゃなくて自己組織化探索の方か。
855 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 01:06:00 ]: 論文の英文和訳なんてこんなところでやらんでくれ。
856 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 09:13:33 ]: >>853
翻訳が怪しくなりそうなところは英単語のままにしてあります。
アクセス時にmove-to-frontするというのは良く分かりませんが、直訳ぐらいにはなってるでしょうか。

>>855
すみません。今回は翻訳は置いといて（継続！？）
お詫びに、昨日お風呂の中でふと思いついたネタを投下します。

はじめに（論文っぽく）

ハッシュは完全ハッシュしか良いとは思っていません。例えば、>>844でいうと
1 <= A->B->C->A
2 <= A->B->C->B
3 <= A->C->C->C->D
という処理をハッシュでやると、右側を文字列として
int[][][][][] pattern;
pattern['A']['B']['C']['A'][0] = 1;
pattern['A']['B']['C']['B'][0] = 2;
pattern['A']['C']['C']['C']['D'] = 3;
という感じでやります。

しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
そこで最小完全ハッシュを考えます。最小完全ハッシュとはハッシュ値を
0からデータ数-1に割り振る事です。例えば'A'を1、'B'を2、'C'を3にする事を考えますと
すぐに思いつくものはkey['A'] = 1という感じでやれば出来ます。

このまま終わればそっちのネタになってしまいますが、ここからが本題です。
最小完全ハッシュの為のキーを返す処理にただの完全ハッシュを使うのでは本末転倒ですが
その処理を量子演算、量子アルゴリズムを使えば簡単に出来てしまうのではないか
という事を思いつきました。ただの思いつきではなくて見込みのある思いつきだと思います。

そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。（おれ誰？）あ、出掛けます。。。
857 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 04:24:47 ]: ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ
858 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 06:01:04 ]: >>856
そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。

＞しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。

だってこの発想からだろｗ
続きはブログでやれ。ブログぐらい持ってるよな？ｗ
859 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 11:40:59 ]: ふつーにBM法？
860 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:18:46 ]: >>857
その通りでした。でも、完全ハッシュを説明する為の例なので、言いたい事が伝わればいいかなと思います。

>>858
ブログありますよ。だいぶ書いてないので、仕様で少し大きめの広告をのせられてますが。。。

>>859
BM法は今まで使う機会が無かったですが、>>844には良さそう（？）です。良く分かりませんが。

量子アルゴリズムには一匹も釣れ・・誰も反応しませんねぇ。改めてWebで調べたら思っていたのと
ちょっと違う感じでしたが、少し考えを進ませました。量子アルゴリズムは厳密ではなくても高速で
結果を知りたい場合に有効らしいので、それを元に考えてみました。例えば、キーが3bitで表せるとして
101, 000, 010のデータに最小完全ハッシュを施すのに、3bitの全パターンの全並び（順列）の中から
データがなるべく始めの方に固まっているパターンを見つけます。例えば100 000 010 101 001 111 110 011
という並びは、始めの4つまでに全データが現れるので、ハッシュの大きさは4つ分ですみます。
次に、全並びに番号をつけたとしてその並びの番号を覚えます。この場合は0～!(2^3)-1の番号をつけて974を
覚えます。そして、例えば000のキーが知りたい場合は、番号から並びをほぼ正確に復元して
データのある位置がキーになり、なるべく正しい位置を探します。
この処理のどこかに量子アルゴリズムを適応できるか。あと、格納は置いときます。

翻訳>>851のつづき
-------------------------------------------------------------------------------
burst-trieのボトルネックを解決する為、トライ走査のコスト(作成されるだろうトライノードの数)を
かなり削減しなければならないが、より重要なのはbucketsを探すコストであるが、
それらが現在アクセスする中で最もコストのかかる要素だからである。
そのような削減はbucketsの表現をlinked listからキャッシュを考慮した巨大な配列に
変える事でしか達成できない。したがって、それはキャッシュを考慮したハッシュテーブルの
bucketsの構造化を考えるとよい(Askitis & Zobel 2005)。
シンプルな配列と対照させてハッシュ配列を使う利点は、bucketsがはるかに効率的にscale muchでき、
さらに保持されるトライノード数を減らせることである。
861 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:47:32 ]: >>860
ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。
862 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:56:42 ]: 多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ
なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。
863 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 12:04:51 ]: >>862 から僻み野郎の気配がビンビン感じられる件
864 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 16:41:59 ]: 流れはよく判らんけど訳すなら全部訳してくれると嬉しい
中途半端はよくないよ
865 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 20:58:14 ]: 全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。
多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。
866 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:29:56 ]: 木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？
ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします

現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー？って思ったんです
867 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:44:55 ]: 自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。
木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。
868 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:46:22 ]: あと昔のアルゴリズム事典に紐付き2分木というのがあったな。
末端の空きノードを利用するって事だったけど忘れた。
869 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:49:46 ]: まあ何も考えずスタックで組んだほうが保守も楽だし、
追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。
870 名前：デフォルトの名無しさん mailto:sage [2008/12/20(土) 01:36:40 ]: 昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef