計算アルゴリズム【�U】

ある会計（０円〜９９９円）を行う際に
一回の硬貨のやり取り（渡す枚数+受け取る枚数）を最小にするアルゴリズム

考えているんだけど思いつかない・・・助けてくれ

void minimumExchange(int account) {
　　int pay = account;
　　int min = getCount(account);
　　for (int i = account + 1; i < 1000; i++) {
　　　　int c = getCount(i) + getCount(i - account);
　　　　if (c < min) {
　　　　　　pay = i;
　　　　　　min = c;
　　　　}
　　}

　　System.out.println("account=" + account + " pay=" + pay + " min=" + min);
}

int getCount(int n) {
　　int c = n/500;
　　n %= 500;
　　c += n/100;
　　n %= 100;
　　c += n/50;
　　n %= 50;
　　c += n/10;
　　n %= 10;
　　c += n/5;
　　n %= 5;
　　return c + n;
}

ちょっと修正

＞　　for (int i = account + 1; i < 1000; i++) {
を
　　for (int i = account + 1; i <= 10000; i++) {

＞int getCount(int n) {
を
int getCount(int n) {
　　n %= 1000;

アルゴリズムを考える時はまず、最も分かりやすい方法（しらみつぶしとか）を考えるといいと思います。
それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。

＃「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。

1円札から999円札まで1円単位の紙幣を使ってもいいんですよね
特に条件が指定されてないので

999円札なんて無いだろ
常識で考えれ
1円札を999枚使うんだ

>>452
>1円札を999枚使うんだ

現在有効なお金
ttp://www.boj.or.jp/type/list/yuko/okane.htm

一円券は今でも有効だから使用は違法ではないし
常識で考えて不可能というわけではないな。
つまり「現在発行されている」という条件がない限り、
硬貨のやり取りは常に0が最小というわけだ。

一本取られたな。

でも一円札とかって１円より価値あるよな

貨幣として使う分には１円だ。

そこでコイン商やオクだな

買いたい人が*いれば*ね。
はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。

金融恐慌時の裏面がすってないお札なんかは高かったりするのだろうか

刷られた数
使用された期間
現存数
等は少なければ少ないほど良い


どんなにいらなそうな物でもコレクターにとっては価値がある

そういえばうちの親父が記念硬貨とか集めてたな。
天皇陛下御在位６０年1万円硬貨とか。

売りたい人は山のようにいるから。

質問よろしいですか。

２次元空間上に重複して平面が沢山（簡単のため長方形で）ありました。
ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、
どんなアルゴリズムがいいでしょう？

よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも
教えていただけると助かります。

ん？

たとえばＡ４用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。
ピンが刺さっている紙を全部調べよう

って問題？

>>463
ピンを横に置くんじゃないの？

長方形と点のコリジョンだね。元データをグリッドに分割しておくのが
普通かな？２次元だと正方形や可変サイズのグリッドとか
ツリー状（検索を対数的なオーダーに減らす）にしておくとかいろいろ種類はあるよ。

重複していない空間の分割なら、もっと簡単なのだから
平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな

六十周年金貨はあったけど
五十周年金貨ってなかったよね？

そうです、紙をピン止めみたいな奴です。

3次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。

実装は難しくてもかまいません。

長方形は固定で点がいろいろ与えられるって考えていいのかな
今適当に考えただけだけど
最初に排他的な長方形の集合を探してR1とする
(多い方がいいけど最大独立点集合問題はNP困難なので適当でいい）
R1に含まれてない長方形の中から排他的な集合を探してR2とする。
これを再帰的に繰り返す。
点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。

全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから
結局全部チェックしなきゃいけなくなってしまうのでダメ。
もっといい方法があるのかもしれん。

空間を超平面で切って平面集合を2つに分ける。
両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。
探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。
これで全部の平面を総当りよりおよそ1/2の計算量になる。
あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。

空間を超平面で切るってのは、いわゆるBSP木みたいなもんですよね。

その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。
例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら
なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。

閾値より大きな領域は、別段そのツリー内に入れなければいいのでは？
単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。

空間を平面で切るときに
・一方の空間に完全に属する領域の集合（２つ）
・断面と交わる領域の集合
の３つに分けてみるのはどうか．こうすれば各領域は必ず一箇所に属する．

探索するときは，断面上の領域と点の落ちる空間内の領域の２つを調べる．

断面と交わる領域の格納は
数が少ないとき（多分，n < (log(n))^d'（d'は断面の次元）のとき）は単純なリスト
数が多いときは１つ次元を落とした同様の構造にする

よくわからないけど最終的には
(log(n))^d （dは次元）←適当
あたりになりそうな気がする．

>470-471 >473
なぜ一般次元に拡張を…
応用が利くのは良いっちゃあ良いんだけど微妙

>>472
大きいというか、重複が多い場合に結構問題になるんです。
今回は空間全ての領域で少なくとも３枚は被さっているのを想定してるんで、
必要な記憶領域がかなり大きくなってしまうという。

>>473
あ、そうか、２つとも探索すればいいんですね。
１次元で紙に書いてみたら、いけそうな感じです。
記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。
よーし、明日の夜にでも組んでみます。

こーいうのって全くの別人が同時期に同じ解法を求める事ってないよな。

特定(ry

空間を分けるってちゃんと図形の配置を考えてやるの?
そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ
それに重なってるところは分割できないので結局全探索になる

473氏の方法をちょっと変えた物で、無事実装完了しました。今のところい
い感じに動いています。ありがとうございました。

高卒でしかも数II？とか勉強いたことない俺にはまったく理解できないんだが
どうすりゃいい？

絵を描いてみる
諦める

>>479
余り気付かれていないが、高校生ではなくても高校レベルの数学を
勉強することはできる。

>>477
おまえ他人の言ってる事理解してないよ
でしゃばるなカス

>>482
理解できてないといって理由を書かない

自然科学なんかだと、実測データをグラフにプロットしたあと、なめらかな曲線でつないだりしますが、
そういう曲線を計算するアルゴリズムはありますか？

つ[Excel]
一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。

ググってたらcurve fittingと呼ばれている問題だと分かりました。
すれを汚してすいませんでした。

>>485
キーワードありがとうございます。
調べてみます。

最小二乗法とかね

SHA-1のハッシュを求めるプログラムを作ろうと調べていて
ttp://homepage2.nifty.com/bkclass/doc_sha1.html
のサイトを見ていたのですが、

他に参考になるサイトはありませんか？

Wikipedia(EN)

計算アルゴリズムには限界があり、結局は全部探索したほうが良いって結論？

そーでもないと思う。問題が大規模な場合はアルゴリズム使わないと無理だね。
でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、
問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が
安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち
ゃうし。

２４シーズン�Xで解析に、独自のアルゴリズムを使って出す、とか言ってた。

OR

今日専門の方でアルゴリズムの授業が行われたんですがその際この3問だけどうしてもわかりません
何方かこの3問のフローチャートがかける方が居ましたら教えてください
1問目：成績判定１
アルゴリズムの点数を入力して、80点以上のとき「Ａ」、60点以上80点未満の時「B」、60点未満の時「Ｃ」
と出力するフローを答えなさい

2問目：成績判定２
英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。
なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること

3問目：成績判定3
2-12.成績判定2の選択処理の部分を一つにまとめなさい
選択処理部分
英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する

アルゴリズムじゃない。

そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。

それが問題集しかもらってなくてわからないんですよ

>>495
ttp://www.cs.takushoku-u.ac.jp/caed/kisosemi/k7/FlowChart.html
これみりゃ大体わかるだろ。
いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。

スレ違いsage

問題集しかもらってなくてわからないとか言うんだったら、
2chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で
わからないのであったら講師や友達に聞け。

ぐぐれる香具師
友達いる香具師

は

2chで質問しない

友達の作り方を教える本でも買った方がいいと思う。

おとうさんはネットで調べても作れなかったけど

グラフ探索でダイクストラやA*より良いのない？

それはそうとA*探索はぐぐるのが難しい。

>>503
「Astar探索」とかでググってみたら？
ちなみにA*の場合、heuristicsがadmissible（各ノードから目的地までの予測コストが実際のコストを決して上回らない）でconsistent（いわゆる三角不等式が成立）なら、必ず最適解を返すよ。
それよりも良いってのは、heuristicsを設計できない場合ってこと？

どんな探索かわからんし、「良いの」って意味もわからんなあ。

>>504
そうですね、良いヒューリスティックを設計できない時です。
近似解法含め、良いのを探してます。

>>505
たしかに「良い」ってのはアバウトでした＾＾；
主観的にでも、よさげなアルゴリズムがないかなぁと。
検索してもダイクストラばっかり引っかかるもので。

すみません、間違えて名前欄に書いてしまいました・・・

最短路探索ってことでいいの？

だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、
実用的にはヒューリスティックに頼るってのが現在の理解だと思う。
（現在行われてるコンテストでもそんな調子だよね）

近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに
ヒューリスティックを突っ込んだりするくらいだけど、
グラフが何の性質も持たない場合は性能評価が難しいところ。

ヒルス達がやってる６４個のソート問題ってどんな問題？

クイックソート問題

つまりのところ、厳密解を求めるなら、あまり良くないヒューリスティック
を用意した時、A*（と色々な改良版）が最速ってことですか。
というか、授業で習ったダイクストラとA*しか知らない物で＾＾；

近似についても、微妙な改良版くらいしかないって事ですね。

>>511
とにかく実行速度をなんとかしたいという実用的な要求なら、
問題にあったヒューリスティックとヒープを設計して A* が
たぶんもっとも現実的だと思う。

近似は、微妙な改良版といっても、たとえば幾何グラフとかなら
普通の Dijkstra と比較して一億倍以上早くなるケースもザラなので、
具体的な問題を見ないとなんともいえないところ。

ありがとうございます。じゃヒューリスティックに精を出してみることに
します。ちなみに問題は経路探索です。

>513
ちなみに、カーナビの経路探索だと、ネットワーク側の方を階層的にいくつか持って切り替えることによって高速化してる。
現在地、目的地近辺では全道路のネットワークで探索、それで見つからなければ国道以上のネットワークに移って探索、
さらに探索する場合は高速道路のみのネットワークに移って探索、みたいな感じ。
もちろん最適解は出ないけど、そもそもカーナビの場合、計算で出てくる最適解が、ドライバーにとって最適になるとも限らないしね。

あぁ、なるほど、中距離の探索とかで、たまにすごくアホな間違いをするの
はそれが理由なんだ。

いや
渋滞回避してるだけだろう

http://pc11.2ch.net/test/read.cgi/jisaku/1179911252/
上記スレで強制NaNの計算でインテル不利にするベンチが論争を呼んでますが
極端にAMD不利にする方法を探しています。
では。

多倍長演算の割り算のアルゴリズムで
たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
２桁目を決めよう
↓
答えは10かな？21*10＝210で521より小さい
↓
じゃ20かな？21*20＝420＜521
↓
じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする）
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は１桁目・・・

こんなのを考えたのですが、もっと良い方法はないですか？

age

何このマルチレス

10,20,30...
だったら時間掛かるだろ

自分で考える前にまず一般にどういう方法が使われているかを知れ
せっかく苦労して自分で考えついたとしても
それが既にみんなが普通に使ってるものと同じやそれ以下だったら悲しいだろ？

http://ss.nkk.affrc.go.jp/library/publication/seika/seikajyoho/2003/15/15.html
に記述されている、
図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？

マルチうぜえ

ウィキペディアでB木の項を参照すると、
B+木やB*木というものが存在するとに書いてありますが、
どういったものですか？

>（厳密にはB木の改良型であるB+木やB*木を使うことが多い)

B+ は B であって、キーを葉にのみ格納するもの
B* は B で、子の比が 1/2 だったところを 2/3 にしたもの

wikipedia の情報は不正確だから参考にすんな
ちゃんとした教科書とか論文を参照すれば分かるだろ

>>526
ありがとうございました。
ウィキペディアから引用したら怒らせてしまった様で。
たまたま名前が載ってたから出しただけです。
B+木B*木は名前だけは以前から知ってましたが、
ググっても関係しそうなのは引っかからないですね。
本は
アルゴリズム事典
はじめてのアルゴリズム入門
アルゴリズムとデータ構造
など持ってますが、載ってないみたいです。

>教科書とか論文
できればこれのポインタ教えてください。

>>527
誰が怒っているの?

>教科書とか論文
できればこれのポインタ教えてください。

>>527
B-plus-tree とか B-star-tree で検索すればいくらでも出るんだけどね。

教科書については、そんな一般的なアルゴリズムの本には
あまり出てなくて、データベースよりの本を見ないとダメ。
R. Ramakrishnan, J. Gehrke, "Database Management Systems", 3rdEd. McGlaw-Hill, 2002

まあ次のサーベイ論文がよくまとまってるので、これを読んでおけば十分だろうけど。
D. Comer, "Ubiquitous B-Tree", ACM Computing Surveys, 1979
(http://www.cl.cam.ac.uk/~smh22/docs/ubiquitous_btree.pdf)

便乗だけど、B木と赤黒木どっちがいいか、
って判断はどこら辺ですればいいですか？
使い分ける時の基準みたいなのが知りたい。

>>531
どんな用途に使おうとしてるか分からないので、普通の設定で一般的な話をする。
赤黒木は、本質的にはブロックサイズの小さな B 木なので、
あなたの質問は B 木のブロックサイズをどう選ぶか、という質問と同じ。

普通の実装では、n 個の要素を格納するブロックサイズが b の B 木から
要素を検索には O(log (n/b)) 回の木上の探索（ランダムアクセス）と
O(b) 回のブロック内の探索（シーケンシャルアクセス）が必要となる。

ここで雑な計算をするとブロックサイズは、木上の探索の速度と
ブロック内の探索の速度の比くらいに選ぶのがよいことが分かる。

木が丸ごと全部メモリに乗るような場合は、木のアクセスもブロックの
アクセスも同じくらいなので、ブロックサイズも小さく選ぶのが良い。
一方、ハードディスクやネットワーク上のデータベースのような
木のアクセスが遅く、ブロックのアクセスが早い場合は、
ブロックサイズも大きく選ぶのが良い。

>>528 参考にすんな→この人怒ってる怖いよぉ

どこぞの園児じゃあるまいし。

なんでそんな偉そうなんですか

どこが偉そうなの

質問を質問で返すな
わかりませんと言え

なんでそんな偉そうなの

そういうのは質問の体をなしてから言え

順序付きコンテナは、どうもトライが最強っぽいんだけど、
メモリが・・
なんとかなりませんか？

つ パトリシア

2Dの多角形ポリゴン2個(n個)を合成して1個(?)の多角形にするアルゴリズム

ネット上にこれを実装したソースコードが公開されてない(見つからない・・・)のでどなたか教えてください。
＿＿
＿|＿ |
| |＿|＿|
|＿＿|

ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
　↓
＿＿
＿| |
| ＿|
|＿＿|

ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)

というような感じです。
中抜き( 合成後のポリゴンの内側に穴が開いている )まで考えると、結構むずかしそうで・・・

これでやりたいことは、国土地理院の市町村別のポリゴンデータを県ごとに合成して、県別のポリゴンデータにすることです。
Excel VBAで精細な都道府県地図を描きたいなーと思って、
都道府県の無料のポリゴンデータを探したけど市町村別しか見つからなかったので
じゃあ合成して作ろうか、と思ってたんですが・・・詰まりました。

Java の awt パッケージでポリゴンの合成をしているクラスのオリジナルのソースコードを見ればアルゴリズムがわかるかも
とも思ってみてみたけどソースコードは入っておらず・・・orz

宿題とか課題とかではなくて、あくまで趣味的なものなので急ぎません。
VBでもcでもc++でも良いので、どなたか、お知恵を拝借させてください。

>>542
図形ずれちゃった・・・
　　＿＿
＿|＿　 |
|　|＿|＿|
|＿＿|

ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
　↓
　 ＿＿
＿|　　|
|　　＿|
|＿|

ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)

こうです。

>542
悪いこと言わないから別の方法考えたほうがいいと思う。
塗り分けるだけなら市町村別のデータでも構わないわけだし。

で、
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277X
の第 2 章にアルゴリズムは載ってる。でも、ここから実装まで持っていくのもそう単純じゃないと思う。

あと、オープンソースライブラリの CGAL にそういう機能はある。
http://www.cgal.org/
Reference Manual の VI Polygon and Polyhedron Operations 辺り。

>>544
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277Xの第2章 早速読んできました。
例題に挙げられてるのも地図でよさそうだったけど、
プログラミング言語を限定してないアルゴリズムとしての本なんで、
やろうとしていることを実装するには、どういうプログラムを書けばよいのかまでは踏み込めなそうです。

せめて
i ← S1 と S2 の交点
みたいなのがあればなぁ。


CGALのマニュアルも読んでみました。joinあたりのコードか数式が出ていればVBAでも実装できそうなんですが・・・

>悪いこと言わないから別の方法考えたほうがいいと思う。
そうですねー。
ただ、ポリゴンをくっつけるのはもうちょっと粘ってみます。考えるのも楽しいので。

市町村同士は重ならないので、
・辺と辺が重なっている（隣り合っている）ところを見つけてくっつけていく
・中抜きはこの際無視
というように簡単なものを作る方針で考えてみます。
重なりまで考えて汎用的なアルゴリズムにしようと思ったけど、結構しんどそうですので・・・

どうもありがとうございましたー。

今日から専門学校のほうで授業アルゴリズムが始まったんですが
時間計算
分時間を入力して○時○分に変換して出力するフローのaとbに該当する処理を記述しなさい。
なお、計算結果は整数部のみとし、小数部は切捨てとなる。
余り（X%Y)で除数の余りを求めることができる。[例、余り（100%3）は1となる]
例：117分の時　1時間57分
（開　始）　何方かa bに入る答えがわかる方いましたら教えてください
　　↓
（データ）・・分時間を入力
　　↓
（処理）・・a 時を求める
　　↓
（データ）・・時を出力
　　↓
（処理）・・b 残りの分を求める
　　↓
（データ）・・分を出力
　　↓
（終了）

aとbに入るのは数字？式？言葉？

式です＾＾；

a・・・分時間/60
b・・・分時間%60

>>546
宿題はスレ違い
しかも回答もらって礼も無しかよ

三角関数はマクローリン展開して計算しますよね。
単純に考えればsinθのθが何であれ計算時間は変わりませんが、
速度面でチューニングが施されているであろうライブラリではどうなんでしょう？

>三角関数はマクローリン展開して計算しますよね。
ここで間違ってる
関数近似の教科書読むべし

>>552
すみません、悠長に教科書読んでる暇がないので結論をお願いします

CPUのアーキテクチャ等やライブラリ作った奴の腕に依存して色々な可能性がある
ただ，どれもθを0〜π/2の範囲に正規化してるだろうから
その範囲なら少し速いはず
これ以上は本嫁

ぶっちゃけ、今時の単精度演算アクセラレータはテーブル参照プラスリニア補間で済ませている希ガス。

>>554
絶対的な速度が問題なのではなく、速度のむらを気にしているのです。
たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか？ということです

>>555
ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。

ターゲットはSH7145
ルネサスのコンパイラを使ってます。
ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので
VCやgccだったらどうなのかという意見でもいいのでお願いします。

後出し多いな

5倍の差はないだろうけど，1〜2割位なら充分あり得る
実測するのが手っ取り早いかと

>>556
マイコンの方がむしろテーブル変換使用すると思うが

>>554
いっそπ/8に正規化するとか

>>553
＞悠長に教科書読んでる暇がないので

そうか。残念だったな。

差異のアルゴリズムでレーベンシュタイン距離を求めていますが、
結局これ求めてどうなるんですか？
馬鹿でも分かるようにく教えてください。

>>562
そんな限られた分野でしか使わないようなものを
さも誰もが知ってるかのように聞かなくても。

自然言語処理とかで使う。
Google 先生とかがよくやってる
もしかして: ○○
を出したりとかに使える。

>563
レスどうも。

2つの文字列を比較して"n文字違います"とかは想像できるんだけど、
diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、

>>564
http://ja.wikipedia.org/wiki/Diff

今、ロバスト解について勉強しています。
ロバスト解発見手法にはシックスシグマ法のDesign For Six Sigma[Brue 03]やDesign For Multi-Objective Six Sigma[Shimoyama 06]、またはガウスノイズがあるということが分かりました。
しかし、上に述べた手法の利点・欠点がほとんど分かりません。
どなたか他の手法と比べた場合の利点・欠点を教えてはいただけないでしょうか?
下に今分かっていることを書きます。
----------------------------------------------------------------------
Design For Six Sigma[Brue 03]
ロバスト解を1つ発見する場合に有効。

Design For Multi-Objective Six Sigma[Shimoyama 06]
Design For Six Sigma[Brue 03]を拡張したもの。複数のロバスト解を同時に発見する場合に有効。

ガウスノイズ
アルゴリズムは簡単。
ガウスノイズは上に述べたシックスシグマ法を使ったときよりもすばやく収束できる。
吸収現象などのせいでロバスト解からずれた位置に収束するかもしれない。

質問させてください．
y=Ax （x,y:ベクトル， A:マトリックス，大きさ数百〜数万）
に対し，
x = inv(A) * y
を解く問題を考えています．
ここで，逆行列演算inv(A)がO(N^3)のコストが掛かり，ネックになっています．
いま，Aは疎な帯行列（しかも対称）という条件があるので，
大幅な計算削減ができるのではないか？と考えております．
例えば，計算コストをO(N^2)にするといったことは可能でしょうか？
キーワードだけでも良いので，知恵を貸していただけると幸いです．

つ[特異値分解]

>>567
LU使っているのか？
対称行列だと、LDL分解でOK
帯行列だとさらに、0要素を見ないことで、さらにスピードアップ

そんな話，数値計算の本見ればいくらでも載ってるだろ

>>568
キーワードありがとうございます！
調べてみます．

>>569
LU分解→直接法で逆行列としていました．
LDL分解というものがあるのですね．
解法は反復法に持って行くのですかね・・・調べてみようと思います．
反復法は精度の面が少し気になりますが，勉強含めて試してみます．
多謝！

>>570
数値計算の門外漢なもので・・・勉強してきます．

kd木で、近い領域を何度も連続して調べたい時、毎回根から辿らないようにショートカットするような技法ってありますか？

二つの整列済みリストのマージで
要素数が一方がk個,もう一方が2個の場合,
n回の比較でマージできる最大のkをanとすると
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
で与えられるらしいのですが
これがどういうアルゴリズムでマージしたときの物なのか,
またこれが最良値なのか知りたいのですが, 誰か知りません?

>>573
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
この式を見るとnが1増えると√2倍でa[n]は指数的な増加。

ソート済みk個と2個のマージは
2分探索を2回使えば2logk回。
詳しくは見てないが、2logkの係数の2が√2になりそうだし、
kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。

>>574
考えてくれてありがとう.
2分探索だけだと最良値にはならないみたい.
573の式だと最初の10個位までは最良値になってるのは
確認できた(虱潰しで)

さらに知らべて,もう一方のリストが3個の場合みっけた.
Optimal Merging of 3 Elements with n Elements
っていう論文のAbstructで
f3(1)=0, f3(2)=1, f3(3)=1, f3(4)=2, f3(5)=3, f3(6)=4, f3(7)=6, f3(8)=8
r >= 3
f3(3r) = [(43/7)*2**(r-2)]-2
f3(3r+1) = [(107/7)*2**(r-3)]-2
f3(3r+2) = [17*(2**(r-3)-6)/7]-1
との事.

各データの値がかなり近い時に
ハッシュのみだとデータの衝突回数
多い場合ってどうやってみんななら解決する？

あとね、kd木で何の本に詳しく載ってますか？

値近くてハッシュが衝突するって、どんなアルゴリズムだよ

8byteの16進データを
完全ハッシュ化するソースコード置いてある
とこないですか？

区分サンプリング法やラテン超方格法のアルゴリズムを教えてください。

二点で定義されてる直線上に、ある点があるかどうかを判定するにはどうすればいいですか、教えてください。

要は３点が一直線に並んでいるかを知りたい、と解釈し直してみた。
１点を基準に他２点へ直線を引くときの傾きが一緒だったらOK。
x軸と垂直だった場合なんかも考慮すると、
(x1-x0)*(y2-y0)==(x2-x0)*(y1-y0)

あ、なるほど、ありがとうございます

[N][N]の2次元配列を３つ

[N]の配列を2つ使ってる場合の使用領域のオーダーってＯ(n^2)におさまります？

うん

3N^2+2N = O(N^2) が分かってないのか？

グレブナ基底を求めるプログラム、誰か持っていませんか？
C言語でおねがいしたいです。

>>586
23457円になります。

均一なセル上に分割した空間で、円（または球）を配置して、円と交差する
セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう？

セルってのはよくわからないのだが、格子なの？
格子が座標と平行になるように回転変換して　格子間隔が1になるように伸縮して
円の中心座標の小数点以下座標を見ればいいだけでは？

あ、格子です。あ、最初から座標軸並行を仮定してます。
さらに辺の長さを1で仮定してしまいましょか。
えーと意味がいまいちつかめないんですが、

＞格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮
これは元々が単位格子であるなら何もしないでOK?

＞円の中心座標の小数点以下座標
これで、なぜ全ての格子が求まるかがわかりません。
整数部をみれば、中心を含む格子は求まると思いますが。

欲しいのは「円周」と交わるセルだろ？
そこがちゃんと書いてないから勘違いされたと思われ

あ、そうです。申し訳ない。

DDA(digital diffrential analyzer)というのがあるが使えないかな？
３次元は分からんが

3次元も、半径が違う円で切り出したものと考えればイケルんじゃないの？

ある年月日が与えられ、そのn日後の日付を求めたいのですが、
1,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める
2,days+nを西暦年月日に変換する
という方法を考えました。
2は1の式を変形して解けるだろうと見当を付けていましたが、
小数点以下を切り捨てたりしているためうまく式を求められません。
素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか？
日付は最近のものに限定して考えています。
ユリウス暦とグレゴリオ暦の判断が面倒になるので…

>>595
日付を1日進めるプログラムは書けるかい？

おｋ。ならば、1日進める部分をn回実行するんだ。

つーか、なんで既存ライブラリを使わないのだろう。
大抵の言語に日付け処理系の関数があると言うのに。

>>595
ttp://ufcpp.net/study/algorithm/o_days.html

>>595
ちょっと検索してみたらこんなのがあった
delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい

ttp://kwikwi.cocolog-nifty.com/blog/2005/12/delphi_266f.html

ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの？
日本のサイトしか引っかからないんだよね

>>596
なるほど。
ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので
上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと･･･
>>597
Cなのでそういった関数はもちろんあるのですが、若干不便なので
勉強も兼ねて自前で実装してみようというわけです。

>>598
おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25　　…?　もはや何がなんだか。

ttp://cl.is.kyushu-u.ac.jp/Literacy/PP/H14/adp/program/date.html
こんなの見つけたので読んできます。

>>600
ttp://www.tensyo.com/urame/date/day_c.shm
ここの
int YMD_AddD(int *Y,char *M,char *D,long d）　って関数を見ると
負数を渡した場合は　400年循環を使って正に直せばいいみたい。

つまり、-3日なら 400年前から(146097-3)日後と計算するわけか

除算のシフト演算化はコンパイラの最適化段階で
自動でやってくれるものだと思ってたんだが、そうでもない？

コンパイラの性能がソレなりならって事でしょう。
固定値の除算ならさらに、掛け算で代用してくれるのも多いね。

>>604
2のべきの定数ならね。

という事で
１、カレンダを1日進める関数関数を作る
２、+N日は１の関数をN回呼ぶ
３、-N日は、年数を400日戻してから、146097-N回 １の関数を呼ぶ

これでいいのかな？
struct Date{
　int year,month,day;
};
/* 1日進める */
void tomorrow(Date& x)
{
　int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
　if((x.year%4==0 && x.year%100!=0) || x.year%400==0){
　　days[2]++;
　}
　x.day++;
　if(x.day>days[x.month]){
　　x.day=1;
　　x.month++;
　}
　if(x.month>12){
　　x.month=1;
　　x.year++;
　}
}

/* n日後の日付 */
Date after(Date x,int n)
{
　for(int i=0;i<n;i++){
　　tomorrow(x);
　}
　return x;
}
/* n日前の日付 */
Date before(Date x,int n)
{
　n=146097-n;
　for(int i=0;i<n;i++){
　　tomorrow(x);
　}
　x.year-=400;
　return x;
}

「1にちずつ遡りながら日付を表示」とかやるとbefore()の処理量が馬鹿にならないので、
>>601に載ってるのを参考に書き換えてみました
/* 西暦1年1月0日からの経過日数から、日付を求める */
Date make_date(int n)
{
　int y=(n+305)/146097*400
　　　　+(n+305)%146097/36524*100
　　　　+(n+305)%146097%36524/1461*4
　　　　+(n+305)%146097%36524%1461/365;
　int diff=n-(365*(y-1)+y/4-y/100+y/400+31+28);　// 3月0日からの経過日数
　if(diff==0){　　　　//2月29日
　　diff=366;
　　y--;
　}
　int m;
　for(m=3;;m++){
　　//3月0日からm月0日までの経過日数, 30*(m-3)+3*(m+1)/5-2 の変形
　　if(153*(m+1)/5-122<diff && diff<=153*(m+2)/5-122){　
　　　break;
　　}
　}
　int d=diff-(153*(m+1)/5-122);
　if(m>12){
　　m-=12;
　　y++;
　}
　Date x={y,m,d};
　return x;
}

漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ

誤爆です。
ごめんなさい

>>611
そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。

質問させてください。

「ハッカーのたのしみ」p137 で多倍長のかけ算のサンプルがあったのですが、
わからない部分があります。

void mulmns( unsigned short w[], unsigned short u[], unsigned short v[], int m, int n ) {
unsigned int k, t, b;
int i, j;
for( i = 0; i < m; i++ ) {
w[ i ] = 0;
}
for( j = 0; j < n; j++ ) {
k = 0;
for( i = 0; i < m; i++ ) {
t = u[i] * v[j] + w[ i + j ] + k;
w[ i + j ] = t;
k = t >> 16;
}
w[ j + m ] = k;
}
}

u と v がかける数、かけられる数、w に結果が入ることはわかるのですが、k は何に使われているんでしょうか？

繰り上がり

>>615 すばやい回答ありがとうございます。
くりあがりですね。

このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、
この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？

>>616
そのとおり。

10進数で画面に表示する回数が、普通の計算を行う回数よりも
圧倒的に少ないと考えると、そういう数の表現になる。

w[ i + j ] = t;
k = t >> 16;
この部分を
　k = t/10;
　t -=k*10;
w[ i + j ] = t;
とすれば、１０進法になるんじゃない？
8bitなら１００進数
16bitなら10000進数なんてのがオススメだよ

HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた

行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、
調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか？

誤差についてはほとんど知識がないので調べてみました。
たまたま今やっていることに関係あるので。

さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。
なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を
しなければいけないこと。まぁ大体こんな感じです。

ではなぜ掃き出し法が誤差が大きいかというと、予測ですが
単純に計算量が他に比べて多いからではないでしょうか。
誤差を含む演算はやればやるほど誤差が大きくなるというわけです。

ちゃんとした理由ではないかもしれませんが、それよりも
どうすれば誤差を小さくできるか考えた法がいいと思います。
まぁ原因が分からなくては始まりませんが。

>>621
そんなに詳しくないから適当に書くけど、
基本的にはその通り。
収束性が悪いほど誤差は積もりやすい。

あと、除算があると誤差大きくなる。
なので、掃き出し法みたいな手計算的手法のものよりも、
ガウスザイデル法みたいな反復計算の方が誤差少ない。

>>620
一概にそうとは言えない。というか、単純に比べることは不適当。


そもそも掃き出しは（解けるならば）必ず A x = b を解くが、
ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。
したがって、無条件で比較することはできない。

次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。
一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。
反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。

>>623
掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか？
新たな課題ですね(￣□￣;)!!
実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、
エクセルの分析ツールの回帰分析した結果、
後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。
後者はガウスザイデルなのかもしれません。

>>624
マクロでやってるなら、ピボットの選択してる？

>>624
掃き出しで解けてガウスザイデルで解けない問題なんて
いくらでもあるよ．たとえば
　x + 2 y = 1
　2 x + y = 1
をこの順番で連立方程式と考え，ガウスザイデルを
初期値 x = 0, y = 0 で適用すると，発散する．
ガウスザイデルが収束する必要十分条件は，未解決のはず．

>>625
＞ マクロでやってるなら、ピボットの選択してる？
いえ、まず中心をすべて1にしてから掃き出しています。
これではダメでしょうか？

>>627
ダメ

あげ

ユークリッドのアルゴリズム(テキストp.10参照．java版はHP参照)を用いて
1,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、
引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック
1GHzに相当）を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。
「X年Xヶ月」など実感が分かる単位に直して答えよ。

この解き方がわかる人がいましたら是非教えて下さい。
解けなくて困っています。

>>630
宿題は自分で解決しようと努力しないと意味がないぞ
どこまでは理解できていて、どこが分からないんだ？

というか、奇妙な問題だな
10^N は N>=2 なら25で割り切れる。
つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう

もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら
って場合か？　それでも実感がわかる単位にはならないわな

・>>630が問題を間違えている
・出題者のちょっとした遊び心
どっちかじゃね？

難しそうに見えて実は簡単な問題を出して
最初から課題をやる気がない奴を調べるためだったりしてｗ

int型のデータをN個格納できる配列aを考える．つまり，配列要素は a[0],
a[1], ..., a[N-1] でアクセスする．a[0]〜a[k]まではデータが既に格
納されており，a[k+1]〜a[N-1]までは「空き」の状態であるとする(0 <= k < N)．
このとき，次に挙げる各操作に必要な手間(時間)を，「最も手間のかから
ない場合」と「最も手間のかかる場合」のそれぞれの場合について答えよ．
理由も書くこと．(例を参考にせよ)

例：指定された位置にデータを挿入する操作

答:最も手間のかからない場合：定数時間
最も手間のかかる場合：kに比例する時間
理由：指定された位置が末尾の場合には，データをずらす必要がな
いため定数時間で可能．指定された位置が先頭の場合には，既に格
納されているk+1個のデータを順にずらす必要があるため，kに比例
した時間が必要．

1-1 指定した位置のデータを削除する操作
1-2 指定したデータが格納されているか探索する操作
1-3 格納されているデータの中で最小の値を探索する操作

これを現在解こうと思っていますが、よく分かりません。
分かる人は是非教えて下さい、お願いします。

1-1
最良：定数
最悪：k比例
1-2
最良：定数
最悪：k比例
1-3
最良：k比例
最悪：k比例

配列を用いてリストを実現することを考える．今，配列には以下のように
データが格納されているとする．(配列keyと配列nextはint型のデータを格
納するとする)

key[0] = 0 ,next[0] = 3
key[1] = 0 ,next[1] = 1
key[2] = 'S' ,next[2] = 6
key[3] = 'L' ,next[3] = 4
key[4] = 'A' ,next[4] = 5
key[5] = 'I' ,next[5] = 2
key[6] = 'T' ,next[6] = 1

位置0はhead, 位置1はzを表す．
このとき，次の問に答えよ．

(1)リストに格納されている文字を，リストの先頭から順に書け．
(2) もしも next[0] の値が4だった場合，リストに格納されている文字を
リストの先頭から順に書くとどうなるか述べよ．
(3) リストから'A'を格納している節点(key[4]とnext[4]に対応)を削除し
た場合，配列keyと配列nextの中身はどのように変化するか述べよ
(key[4]とnext[4]の値はそれぞれ0に設定せよ)

ここは宿題すれじゃねーんだよ・・・

行列計算のガウスザイデル法が収束しないことがあるので気になっていたけど
検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。
(残差を最小にするから、たとえ解が無くても最適な値が求まる？収束に向かうのは確実？)

ただ、ガウスザイデル法は数行のプログラムなのに対して
見つけたプログラムがかなりでかいサイズになっているのがまた気になる。

ガウスザイデル法で残差を小さくするような改良って無いのかな？誰か知ってる？

これが、SOR法である。
ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。
http://www.akita-nct.ac.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html

ω=1.9から始めて発散なら値を引き下げていけばいいって事だな
ω=1がもともとのやつ　

ガウスザイデル法には，原理的に収束しないインスタンスが存在するので
収束しないことが気になるような場合には，そもそも使ったらダメ．
これはSORでも状況は変わらない．

GMResやらBiCGやらIDRやら反復解法は色々あるんだから
解きたい問題にあわせて適切に解法を選ばないとダメよ．

原理的に収束しないとは? 解が存在する行列でもできないってこと?

>>641
なるほど、どうもです。
プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが
やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても
その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。

>>642
そのとおり．
ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて
解が存在しても，収束するとは限らない．

いつ収束するかの厳密なところ（必要十分条件）は，現在でも未解決問題．

>>644
639のこれは?

。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。

>>644
SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている
ωの値によって収束が左右される　0に近づければガウスザイデル法で無理な場合も収束するのでは?

ω=1はガウスザイデル法である

グレースケール変換。こいつより高速アルゴキボンヌ。
条件：徐々にグレースケール変換できればvolumeの持たせ方は自由

// 【メソッド名】convGrayScale
// 【引数説明】
// srcRGB：変換元画像(0xRRGGBBのピクセル配列)
// pixel_num：ピクセル数
// volume 0(無変換)〜255(完全変換)の範囲でグレースケールに変換
// dstRGB：変換先(0xRRGGBBのピクセル配列)

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;　// 変換結果
　　}
}

あ、一応JavaだけどCとかでもおｋ

volumeって要は、グレイ化度合いみたいなものなのね。
処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。

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に使うことはない

ちなみに、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

Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
これの意味を教えて

>>654
YUV とか 色空間あたりでググって見たら、、、
wikipedia の 「色空間」だとか
http://ofo.jp/osakana/cgtips/grayscale.phtml の 2.NTSC 〜
にある式を 小数点 の無い形にしたと考えたらいいんじゃない?

こういう時は
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) );
としたら掛け算は減らせるよ

