計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

596:デフォルトの名無しさん
07/12/31 08:25:44
>>595
日付を1日進めるプログラムは書けるかい？

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

597:デフォルトの名無しさん
07/12/31 08:49:10
つーか、なんで既存ライブラリを使わないのだろう。
大抵の言語に日付け処理系の関数があると言うのに。

598:デフォルトの名無しさん
07/12/31 11:47:35
>>595
URLﾘﾝｸ(ufcpp.net)

599:デフォルトの名無しさん
07/12/31 12:25:41
>>595
ちょっと検索してみたらこんなのがあった
delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい

URLﾘﾝｸ(kwikwi.cocolog-nifty.com)

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

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

601:デフォルトの名無しさん
07/12/31 12:51:11
>>598
おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25　　…?　もはや何がなんだか。

URLﾘﾝｸ(cl.is.kyushu-u.ac.jp)
こんなの見つけたので読んできます。

602:デフォルトの名無しさん
07/12/31 13:18:34
>>600
URLﾘﾝｸ(www.tensyo.com)
ここの
int YMD_AddD(int *Y,char *M,char *D,long d）　って関数を見ると
負数を渡した場合は　400年循環を使って正に直せばいいみたい。

603:デフォルトの名無しさん
08/01/01 10:28:35
つまり、-3日なら 400年前から(146097-3)日後と計算するわけか

604:デフォルトの名無しさん
08/01/02 02:09:27
除算のシフト演算化はコンパイラの最適化段階で
自動でやってくれるものだと思ってたんだが、そうでもない？

605:デフォルトの名無しさん
08/01/02 08:29:27
コンパイラの性能がソレなりならって事でしょう。
固定値の除算ならさらに、掛け算で代用してくれるのも多いね。

606:デフォルトの名無しさん
08/01/02 10:22:11
>>604
2のべきの定数ならね。

607:デフォルトの名無しさん
08/01/02 12:18:44
という事で
１、カレンダを1日進める関数関数を作る
２、+N日は１の関数をN回呼ぶ
３、-N日は、年数を400日戻してから、146097-N回１の関数を呼ぶ

608:595
08/01/02 20:05:17
これでいいのかな？
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++;
　}
}

