- 1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18]
- どこにもない強固なスレにしたい
- 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
> 全ての点間で距離を最大化できても見づらい色同士が出てくる
かどうかは、やってみなくちゃ分からんと思うが
そもそも、距離を最大化する配置が分かってないのに言えんだろ
|
 |
