- 1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18]
- どこにもない強固なスレにしたい
- 828 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:00:00.47 ]
- >>823
が言いたいことはGraham捜査で全ての点を包含する凸包の点を取得し、
その集合からXYそれぞれについての最上、最下の座標を探せば言いよってことなんじゃねえかと。
まあ全ピクセルを捜査してXYの各座標について最小、最大を
見つけるたびに書き換えてあげれば目的の長方形の見つかると思う。
ただし重いｗ
もしデータを書き込むところから制御できるなら、書き込むたびに
XYについて最小値、最大値を書き換えてあげば簡単に見つかると思う。
- 829 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:35:11.13 ]
- >>828
もし >>823の意図がそれなら、彼は必ず一つの長方形で覆うものと勘違いしてないか？
点群が１ヶ所に固まっていれば長方形一つが最も無駄が無いだろうが、
まばらに分散していれば複数の長方形で覆った方が無駄が無い場合の方が多い
- 830 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 13:18:57.72 ]
- >>810の問題だと一つ以上の長方形の集合を求めるだっけか。
前提として点を2つ以上含めた物を長方形とするって決まりが暗黙的に適用されるのかな。
長方形同士ってかさなってはいけないとかもあるのかな？？
- 831 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:06:17.79 ]
- 微妙に問題が曖昧なんだな。
とりあえず、ある程度の塊に点群を分類してからやりたいなら、空間(ここでは平面か)分割してクラスタリング。
クラスタ重心を計算しながら分割領域を調整。調整が終わったらグラハムさんの出番。
…で、できそうな気がするけど、適当思考なので上手く分割できるかちょっと自信ない。
これだと、矩形の重なりは発生する可能性が残ってるし。
- 832 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:17:43.65 ]
- 危険点をカバーするように検査エリアを設定したいのかな。
だとすると、水平方向はある程度無駄が在ってもいいけど垂直方向はできるだけ無駄がない方がいいとか、
矩形同士が重ならないだけでなく水平方向に違う高さを持つ矩形が存在したら拙いとかw
- 833 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:25:36.60 ]
- >>810応答せよｗ
- 834 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:47:16.41 ]
- 何を求めるのか、それが曖昧だ。
面積を最小にするのか、矩形の数を最小にするのか。
n個の点に対して、面積の最小値はnだし、矩形の最小値は1。
なので、求めるモノを定義しないと、「だいたいこんな感じ」の解しかでてこない。
- 835 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 18:06:34.87 ]
- >>834
だから >>818 で評価関数はどうすんのと訊いたら、
>>821 でまだ考えていないと
- 836 名前：デフォルトの名無しさん mailto:sage [2011/05/12(木) 00:17:47.50 ]
- 求めたものを結局何に使うのかがわかればもっと適した方法が絞れるんだろうけどな
- 837 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 19:43:52.24 ]
- ループと動的確保なしで数値範囲の和と積を扱う手法は有りますか？
- 838 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:05.61 ]
- >>837
悪いが意味が分からん
具体的に、何か例を示してくれ
こういう入力に対して、こんな計算をして、こういう出力を得たい、とか
- 839 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:53.56 ]
- >>837
なぜにそんな限定を？
- 840 名前：837 mailto:sage [2011/05/16(月) 22:13:20.11 ]
- YesNoで答えられる質問一つで数値の範囲が決まる
Yesなら[a,b)、Noなら[-inf,a)or[b,+inf)
で可変個の質問にユーザーに答えさせて範囲をand結合して絞りこむ
で、最後に絞り込んだ範囲を表示
という課題がでたんです
でもその講義でまだ入出力とifとgotoしかやってないんです配列もやってません
どうも周りに聞いたところによるとその教授は講義範囲外のことをあまり使うといい顔をしないらしいんです
ですので講義範囲内で処理したいんですが…という感じです
- 841 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 22:58:41.22 ]
- goto と if 使えるならループ作れるじゃん
- 842 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 23:32:25.49 ]
- >>840
宿題は自分でやれよ屑。
あと、おまえみたいなゴミは社会に出てくるな。
氏ね。
- 843 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 01:34:33.75 ]
- いずれにしろこのスレで聞く事じゃないな
- 844 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 03:16:59.99 ]
- >>840
講義範囲外のこと使っていい顔しない教授とかクソだから無視で。
- 845 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 07:32:31.58 ]
- ざっとみて講義が目標とする力量に達していたら
「できるんだったら来週からこなくていいよ。単位だしとくから」
ってのが大学的
- 846 名前：デフォルトの名無しさん [2011/05/31(火) 21:25:56.80 ]
- 相異なる３１個んもデータがある。この中に含まれる数をキーとして逐次探索
を行うデータが見つかるまで、それぞれ何回の判定が必要か、期待値を求めよ
これの逐次ってどうやって求めるんですか？？
1/31+2*1/30+・・・・
みたいな感じでしょうか・
またキーが含まれない場合もおしえてくださいｍｍ
- 847 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 21:39:11.09 ]
- 期待値は31/2回
キーが含まれない場合は31回
- 848 名前：デフォルトの名無しさん [2011/05/31(火) 21:53:04.17 ]
- ありがとうございます
含まれる場合の期待値の求め方をおしえてください
キーが含まれない場合の２分木探索はどうやるんでしょうか？？
- 849 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 23:00:07.25 ]
- どっから二分木でてきたんだ
- 850 名前：デフォルトの名無しさん mailto:sage [2011/06/04(土) 19:20:16.63 ]
- Write-Ahead Loggingのアルゴリズムって
何があるのですか？
- 851 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:23:27.24 ]
- Nこ（N<=256）の重さ付き要素から最小の2こを取り出して合計して1つにして戻す（N-1こになる)という操作をするときに
①昇順ソート→index1,2を取り出して合計して戻す
②一回操作して最小の2つのインデックスを記録→取り出して合計して戻す
どっちが速いかな？オーダーだけ見ると①のような気がするけどswapコストとか考えると②の方がいい？
- 852 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:29:12.79 ]
- それこそ直ぐにプログラムかいてベンチとれってかんじじゃね？ｗ
- 853 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 16:00:31.18 ]
- 256個なら誤算の範囲。
N=100万とかなら、迷わず2じゃね？
なんで、1のオーダーの方が小さいと思うの？
- 854 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:40:48.70 ]
- 各ピクセルが得られるビットマップ画像があります
これをjpgエンコードしたほうがいいのかpnhエンコードしたほうがいいのか判別するにはどのような方法が考えられるでしょうか
- 855 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:42:51.03 ]
- 何を指標にして判断したいのかかけよな、エスパーでもさがしてんのかよ。
- 856 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 16:12:56.69 ]
- 俺はピクセルの取得できないビットマップ画像を教えて欲しい。
- 857 名前： 忍法帖【Lv=3,xxxP】 mailto:sage [2011/06/10(金) 16:31:42.49 ]
- そんなことよりも、私はpnhエンコードとやらを知りたい。
- 858 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 19:09:13.91 ]
- ピンフ形式だよ。言わせるな恥ずかしい。
- 859 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 20:40:53.31 ]
- アンコの方が好みです
- 860 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 21:44:37.61 ]
- 平和、すなわちパチンコ業界の手先だな
- 861 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 22:29:46.37 ]
- 麻雀の役を辞書にして圧縮するとかどうだろう。
グラデは順子が多いとか。
- 862 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 23:47:52.31 ]
- >>851
(3) 最初にヒープを作る→ヒープから最小値2個取り出し合計してヒープに戻す
オーダー的にはこれがいいと思うよ
- 863 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 18:55:05.37 ]
- アルゴリズム考える時ってキャッシュ効率とかアクセス効率とか最初から含めて作業始める？
それとも論理的な計算量だけで考える？
- 864 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 19:16:10.15 ]
- 私は数学屋じゃないから、先ずはシンプルかつ汎用性を考えるね。
- 865 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 21:48:47.05 ]
- 非負の整数a, b（a <=b)があったときに
a <= x <= bになる、「いい感じの整数x」を求める方法はないかね？
クイックソートのピボット選択や、パーリンノイズやGAで使いたい。
一番簡単なのはx=(a+b)/2なのだが、面白味に欠ける。
x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
できればaとbが一意ならxも一意で決まって欲しい。
フィボナッチ分割はどーかなー。
- 866 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:00:02.99 ]
- 黄金分割しろ。
- 867 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:27:59.93 ]
- >>865
> x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
アルゴリズムスレなんだから、「気がする」で放っておくんじゃなくて、
本当に求めているパフォーマンスを達成できないほどのオーバーヘッドか確認しようよ
あとアルゴリズムスレなんだから、何が「いい感じ」なのか
できる限りハッキリさせようよ
とりあえず、a と b の中間値が「いい感じではない」ことは分かった
擬似乱数はシードを決めれば入力値に対して一意に決まるが、
もしオーバーヘッドが気にならないほどであれば、擬似乱数でいいのか？
擬似乱数が「いい感じ」なのか？
そして、アルゴリズムスレなんだから、「フィボナッチ分割はどーかなー」ではなく、
実際にフィボナッチ分割したらどんな a b に対してどんな値が出力されたのか示してくれ
- 868 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:44:09.90 ]
- ゆとり乙
- 869 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 10:53:51.44 ]
- 比率を一定にしたいなら、積の平方根とか。0が入ったら知らんが。
でも、ピボットに使うっていっても、分布しだいじゃね？
- 870 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:07:33.88 ]
- たとえば
func shikaku(left, top, right, bottom){
if (十分小さければ){
塗りつぶす(left, top, right, bottom);
} else {
x = bunkatsu(left, right);
y = bunkatsu(top, bottom);
shikaku(left, top, x, y);
shikaku(x, top, right, y);
shikaku(left, y, x, bottom);
shikaku(x, y, right, bottom);
}
}
で、モヤモヤした感じが出したい。
ピボットはまあ、乱択っぽくて任意の分布でもいいかなと。
- 871 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:15:47.19 ]
- どう見ても全部塗りつぶしてるようにしかみえないのだが。
- 872 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 18:27:45.99 ]
- ああっ、色を指定するの忘れていた
- 873 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 00:42:57.61 ]
- 株に関するプログラムをしたいのですが、
ここで質問して良いですか？
株の専門用語の話とかじゃなくてグラフに関する事なんですが。
- 874 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 09:06:44.12 ]
- ロケット工学投資法を読破した俺が答えてしんぜよう
- 875 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:11:15.41 ]
- >>874
では、それで御願いします。
株のサイトでチャートの形によって、売買銘柄を
選択するサイトがあるのですが、その仕組みというか
考え方を教えて下さい。
一例として、上昇トレンドかどうか判断するには移動平均を
1日ずつ計算して前日より上がっているかどうかを比較して
いけばいいかなと思ったのですが、実際には上がったり下がったりして、
単純な比較だと、実際は上昇トレンドなのに途中に下がった日があるので、
上昇トレンドと判定できない場合が出てきます。
期間を決めて、その期間内の最高値と最安値が何月何日か、
もしくは、本日が期間内の最安値より高いかで決めるにも、
それじゃ、期間を何日間にするのかと言った条件によって
変わってくるだろうし、どう判断条件を作ればいいか分からないのです。
チャートの形にも色々あるので、簡単には説明できないと思いますが、
上昇トレンドの判断の仕方だけでも教えてもらえれば、他にも応用できるかも
しれないと思いますのでよろしくお願いします。
長文失礼しました。
- 876 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:52:34.06 ]
- そりゃスレチだな。
- 877 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 12:13:47.96 ]
- スレチですか。
失礼しました。
- 878 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:12:58.78 ]
- >>875
ロケット工学投資法にはトレンドラインの作り方が載ってる
まああれを馬鹿正直に実装するより楽な方法もあるんだが……
タダでは教えられんｗ
- 879 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:14:23.21 ]
- >>875
追記。単に作画したパターンにマッチする銘柄を選択するだけなら、
それは「パターン認識」技術の世界だ。ぐぐれ。
- 880 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 15:01:28.43 ]
- >>878
∧∧ ｺｲﾔｧｧｧｧ！！
(д´* )
（⊃⌒*⌒⊂)
/__ノωヽ__）
>>879
パターン認識、オソロシス
- 881 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:17:06.36 ]
- この株のネタだと微分の話になるんじゃないのか？
- 882 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:19:46.59 ]
- >>875
チャートだけ見て判断とか馬鹿だろ。
帰納的に、現実に起こった事実と、チャートの微分を比較できなきゃ
予測がかすりさえしないだろ。
- 883 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:47:34.80 ]
- >>882
お前は質問スレで何言ってんだ？
だったら、微分を調べろで良いだろ
馬鹿なのか？氏にやがれなのか？
- 884 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:10:40.43 ]
- ここ質問スレじゃないだろ・・・スレタイなんて書いてあ
- 885 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:15:05.39 ]
- あ、ホントだ
ごめんよ
- 886 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 05:50:28.01 ]
- 木に一本だけ辺をつけ加えて最長となる閉路を探すアルゴリズムか
グラフの中から最長となる閉路を探す方法を教えて下さい
- 887 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 14:11:58.10 ]
- >>886
前者の場合
元の木Tの最も深いノードをルートにした木T'において、
木T'のルートと最も深いノードの間に
一本だけ辺をつけ加えたのが最長閉路になるのでは？
- 888 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 11:34:06.03 ]
- 勉強で木構造とそれを巡回するイテレータをC++で作ってるんですが(STLのようなインターフェイスで)
イテレータの内部にスタックorキューor到達済みノードのリストを動的に確保して保持することなく
すべてのノードを巡回する方法はありますか？
イテレーターなので再帰関数を使って一気にという事ができないので
どうしても内部に状態を保持しないとダメかなとは思うんですがアロケートを駆使返すのは効率が気になって…
- 889 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 13:32:29.72 ]
- vectorかlistを包含したnodeクラス作って再帰で巡回させるのはだめなのかい？
- 890 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 20:48:32.37 ]
- 巡回する順番はどうでもいいんだったら
すべてのノードを共通の動的配列上に確保しておけば?
- 891 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 21:27:39.01 ]
- Addしたら必ず1本の共通なリストにノードを追加するのはありだね！
- 892 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:06:08.91 ]
- オブジェクトプーリングするのもいいかも
- 893 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:27:53.42 ]
- 配列もリストも使わずに、状態保持もしないで全ノードを巡回するアルゴリズム
ただし、木を破壊する
[1]. ルートノードを巡回する
[2]. ルートノードの子ノードから１つノードxを選び、
他の子ノードを全てxの子ノードにする
[3]. xをルートノードと見なして [1] へ
- 894 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:32:36.91 ]
- 親へのポインタ持ってたら普通にできますた
- 895 名前：デフォルトの名無しさん mailto:sage [2011/10/13(木) 14:44:27.48 ]
- バーローｗ
- 896 名前：デフォルトの名無しさん [2011/10/25(火) 21:39:34.27 ]
- 誰か教えてください。
アルゴリズム入門の授業なんですが
・性の小数部分を求めるサブルーチンＤＥＣのフローチャートを書け
・サブルーチンＤＥＣとサブルーチンＩＮＴを使って入力した正の実数の小数点以下を切り上げた
整数を表示するフローチャートを書け
お願いします
- 897 名前：デフォルトの名無しさん mailto:sage [2011/10/25(火) 22:24:50.90 ]
- まず浮動小数点数の規格を調べます
- 898 名前：デフォルトの名無しさん [2011/10/26(水) 02:34:55.29 ]
- 言語の持っている暗黙のキャスト機能が使ってよいなら簡単なんだが
アルゴリズムの授業なんだから多分ダメなんだろうね。
- 899 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 04:55:27.33 ]
- まずは、整数値を求めればいい。元の値 - 整数値が小数部分だ。
切り上げは、小数部分が0かどうかで整数値か整数値+1かを返せばいい。
整数値は
1より小さくなるまで10で割るのを繰り返す。
その回数分10を掛けながら1～9までの値と比較することで一桁づつ数字を確定していく…
なかんじかな。ループ中に10を掛けている値から確定した数字を引いていくのと、
0に初期化してある変数に10を掛けながら足していくのを忘れずに。この変数が元の値の整数値になる。
浮動小数点数でやると、誤差が出るだろうけれど…
- 900 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 08:11:17.89 ]
- アルゴリズムをフローチャートで書かせるって、まだ一般的なんか？
- 901 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 09:02:43.69 ]
- いまどき信じられん教育のレベルだ
- 902 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:02:05.33 ]
- 高校の情報なんちゃらとかって科目じゃね?
- 903 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:14:01.81 ]
- てことは、日本の高校が信じられん教育レベルだって事実になってしまうわけだけども
- 904 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:13.30 ]
- www.johoka.net/flowchart.htm
- 905 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:20.20 ]
- 実際、「使える！Microsoft Office」って改名したらどうだ？ って言いたくなるような
教科書が、高校の情報の教科書の中で一番人気だという話だ。
- 906 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:30:03.53 ]
- 大半の人にとって、Office の使い方が将来一番役立つ可能性が高いのは確かだけども。
日本のソフトウェア開発は育たないわね。
- 907 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:36:20.78 ]
- 小学校から徹底してopen officeを使うように指導すれば
日本全体でオフィスソフトに使われている莫大な金を節約できる
- 908 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 16:20:09.01 ]
- その考え方はまずい…
使う側からしたら無料なのはありがたいけど、作る側それこそ育たない。
- 909 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:41:00.78 ]
- その論理ではOpenOfficeはともかく、GCCとかはこの世に存在しないことになるね。
- 910 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:58:05.44 ]
- >>907
有料だと金が国外に流出してるだけだし
かといって無料だと国内でも回らないし
- 911 名前：デフォルトの名無しさん [2011/11/07(月) 18:03:02.90 ]
- （ExcelVBAのスレから誘導されてきました）
末尾再帰の最適化について質問です。
FunctionA(n As Long)
If n=0 then
FunctionA=1
Else
FunctionA=FunctionA(n-1)+FunctionB(n-1)
End if
End Function
FunctionB(n As Long)
If n=0 then
FunctionB=2
Else
FunctionB=FunctionA(n-1)+FunctionB(n-1)
End if
End Function
このように末尾で2つの関数が再帰呼び出しされている場合、どのように最適化すればよいでしょうか。
nが大きいと2の累乗でスタックに詰まれていくから重くなるのだと思います。
- 912 名前：デフォルトの名無しさん [2011/11/07(月) 18:19:50.43 ]
- forをつかって普通にループをかいてください。
これで理解できなければあなたには無理です。
- 913 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 18:56:27.71 ]
- っていうか、FunctionA や FunctionB の演算って末尾なの？
- 914 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 19:25:14.40 ]
- どちらも、最後に自分に戻ってきて、2つの値を足して、それを戻す、という形になってるから、
末尾呼び出しになってない。
- 915 名前：デフォルトの名無しさん [2011/11/08(火) 00:20:34.51 ]
- うるさいな
- 916 名前：デフォルトの名無しさん [2011/11/08(火) 09:56:31.88 ]
- 足し算じゃなく1個ならforなりn--なりで終息させられるが2個なのが厄介だな
- 917 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 12:52:21.06 ]
- 例が悪いよ
2つの関数が再帰呼び出ししてるのは関数の末尾じゃないし、
FunctionA と FunctionB で異なるのは引数がゼロの場合の返値だけ
おまけに、FunctionA(n-1)+FunctionB(n-1) は共に同じ n-1 に関数を適用してる
だったらアルゴリズムのスレとしては、
相互再帰呼び出しの形自体を止めて一つの関数にまとめた方が効率が良い、
としか言いようがない
そもそも、ここはアルゴリズム大辞典のスレなんだから、
何を実現したくてこのアルゴリズムを選択したのか言わないと議論にならん
（何を入力して何を得るのか）
これなら、ここじゃなくてExcelVBAの住人が答えるべきだと思うが
- 918 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:09:42.38 ]
- www.cc.kyoto-su.ac.jp/~yamada/ap/array_rep2sol.html
このサイトの後半で紹介されている
最大公約数を使って配列を回転させるアルゴリズム
何か名称がついていたら教えてください。
- 919 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:38:54.10 ]
- >>918
もしかして、
p2.2ch.net/p2/read.php?host=hibari.2ch.net&bbs=tech&key=1086272325&rc=918#r917
ここの METHOD 3 と同じかな
>>918 のページの方は配列の要素が遷移する様子が解説されていないから、
処理を追うのが面倒でざっとしか見てないが
「珠玉のプログラミング」という本にも
METHOD 3 と同じ [お手玉の方法] として紹介されているらしいね
- 920 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:42:11.71 ]
- 開発者の
ecommons.cornell.edu/handle/1813/6292
の中では Dolphin algorithm って書いてあるけど、
そんな名前で呼ばれてもだれもわからんだろうな
- 921 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:44:20.42 ]
- あと、ここも
www.imminentweb.com/technologies/rotating-algorithms-programming-pearls-jon-bentley
- 922 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:58:54.92 ]
- >>919, >>920, >>921
ありがとうございます。
自分で図を書いて理解した後だと
イルカが連なって飛び跳ねるイメージはしっくり来ますね。
- 923 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:02:34.39 ]
- 「珠玉のプログラミング」に載ってる、といって先日人から教えてもらったが、
名前が付いてるということは初めて見た気がする。
- 924 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:09:28.83 ]
- いや、俺も実際に「珠玉のプログラミング」を読んだわけじゃないんだ
"gcd array rotate" でググったら、一番最初に >>919 のページがヒットして、
9件目にその本に載ってると書かれてたブログがヒットしたのを見ただけ
- 925 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:20:34.12 ]
- 本にも載ってるけど、大きい配列だとキャッシュが働かなくて結局遅いっぽいね
- 926 名前：918 [2011/11/08(火) 20:40:16.46 ]
- >>919 の URL では見えなかったですが
www.geeksforgeeks.org/archives/2398
の事だったんですね。 キーワードが分かったのでたどり着けました。
- 927 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 21:08:53.87 ]
- どうしても速度を求めてるなら、テンポラリ使ったほうが速そう。
あるいは全体の位置が移動してもいいとか。エレガントな手法として悪くないと思うけど。
- 928 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 22:37:53.23 ]
- >>926
スマン、指摘されるまで全く気づかんかった
貼るURLを間違えてた
- 929 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 18:35:38.20 ]
- 上で紹介されている配列回転アルゴリズムはコピーにコストがかかるデータの場合に有利ですね。
テンポラリ配列や２回逆転方法の約半分のコピー回数で済むので
例えば、私の環境では以下のようになりました。
typedef struct {
long id;
long data[1000];
} data_t;
こんなデータの配列 data_t arr[1000] を回転操作( 0〜999 )
$ gcc -O3 -o rotate_temporaly rotate_temporaly.c
$ time ./rotate_temporaly
rreal 0m3.172s
user 0m3.158s
sys 0m0.012s
$ gcc -O3 -o rotate_reverse rotate_reverse.c
$ time ./rotate_reverse
real 0m1.915s
user 0m1.910s
sys 0m0.004s
$ gcc -O3 -o rotate_dolphin rotate_dolphin.c
$ time ./rotate_dolphin
real 0m0.703s
user 0m0.699s
sys 0m0.003s
おそらく細かい実装の違いではカバーしきれないほどの差が出ます。
まあ、この種のアルゴリズムが必要になる前にデータ構造の見直しをしたほうがいいとは思います。
リスト構造なら一部の配線付け替えで一瞬です
- 930 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 19:22:14.99 ]
- アルゴリズムの性能評価をするときに、コンパイラの最適化を有効にするのって無しでしょ？
- 931 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 20:04:05.29 ]
- >>930 確かにそうですね。
というわけで最適化無しでもやってみました。
$ time ./rotate_temporaly
real 0m4.044s
user 0m4.032s
sys 0m0.011s
$ time ./rotate_reverse
real 0m10.280s
user 0m10.274s
sys 0m0.005s
$ time ./rotate_dolphin
real 0m3.495s
user 0m3.490s
sys 0m0.004s
これで比べるとテンポラリ配列の方法もそれなりに健闘しています。
二回逆転の方法は、おい大丈夫か？レベルです。最適化ってすごいですね
- 932 名前：デフォルトの名無しさん [2011/11/09(水) 21:51:10.45 ]
- >>929
珠玉のデータはもっとでかい配列までとってたような気が。
> リスト構造なら一部の配線付け替えで一瞬です
目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
- 933 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 21:53:47.81 ]
- >>930
> アルゴリズムの性能評価をするときに、コンパイラの最適化を有効にするのって無しでしょ？
なんで？ありでしょ。
どれもO(n)だ、結局どれが速いのってときに、
最適化しなかったらコーディングの差を見てるだけになる。
- 934 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:12:51.33 ]
- コンパイラの最適化で比較するのは、本当に最後の最後
その前にもっとやっておくことがある
同じ O(n) でも n を何で測るかをちゃんと揃えないといけない
例えば一方のアルゴリズムはステップ数で測って、
他方のアルゴリズムはステップ数にメモリアクセスの数も含めて測る
なんてやってはいけない
その上でまだ同じ O(n) なら、今度はオーダーを計算する為に省いた係数を
低次元のものまでちゃんと補ってより細かく比較しないといけない
コンパイラの最適化に頼って処理速度によるアルゴリズムの優劣を比較するのは
少なくともその後にすべきで、同じ O(n) だからといって安易にすべきではない
それでも、その最適化による比較で分かるのはアルゴリズムの質的な優劣ではなく、
単にそのコンパイラや表現する言語と「相性が良いかどうか」でしかないと思う
- 935 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:17:14.40 ]
- node数が億単位(>=2^32)になるとlinked list実装の方がはるかに高速というハード（システム)も現実にある
- 936 名前：931 mailto:sage [2011/11/09(水) 22:30:20.09 ]
- ごめんなさい。単に興味を持ってやってみたらこうなったよ程度に受け取ってください。
- 937 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:34:33.71 ]
- キャッシュの有効利用でさえ、良いアルゴリズムの条件。
最適化なしに測定なんかできん。
- 938 名前：931 mailto:sage [2011/11/09(水) 22:35:58.31 ]
- >>932 なんか蒸し返してしまいますが
>目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
例にあげたようなノードオブジェクトが大きい場合
リンクを辿るのに要するコスト ＜ ノードコピーに要するコスト
になりますよね。
>>934 の言う
オーダーを計算するための係数の違いという事になると思います。
- 939 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:41:21.64 ]
- >>937
そうであるなら、その比較検証に使用したマシンの
キャッシュ性能や特性もちゃんと細かく公表しないとけないね
（細かくと言うのは、処理速度の計測に影響が出る範囲でという意味）
でなければ、追試や他環境との比較ができない
- 940 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:53:01.18 ]
- もちろん。最善のアルゴリズムなんて、マシン固有のもので、
だからこそatlasなんかビルド時にベンチマークしてチューンしまくる。
- 941 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:53:21.32 ]
- そこまでやらなないと優位性をアピール出来ないような代物はハードの性能向上によって数年で淘汰される
- 942 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 12:09:55.94 ]
- アホかwwww
BLASが何年生き残ってると思ってるんだwwww
新しいハードウェアができたらそれに合わせてパラメータをチューニングするんだよ
- 943 名前：デフォルトの名無しさん [2011/11/10(木) 13:38:08.42 ]
- ソートのアルゴリズムの性能って、数学的にはデータを移動させる回数で評価するんだっけ？
- 944 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:43:19.12 ]
- 比較する回数じゃなかったっけ？
- 945 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:54:42.97 ]
- 比較して、結果によって一定割合で移動が発生するんで、どっちでも同じ
- 946 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:57:53.23 ]
- もしオーダーが違うなら当然大きい方な
- 947 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 17:56:42.11 ]
- 比較に時間がかかる場合、コピー(移動)するのも時間がかかるか？
それは場合によるので一般的な基準はないでしょうね。
- 948 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 09:21:28.97 ]
- 無比較ソート
- 949 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 19:47:40.37 ]
- 比較にむちゃくちゃ時間がかかる場合は、一般的でない別の手法を使うこともある
移動については、ワードよりでかい物のソートの時はポインタ使うのが普通
- 950 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 22:49:55.98 ]
- そんなこんなでソートのアルゴリズムの優劣の比較には
値の大小判定の回数を使うのが普通
- 951 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 22:54:18.35 ]
- STLを馬鹿にするな
- 952 名前：デフォルトの名無しさん mailto:sage [2011/11/12(土) 12:37:01.03 ]
- STLを馬鹿レスがどこにある？
- 953 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:14:05.30 ]
- 乱数におけるXORみたいに、処理が少なくてなおかつそれなりに良い感じにバラける、典型的なハッシュアルゴリズムってありますか？
ちなみに入力はゼロ終端のASCII文字列で出力はintです
- 954 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:16:27.86 ]
- XORShiftのこと？
- 955 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:21:41.41 ]
- 俺の知る限りだとZobrist Hashingが使えるね
1文字ごとにあらかじめ用意したテーブルから文字に対応する乱数を持ってきてXORしていく
そこそこ軽くてばらつきはいいよ
- 956 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 22:35:28.70 ]
- >>955
良い感じですね
ありがとうございます
- 957 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:46:10.28 ]
- 重ならない矩形領域が沢山あって、
矩形領域内を差した時にどの矩形領域内を差したかを
効率よく判定する方法がありましたら教えてください
- 958 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:48:54.81 ]
- 個数は何桁くらい？
- 959 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:54:28.80 ]
- >>957
矩形をx方向にソートしてｘ方向で二分探索して候補を絞る
絞った候補をy方向にソートしてy方向で二分探索して確定
- 960 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 03:29:35.09 ]
- そんな単純にはいかない
- 961 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 03:51:15.50 ]
- 開き直って全数探索するのがマシだったりするけど
まあ例えばいくつかの領域に区切り
それぞれの領域と重なるオブジェクトを登録しておくとか…
- 962 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 04:22:36.90 ]
- 領域が重なるならR-Treeがいいけど、
重ならなくてもR-Treeでいいかも
まぁ、簡単な >>959 を試してからでいいね
- 963 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 07:25:04.86 ]
- 二分探索が適用できる矩形のソートってどうやるの？
- 964 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 09:20:04.63 ]
- ヒットテストは
1つの点対無数の矩形なのか
無数の点対無数の矩形なのか
何回ぐらい判定するのか
複数回判定するとして矩形の座標は頻繁に更新されるのか固定なのか
このへんの情報で変わってくるよね
点1つ、判定一回なら全探索が最速だし
そうでないなら空間分割が速い
- 965 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 12:52:40.84 ]
- この辺り、「プログラミングのための線形代数」って本を読むと、
いろいろヒントが得られる
- 966 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 12:54:24.91 ]
- >>965
間違えちゃった
「コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用」 でした
- 967 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:08:59.61 ]
- 二分木構造の外部イテレーターってスタック無し、巡回済マーク無しでも実装できる？
- 968 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:40:59.57 ]
- 巡回済マークの一種かもしれんが、Knuthがポインタ付け替え法というのを提案してる。
激しくおすすめできないが。
- 969 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:59:05.77 ]
- 望みのイテレート順はあるの？
- 970 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 17:28:00.43 ]
- >>968
すいませんググったけどわかりませんでした
>>969
pre-orderを考えてます
- 971 名前：デフォルトの名無しさん mailto:sage [2011/12/24(土) 09:59:11.16 ]
- あーごめん「ポインタ反転法」だわ
- 972 名前：デフォルトの名無しさん mailto:sage [2011/12/26(月) 19:38:15.54 ]
- ノードは親ノードの参照を持ってるの?
持ってるのならそれほど難しい問題ではないけども・・・。
- 973 名前：デフォルトの名無しさん mailto:sage [2011/12/26(月) 20:28:32.10 ]
- pre-orderって何？
- 974 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 09:01:44.93 ]
- 行きがけ順？
- 975 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 12:35:05.74 ]
- Wikipedia で「木構造」を調べてみろ
他の情報も合わせて詳しく載ってる
- 976 名前：デフォルトの名無しさん [2011/12/27(火) 17:38:21.78 ]
- 最大の色差を持つn階調の色テーブルを作るアルゴリズム教えて。
例えば10色欲しいとしたら、10個のテーブルで、各色の色差が最もあるテーブルを作りたい。
単色グラデーションなら簡単だけどRGB織り交ぜた最大の色差を出すのが難しい。
- 977 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 17:54:40.80 ]
- 特定の３次元空間の領域内で、
それぞれの距離の平均が最大となるn個の点の座標を求める問題と同じ？
特定の３次元空間の領域内というのがRGB色空間やHSV色空間になるわけだけど
- 978 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 02:14:38.09 ]
- 「最大の色差を持つ」がどういうことなのか定義しよう
色iと色jの距離をd(i,j)としたとき、次の(1),(2),(3)のどの定義を採用するかで
(1) min_{i<j} d(i,j) が最大
(2) sum_{i<j} d(i,j) が最大
(3) sum_{i<j} d(i,j)^2 が最大
それぞれ違った答えが出てくる
次にこういった変数の個数の多い問題は手計算で答えを得ようとせず
プログラムを書いて数値計算で求めてみよう
step 1. 乱数でn個の色の初期値を決める
step 2. 乱数でn色の中から1色をランダムに選び、その色だけを変えて他の色を変更せずに
「色差」が最大になるようにする. この操作を1000回ぐらい繰り返す
問題の性質が良ければ、適当な答えに収束するかも
- 979 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 07:20:57.68 ]
- 10個くらいなら、全ての点と点の間に自然長が色空間より遙か長いバネを入れて、
色空間の中心にぎゅっと押し込めてから緊張を解くことをシミュレートしてみるとか
やったこと無いから、実際にどうなるかは知らんが
- 980 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 08:21:41.06 ]
- 大団円
- 981 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 19:20:40.87 ]
- １０色なら、真っ白と真っ黒と円周上の６色だよな？
- 982 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 19:25:49.87 ]
- >>981
証明しろよ
- 983 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 10:19:39.29 ]
- >>981
６角形の一辺の２色と、一つ飛びの２色との間にある色は
一辺の色差より大きい
だめだ論破
８色だと、立方体の頂点でいいんだよな。たぶん。
- 984 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 14:20:05.95 ]
- RGBでもHSVでも空間距離が単純に見た目の色差と比例するわけではないよ
全ての点間で距離を最大化できても見づらい色同士が出てくる
- 985 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 21:05:13.74 ]
- n体の色相環を使うのはダメなの？
- 986 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 21:15:13.49 ]
- >>984
> 全ての点間で距離を最大化できても見づらい色同士が出てくる
かどうかは、やってみなくちゃ分からんと思うが
そもそも、距離を最大化する配置が分かってないのに言えんだろ
|
 |