>>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

>>657
distRGB の方は、
(red + (〜)>>8)<<16 を red<<16 + (〜)<<8 などど展開して
red<<16+green<<8+blue とまとめて、
*volume) << の部分を出して因数分解できれば良さげだよね。
>>8 の方も レジスタの H を取るような方法で早くなるかな。
だだ、新しいCPUだと シフト演算もテーブル化してあって
シフト回数がステート数に影響しないからなぁ。
あっ。もうすぐ9時なのでここまででカキコ。

java　だから　割り算をシフトにするとかの最適化があんまり効かないのかもな

どの行が一番時間かかってるか　コメントアウトしては時間計って
一番時間かかってる行から順に工夫してゆくしかないと思うけど
cかDelphiでDLL作った方が早いんじゃないの？

あとは
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 は最初からそう使えば問題ない
でも半分は無理だろな

>>645
任意のパラメタωに対して、真の解に収束しない例が作れる．

>>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
クイックソートがソートの中で最速ってわけではないが……
同じデータ数なら、挿入法よりもクイックソートの方が
ソートが完了するまでの比較回数やデータ位置の入れ替えの回数が
平均的に少ないアルゴリズムになっているから。
ソートは基本的にループや再帰呼び出しによる操作だけれど、
ループに入る前や出た後の準備や後始末、
それにループ内での操作が少しくらい複雑になっても、
ループや再帰の回数がそれを補って余るだけ減少する方法なら全体として速くなる。

