- 1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ]
- 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉
>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。
前スレ↓
pc8.2ch.net/test/read.cgi/tech/1090227743/
- 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 ]
- うん
|
 |