609:595
08/01/02 20:06:50
/* 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;
}

610:595
08/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:デフォルトの名無しさん
08/01/08 03:16:56
漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ

612:デフォルトの名無しさん
08/01/08 03:17:24
誤爆です。
ごめんなさい

613:デフォルトの名無しさん
08/01/08 13:01:23
>>611
そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。

614:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/02/09 20:31:46
繰り上がり

616:614
08/02/09 20:41:09
>>615 すばやい回答ありがとうございます。
くりあがりですね。

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

617:デフォルトの名無しさん
08/02/09 20:44:43
>>616
そのとおり。

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

618:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/02/11 23:37:33
HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた

620:デフォルトの名無しさん
08/02/18 17:15:48
行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、
調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか？

621:デフォルトの名無しさん
08/02/18 23:15:28
誤差についてはほとんど知識がないので調べてみました。
たまたま今やっていることに関係あるので。

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

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

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

622:デフォルトの名無しさん
08/02/18 23:42:00
>>621
そんなに詳しくないから適当に書くけど、
基本的にはその通り。
収束性が悪いほど誤差は積もりやすい。

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

623:デフォルトの名無しさん
08/02/19 02:13:06
>>620
一概にそうとは言えない。というか、単純に比べることは不適当。

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

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

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

625:デフォルトの名無しさん
08/02/19 16:20:26
>>624
マクロでやってるなら、ピボットの選択してる？

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

627:デフォルトの名無しさん
08/02/21 22:41:32
>>625
＞マクロでやってるなら、ピボットの選択してる？
いえ、まず中心をすべて1にしてから掃き出しています。
これではダメでしょうか？

628:デフォルトの名無しさん
08/02/22 19:59:46
>>627
ダメ

629:デフォルトの名無しさん
08/04/03 03:18:18
あげ

630:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/17 13:30:05
>>630
宿題は自分で解決しようと努力しないと意味がないぞ
どこまでは理解できていて、どこが分からないんだ？

632:デフォルトの名無しさん
08/04/17 14:05:58
というか、奇妙な問題だな
10^N は N>=2 なら25で割り切れる。
つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう

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

633:デフォルトの名無しさん
08/04/17 14:46:19
・>>630が問題を間違えている
・出題者のちょっとした遊び心
どっちかじゃね？

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

634:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/21 13:32:09
1-1
最良：定数
最悪：k比例
1-2
最良：定数
最悪：k比例
1-3
最良：k比例
最悪：k比例

636:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/21 16:28:55
ここは宿題すれじゃねーんだよ・・・

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

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

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

639:デフォルトの名無しさん
08/04/21 17:40:08
これが、SOR法である。
ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。
URLﾘﾝｸ(www.akita-nct.ac.jp)

640:デフォルトの名無しさん
08/04/21 18:02:14
ω=1.9から始めて発散なら値を引き下げていけばいいって事だな
ω=1がもともとのやつ　

641:デフォルトの名無しさん
08/04/22 00:29:31
ガウスザイデル法には，原理的に収束しないインスタンスが存在するので
収束しないことが気になるような場合には，そもそも使ったらダメ．
これはSORでも状況は変わらない．

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

642:デフォルトの名無しさん
08/04/22 00:57:39
原理的に収束しないとは? 解が存在する行列でもできないってこと?

643:デフォルトの名無しさん
08/04/22 05:48:37
>>641
なるほど、どうもです。
プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが
やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても
その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。

644:デフォルトの名無しさん
08/04/22 09:27:07
>>642
そのとおり．
ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて
解が存在しても，収束するとは限らない．

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

645:デフォルトの名無しさん
08/04/23 16:48:12
>>644
639のこれは?

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

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

647:デフォルトの名無しさん
08/04/23 20:15:14
ω=1はガウスザイデル法である

648:デフォルトの名無しさん
08/04/25 01:51:21
グレースケール変換。こいつより高速アルゴキボンヌ。
条件：徐々にグレースケール変換できればvolumeの持たせ方は自由

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

649:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/25 01:54:17
あ、一応JavaだけどCとかでもおｋ

651:デフォルトの名無しさん
08/04/25 02:10:24
volumeって要は、グレイ化度合いみたいなものなのね。
処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。

652:648
08/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
08/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:デフォルトの名無しさん
08/04/25 06:45:23
Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
これの意味を教えて

655:デフォルトの名無しさん
08/04/25 06:54:50
>>654
YUV とか色空間あたりでググって見たら、、、
wikipedia の「色空間」だとか
URLﾘﾝｸ(ofo.jp) の 2.NTSC ～
にある式を小数点の無い形にしたと考えたらいいんじゃない?

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

659:デフォルトの名無しさん
08/04/25 10:12:30
java　だから　割り算をシフトにするとかの最適化があんまり効かないのかもな

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

660:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/26 10:06:56
>>645
任意のパラメタωに対して、真の解に収束しない例が作れる．

662:648
08/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:デフォルトの名無しさん
08/06/12 13:23:40
誰かクイックソートが挿入法よりなぜ早いのか教えてくれ

クイックソートのほうがめんどくさそうなのに最速とか理解できん・・・

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

665:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/07/04 23:20:30
エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)

667:デフォルトの名無しさん
08/07/27 08:46:19
>>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？

668:デフォルトの名無しさん
08/08/30 18:14:43
あげ

669:デフォルトの名無しさん
08/10/11 22:27:10
URLﾘﾝｸ(www.forest.impress.co.jp)
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）

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

670:669
08/10/11 22:29:00
失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)

プログラミングの為の数学と算数 vol.3
ｽﾚﾘﾝｸ(tech板)

671:デフォルトの名無しさん
08/10/11 23:04:05
>>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？

672:669
08/10/11 23:11:15
>>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。

673:デフォルトの名無しさん
08/10/11 23:16:47
>>669
手始めに ONP とか LCS とかでググレばいいんじゃね。

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

674:デフォルトの名無しさん
08/10/12 01:23:58
どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。　いや、やりたいことはdiffなんだろうけど。

675:669
08/10/12 01:54:11
>>674
オリジナルの文のうち、消えた部分を特定できれば十分です。

aaa　aaa
bbb　ccc
ccc　ddd

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

676:デフォルトの名無しさん
08/10/12 02:27:20
>>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。

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

677:デフォルトの名無しさん
08/10/12 07:27:56
> 手軽にやりたくて、

今時 FC はないだろ。

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

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

参考 URL: URLﾘﾝｸ(d.hatena.ne.jp)

678:デフォルトの名無しさん
08/10/12 12:10:51
>>677
DFってそういう出力する方法あるのか？

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

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

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

679:デフォルトの名無しさん
08/10/12 13:30:35
> わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

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

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

680:669
08/10/12 14:19:04
動的計画法と配列アラインメント
URLﾘﾝｸ(www.ibm.com)

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

681:デフォルトの名無しさん
08/10/12 15:09:12
>>679
勧めた理由はその次の行に書いたが？

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

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

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

682:デフォルトの名無しさん
08/10/12 15:26:58
>>681
> 勧めた理由はその次の行に書いたが？

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

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

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

頑張れ > >>669

683:デフォルトの名無しさん
08/10/12 16:11:41
確かにプログラム書くことが目的なのかアルゴリズム知ることが目的なのかもはっきりしてなかったね。

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

684:669
08/10/12 16:18:39
みなさん暖かい支援どうもですm(_ _)m

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

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

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

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

685:669
08/10/12 16:19:20
>>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
URLﾘﾝｸ(d.hatena.ne.jp)

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

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

686:デフォルトの名無しさん
08/10/12 16:22:21
>>685
もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?

687:669
08/10/12 16:35:39
>>686
左のbbbには\nを付けましたが、やはりModifiedが返されるようです。

あと
aaa　aaa
bbb　ccc
　　　 bbb
だと

Common
Modified
Common

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

688:デフォルトの名無しさん
08/10/12 17:10:18
> ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

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

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

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

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

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

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

691:だから、無駄なことはやめておけと
08/10/12 18:14:36
>>690
読解力のない間抜けだということはよく判りました。

692:デフォルトの名無しさん
08/10/12 18:47:39
何で>>690みたいなゴミみたいな奴がアルゴとかやってんの？

693:デフォルトの名無しさん
08/10/12 19:52:19
>>685
> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> URLﾘﾝｸ(d.hatena.ne.jp)

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

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

695:デフォルトの名無しさん
08/10/12 21:04:24
>>691
> 読解力のない間抜けだということはよく判りました。

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

696:デフォルトの名無しさん
08/10/12 21:07:15
面白そうだから黙ってたのに。

697:デフォルトの名無しさん
08/10/12 21:07:29
頭おかしくなっちゃうと屁が出るんだよねｗ

698:デフォルトの名無しさん
08/10/12 21:17:48
>>689
(ﾉ∀`)ｱﾁｬｰ

699:デフォルトの名無しさん
08/10/12 22:11:35
basicのほうが早くね

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

701:デフォルトの名無しさん
08/10/14 18:55:04
URLﾘﾝｸ(hdl.handle.net)
ここにたどり着いた
あってるかは知らん

702:デフォルトの名無しさん
08/10/14 19:06:55
management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？

703:
08/10/15 18:43:09
>>701
エラーがでます。

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

704:アラフＯＯ.ｏ（笑）
08/10/15 23:21:58
>>703
オモローな記事があるぞ。兄弟。

いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
URLﾘﾝｸ(www.atmarkit.co.jp)

705:デフォルトの名無しさん
08/10/16 20:09:11
>>703
URLﾘﾝｸ(pr.fujitsu.com)
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。

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

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

706:
08/10/17 03:43:42
>>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。

707:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/18 18:46:16
あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。

709:デフォルトの名無しさん
08/10/18 18:53:28
多めに確保して置いて、存在するところのビットを立てておけ。

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

711:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/18 19:19:05
そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？

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

714:デフォルトの名無しさん
08/10/18 19:39:07
>>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。

715:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/18 23:22:08
>>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
　unsigned int StartIndex;
　unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。

718:デフォルトの名無しさん
08/10/18 23:25:14
>挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？

719:デフォルトの名無しさん
08/10/19 00:17:17
>>713,714
反応してくれてどうもです。

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

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

720:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/19 00:59:37
>>720
想像力不足

722:デフォルトの名無しさん
08/10/19 01:38:10
俺は動画のフレーム編集を想像しながらスレを見てた

723:デフォルトの名無しさん
08/10/19 01:42:24
だとしたら>>716のa,bはa？

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

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

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

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

726:デフォルトの名無しさん
08/10/19 12:23:29
>720
URLﾘﾝｸ(icpcres.ecs.baylor.edu)
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。

727:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/22 23:37:07
N = 3m+5nでしょ。　互いに素ならいけるんではなかったか? m,nが整数なら

729:デフォルトの名無しさん
08/10/22 23:37:40
単に3と5の個数をデータとして持てばいいんじゃないの?

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

730:デフォルトの名無しさん
08/10/22 23:39:21
ax+by=1を満たす整数x,yが存在する

URLﾘﾝｸ(d.hatena.ne.jp)

731:デフォルトの名無しさん
08/10/22 23:41:50
そしたら連続する3つ作れればそれ以降、全てつくれるってことだな

732:デフォルトの名無しさん
08/10/23 00:01:14
その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました

次ページ