>>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回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。

エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)

>>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？

あげ

http://www.forest.impress.co.jp/article/2007/04/24/dfsupt.html
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）

この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか？

失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)

プログラミングの為の数学と算数 vol.3
http://pc11.2ch.net/test/read.cgi/tech/1197063023/

>>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？

>>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。

>>669
手始めに ONP とか LCS とかでググレばいいんじゃね。

ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。

どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。　いや、やりたいことはdiffなんだろうけど。

>>674
オリジナルの文のうち、消えた部分を特定できれば十分です。

aaa　aaa
bbb　ccc
ccc　ddd

左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。

>>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。

外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
２ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおｋ

> 手軽にやりたくて、

今時 FC はないだろ。

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

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

参考 URL: http://d.hatena.ne.jp/siokoshou/20070308

>>677
DFってそういう出力する方法あるのか？

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

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


あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。

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

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

比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。

動的計画法と配列アラインメント
ttp://www.ibm.com/developerworks/jp/java/library/j-seqalign/index.html

↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。

>>679
勧めた理由はその次の行に書いたが？

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

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


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

>>681
> 勧めた理由はその次の行に書いたが？

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

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

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

頑張れ > >>669

確かにプログラム書くことが目的なのかアルゴリズム知ることが目的なのかもはっきりしてなかったね。

