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

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 610 名前：595 mailto:sage [2008/01/02(水) 20:39:23 ] 「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; } 611 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:16:56 ] 漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ 612 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:17:24 ] 誤爆です。 ごめんなさい 613 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 13:01:23 ] >>611 そのまんまの意味じゃなーの。 f(x)=sin xで1,-1は明らかに漸近的ではないが g(x)=1/x(x≥0)で0は漸近的。 614 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:18:07 ] 質問させてください。 「ハッカーのたのしみ」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 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:31:46 ] 繰り上がり 616 名前：614 mailto:sage [2008/02/09(土) 20:41:09 ] >>615 すばやい回答ありがとうございます。 くりあがりですね。 このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、 この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？ 617 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:44:43 ] >>616 そのとおり。 10進数で画面に表示する回数が、普通の計算を行う回数よりも 圧倒的に少ないと考えると、そういう数の表現になる。 618 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 16:13:21 ] w[ i + j ] = t; k = t >> 16; この部分を 　k = t/10; 　t -=k*10; w[ i + j ] = t; とすれば、１０進法になるんじゃない？ 8bitなら１００進数 16bitなら10000進数なんてのがオススメだよ 619 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 23:37:33 ] HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた 620 名前：デフォルトの名無しさん [2008/02/18(月) 17:15:48 ] 行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、 調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。 なぜ誤差が大きくなるのでしょうか？ 621 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:15:28 ] 誤差についてはほとんど知識がないので調べてみました。 たまたま今やっていることに関係あるので。 さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。 なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を しなければいけないこと。まぁ大体こんな感じです。 ではなぜ掃き出し法が誤差が大きいかというと、予測ですが 単純に計算量が他に比べて多いからではないでしょうか。 誤差を含む演算はやればやるほど誤差が大きくなるというわけです。 ちゃんとした理由ではないかもしれませんが、それよりも どうすれば誤差を小さくできるか考えた法がいいと思います。 まぁ原因が分からなくては始まりませんが。 622 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:42:00 ] >>621 そんなに詳しくないから適当に書くけど、 基本的にはその通り。 収束性が悪いほど誤差は積もりやすい。 あと、除算があると誤差大きくなる。 なので、掃き出し法みたいな手計算的手法のものよりも、 ガウスザイデル法みたいな反復計算の方が誤差少ない。 623 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 02:13:06 ] >>620 一概にそうとは言えない。というか、単純に比べることは不適当。 そもそも掃き出しは（解けるならば）必ず A x = b を解くが、 ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。 したがって、無条件で比較することはできない。 次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。 一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。 反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。 624 名前：デフォルトの名無しさん [2008/02/19(火) 13:21:15 ] >>623 掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか？ 新たな課題ですね(￣□￣;)!! 実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、 エクセルの分析ツールの回帰分析した結果、 後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。 後者はガウスザイデルなのかもしれません。 625 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 16:20:26 ] >>624 マクロでやってるなら、ピボットの選択してる？ 626 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 18:31:45 ] >>624 掃き出しで解けてガウスザイデルで解けない問題なんて いくらでもあるよ．たとえば 　x + 2 y = 1 　2 x + y = 1 をこの順番で連立方程式と考え，ガウスザイデルを 初期値 x = 0, y = 0 で適用すると，発散する． ガウスザイデルが収束する必要十分条件は，未解決のはず． 627 名前：デフォルトの名無しさん [2008/02/21(木) 22:41:32 ] >>625 ＞ マクロでやってるなら、ピボットの選択してる？ いえ、まず中心をすべて1にしてから掃き出しています。 これではダメでしょうか？ 628 名前：デフォルトの名無しさん mailto:sage [2008/02/22(金) 19:59:46 ] >>627 ダメ 629 名前：デフォルトの名無しさん [2008/04/03(木) 03:18:18 ] あげ 630 名前：デフォルトの名無しさん [2008/04/17(木) 12:46:54 ] ユークリッドのアルゴリズム(テキストp.10参照．java版はHP参照)を用いて 1,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、 引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック 1GHzに相当）を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。 「X年Xヶ月」など実感が分かる単位に直して答えよ。 この解き方がわかる人がいましたら是非教えて下さい。 解けなくて困っています。 631 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 13:30:05 ] >>630 宿題は自分で解決しようと努力しないと意味がないぞ どこまでは理解できていて、どこが分からないんだ？ 632 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:05:58 ] というか、奇妙な問題だな 10^N は N>=2 なら25で割り切れる。 つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら って場合か？　それでも実感がわかる単位にはならないわな 633 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:46:19 ] ・>>630が問題を間違えている ・出題者のちょっとした遊び心 どっちかじゃね？ 難しそうに見えて実は簡単な問題を出して 最初から課題をやる気がない奴を調べるためだったりしてｗ 634 名前：デフォルトの名無しさん [2008/04/21(月) 13:16:15 ] 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 格納されているデータの中で最小の値を探索する操作 これを現在解こうと思っていますが、よく分かりません。 分かる人は是非教えて下さい、お願いします。 635 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 13:32:09 ] 1-1 最良：定数 最悪：k比例 1-2 最良：定数 最悪：k比例 1-3 最良：k比例 最悪：k比例 636 名前：デフォルトの名無しさん [2008/04/21(月) 15:08:07 ] 配列を用いてリストを実現することを考える．今，配列には以下のように データが格納されているとする．(配列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に設定せよ) 637 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 16:28:55 ] ここは宿題すれじゃねーんだよ・・・ 638 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:03:43 ] 行列計算のガウスザイデル法が収束しないことがあるので気になっていたけど 検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。 (残差を最小にするから、たとえ解が無くても最適な値が求まる？収束に向かうのは確実？) ただ、ガウスザイデル法は数行のプログラムなのに対して 見つけたプログラムがかなりでかいサイズになっているのがまた気になる。 ガウスザイデル法で残差を小さくするような改良って無いのかな？誰か知ってる？ 639 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:40:08 ] これが、SOR法である。 ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。 従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。 www.akita-nct.ac.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html 640 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 18:02:14 ] ω=1.9から始めて発散なら値を引き下げていけばいいって事だな ω=1がもともとのやつ　 641 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:29:31 ] ガウスザイデル法には，原理的に収束しないインスタンスが存在するので 収束しないことが気になるような場合には，そもそも使ったらダメ． これはSORでも状況は変わらない． GMResやらBiCGやらIDRやら反復解法は色々あるんだから 解きたい問題にあわせて適切に解法を選ばないとダメよ． 642 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:57:39 ] 原理的に収束しないとは? 解が存在する行列でもできないってこと? 643 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 05:48:37 ] >>641 なるほど、どうもです。 プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。 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フィールドがあります。 考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ サーチして追加位置決定？ んー。

---

---

[ 続きを読む ] / [ 携帯版 ]

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