とはいえスレとしては後者として考えるべきだった。　ｽﾏﾝｶｯﾀ

みなさん暖かい支援どうもですm(_ _)m

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

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

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

さっそくO(ND)とO(NP)を解説した原著論文をDLしてきたのですがなかなか全体像を
把握するのが難しいです(´･ω･｀)
もう少し優しくかみ砕いて説明してくれているサイト、できましたら日本語で、があれば
嬉しいのですがそういうサイトは無いでしょうか？

>>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
http://d.hatena.ne.jp/siokoshou/20070315

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

早速この二つを比較してみたところ。
オリジナルの"aaa"はCommon（共通）と判断されたものの、オリジナルの"bbb"はModified（変更）
と判断されました。ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

>>685
もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?

>>686
左のbbbには\nを付けましたが、やはりModifiedが返されるようです。

あと
aaa　aaa
bbb　ccc
　　　 bbb
だと

Common
Modified
Common

と返されるようです。
オリジナルが2行なのに返される行が3行だと後々の処理がちょっとややこしくなるかもしれません・・・

> ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

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

あと、それはそれとしてバイナリエディタを１つ使えるようになっておいた方がいいと思う。
テキストエディタ上では同じ改行に見えても片方は 0x0d のみで、もう一方は 0x0d 0x0a
なんてこともあるから。

>>687
鈍らな比較ツールだと、「挿入された」ことを理解できないから>687のようなことになる。
逆に言えば、「挿入された」ことを考慮しないアルゴリズムでは、目的に合っていないと言うことだけ。
それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

>>689
> それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
> 意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

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

>>685も>>687もどちらもオリジナルが2行なのに対して
比較対象の文字列（どちらも3行）をいじるだけで出力が
2行になったり3行になったりと変わってしまうと後々の
処理がややこしくなるかなと思った次第です

>>690
読解力のない間抜けだということはよく判りました。

何で>>690みたいなゴミみたいな奴がアルゴとかやってんの？

>>685
> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> http://d.hatena.ne.jp/siokoshou/20070315

そこのコードは最長共通部分とか返してくれない。
「とにかくO(NP)の最速で動くdiffコードを作ってみました」
ということを実証するためのコードだからあまり実用的じゃないぞ。
あるいはコードに手を入れてちょっとした改造を施すか汁。

>>689
>それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
なんか勘違いしてね？
その二つの例が別の話題だということは>>687が「あと」と言っていることから分かる
自分の読解力を過信して、ろくに理解せずに他人にいちゃもんを付けるのは格好悪いよ

>>691
> 読解力のない間抜けだということはよく判りました。

読解力の無いマヌケはお前の方だったようだなｗ

面白そうだから黙ってたのに。

頭おかしくなっちゃうと屁が出るんだよねｗ

>>689
(ﾉ∀`)ｱﾁｬｰ

basicのほうが早くね

文字列照合アルゴリズムでSIGMAてのがあるらしんですけど
詳しいアルゴリズムを解説したページありませんか？
なんか宣伝のようなページしか見つかりません。

ttp://hdl.handle.net/2324/3109
ここにたどり着いた
あってるかは知らん

management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？

>>701
エラーがでます。

>>702
シュンサクとかいうデーターベースで使われてると読んだのです。

>>703
オモローな記事があるぞ。兄弟。

いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
ttp://www.atmarkit.co.jp/fcoding/articles/algorithm/01/algorithm01a.html

>>703
http://pr.fujitsu.com/jp/news/2006/12/15.html
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。

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

あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。

>>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。

範囲のリストに新しい１つの範囲を追加するアルゴリズムをお願いします。
例えば、[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万件とか２万件を高速に連続追加できれば幸いです。

よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。

あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。

多めに確保して置いて、存在するところのビットを立てておけ。

データ構造はリストでお願いします。聞きたいのはアルゴリズムです。
実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定？
んー。

ふと思いついたもの。

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

上の例で実際にやってみる。
[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からリストを作るので、そこは作る処理の時間だけ遅くなる。

そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？

あー。すみません。データ構造とアルゴリズムは関係があるので、データ構造はリスト
でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。

>>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。

範囲の列を、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)で挿入できるかな

>>702 >>713
データ構造を弄ってよいなら，
できるべき操作をちゃんと指定してほしい．
たとえば

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

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


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

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

どっち？

>>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
　unsigned int StartIndex;
　unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。

>挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？

>>713,714
反応してくれてどうもです。

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

こういう場合の為におすすめです。あまり無いと思いますが。。。

＞上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
＞[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの？　そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。

>>720
想像力不足

俺は動画のフレーム編集を想像しながらスレを見てた

だとしたら>>716のa,bはa？

あと>>721はどんなもの想像してたんかな？

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

もうちょっと色々もだえてみます。

・リストの先頭から末尾への連続アクセス
だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。

>720
ttp://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。

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

N = 3m+5nでしょ。　互いに素ならいけるんではなかったか? m,nが整数なら

単に3と5の個数をデータとして持てばいいんじゃないの?

8,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。

ax+by=1を満たす整数x,yが存在する

http://d.hatena.ne.jp/gould2007/20071009

そしたら連続する3つ作れればそれ以降、全てつくれるってことだな

その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました

どうもおかしいと思った。

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

6つあったのねw

A Small and Fast IP Forwarding Table Using Hashing.
これ何度みても計算できねぇ助けて

一緒に考えてやるからその論文を見る方法を教えろ

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
ぐぐった
合ってるかは知らん

>>736
それっすそれっす

突然すみません。しろうとです。
バイナリーサーチの計算量は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って何なんでしょうか？

アルゴリズムをよく考えてみ
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　→ ???を求める為には
数式頼みはよろしくないよ

>>738
ひどい導出だ．O(1) の扱いが雑すぎる．
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述．

もし本当に本にこう書いてあるなら捨てたほうがいい．

プログラムの初心者です。
アルゴリズムの流れ図について、自然数ｍ、ｎに対して、
ｍのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。

流れ図の問題なんだな？そうなんだよな？
ではまず、効率の良いアルゴリズムを言ってくれ。

ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。

n＾２＊ｎ＾２＊ｎ＾２
これがヒントだそうです。
どうしたら、よろしいのでしょうか？
お願いします。

ｎの４乗はｎの２乗×ｎの２乗です。　ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。

従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。
の2乗
これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。

よくわからんな、何だろ
ビット演算を絡ませたアセンブラ的な問題なのかな？
お前らどうする？これ放置していいん？

罠じゃねえの?

説明がデタラメだし。

>>744
＞ｎの８乗はｎの２乗×ｎの４乗
ダウト。乗数は足し算です。

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

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

つまり
>>745
問題のヒントが出鱈目だから放置していい。

>>736の問題助けてくれｗまじでｗ

要するに>>736を分かりやすく翻訳してくれって言ってる？
サマリー読む限り、別に問題提起ってわけではなさそうだけど……？

>>749
4bitの集合を考え、具体例として以下で計算した場合
0000, 1100　0011, 0100, 0110, 0111, 1011, 0001.

1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね？

４ページのExample 1の話？

うん

http://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]の２が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。

>>753
リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。

再帰の仕組みって勉強すればなんとかなるもんじゃないだろ
何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ

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

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

みたいな考え方を適用すべき

LISP学んだり、フラクタル図形書いてみたり
だまし絵とか見に行くといいんじゃないかな

>>753
おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。

n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？

ソートして先頭3つでやるのはなんかもったいない気がして・・・

端から舐めて上位3個を取り出す方法だろうなぁ

それだと比較回数3n？

ヒープ

20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？

>>757
ありがとうございました。

nth_element, partial_sort

>>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．

実用的にはデータの分布に依存するので，実測しないと何とも．

>>765
全体ソートするのとオーダーかわらんじゃん

っ「選択アルゴリズム」

選択アルゴリズムはk番目の値しか探せないぞ

>>768はまったくプログラミングの才能が無いな。

partial_sort使うのがいいんじゃない？

>>770
それ、なんのこと言ってるの? C++前提なの?

「部分ソート」と呟いておく。

たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして
93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。

もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。
次のループでそれ以上を選ぶ。

v[0]が4にならねーよ
わからねー

>>766
全体ソートは　O(n log n) だから log の値が違う

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)より速い方法を探しています。

ないな　O(N)で困る例はなんだよ

>>778
ないこと証明できる？

困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり？

a,bの存在範囲毎に最小点を計算しておけば定数時間

>>777
http://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*」
という関係になることに注意して，点位置決定問題に帰着するだけ．

>>781
あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。

追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか？

そもそも何に必要なんだよ?

>>782
私の大学からだとCY84以外は契約論文誌なので，Webから取れた．
もし必要ならどっかにアップロードするよ．

Mu03はciteseerからも取れたので，論文名で検索してみると良い．

前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では?

最後のやつだとこの辺に関連情報あるぞ
http://scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr=

>>784
Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。

>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。

>>785
O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。

なので、クエリ時間を増やしても n^2 より安い手法が存在する。

マス目に二種類の記号を置いていった時、

AAA　　　　ABA
ABB　　　　ABA
AAA　　　　AAA

というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？

>>789
問題が不明瞭

マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ？

簡単な方法はない。
地道に全回転・反転パターン（8通り）を網羅してチェックする。

プログラムが見通しよくなるように工夫がひつようかも。

行同値的を出してそれを比較すれば・・・駄目か

トランザクションメモリの実装
ここでやる夫的に説明してくれよ

　　　 .　'　　　_ 二二 _ .､
　　　 　 　 　 ／　　　 /´ -‐…‐- .｀＼
　　　　　 　 /　　　　 /´　　　 i　　 !｀ヽﾄ､
.　　　 ,ﾍ　 ,' 　 i　 　 !　 !　 |　|i　　|ﾊ　i　ヽ　ｷﾘｯ
　　　/　 ゝ!　 ﾉ|　　! !::__!::ノ ´　￣　 i::.i ｜!
　　　＼　 .|　.:i i :i　i |´　　 ＼　　／　｀!､ﾊ:!　　
　 　 　 ｀ヽi　 从 i　i | ニﾆﾐ　　　 .ﾆニ !:::::|　　 ＜トランザクションメモリの実装
.　　　　 　 | 　ＹﾊｉﾊN　 {r::ﾘ｀　　´{r::ﾘ '::::N　　　　ここでやる夫的に説明してくれよ
.　　　　 　 |　　ヽゝ　　 ´´　　　　　｀｀ﾊ!｀　
.　　　　 　 |∧ 　 �Y!　　　 　 　 ′　,':::|
　　　　 　 ｊ/∧　 _!::｝　、　　 ⊂'　..ｲ:::::|
　　　　　 ///∧´ ∨　　｀ 　,.... ィ´ﾞY:::::|
.　　　　 /////∧　ヽ　　　　{ﾄ､∧　|::::::!
　　　　 ,＜￣￣∧　 } ｀ヽ　　＞''}　{￣｀ヽ
.　　　 / 　 ｀ヽ:::::::::Y´ヽ　　　　　 i´｀∨::::∧
　　　/　 　 　 ∨:::::| .:: !　　 　 　 i .:.: !::::/　i

　　　　　　　　　　　＿ ＿＿_
　　　　　　　 ,. :'´: :,.　-―‐-ミ:ヽ、
　　　　　　／: : : :厶ｨ': ´￣￣ヾ : :＼
　　　　　 /: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼　　　＜じゃっておｗｗｗ
　　　　　ｉ: : :.!: : : ﾚ‐'　｀￣⌒　⌒" ﾄﾍ:ﾊ!
　　　ﾄ--|: : :.!: : ､|　　ｰ‐'' ´ ｀'ｰ　　}: :.ﾄ
　　ﾐ　ﾐ　ﾐ : :!: : : :!　z=≡　　　≡z.{: :.ﾊ　　　　ﾐ　ﾐ　ﾐ
　/⌒)⌒)⌒.ﾊ :_Nとつ　＼＼＼ C VVﾘ 　　/⌒)⌒)⌒)
　|　/　/　/:弋こ　＼ヽ　＿＿,.　　　}　(⌒)/　/ / /／
　|　:::::::::::(⌒) : :}＼　　/　　　1　 ／　　ゝ　　:::::::::::/
　|　　　　　ノくf⌒Y ｀　{_　　_,ﾉイ| 　　　/　　）　　/
　ヽ　　　　/　 ヽ　ﾍ,､　　_｢　|::!:::::} 　　/　　　　／　　　　 バ
　　|　　　　|　　 l||l　从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l　　バ　　ン
　　ヽ　　　 -一''''''"~~｀`'ー--､/:::::ｲ;　 -一'''''''ー-､　　　　ン
　　　ヽ ＿＿＿＿(⌒)(⌒)⌒)　):::/}　 (⌒＿(⌒)⌒)⌒))

かんなぎは評価されすぎ。

無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。
って意味のわかる人教えて下さい。

意味が分からんな。
「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。

>>797
無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか？

やはり意味不明。
今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。

そうですか。失礼しました。忘れてもらって結構です。

別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは
例えばどういうときかわかりますか？

>>801
G = (V,E) を 3点 a,b,c からなるグラフとし，
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し，
頂点 a から b への最短路を求めようとすると破綻する．

なるほど。素早い回答ありがとうございます。

>>802
その例では破綻しないぞ

>>804
kwsk

>>802の例だとd(a, b) = 0で探索終わらね？

正答が得られないって意味で破綻なんじゃね？

ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。
ぜひ解答お願いしたいです。
スレチでしたらすみません。。

アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。
（どの用語がどの用語の中に含まれているのかとか）
ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？

木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子
木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、
　　　　　　　　　　　　　　　　　　　　　　　　　 （２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい
木構造--------二分木---------------ヒープ・・・二分ヒープと同義？
木構造--------多分木

>>808
ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう．よって．一般の木上のヒープがありうる．
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし，
より一般の木上のヒープとしてはフィボナッチヒープが有名．

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

場合によっては配列実装まで含めてヒープと言う場合もあるけど，
フォーマルには構造と実装は別に考えるので，
>>808 の二分ヒープの説明は本当はちょっとよろしくない．

>>807
どれくらいの精度で解析すればいいの？

あと，Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ？
それとも，フィボナッチ数で抑えること自体が禁止されるの？

>>810
どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。

>>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) 回以下のステップ数で終わるため．

ありがとうございます

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

この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。

>>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底)．

ありがとうございます。
もう一度問題と向き合って理解を深めたいと思います。

>>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))

ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです

>>816
アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど，
あなたの説明だと，良く分からない部分が多い．
（もちろん「普通の実装」というのがあるのだけれど，
　それがあなたの理解しているものと違う可能性もある）

なので，あなたが理解している形で，For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな？
その計算量だったら評価するよ．

>>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)
---------------------------------------

>>818
その本に計算量の説明が懇切丁寧に書いてあるよ

ならし解析ですね分かりません。

LC-Treisってどんな木なのですかね？

>>819
了解です！

「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が
正の数だった場合、ダイクストラ法は失敗することがあるか？」

あれば例を教えて欲しいです

「開始点から離れて行く辺」の定義が必要なんじゃね？

sourceのことだと思います

バイナリ木関連のアルゴリズム
詳細に書いてる本ってありますか？

>>826
詳細ってどの程度？
必要なトピックを具体的にいくつか挙げてください。

トポロジカルソートはなぜグラフがDAGであることが前提なのですか？
サイクリックなグラフでもソート出来ると思うのですが。

>>828
トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？
いくつか流儀があるから君の流儀が分からないと適切には答えられない．

トポロジカルソート：
（１）DAGに対して、DFSを実行する。
（２）Finishing timeの大きい順に頂点を並べる。
というものですが、いかがでしょうか。

>>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）

普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．

>>831
なるほど。わかったような気がします。
ありがとうございます。

突然すみません。これからプログラミングで一辺に対して指定した数分の円を正六角形の中に敷き詰めるプログラムを
書こうとしています。例えば１と指定した場合は六角形内に１個の円が描かれます。例として９を指定した場合の図を
添付します。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8194.zip

聞きたいのは、nの辺の数に対してどのような法則性があるかということです。
１辺の長さを仮に１とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、
n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な
法則などあるのでしょうか。アホな質問だったらすみません。

>>833
数学板へどうぞ。

>>833
(√3/2)/n

>>833
>>835は間違い。

(√3/2)/(1+n√3)

>>836
さらに間違えてた。orz

(√3/2)/(1+ (n-1)√3)

有り難うございました。

ビッグ・オー記法の問題ですが、
a(n)=n^(1/2)
b(n)=10*log[2]n
どちらが大きいですか？導き方を教えて下さい。

>>839
十分大きな n に対しては n^{1/2} > 10 log n．

lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して
εδで書いてε = 1 にでも取れば良い．

>>840
limがわかっていないのですが、limを使わずに導くことは可能でしょうか？

δε論法

わからないなら
a^n >> n^b >> log(n)
とでも暗記しておけ。
大概はこれだけ覚えてりゃ問題ない

ノイズのある入力列の中から
A->B->C->A => 1
A->B->C->B => 2
A->C->C->C->D => 3
とかの並びが含まれていたら、それをパターンと識別して
=>の後の値に変換する処理を書いています。
今はパターンをトライ木に登録していて速度は問題ないのですが、
共通パターンが少ないとメモリを食うのが気になります。
もう少し効率の良い方法はあるでしょうか。
パターンの候補であるかはインクリメンタルに読み取れる必要があります。

wiki見たら

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

だとか。もう少し見たら

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

とか。

>>844
パトリシアではダメ？

パトリシア木でもいいんですが、
何か別の方法がないか聞いて見ました。
HAT-trieは初めて聞きました。調べてみます。

>>847
自分もかなり興味があるので調べているのですが、難しいです。。。

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

調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。

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

今使ってるトライのコードは登録検索だけですが60行程度です。
パトリシアにするだけでコードは2倍以上に増えました。
メモリは半分以下になりますが速度は3割減ぐらいです。

とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう)
間違いがあるかもしれませんが。。。

-----------------------------------------------------------
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はソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。

引き続き翻訳してみます。
初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。

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

現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。

最後の「原因」は「問題」の方が良さそうです。

アクセス時にmove-to-frontする
ってどういう事？

あ、文字列のMTFじゃなくて自己組織化探索の方か。

論文の英文和訳なんてこんなところでやらんでくれ。

>>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という感じでやれば出来ます。

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

そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。（おれ誰？）あ、出掛けます。。。

ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ

>>856
そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。

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

だってこの発想からだろｗ
続きはブログでやれ。ブログぐらい持ってるよな？ｗ

ふつーにBM法？

>>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でき、
さらに保持されるトライノード数を減らせることである。

>>860
ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。

多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ
なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。

>>862 から僻み野郎の気配がビンビン感じられる件

流れはよく判らんけど訳すなら全部訳してくれると嬉しい
中途半端はよくないよ

全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。
多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。

木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？
ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします

現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー？って思ったんです

自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。
木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。

あと昔のアルゴリズム事典に紐付き2分木というのがあったな。
末端の空きノードを利用するって事だったけど忘れた。

まあ何も考えずスタックで組んだほうが保守も楽だし、
追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。

昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。

16進数での四捨五入(7捨8入)をやりたいのですが、
短い方法はないでしょうか？
n = n & 0x8 ? 1 : 0;
n = (n & 0x8) == 0x8;

間違えました。
unsigned char n;
n = (n & 0xf0) + (((n & 0x8) == 0x8) << 4 );
のようなことです。

0x17なら0x10、
0x18なら0x20、
0xffならオーバーフローして0でかまいません。

これをもっと簡単にできないかと。

n = (n+7)&0xF0;

おお凄い短いですね！
ありがとうございました。

アメロ計画によるドル大暴落説
http://namidame.2ch.net/test/read.cgi/eco/1205843429/l50

1 ：金持ち名無しさん、貧乏名無しさん：2008/03/18(火) 21:30:29
アメリカは、アメロに移行し、わざとドルを暴落させ、
国債を返還するのではないかという説

アメロ
http://www.y-asakawa.com/message/amerikano-inbou.htm

ふーむ、ジム・ロジャース氏がドル建て資産をすべて処分したのも・・・？？？

アメリカに対して厳しすぎるのではないかとの問いに
2年後にわかるだろうと答えたのも・・・

気になるところです

void div(vector<unsigned>& vec, unsigned divident, unsigned divisor);

ってのを考えてます。

要するに除算なんですが、vec.size() == divisor であ
り、かつ、vec 内の総和が divident に等しいものです。

divident % divisor をブレゼンハムみたいに振り分け
たいのでブレゼンハムから色々考えてみたんですがうま
くいきませんでした…。

エスパー参上

void div(std::vector<unsigned>& vec, unsigned divident, unsigned divisor) {
　vec.resize(divisor);

　uint64_t prev = 0;
　for (unsigned i = 0; i < divisor; ++i) {
　　uint64_t cur = (uint64_t(i + 1) * divident + divisor / 2) / divisor;
　　vec[i] = unsigned(cur - prev);
　　prev = cur;
　}
}

>>876
要するに、ある整数(divident)をある個数(divisor)で分割するって事？(「要するに」の使い方を参考にしてください)

> divident % divisor をブレゼンハムみたいに振り分けたい

まず、vecにはそれぞれdivident / divisorを入れるのはOKですよね。
次に、余り(divident % divisor)を振り分けるのは
vecの0から(divident % divisor) - 1までを+1すればいいのではないでしょうか。

いや、ブレゼンハムっぽく余りはなるべく均等に配分したいんです。

>>878です。
少しキツイ言い方になりましたが、これは>>877やその他の方への配慮です。

丁寧さに限度はないと思いますので、質問は出来るだけ伝わりやすくした方が良いのかなと思います。

ついでに面白い読み物を紹介

身近な具体例の利用は数学学習の助けにならない
http://health.nikkei.co.jp/hsn/hl.cfm?i=20080501hk000hk

テレビのニュースで見たのですが、最初は「えっ」と思いました。
最近、気になって検索して読み返したら、「文章題やおはじき・・・」で始まる最後の段落を見て納得しました。
どこが納得したのかははっきりは言えませんが、今まで考えていた事を否定する内容ではなかったようです。

回りくどくなってしまいましたが、具体例は伝えやすくする為に便利です。

>>879
あ、ちょっとレスが前後してしまいました。


整数ではこれ以上均等に配分できません。

えー、敢えて具体例を出しますが 2/5 の時に

1 1 0 0 0

ではなくて

0 1 0 1 0

のようにしたいということなんですが。
DDA っぽくと言い換えてもいいけど。

そこまで言うなら自分で考えろ

かなり難題ですね。（素数がらみ？）

しばらく考えてみます。

int s = 0;
int[] data;
for(int i = 0; i < 5; ++i){
　s += 2;
　if(s >= 5){
　　data[i]++;
　　s -= 5;
　}
}

ifをwhileにしたほうが一般的にいけるな。

変数つかって書き換えておいた。計算量はO(divident)になる。

int s = 0;
int[] vec;
for(int i = 0; i < divisor; ++i){
　s += divident;
　while(s >= divisor){
　　vec[i]++;
　　s -= divisor;
　}
}

O(divident + divisor)か

余りが片寄らないようにすると↓みたいになるかな。も
うちょっと考えると while() が消せるかも（ブレゼン
ハムで線引く場合に縦長／横長で場合分けする感じ）。

void Div(vector<unsigned>& vec, unsigned divident, unsigned divisor) {
    int e = divisor;
    while (vec.size() < divisor) {
        e -= 2*divident;
        unsigned q = 0;
        while (e <= 0) {
            e += 2*divisor;
            ++q;
        }
        vec.push_back(q);
    }
}

void div(std::vector<unsigned>& vec, unsigned divident, unsigned divisor){
    vec.resize(0);
    vec.reserve(divisor);
    unsigned div = divident / divisor;
    unsigned mod = divident % divisor;
    unsigned of = divisor;
    for(std::vector<unsigned>::size_type c=divisor;c--;){
        of += mod*2;
        vec.push_back(of >= divisor*2 ? of -= divisor*2 , div + 1 : div);
    }
}

要素数　最小100から最大65000
データ内容　１から40億までのUINT型の値

こんなデータ内容を格納するのに最適な
木構造って何かありますでしょうか？

目的が分からんが、平衡二分木では困るのかの？

データ構造にどんな機能を求めるか、何がしたいかによる。

順序性のある連想配列が必要なら平衡2分探索木とか、
最小値だけ必要ならヒープとか。

それこそ単なる連想配列として使いたいなら
いっそハッシュテーブルでいいし、
格納するだけならリストでいい。

整数ってだけじゃ木構造で
特別有効なデータ構造は思いつかないが…

>>891
要素数や値の最大値が見えてるから
それを使えば色々と高速な構造がある。

B木とかどうよ

>>894,895
Bツリーか赤黒木を作ろうかと思います

STL の std::set とか大抵赤黒木で実装されてなかったっけ。

パスカルの三角形

AAツリーと赤黒木ってどっちが優秀なの？
計算量は同じようですが

質問です。
１．点数がnの完全２分木の高さhを厳密に求めよ。そのうえで、h＝Θ(log(n))であることを示せ。
２．単純な無向グラフＧを表現する隣接行列をＡとする。また、Ａ^k＝(※)とする
※aの右下にij、右上に(k)
(1)A^2,A^3,...,A^iは何を表すか
(2)(aの右下にii、右上に(2))は何を表すか
(3)1/6Σ(aの右下にii、右上に(3)) は何を表すか。ただし、n=n(G)とする。

できれば考え方等も教えていただけるとありがたいです。

>>900
1.
n = 8 くらいまで書いて類推するだけ．略．

2.
(1). A^k は，ij 成分が「i から j へ k 歩で行く方法の数」を表す行列．
これは冷静に考えればわかる．分からないなら帰納法で確認．

(2), (3) は (1) を使えばいいだけで，たとえば (2) だったら
「i から i へ 2 歩で行く方法」がどんなものがあるかを考えればいい．
(3) も同様．ただし同じものをマルチカウントするので 1/6 している．

>>899
ぶっちゃけB木の方が速い

>>902
B木書くの面倒やだ

http://www.geocities.jp/m_hiroi/light/pyalgo16.html

これ再起無しにするの難しい

再帰を再帰無しにするのは簡単だぞ。
スタックを自分で作ればいいだけ。

ここらへんとか参考に
http://d.hatena.ne.jp/yaneurao/20051008
http://d.hatena.ne.jp/yaneurao/20051025
http://d.hatena.ne.jp/yaneurao/20060227

高速なバイナリサーチが書けません

鬱になりそうです助けてください

>>907
真面目に「高速な」ものを作ろうと思ったら
CPUの特徴とかを考えながら組むんだけど，
そういうことをしたいの？

とにかく問題設定がよく分からないので
なんともいえない．

鬱になったらまたおいで

strstrの実装で、BM法も結構複雑なんですけど、文字列検索はアルゴはあまり存在しないんですか？
ソートは結構な種類がありますが、文字列の方の比較的簡単なアルゴはあとはハッシュ法ぐらいしか思い浮かびません。
一応正規表現を自作してるのでstrstr（とmemchr）は切っても切り離せないんですけど、何か助けとなるような助言はありませんか？

>>908
そもそもバイナリサーチが遅いということ自体あり得ないと思うんだが。
どんなに遅くても 32 回もかからんっつーのに。

>>910
助言もなにも、何がしたいのかが分からんよ。

文字列検索なんて、それだけで一冊本が書けるほど大量にある。
簡単なものでも http://www-igm.univ-mlv.fr/~lecroq/string/index.html くらい。

アルゴって何だろう？

>>910
有名なのには他にKMP法ってのもあるよ。
Wikipedia を見ると他にもあるようだよ。
ttp://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

>>911
データサイズが非常に大きいとか
CPUが貧弱とか
バイナリサーチを多数回実行するとか

バイナリサーチを僅かでも高速化したい状況は結構あるよ。

結構あるんですね。助言ありがとうございます。
奥村先生の本でやってるんですけど文字列検索はあまり載ってなかったんで、検索アルゴはあまりないのかなって。
ただ、正規表現自体が文字列検索そのものなので、BM法みたく表作ろうかどうしようかなって・・・
ソートしたり、表作ったりするよりも、結局一番単純なmemchrがいいのかなってのが感想です。

多少遅いかも知れませんが、今のハードの資源を考えると、BM法も単純なリニア検索もたぶん10ミリ秒以内の差しかないんでしょうけど。
検索アルゴ自体よりも、newしたりメモリにアクセスする方が時間かかるんじゃないかなとか・・・

実測してから考えたら

>>913
Javaスレにいたアルゴ厨です。

>>916
やっぱり何がやりたいか分からんよ．正規表現をどうしたいんだ．

あと線型探索は実装にもよるけど普通は O(n^2) でしょ．
aaaa....a から aaa...b を探すことを考えたら時間が大差なのは明らかだと思うけど．

>>913
http://www.sansu-olympic.gr.jp/algo/　これじゃね？

ああ、きっとそれだな

正規表現を自作ライブラリとして実装してるんですけど・・・・通じませんでしたか？
アルゴは、アプリと同じくなんとなく響きがいいですよね。

既にどういう状況でアルゴを適用するか決定してるので、>>919のようなaaaaaa...aの状況は現実的にありません。
別に１００ミリ秒以内に結果が出ればどうでもいいかなってところです。上の１０ミリは１００ミリの間違えです。
どうせGUIとかWEB環境で使うつもりなんで難しい実装で小手先技を披露するよりも、
簡単な実装でかつバグがなく動く（必ず停止する）方が重要なんで・・・そういう実装が容易なアルゴはないかなって。

> アルゴは、アプリと同じくなんとなく響きがいいですよね。
いいえ。

そんな（TT)

林はるひこの本も手元にあるんですけど、はるひこもアルゴも同じぐらいキモキモ・オーラが出てるですけどね。
とすると、アルゴってのが嫌なら、アプリって省略することも、あなたの信念に反するんじゃないですか？

だよね。アルゴの響きはいいけどアプリは悪いよね。

>>922
正規表現を実装したかったのか．

正規表現なんて決まりきった実装法があるでしょ．
決定化しなかったら数十行で書ける．
memchr やら何やらを持ち出す理由が分からん．

アプリ：使う人が多くイケメンもフツメンもキモメンも居る
アルゴ：使う人が極少でキモメンばかり

OK？

>>926
いや、だから正規表現自体が、（検索キー・パタンが固定ではない）文字列探索なんですけど。おｋ？

クラ・サバのシステムでオレッちのアルゴがアプリでバキバキ！（笑）（爆）

これも一つの情報のデータ圧縮でしょうかね？！
計算速度の高速化とかオーダーにこだわったりして業界に深くかかわっていると観念が固定化してしまい、新しい発想（発明）ができなくなりますよ。

発明してない＆できない奴が言っても説得力ないんだけどね

>>928
それがどうしたの？

>>929
よくあるトンデモ系の意見だな。
先行研究に対する理解なしに新規的な発明はできんよ。

再発明したいつってんだからやらせてやれば

実装が難しいのは、いくら高速でもあまり評価されませんけどね。
あまりに複雑な仕様のコンパイラなどは誰だって実装したくはありませんよね。
実際ハードの方が技術革新していった高速化していけば、線型探索でも十分に実用なんでしょうけど。
その発明＆研究した複雑怪奇なアルゴリズムはいつ寿命が尽きるんでしょうか？

>>934
> 実際ハードの方が技術革新していった高速化していけば、線型探索でも十分に実用なんでしょうけど。
そんなことはないよ。
ハードウェアが高性能化すればするほど扱えるデータが増えるから、
効率の良いアルゴリズムが必要になる。
アルゴリズムが使われなくなるのは、より良いものが出たときだけ。

つーかそもそもの話題だった正規表現の標準的なアルゴリズムは
非常に簡単で、しかも高速なんだけど？

>>935
ネタ投入するといきなり活性化するスレですね。

あなたの論調では、扱えるデータ量が増えたら、それを扱う使う人も当然データ量を増やしていくって前提がありますね？
普通の人間なら、新しい機械が導入されたとしても従来からやってる仕事（例えばお役所仕事・事務処理とか）が速く終わるってことだけであって、
だからといって従来の仕事量以上の仕事を抱え込んだりはしませんよ。どうせ給料も同じなんでしょうし。
そういう辺りをちゃんと考慮しているかどうかってのが現実的な実用的なアルゴかどうかってことです。
正規表現は、文字クラス[ab]をどうしようかなってところですけど。

>>>922
> 難しい実装で小手先技を披露するよりも、
> 簡単な実装でかつバグがなく動く（必ず停止する）方が重要なんで

だったら、まずは線形探索で十分かどうか試すべきでは？
案外それで100ミリ秒の要求が達成できるなんてこともあり得る。
もう試していたらごめん。

アルゴ君と遊ぶスレかここは

おい
おい
紀伊店丘
おい
データ量＝給料らしいぞ

>>936
> 正規表現は、文字クラス[ab]をどうしようかなってところですけど。

お前には無理。

[1,5,10,13,15,19,21,26,30]という配列がありまして

入力値7を入れると
結果値10を返す検索を実現したいのですが
やり方が全然わかりません。

自分より大きくて配列要素の中でもっとも近い
要素を返す処理だと思うのですが
どうやって書けばいいのか思いつきません

>>941
配列の最小値を探す処理は書けるか？
書けるなら、入力の配列から7以下の要素を取り除いた配列を作って、それの最小値を返せばいい
最小値を探す処理を工夫して、7以下の要素を無視するようにしてもいい

入力が昇順に並んでいることを仮定していいなら、二分探索が使える

誰か
http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-639.pdf
これCで実装できる神様いませんか？

簡単だろ

Javaスレにいなかった人は免疫ないだろうけど、アルゴ君は適当にいなしておいたほうがいいよ。

Javaスレは昔見てたけどアホだらけなんで最近見なくなってた
状況は変わってないようだな

>>945
コテンパにやられたんですねｗ
調子にのっちゃうとコテンパにされて痛い目にあう典型例ってことでしょうか。

>>947
＞コテンパにやられたんですねｗ
コテンパって何ですか?

えっ？いなすんじゃないんですか？？

アルゴリズムを実装するときは今の時代だとJavaかC#（やruby)が楽だと思うのですが、どの言語でやってるんですか？
C/C++でも差はないのですが、なにぶんゼグメント・バイオレンスや時間関係のライブラリ（並列計算なども）が充実してないので、
それも自分で実装して再発明したり数値計算パッケージを導入することになります。
すると本来実装したいアルゴリズム以上の苦労がありませんか？
まさか「言語なんてどれも一緒。アセンブラでやれよ」ってのなしで。

求められる速度によるとしか。

それは本実装（リリースとか論文掲載とか）のときですよね。
実験や試験的に試行錯誤したりするときはやっぱりC/C++なんですか？
アルゴリズはほとんどがメモリ操作であって、ハードをいじったりハードにアクセスすることはないので、
C/C++じゃなくJavaやRuby,C#（他のでもいいんですけど）でいいかなと思うんですが。

>>950
アルゴリズムの種類にも、状況にも拠る。
行列が対象ならmatlabクローンのoctaveで確認してからってこともあるし、
数値解析関係ならmklが使えるc/c++からってこともあるし、
持ってお手軽にOpenOfficeCalcでちょちょいと試してからってこともある。

逆に寧ろ、C++を嫌う理由が判らん。
Cだとメモリ確保が面倒だってこともあるけれど、C++ならクラスも使えるしSTLもあるから融通が利くと思うが。

ちょっとしたパズル問題を解くときにはScheme使っている。

Mathematica でやる人もいるか。

>>954
アルゴリズムの実装にクラス生成が必要ならその意見もわかるんですけど、そこまでC++に慣れちゃってるんですか？
べつにC/C++でも普通に使えるんでなんでもいいんですけど、Cはポインタに関係するバグ（というかコードミス）が多くて実装と関係なく、
C++はvtableがらみアライメントがらみでこれまた面倒が多いので、結局現代的なJavaとかになるんじゃないかなって。

Java,C#はGUI（アプレットとか）も簡単に作れるんで、グラフ化したり視覚的に速度比較するのも余裕なんですが。
The Sorting Algorithm Demo (1.1)
http://java.sun.com/applets/jdk/1.3/demo/applets/SortDemo/example1.html

英語はそんな苦じゃないので主にJava使ってますけど。

さて順調に脱線してまいりました。

初心者のためのプログラミング言語ガイド Part12
http://pc11.2ch.net/test/read.cgi/tech/1226761546/

>>957
いやだから、何でわざわざ地雷を踏まないといけないのよ。
C++使うからといって必ず継承するような必要もないし、低レベルのメモリ管理をする必要もないんだけど。
例えばたまたま手元にあるデータをちょっと加工したいときはawkを使うことだってあるけど、
そんなときに処理速度なんか気にしないしね。

あんたがJavaやC#やRubyに精通していて、他はろくに知らんと言うのなら黙ってJavaやC#やRubyを使っていてくれ。
こっちは適材適所でやるから。

>>957
とりあえずコテハンつけてくんない？

アルゴリズムの実装については速いかどうかしか評価されていないようですけど、
確実に停止するか（解が得られるか）が一番大事なことなんじゃないでしょうか？

それも、汎用的なアルゴリズムは既に50-70年代で出し尽くしてるので、
それ以上の技巧を凝らすのはナノ秒を競い合って職人技（論文）合戦しているだじゃないですか。
新しい分野たとえば動画の動き予測とかガベジコレクトとか資金が流れてるところはアルゴリズム研究もHOTななんですけどね・・

なので、解が得られるかどうかが一番大事なのにいつのまにか速度(O[n^2]とか）の問題になって、速度（速く解が得られるか）にこだわる意味が全く分からないんですが、どうしてですか？
そういう速い・実用ではないなどの問題はアルゴリズムじゃなくてハードの問題なんじゃないでしょうか？

計算アルゴリズムというよりは計算機アーキテクチャとか実践プログラミング（笑）の話題だな

アルゴリズムを語るときに、オーダーを無視する奴なんて論外だろ？
log n と n^2 を同列に扱えって主張はおかしい。

>>960
適材適所とかなによ？誰もあんたのプログラミングスタイルなんか聞いてないよｗ

> 確実に停止するか（解が得られるか）が一番大事なことなんじゃないでしょうか？
その通り。これを評価する仕組みがO記法によるオーダー。これは計算量であって速度そのものではない。

例えば、O(n)やO(n log n)くらいなら、ハードウェアの性能向上でなんとかなると言える。
逆にO(c^n)なら入力をちょっと増やすだけですぐに計算量がおそろしく増えるから、
ハードウェアの性能向上は待っていられないねという具合。

現在、1日で答えが欲しい問題を解くに1年かかるなら、それは答えが出ないのと同じこと。

ダメだこりゃ。

そりゃ速いに越したことないけど、実際は新しい分野で確実に答えが出るアルゴリズム（
なんて考えつく人は○○賞もらうレベルの人で滅多にないから。圧縮とかでも。
それをベースとして２,３度修正して速度調整する程度でアルゴリズム（ソフト）上の仕事は終わり。

例えば、O[n^2]だとしてもそのハードで40ナノ秒程度なら誰も気にしないよ。
かといってO[1]なのに、５秒掛かるなら問題あるなぁ。
例えばハイパリンク押した（定数）なのに、応答（ダウンロード）が５秒とか。
実践云々じゃなくて、そういうこと。

>>962
普通のアルゴリズム論の文脈では、停止しないものはアルゴリズムとは言わない。

あと、普通のアルゴリズム系の論文では実時間を競うようなことはしない。
実時間なんて実行環境によっていくらでも変わるから、オーダーで測る。

>>968
頼むからコテハンつけてくれ

>>968
計算量＝実実行時間なの？バカなの？死ぬの？

たとえが例えになってないので、ソーティングの話で例えてください (10点)

>>966
あの〜意味が全く分からないですが、O[c^n]のアルゴｗをn=2Gのデータ量に適用した場合、nが600MB増減してまあまり関係ないと思うんですけど。
たとえばコーデックとかだと当たり前ですよ？ｗ
製作時間（総レンダリング）が３年にも及ぶCGを駆使した映画とか昔はありましたけど？

その１年ですけど、O[c^n]のアルゴｗで並列計算（PC１００台とかGPU２０枚のハード）でやったら３０秒で答えが出たとき、あなたは考え方を変えますかね。
どうせあなたは教科書読んで勉強すら出来ない人なんでしょうけど、あなたは何を言いたいんですか？

並列計算って計算量的にどう変わるんだっけ。

>>973
かなり関係あると思うんですけどーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

>>974
大まかには単純にコア数分の１にしかならない。
実際にはコア数分の１になるのは並列化効率100%の時だけで、
100%に満たない場合はいくらマシンを増やしても
あまり効率が上がらない限界が存在する。
アムダールの法則でググれ。

アルゴ君が、逆切れしてまいりました。そろそろ自演や荒しが始まります。

他の計算結果を利用しないなら、並列数だけ倍増だろ。
例えば、素数を割り切れるかどうかで判定しようとすれば
1　-　100　と 101 - 200は別々に処理できる。

オーダ数はアルゴリズムの性能を評価するためだけに導入されているだけですよ？

だから通常の利用で１秒以内に答えが欲しいなら、O[n]もO[n^2]も実質同じってことです。
実質同じなのに性能比較する必要はあまり実益があるとはいえません。
つまりハード（資源）が速く十分に使えるため、アルゴリズムが性能に及ぼす影響は全くないということです。
O[c^n]とかでも今のハード（例えば携帯とか）では n<2^64 までとか縛ればいいだけです。
なんか「理系が騙される統計のマジック！」とかと同列の議論ですね。ｗ

それにも係わらずいつまでもオーダを気にするのはいかがなものかと。

アルゴと略さないと誰も釣れないぞ。

>>979
ここはアルゴリズムのスレなので、オーダを気にするところです。
つまり、自らスレ違いである理由を列挙しているということです。

各アルゴリズムの性能評価のオーダ量と、それを実際に適用・活用する（性能比較）のコスト（時間やバグ取りなど運用コスト）は分けてますか？
いくら早くてもあまりに実装が複雑なアルゴ、あまりに難解な論文はいらないかなって・・・
そのうち（３年程度で）ハードの方が速くなって、そういう運用のためのコストが高いアルゴリズムはどうでもよくなるんですけど、どうしてオーダでしか評価しないんですか？

アルゴと略さないと誰も釣れないぞ。

たしかにオーダ表記に騙されてたよな・・・
差分時間も３ミリ秒程度で実質同じなのに・・・

情報系が騙されるオーダ記法のマジック！ｗ

そろそろ自演がはじまったようですから、気をつけてくださいね

実装が難しいなら、頭のいい人に任せるだけ。
クイックソートはqsortを呼び、PNGを作りたければlibpngをリンクする。

「ぼくが理解できないアルゴリズムは禁止」

>>986
自分たちの開発対称になってるドメイン固有の問題はどうすんの？

金さえちゃんと払えば頭のいい外注さんとというのもありだろ。

>>988
さあ？アルゴ本人に聞いてみたいところだ。

次スレ立てる？
それともここ使う？
http://pc11.2ch.net/test/read.cgi/tech/1217773415/

正直どっち使っていいか判らんから
1つでいいよ

じゃあ埋め

俺も一つでいい

アルゴ体操はじまるよー

は？

アルゴ探検隊の大冒険

アルゴ君体操！

.

1000ならジュースでも飲むか

このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。