データ構造とアルゴリズム総合

1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ] データ構造とアルゴリズムに関する総合スレ。 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ 232 名前：230 mailto:sage [2012/07/02(月) 17:04:55.20 ] エエｴｴェェェｪ(略 しかし別スレに移動したら、マルチあっちいけと叩かれるだけ。 このスレでお願いしますOTL 233 名前：デフォルトの名無しさん mailto:sage [2012/07/02(月) 18:04:21.18 ] 片山議員は参加者に囲まれながら、「民主党政権になってから、生活保護の不公平が見逃すことができないところに来ている。 外国人の不正受給に関しても、まずは日本人の、真面目に義務を果たしている人が優先。 今は特に、韓国なんてすごく豊かなんですから」と持論を展開し、 「私に対してもいろいろ嫌がらせがあったが、どこから来ているかはわかるんですよね。私たちの日本を愛するマグマの方が強いことを教えよう。 日本が正直者が報われる、本当に強い国にもう1度なれるように、私たちががんばりましょう」 と呼びかけると、参加者からは大きな拍手が起こった。 www.j-cast.com/2012/07/01137691.html?p=all www.j-cast.com/images/2012/news137691_pho01.jpg www.j-cast.com/images/2012/news137691_pho02.jpg 前 engawa.2ch.net/test/read.cgi/poverty/1341150152/ engawa.2ch.net/test/read.cgi/poverty/1341153256/ 234 名前：デフォルトの名無しさん mailto:sage [2012/07/02(月) 18:16:36.16 ] >>230 > 色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz なぜBoost.Polygon.Voronoiではダメなのか svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm を見てもわからない。 せめてBoost.Polygon.Voronoiが動作しない環境を挙げるべきでは。 235 名前：デフォルトの名無しさん mailto:sage [2012/07/02(月) 19:15:21.06 ] >>232 マルチした以上しかたない ２ｃｈで質問したいなら半年ＲＯＭれ 236 名前：デフォルトの名無しさん mailto:sage [2012/07/02(月) 22:33:24.51 ] >170 ・中心(0,0)、半径1の単位円として一般性を失わない ・1点を (-1, 0)と決め打ちしても一般性を失わない この条件下で、最近傍の点との距離を dist とした場合に n 点詰め込む処理を用意して、 dist に対して二分探索を行った。 詰め込む処理はある点を追加した時に、 1) その点を中心とした半径 dist の円と単位円の交点 2) その点を中心とした半径 dist の円と、今まで追加してきた各点を中心とする半径 dist の各円との交点 を次の候補として探索した。 n = 20 辺りから急激に遅くなる。 似た問題で en.wikipedia.org/wiki/Circle_packing_in_a_circle があってその結果と比べると大体合ってそうな感じ。 ideone.com/fOz4R 237 名前：236 mailto:sage [2012/07/02(月) 22:40:36.62 ] 勢い込んで書いてからあれだけど >210 >最小距離を最大化すればいいという考え方と >全ての点の組み合わせの距離の総和を最大化するという考え方の違いか で、最小距離を最大化した場合(あるいは >216 の定式化の場合)で、総和が最大になるかは分かんないね。 238 名前：230 mailto:sage [2012/07/03(火) 09:11:29.66 ] >>234 HEW。 テンプレート構文を対応していないので、STLも使えません。 >>235 マルチしていません。 239 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 09:21:35.74 ] スレ違いつってんだろが 失せろゴミ 240 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 09:52:51.30 ] Voronoiのデータ構造とアルゴリズムについてでそ。 脳に障害があるの？239はｗｗｗ 241 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 09:54:38.21 ] ↑池沼 242 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 11:24:00.28 ] 回答が返って来ない所でうだうだとするより、他所に行った方が良くないか？ 243 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 11:30:59.47 ] ↑オマのうだうだジャマ。てか、それがオマエの存在そのものｗｗｗｗｗ 244 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:06:27.06 ] クラスライブラリの場所を尋ねるスレだったのかここ 245 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:07:08.76 ] >>238 スレ立てるまでもない質問はここで 120匹目 toro.2ch.net/test/read.cgi/tech/1341099441/ 246 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:13:40.25 ] と言うよりこのスレで質問することが妥当であることを示す一言でもあればよかったのにね 『特殊なアルゴリズムのためこのスレの方が一番詳しいんじゃないかとここで質問いたしました』とかさ 247 名前：230 mailto:sage [2012/07/03(火) 12:19:40.11 ] 意外や意外に妥当なvoronoiクラスライブラリが無かったので来ました。 ・アルゴリズム事典に無かった ・Javaアプレットは小型のものがあったがC++やC言語が無い ・既存の演算やBoostで出来ちゃうから無い？ ネットにソースが散在してると思っていたんですが。。。 248 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:28:02.45 ] >>247 アプレットがあるならそれをベースにすればいいだろ。 物乞いしたいのなら、スレ違いだってばさ。 249 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:38:35.39 ] いろんな環境で動作させたいんなら環境依存の少ないJavaのそのライブラリ使えばええやん 250 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:39:59.36 ] Javaの奴ってこれだろ？ Lee Byron ≫ Else ≫ Mesh ? A Processing Library www.leebyron.com/else/mesh/ 251 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 12:43:12.80 ] Voronoi diagram - Wikipedia, the free encyclopedia en.wikipedia.org/wiki/Voronoi_diagram 外部リンクでも辿って探せや 252 名前：230 mailto:sage [2012/07/03(火) 12:48:19.89 ] 本当に物乞いするだけなら、スレじゃなくてググルするだけだし。 どちらかというと、検索結果があれ？となって、他の人がどういう対応なのか知りたかったのです。 >>248 それは不可能じゃないですが、だから、C++な人の通常の方針が知りたくて。 自分が見つけたリンクは、 Javaは　ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/normal/index.html その他は　ttp://gihyo.jp/dev/serial/01/geometry/0012 といった感じです。 が、上のレスに貼られたリンクに入ってみます。 253 名前：230 mailto:sage [2012/07/03(火) 13:12:28.17 ] voronoiで、先ず、ある点の一番近くの点と結ぶのは、全部やる方法もありますし、工夫する方法も分かります。 その次の、あるドロネー辺の２等分垂直線同士の交点座標を取得方法も分かります。 が、しかしドロネー辺が無数にあると、計算時にどれ活かすか難しくないですか？？？ 254 名前：230 mailto:sage [2012/07/03(火) 13:31:00.88 ] それと、ある点に対して出来上がるvoronoiが何角形かも不明だし、 関係している線分と関係してない線分とか、線分で領域が閉じてるか、 とか、簡単に分かるのかなぁ？ 実際の図を描けば分かっても、プログラムだと１次元的に見えますよねぇ。 255 名前：230 mailto:sage [2012/07/03(火) 13:41:48.29 ] 連投すみません（連投の最後）： ある点の一番近くの点と結ぶのは全部やる方法、じゃダメですよね。 余分に結ぶと余分に線分が出来て、余分に多角形化しちゃうし。 どうもvoronoiの認識が足りないので、そちらを勉強してみます。 もしくは、高度なポリゴンクラスライブラリを持っていれば簡単に解決なのか？＿？ チラ裏となってきたので、一旦消滅します。レスはずーっと読み続けますが。 256 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 14:16:40.53 ] まとめると、「自分で実装する気はないからライブラリ教えろや！」 257 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 14:21:50.90 ] ライブラリが存在しないケース ・アルゴリズムの再現自体が不可能 ・複雑なプログラムになり相応のコストがかかるため、無料提供が無いが有償提供ならある ・アルゴリズム自体の知名度や有用度が低いため手を付ける者が少なくライブラリ化してない ・あまりにも簡単で単純なアルゴリズムのため、わざわざライブラリにして提供するまでもない 258 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 14:24:57.60 ] ？ 259 名前：230 mailto:sage [2012/07/03(火) 14:26:39.02 ] どうも、いきなりボロノイを実装するのではなく、 ＞ボロノイ〜逐次添加法 ＞ボロノイ〜再帰二分法 といった手法が定石みたいでつね。 それらでググったら、多少ひっかかってきますたｗ ttp://suuri.ics.kagoshima-u.ac.jp/lectures/easywin/docs/voronoi/Voronoi.h ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/index.html ttp://i-health.u-aizu.ac.jp/CompuGeo/2011/exercises.html 理解して修正できるコンパクトなものにしたいでつ。 260 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 14:27:20.48 ] さっきから日本語サイトばかり 261 名前：230 mailto:sage [2012/07/03(火) 16:27:55.65 ] 英語サイトもみっけ： ttp://www.koders.com/c/fid17552685298283A6BFE8B1CBCC2D3E9A35C58C16.aspx ttp://www.leebyron.com/else/mesh/ ttp://www.codeforge.com/s/0/alghorothm-for-voronoi ttp://www.geocities.co.jp/SiliconValley-PaloAlto/4089/voronoi.html 262 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 16:48:17.86 ] おまえなんでここにメモってんの？ここにメモる必要ないだろ 263 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 16:56:47.24 ] おまえなんでここ監視して余計なこと言ってんの？ここで発言する必要ないだろ 264 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 17:44:41.21 ] >>261>>263 失せろゴミ 265 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 17:48:18.98 ] （笑） 266 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 20:49:04.54 ] 空間ってか直方体を8つごとに分けていって 8分木の形にしたデータ構造の,一部の葉だけが選択されていて,それらの葉の接続関係 を求めるってどうすればできますか？ 葉に対応する直方体の面同士が接していれば接続しているとしたいのですが 階層がちがうのの扱いがよくわかりません。。。 267 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:00:13.81 ] ？ 268 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:04:32.27 ] 点の絶対座標から、その点を含むノードのアドレスを出せるよう、ノードのアドレスを工夫する。 （ここで言うアドレスとは、root->node[0]->node[1]->node[4] における (0,1,4) のようなもの） で、選択されたノードの中心座標 (x,y,z) から (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz) （復号任意）を含むノードのアドレスを得る。 269 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:19:16.93 ] >>268 どうもです^o^ 270 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 22:08:59.67 ] ミスった。 > (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz) ここ普通に (x±dx, y, z) (x, y±dy, z) (x, y, z±dz) だ。 dx, dy, dz はまあ、直方体のサイズとかでも。 271 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 23:26:29.68 ] >>255 www.pi6.fernuni-hagen.de/publ/tr198.pdf 272 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 03:06:25.48 ] 質問させてください C++スレから誘導してもらいました スレチでしたら誘導頂けると幸いです。 O表記法についてなのですが、イマイチ理解できていません。 授業にて以下7つのルールを定義されたのですが 各々について具体的な数字の入った例をいただけませんでしょうか #数学の勉強が足りないのかもしれませんが、具体的な数字があれば理解できると認識しています。 #宿題ではないのですが、以降のテストで以下ルールを適用しながらアルゴリズムの証明を行う問題が出題される予定です。 1). if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n)) 2). if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)) then f(n) + g(n) ∈ O(h(n)) 3). an^k ∈ O(n^k) 4). n^k ∈ O(n^k+j) for any j 5). if f(n) = cg(n) then f(n) ∈ O(g(n)) 6). loga n ∈ O(logb n) O(logn) 7). loge n ∈ O(loge n) お手数ですがよろしくお願いします。 273 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 10:26:48.61 ] いやです 274 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 10:42:54.09 ] >>272 ggrks 275 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 11:57:07.67 ] 雑多な質問スレっていろいろあるのに 何故このスレに誘導されたのだろうか 276 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 12:12:31.31 ] >>272 ランダウの記号 - Wikipedia ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7 277 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 04:03:56.85 ] >>272 オーダー記号って普通は等号使ってn=O(n)とか書くんじゃないかな それはともかく数字があれば理解できるって神だな。 関数の極限の話だし。 278 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 07:19:45.35 ] ヒープソートでなぜ再帰？〜日本語版ウィキペディアの問題点と最強最速のヒープソート〜 www.dreamhope.net/soliloquies/HeapSort/ 279 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 08:54:36.87 ] >>278 この人頭悪いね >同じコンピュータ環境で、Linux GCC環境では2,500,000件程度のデータを取り扱いできるのに対し、 >Windows BCC環境ではその10分の１の258,000件程度が最大です。 >LinuxがWindowsよりも10倍性能が良いのか、GCCがBCCより10倍性能が良いのかはわかりませんが、 >この性能差には驚きました。 そりゃ int dat[DC+1]; //データ格納用配列 のようにスタックに巨大な配列を取ればそのうちスタックオーバーフローするって 更にスタックオーバーフローは都合の悪い事にエラーが出ずに結果だけおかしくなる事が多い ちゃんとソートされているのか結果を見たのかな(ヒープ4だけは見ているようだけど) Linuxはスタックが足りなくなると自動的に拡大してくれるので問題が出ない ヒープに取れば同じ事 速度が4倍〜13倍も違うのはよく分からない ちなみにEclipse CDT + gcc4.6.1でやってみたがbccやvcと速度的には大差なかった スケジューリングの問題かな？ 280 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 10:12:28.23 ] スタックオーバーフローは最近はSEGVで落ちるんじゃね？ ウィキペディアの記事も微妙だが、そのウェブページもいろいろと頭悪いという ことについては同意。 281 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 10:21:47.95 ] >>280 Linuxは拡張しきれないスタックを要求した時はSEGVで落ちるけど Windowsは黙って変な結果を出して終了するか、暴走するかどちらか 282 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 12:08:48.86 ] ランダウの記号って名前があったのか 知らなかった 283 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 12:51:41.81 ] Mac も > 黙って変な結果を出して終了するか、暴走するか 284 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 13:50:54.97 ] VCのデバッグならスタックオーバーフローを検出して止まるので リンカのオプションからスタックサイズを改めて指定しなおす事になる この時に一度ビルドをクリーンしないと単にリンクし直すだけでは スタックオーバーフローエラーは止まらないようだ 285 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 20:40:52.04 ] ＞そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。 ・・・ナゼ 286 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 21:20:43.48 ] 自己顕示欲の強そうな人だね 他の記事も読んだけど首を傾げすぎて首が疲れた データベースは毎回自分で実装した方がいいらしいよ 目から鱗だわ 287 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 16:46:26.64 ] 最適化を語るのにオプションを明示しないとか、 データ量を語るのにオプションを明示しないとか、 処理速度を語るのに環境を明示しないとか、 10〜20年くらい前から知識が更新されていないんじゃないだろうか。 288 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 16:47:09.23 ] >>285 批評に晒されたくないチキンハートなんでしょ。 289 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 19:20:15.32 ] 出回ってる書籍が古いものばかりだからね 図書館で借りようものなら１０年〜２０年昔の本だって当たり前のように陳列されてる 290 名前：デフォルトの名無しさん [2012/07/17(火) 20:23:27.35 ] �@区間スケジューリング問題＜＝ｐ　点カバー問題 �A独立集合問題＜＝ｐ　区間スケジューリング問題 この２つについて (i)Yes　(ii)No　(iii)「これが解ければP=NP問題が解決できるので不明」 のいずれかで答え、その簡単な説明も与えよ。 という問題の答えを教えて下さい 291 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 01:05:55.70 ] C/C++の宿題片付けます 158代目 toro.2ch.net/test/read.cgi/tech/1339338438/ 292 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 01:26:27.60 ] すっげえ宿題でるんだな 俺が通ってた大学での「データ構造とアルゴリズム」ってまんまの名前の授業あったけど 宿題に出たのがせいぜい一般的なソートアルゴリズムいくつかををjavascriptで書けとかそういうレベルだったよ 293 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 04:41:54.35 ] なんでjavascriptなの？なんかその大学に興味があるんだけど 今時は大学でjavascriptでアルゴリズム書かせるのか 294 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 10:28:38.16 ] schemeの代替 295 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:29:46.28 ] web限定用語で教育するってのはちょっとナンセンスかと 296 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:31:53.61 ] 「web限定用語」ってすごい表現だなw プログラミング言語を「用語」って言うのはどこのマヌケ業界だろう？ 297 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:39:08.99 ] web限定言語で教育するって凄い大学だな 298 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:41:14.74 ] 逆にCとかJavaみたいな一般のプログラマにとって中途半端に使えない、 実用的でない言語なんて教えたところで意味無いでしょ。 299 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:49:22.80 ] じゃあpythonでいいだろ 少なくともアルゴリズムの授業でjavascriptってのは学生がかわいそうだ 300 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:53:38.65 ] >>298 いや相手は情報系の学生だぞ？ CもJavaもダメな奴がどうやって情報科学を学ぶわけ 301 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:54:58.55 ] >>298 世界が狭すぎ あなたがどういうバックボーンなのか知りたいわ 302 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:02:34.74 ] 情報系っていうのはプログラマ養成施設じゃないよ。 専門学校か他の工学系と勘違いしてないか？ 303 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:15:03.55 ] 情報系でCもJavaも教えない大学があるのか？ それまともな大学じゃないだろ そんなカリキュラムが存在するならマジで教えて欲しい 聞いたこと無いから プログラマ養成機関じゃないからこそCで本質に切り込むんじゃないの 専門学校みたいなプログラマ養成機関こそがPHPとかJavascriptを教えるんでしょ まあそれはさておき、アルゴリズムの概念を教えるのにJavascriptを使う大学はおかしいよ絶対に それも否定する？ 304 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:18:38.42 ] まともな大学生ならCは自習で既に学んでるから大学ではいちいち教えない 305 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:27:09.76 ] アルゴリズムの本質は言語によって変わらない 306 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:31:27.01 ] 「アルゴリズムの本質は言語によって変わらない」 それはわかるけどさ、だからといって 「アルゴリズムの本質は言語によって変わらないからJavascriptで教えます」 はおかしいでしょう　普通の感覚じゃ考えられない 言語実装に関係のない本質を教えるんであれば、なおのこともっと汎用的な普遍的な言語でやるべきじゃない 307 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:34:34.41 ] そうかい 308 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:36:18.55 ] その感覚はわからなくもないが感覚じゃなく理屈で説明してくれ。 309 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:42:09.35 ] アルゴリズムの授業だからJavascriptなんじゃなくて 別の理由で決まったんだろ 310 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:44:52.14 ] 10年前とは違うからな。javascriptを取り巻く環境は随分改善した。 ブラウザ間の互換性であるとかデバッグ環境はすでに十分な領域に達している。 311 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 13:00:17.42 ] >>305 8-QueenをCOBOLで書くようにという宿題がでるらしいと聞いたら その授業は取らない。 312 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 13:32:43.00 ] そうかい 313 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:07:00.66 ] 8-Queenとアルゴリズム全般、COBOLとJavascriptじゃ違いすぎるな 314 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:36:01.76 ] いい加減スレ違い 315 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:41:23.22 ] そうかい 316 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:59:25.90 ] JavaScriptをウェブ専用とか思ってるバカがプログラマのわけないだろw 317 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 15:00:37.58 ] そうかい 318 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 17:11:07.05 ] ECMAScript は Web 専用じゃないけど Javascript は Web 専用とか、そういう揚げ足取りなのかもね。 319 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 17:44:37.90 ] 言語は手段でしかない 320 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 18:22:28.47 ] javascriptはクロージャを学ぶのに悪くない 321 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 18:57:27.05 ] >>319 このスレの住人が口にすると迫力あるな。 322 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 19:27:20.07 ] そうかい 323 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 20:51:20.96 ] VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。 324 名前：292 mailto:sage [2012/07/18(水) 20:56:44.84 ] 誰のＰＣにでも入ってて使えるプログラム言語だからという理由でjavascriptを指定してたよ 別にHTMLファイルにするとかじゃなくて アルゴリズムを再現したコードをメールに添付して送信するみたいな宿題だった ちなみに情報が専門の学科は無い大学だったのでそういうことに 325 名前：292 mailto:sage [2012/07/18(水) 21:04:23.79 ] ちなみな自分語りになるが 学科名的には電子情報工学科となってて情報系の授業を期待して入学したものの （ちゃんと調べずに願書出した俺が悪いのだが） 情報とは名ばかりで情報系の授業はほとんど開講されず 電子系、特に半導体系の授業ばかりしかなかった その大学わが母校はもう存在してないけどね 326 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 21:13:34.30 ] 本当ただの自分語りだな 327 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 21:21:22.30 ] 寂しい奴なんだろう。 328 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 23:16:38.10 ] >その大学わが母校はもう存在してないけどね 津波で流されたのね 329 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 01:35:32.86 ] つまり本格的な情報科学系の授業では無かったという事の証左だよな まあ非情報系の学生だったらブラウザで誰でも実行環境が整うからあえてJavascriptでやるっていう意味もわかる気がする 330 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 04:30:09.03 ] VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。 331 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 07:32:51.17 ] なんでこんな頭の悪いのがこのスレにいるんだ？ 332 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 09:04:49.51 ] 若者の 2ch 離れが進んでいるな 333 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:06:58.62 ] 2点が与えられたときその2点を結ぶ単純な経路（同じ頂点を通らない経路） が2つ以上存在するかを判定するアルゴリズムと計算量を述べよ。 深さ優先探索とかでしょうか？ 334 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:12:15.02 ] 宿題は宿題スレへ 335 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:36:47.50 ] 失礼しました 336 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 21:33:34.33 ] >>331 どっちのこと？ 337 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 21:44:47.18 ] おそらく自問自答だろう 338 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:42:44.97 ] 二分探索木の平均高さが　O(logN) の証明ってどういう風にやるんでしょうか？ アルゴリズムイントロダクションに書いてあるらしいのですが見当たりません。どのあたりでしょうか？ 339 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:53:14.03 ] >>338 2分探索の構造がわかれば少し考えればわかることだよ 340 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:56:17.57 ] >>338 木 T が平衡なら、そのまま height(N) = 1 + height(N/2) で O(logN)でしょ。分割統治法 341 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 17:29:31.19 ] 手元の本にありましたのでもういいです。 お騒がせしました 342 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 19:17:26.17 ] 宿題は宿題スレへ 343 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:01:26.56 ] 3つのくっついてる円にこれまたくっついて囲まれてる円の半径を 求めるアルゴリズムってどうすればいい？ 344 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:14:49.30 ] ３つの円はどういうくっつき方？ ３つの円の半径はばらばら？ ○○○ 　 ○ 　○○ 345 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:24:10.91 ] 宿題は宿題スレへ blogs.yahoo.co.jp/oka_yadokary/29892416.html 346 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:24:54.06 ] 343は外接・内接という言葉も知らなそうな雰囲気で困る。 347 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:28:43.57 ] >>344 くっつき方は下の方 円の半径はバラバラ 348 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:47:28.98 ] ２本（３本）の双曲線の交点が共通接円の中心か 349 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:31:42.96 ] 互いに接する３つの円　に外接する円の半径の求め方？ 350 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:32:39.99 ] ３つの円すべてと接する外接円は無理じゃね 351 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:36:32.23 ] デカルトの円定理 aozoragakuen.sakura.ne.jp/taiwa/taiwaNch03/enteiri/node2.html 352 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:36:40.22 ] にしてもスレチ。 353 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:55:54.21 ] アルゴリズムでも何でもないなコレ 354 名前：デフォルトの名無しさん mailto:sage [2012/07/22(日) 10:15:52.04 ] プリムのアルゴリズムのヒープ版って (E+V) log (E) ≒ Elog(E)ってあるけど　(E+E) log (E) ≒Elog(E) が正しいと思う 挿入か削除のどっちも Elog(E) でしょ　最悪全枝を一回ずつ挿入と削除する必要があるんだから 355 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 05:54:32.42 ] 王様は王様でも頭が三つある王様はな〜んだ 356 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 06:04:38.43 ] 三頭王 357 名前：デフォルトの名無しさん [2012/07/25(水) 17:58:22.97 ] キングギドラ 358 名前： ◆VD2btbRbPs [2012/07/25(水) 21:41:00.81 ] 大学の課題で二分探索木の高さを調べる実験とその結果を調べる実験が出たのですが どうしたらいいですか 359 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 21:54:46.35 ] そのようにプログラムを作って結果を表示すればいいのでは？ 360 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 16:24:57.70 ] 宿題は宿題スレへ 361 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 21:29:42.06 ] ほんとこういう質問するガキがムカつく どうすればいいですか？って何だよ そんな曖昧な質問で答えられると思ってんのかカスが どこの底辺大学だか知らないが学費が無駄 362 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 22:10:01.46 ] >>358 擬似乱数から最大の低周波成分を除くアルゴリズムを考案する。最大の低周波成分を除く操作を 繰り返すごとに２分探索木の高さが次第に平坦化することを実験・観察する。 363 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 22:23:02.61 ] 教授に不正してる奴がいたと報告しとく 364 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 22:36:52.61 ] 乱数が独立なら、Huffman木を作るといいよ！ 365 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 00:41:56.00 ] ハッシュのチェイン法の同一エントリのチェインの長さに制限があるやつはなんていうんだっけ？ 366 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 00:47:53.60 ] 特にない 367 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 01:03:18.89 ] 半開きハッシュと名付けた 368 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 01:38:15.37 ] こないだから宿題貼り付ける奴がちらほらいるが そのどれも分からなかった俺は才能が無さ過ぎた 369 名前：デフォルトの名無しさん [2012/07/27(金) 08:00:24.64 ] >>361 黙れバカw 空気読んで答えやがれ 370 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 08:13:45.67 ] ↑お前が馬鹿 371 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 09:41:12.30 ] 馬鹿には無理 372 名前：デフォルトの名無しさん [2012/07/27(金) 10:18:48.93 ] >>370 >>371 バカはお前ら お前らのパッパラパーなアルゴリズムでさっさと俺様を笑わせやがれ 373 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 11:49:22.94 ] 馬鹿には無理 374 名前：デフォルトの名無しさん [2012/07/27(金) 12:10:13.43 ] >>373 お前には無理と言うことかw 375 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 19:08:10.29 ] >>374 お前が馬鹿 376 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 19:54:35.27 ] 　　　　　＿＿＿＿ 　　　 ／∵∴∵∴＼ 　　 /∵∴∵∴∵∴＼ 　　/∵∴∴,（・）（・）∴| 　　|∵∵／　　 ○　＼| 　　|∵ /　　三　|　三　|　　／￣￣￣￣￣ 　　|∵ |　　　＿_|＿_ 　|　＜　うるせー馬鹿！ 　　 ＼|　　　＼＿/　／　　＼＿＿＿＿＿ 　 　 　 ＼＿＿＿_／ 377 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 20:23:22.78 ] どーでもいい。 378 名前：記憶喪失した男 忍法帖【Lv=9,xxxP】 [2012/07/28(土) 07:59:18.69 BE:3079593959-2BP(3)] 入力された内容は次のとおりです。 ■件名： 日本のロボットトレーディングサイト「カブロボ」について ■ご意見・ご感想： ロボットトレーディング、あるいはアルゴリズム取引トレーダーについて、少しは知識を得ました。その現状について知ったところ、やはり憂慮すべき事態だったため、意見申し上げます。 「カブロボ」というサイトを知りました。そのサイトについての意見です。政府として、このようなサイトを支援していただきたく思います。 アルゴリズム取引トレーダーとしては、株だけでなく、債券、為替取引にも当然対応するべきであります。 また、株、債券、為替取引は、現実に存在する二百か国以上の国や地域を網羅する必要があります。 それが賢いアルゴリズム取引トレーダーのするべきプログラムであり、 たった三百銘柄の仮想取引では、日本の投資家を育てるのに不適切だと思われます。海外銘柄を扱わないアルゴリズム取引トレーダーに魅力を感じません。 扱う銘柄を、全世界の株、債券、為替をすべて網羅する上級者向けのカブロボを立ち上げることを希望いたします。 379 名前：デフォルトの名無しさん [2012/07/28(土) 10:23:42.25 ] >>375 バカw 380 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 11:39:47.47 ] >>324 その学科何年か前は違う名前じゃなかった？ 381 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 14:26:03.68 ] >>378 当事者が遊びで作ってるものに政府が金なんか出す訳ないだろ 382 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 21:18:50.51 ] ぷよぷよのAIを作っているんですが窒息死します どうすればいいですか 383 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 22:12:51.40 ] ぷよぷよで強いAIってどうすんの？ toro.2ch.net/test/read.cgi/tech/1336825232/ 384 名前：デフォルトの名無しさん mailto:sage [2012/07/29(日) 10:05:48.14 ] >>383 こんなスレあったんですか ありです 385 名前：デフォルトの名無しさん [2012/07/31(火) 08:19:02.42 ] ﾌﾟｯ 386 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 09:24:11.53 ] ﾖｯ 387 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 09:52:41.53 ] ﾌﾟｯ 388 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 21:35:14.84 ] ﾖｯ 389 名前： 【大吉】 mailto:sage [2012/08/01(水) 08:41:13.81 ] O(N) 390 名前：デフォルトの名無しさん mailto:sage [2012/08/02(木) 10:09:55.05 ] ｵﾅﾗﾌﾟｰ 391 名前：デフォルトの名無しさん mailto:sage [2012/08/02(木) 20:47:04.14 ] ガベージ・イン／ガベージ・アウト： 善き人々が悪しきプログラムに手を染める時 practical-scheme.net/trans/gigo-1997-03-j.html 392 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 20:45:11.38 ] ハッシュだけどチェイン法＞開番地法なんだよね？でなければ溢れを気にする必要はないからね ハッシュのチェインの長さに制限があるやつの削除、参照の計算量の解析ってどっかにない？ 393 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 20:56:13.76 ] 「チェイン法＞開番地法」 この意味は何？ 394 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 21:49:02.14 ] 参照、追加、削除の計算量です 395 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 22:12:44.83 ] A>B　はAのほうが良い、ってことで 396 名前：デフォルトの名無しさん mailto:sage [2012/08/04(土) 18:35:46.31 ] >>392 > 長さに制限があるやつ って何よ。 ハッシュ値が衝突した要素を格納するためのコンテナの計算量でいいんじゃないの？ 397 名前：デフォルトの名無しさん mailto:sage [2012/08/05(日) 17:00:36.26 ] ハッシュ法って、均したらまともな実装ならO(1)にならにゃいかんのでは？ 398 名前：1/4 mailto:sage [2012/08/06(月) 18:50:54.98 ] アルゴリズム考えてもらえませんか。 恥ずかしながら、一応自分の考えたのも載せます。 ただ、絶対もっとスマートな解法があると思うのでよろしくお願いします。 ちなみに言語は PHP です（＞＜） 【問題】 整数が二つ入った配列がいくつかあります。(配列の配列) これは何らかの数列の範囲を表しています。 最初の数字が範囲の開始位置、二つ目の数字が範囲の長さ。 例えばこんな具合です。 $data = array( array( 0, 3 ), array( 2, 1 ), array( 4, 2 ), array( 4, 1 ), array( 8, 2 ), array( 10, 5 ), array( 10, 6 ) ); ------------- 長いので続きます -------------- 399 名前：2/4 mailto:sage [2012/08/06(月) 18:52:06.84 ] ---続き--- 抽象的に書くとこうなりますか。 $data = array( array( a1, b1 ), array( a2, b2 ), --- 中略 --- array( an, bn ), ); a1からanは昇順にソート済みです。 同じ値の場合もあります。 b1からbnは1以上で不定です。 $data は、ある数列の 0番目から3スパン、2番目から1スパン、4番目から2スパン...という意味です。 ただし、この $data は範囲の重複の可能性があります。 実現したいアルゴリズムは、この $data が示す範囲を重複のない形で再定義することです。 400 名前：3/4 mailto:sage [2012/08/06(月) 18:53:22.57 ] ---続き--- 例えばそれを実装した関数を linearize とした場合、 $newData = linearize( $data ); の結果は、 array( array( 0, 3 ), array( 4, 2 ), array( 8, 8 ) ); でなくてはなりません。 401 名前：4/4 mailto:sage [2012/08/06(月) 18:56:51.88 ] ------続き------ こちらが自分が考えた関数です function linearizedRange( $data ) { $strage = array(); foreach( $data as $datum ) { if( isset( $strage[$datum[0]] ) && $strage[$datum[0]] >= $datum[1] ) { continue; } $strage[$datum[0]] = $datum[1]; } foreach( $strage as $i => $v ) { $strage[$i] = $v + $i; } $len = count( $strage ); if( $len > 1 ) { $last = null; foreach( $strage as $i => $v ) { if( null === $last ) { $last = $i; continue; } 402 名前：5/4 mailto:sage [2012/08/06(月) 18:58:01.19 ] ------続き------ すいません、予定より1レス多くなりました。 関数の続きです。これで最後です。 if( $strage[$last] >= $i ) { if( $strage[$last] < $v ) { $strage[$last] = $v; } unset( $strage[$i] ); } else { $last = $i; } } } $data = array(); foreach( $strage as $i => $v ) { $data[] = array( $i, $v - $i ); } return $data; } 403 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:04:16.15 ] $data = array( array( 0, 3 ), array( 2, 1 ), array( 4, 2 ), array( 4, 1 ), array( 8, 2 ), array( 10, 5 ), array( 10, 6 ) ); ↓ array( array( 0, 3 ), array( 4, 2 ), array( 8, 8 ) ); 404 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:09:14.78 ] 理屈がよくわからん 405 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:14:28.31 ] できた！ function linearizedRange( $data ) { $n = -1; $result = array(); foreach( $data as $datum ) { if ($dataum[0] > $n) { $result[] = $dataum; $n = $dataum[0] + $dataum[1]; } } return $result; } 406 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:15:48.26 ] でたらめを教える悪い例 407 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:20:34.70 ] DPでいけそう Viterbトレリスを作って一発 408 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:23:59.40 ] ならばこうか！ function linearizedRange( $data ) { $n = -1; $t = null; $result = array(); foreach( $data as $datum ) { if ($dataum[0] > $n) { if ($t !== null) { $t[1] = $dataum[0] - $t[0]; $result[] = $t; } $t = $dataum; $n = $dataum[0] + $dataum[1]; } } $p = array_pop($data); $t[1] = $p[0] + $p[1] - $t[0]; $result[] = $t; return $result; } 409 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:25:08.27 ] 動かないコードなど無意味 410 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:28:20.86 ] うおりゃ！スペルミス直したぞ！ function linearizedRange( $data ) { $n = -1; $m = 0; $t = null; $result = array(); foreach( $data as $datum ) { if ($datum[0] > $n) { if ($t !== null) { $t[1] = $datum[0] - $t[0]; $result[] = $t; } $t = $datum; $n = $datum[0] + $datum[1]; } if ($datum[0]+$datum[1]>$m) { $m = $datum[0] +$datum[1]; } } } $t[1] = $m - $t[0]; $result[] = $t; return $result; } 411 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:30:11.37 ] 動かないぞ 412 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:31:20.11 ] 括弧が一つ多かった！直したぞ！ function linearizedRange( $data ) { $n = -1; $m = 0; $t = null; $result = array(); foreach( $data as $datum ) { if ($datum[0] > $n) { if ($t !== null) { $t[1] = $datum[0] - $t[0]; $result[] = $t; } $t = $datum; $n = $datum[0] + $datum[1]; } if ($datum[0] + $datum[1] > $m) { $m = $datum[0] +$datum[1]; } } $t[1] = $m - $t[0]; $result[] = $t; return $result; } 413 名前：5/4 mailto:sage [2012/08/06(月) 22:54:42.75 ] >>412 さん、さっそくありがとうございますｍ（＿＿）ｍ 凄く短いコードなので感動しました(^-^) が、どこか不具合がある模様です(-_-;) 例題の $data = array( array( 0, 3 ), array( 2, 1 ), array( 4, 5 ), array( 5, 1 ), array( 10, 2 ), array( 12, 3 ), array( 12, 4 ) ); の答えが 414 名前：398 mailto:sage [2012/08/06(月) 22:55:22.08 ] Array ( [0] => Array ( [0] => 0 [1] => 4 ) [1] => Array ( [0] => 4 [1] => 6 ) [2] => Array ( [0] => 10 [1] => 6 ) ) になってしまいました(´・ω・`) 415 名前：398 mailto:sage [2012/08/06(月) 22:56:52.95 ] Array ( [0] => Array ( [0] => 0 [1] => 4 ) [1] => Array ( [0] => 4 [1] => 6 ) [2] => Array ( [0] => 10 [1] => 6 ) ) になってしまいました(´・ω・`) 416 名前：398 mailto:sage [2012/08/06(月) 23:11:31.65 ] 別のデータを用いて模式図を書くとこうなります ( 0, 3 ) … データ1 ( 2, 1 ) … データ2 ( 4, 1 ) … データ3 ( 5, 1 ) … データ4 01234567....　数列 --------------------- ***___________データ1 __*___________データ2 ____*_________データ3 _____*________データ4 ***_**________求める答え(V) V1 = (0,3) V2 = (4,2) こうしてみるとOR演算ですね 417 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 23:49:58.47 ] #PHPのことはわからんのに、適当に投げてみる #どうせどっかでエラーが出る function linearizedRange( $data ) { $max = $min = $data[0][0]; $result = array(); foreach( $data as $datum ) {#---- if ( $datum[0] > $max ) {#====ギャップ感知 $result[] = array( $min, $max - $min ); $min = $datum[0]; }#==== if ( $datum[0] + $datum[1] > $max ) {#==== $max = $datum[0] + $datum[1]; }#==== }#----foreach $result[] = array( $min, $max - $min ); return $result; } 418 名前：398 mailto:sage [2012/08/07(火) 00:47:35.30 ] >>417 m(__)m もう、ほんとうに感謝感謝感謝です。 ありがとうございます。 しかもそのまんまコピペでOKでした。 >>417 さん以外の皆様もありがとうございました。 どこか別の場所で恩返しできるといいです。 419 名前：398 mailto:sage [2012/08/07(火) 00:53:50.40 ] あぁ、そうかぁ、 $result に格納するタイミングは datum[0] > $max のときとループを抜けた最後だけでいいわけか・・・ すごくなるほど。 420 名前：398 mailto:sage [2012/08/07(火) 01:03:25.12 ] あと、元のデータが ( 開始位置, 幅 ) だったので それをループの中でいったん終了位置を $max として求めているのですね。 ということは、元のデータを ( 開始位置, 終了位置 ) として同じコストで作成できるとするならば、 それを採択した方がより良いアルゴリズムになるのですね。 元データの取得方法を再検討してみます。m(__)m 421 名前：デフォルトの名無しさん mailto:sage [2012/08/07(火) 02:43:10.51 ] 宿題は宿題スレって約束忘れちゃったのかおまえら 422 名前：デフォルトの名無しさん mailto:sage [2012/08/09(木) 18:31:48.66 ] ヒープソート、書き換わってるなw 423 名前：デフォルトの名無しさん mailto:sage [2012/08/10(金) 07:22:34.38 ] ホントだ 424 名前：デフォルトの名無しさん [2012/08/14(火) 13:57:01.43 ] あらゆる状況や環境を無視して質問するんだけど STXとETXで囲まれたバイト列を取得 というとき、 <STX>unko<STX>chinko<ETX> というならびになっちゃってるときは chinko オンリーが正解か unko<STX>chinko が正解か、どっちがセオリーかなぁ 425 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:05:59.01 ] 最長一致にするか最短一致にするかは セオリーというより定義の問題だ 426 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:06:25.67 ] 後者。 /*foo/*bar*/ だってコメントアウトされるのは foo/*bar でしょう。 427 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:20:48.63 ] >>426 そっちの方が作るのも楽なんだけどさ なんでわざわざ囲ってんのか という根源的なとこを思うと chinkoオンリーが正解な気がするんだよな 428 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:07:33.07 ] >>427 プロトコル定義次第。 ・<stx>で始まり、<etx>で終わるまで全てがデータ(unko<stx>chinko) ・<stx>で始まり、<etx>以外の制御コードを含まない区間がデータ(chinko) ・<stx>で始まり、<etx>以外の制御コードを無視した区間がデータ(unkochinko) ・<stx>で始まり、<etx>で終わるまでがデータだからネストを認め、内側から有効とする(chinko)(unkoはペンディング) ・<stx>で始まり、<etx>以外の制御コードが出現したらその後のデータは無効(データなし) ちょっと考えただけでもこれだけバリエーションが作れる。 要は、エラーに対する強度の問題。 429 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:10:09.72 ] >>427 <stx>が出現したら出力インデックスを初期化するだけだから、作る手間は殆ど変わらないだろ。 430 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:32:23.36 ] >>428 STXとETXに挟まれたもの という定義なんか作った理由って 開始と終了を検知したいということなんだから、 STXまたはETXの見逃しを恐れるべきですね ということは、STXのあとETXが来ないでSTXきちゃったのは ETXを読み飛ばしちゃったと思った方がいいんだよな、きっと つまり、とりあえずchinkoのみを採用すべきとすべきかなぁ 431 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 16:03:01.12 ] >>430 再入可能かどうかが分からないとなんとも言えないだろ 432 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 16:13:36.40 ] そうか。 再入可能かどうかがキモになるのか。 433 名前：デフォルトの名無しさん [2012/08/20(月) 12:52:16.26 ] AVL木の回転って適当すぎない？ 別に回転じゃないじゃん。 ただ引き上げてるだけで、入れ替えたりしてる時点で 回転ではないだろ。 434 名前：デフォルトの名無しさん mailto:sage [2012/08/20(月) 17:32:15.47 ] 死ねゴミ共がw 435 名前：デフォルトの名無しさん mailto:sage [2012/08/20(月) 20:27:00.20 ] >>433 subtreeのrotationじゃなくて、nodeのrotationなんで。 「入れ替え」くらいが適切な訳だったという感じでしょうかぁ↓ 436 名前：デフォルトの名無しさん [2012/08/21(火) 09:13:13.56 ] バカばっかw 437 名前：デフォルトの名無しさん mailto:sage [2012/08/21(火) 09:44:31.25 ] >>435 いいね！ 438 名前：デフォルトの名無しさん [2012/08/22(水) 00:06:18.81 ] お知恵をお貸しください。 xy平面上にランダムに配置された複数個の点があったとき、 それらを線で結ぶとして、結んだ結果が網の目のように見える ようなアルゴリズムってありますでしょうか。 完全に見た目だけが目的なので自分でも要件が絞り込めて いないのですが、網の目のように見えるための要件は おそらく次のようなものでしょう。 ・全ての点が2個以上の他の点と結ばれている ・線同士が交差しない ・近い点同士が結ばれていて、遠い点同士は結ばれない ・線で囲まれた図形は三角形ないし四角形を構成し、五角形以上にはならない よろしくお願いいたします。 439 名前：デフォルトの名無しさん mailto:sage [2012/08/22(水) 00:11:11.92 ] ドロネー図でggr 440 名前：デフォルトの名無しさん mailto:sage [2012/08/22(水) 23:00:26.94 ] >439 ありがとうございます。 ttp://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay_3958.html ↑ここを参考にして実装を進めようと思うのですが、この方法だと、 一度完成したドロネー図から点を削除して線を引きなおすには、 再度（その点を除いた点群を入力として）ゼロから作図しなおす しか無いのでしょうか？ 441 名前：デフォルトの名無しさん [2012/08/30(木) 18:01:25.35 ] Ｂ木がよく分かりません。誰か簡単に説明してくれませんか？ 442 名前：デフォルトの名無しさん [2012/08/30(木) 18:23:37.01 ] >>441 B木は多分岐の平衡木。 ノードは最大M個のサブノードとM-1個の値を保持する。 ノードの値がM-1個を超えるとノードの分割が行われる。 443 名前：デフォルトの名無しさん mailto:sage [2012/08/31(金) 00:00:52.49 ] 2分平衡木の存在意義がゼロに 444 名前：デフォルトの名無しさん mailto:sage [2012/08/31(金) 20:16:21.92 ] ゼロどころではない。もはやマイナスだ。 445 名前：441 [2012/08/31(金) 20:35:10.27 ] >442 ありがとうございます。 プログラム文がきわめて長いので、使いこなせません…。 446 名前：デフォルトの名無しさん [2012/09/01(土) 03:33:46.99 ] >>445 プログラム使うだけだったら実装の細部まで理解する必要ないっしょ。 Addメソッドを呼んだらが値を追加できてGetメソッドを呼んだら値を 取得できるというようなことさえわかってればじゅうぶんっしょ。 447 名前：445 [2012/09/01(土) 23:51:43.84 ] >446 そうですかねえ。確かに文が400行以上あるので(コメントも含めて)、理解は無理っぽいですねえ。 二度目ですが、シェルソートが挿入ソートより速くなる理由を誰か教えて頂けませんか？ 448 名前：デフォルトの名無しさん mailto:sage [2012/09/02(日) 00:27:54.32 ] ランダムに並んだデータを挿入していくと 比較回数の期待値が挿入１回に対しソート済みデータの半分になるけど 先頭に近そうなデータから挿入していけば 比較は後ろの方の１，２回だけとなることが期待できるってことでは 449 名前：デフォルトの名無しさん mailto:sage [2012/09/02(日) 00:28:30.47 ] １，２回だけ→ほとんどが１，２回くらい 450 名前：デフォルトの名無しさん [2012/09/02(日) 00:43:09.47 ] >>447 語尾が腹立つから教えてあげない 451 名前：447 [2012/09/02(日) 01:05:24.33 ] >448-449 ありがとうございます。けれどやっぱり納得できないというか…。最終ソートの前で既に結構比較・交換にコストがかかってる気がして。 >450 何でですかあ？そんな事言わないで下さいよお。 452 名前：デフォルトの名無しさん [2012/09/02(日) 06:09:50.86 ] >>451 あんまりふざけたこといってるとぶちぎれるゾ（ゝω・）vｷｬﾋﾟ 453 名前：451 mailto:sage [2012/09/02(日) 23:53:28.52 ] >452 怒ったらダメですう。貴方に足りないのはＣａですよお。(特に深い意味はない) 454 名前：デフォルトの名無しさん [2012/09/03(月) 05:10:27.93 ] つまんね 455 名前：デフォルトの名無しさん mailto:sage [2012/09/03(月) 06:29:18.19 ] 例えば挿入ソートだと比較回数は期待値でだいたいこんな感じだろう 右から+の箇所で比較していって*に収まるイメージ(平均なので真ん中) -----------------------------------*+++++++++++++++++++++++++++++++++++ でもシェルソートのごとく予め4つのグループに分けると比較回数がガクッと減らせる -----------------------------------*---+---+---+---+---+---+---+---+--- さらに前段階で13のグループに分ければ比較回数が格段に減る -----------------------------------*------------+------------+--------- いくら前段階というプロセス数が増えるとはいえ、比較や交換回数が小さいわりに 好位置へデータを移動させておくことができるから、全体としてみれば 効率が良くなるんだろう 456 名前：453 [2012/09/06(木) 16:51:56.41 ] >455 しかし何故そうなるのかが分かりません。 今ヒープソートを勉強してますが、これはさらに分かりません。 457 名前：デフォルトの名無しさん [2012/09/06(木) 18:32:25.30 ] >>456 挿入ソートでは要素数が多くなると遠くまでテケテケと要素を1個ずつ移動せにゃならんから 超大変。シェルソートでは要素数が増えても離れた要素を交換することで遠くへ移動するときの コストが減らせちゃうわけ。ゆえに要素数が増えるほどシェルソートが挿入ソートより 速くなるはずよ。 ヒープソートは2分木作っちゃうやつだろ、わかるだろ。 458 名前：デフォルトの名無しさん [2012/09/08(土) 19:22:54.12 ] 基数ソートって分かりやすいしすばらしいですね。 459 名前：デフォルトの名無しさん [2012/09/10(月) 20:53:39.37 ] アルゴリズムとデータ構造の質問なんですけど、ここでいいですか？ 　 　１．2次元以上で、無限に広がるユークリッド空間があります。 　 　２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。 　 　３．ここより先では、砂粒を追加しません。 　 　４．空間上の任意の座標を選びます。 　 　５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色？ 安定じゃなくてもokです。 こういう状況で、良い検索アルゴリズムってありませんか？ 460 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:04:04.91 ] > 安定じゃなくてもok って、等距離に赤も黒もあった場合は、返す値は赤でも黒でも良いと言いたいのか？ 461 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:07:23.58 ] 1ビットごとに次元を変えていくやり方なら地図サービスとかで使われている 462 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:08:15.28 ] >>461 kwsk 463 名前：デフォルトの名無しさん [2012/09/10(月) 21:25:53.08 ] >>460 あ、その通りです。安定ソートっぽい意味でした。すみません。 等距離に、または同じ座標に、赤と黒があるときは、 答えは赤でも黒でも良い、検索のたびに答えが変わっても良い、 ってことです。 あと、例えば等距離に黒が複数ある場合、答えは「黒」と返すだけでokです。 アルゴリズムがどの座標の「黒」を指したのか、 それはアルゴリズム利用者に知らせる必要はないです。 >>461 1ビットごとに？？ すみません、ちょっと想像がつきません…。 どんな仕組みなんでしょうか？ 464 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 22:52:42.26 ] >>463 １ビットずつ混ぜるんだよ。分かれよ。 x座標とy座標をそれぞれ32ビット整数値で表現するとして x = { x31, x30, ... x1, x0 } y = { y31, y30, ... y1, y0 } だとするだろ。x31が上位ビットでx0が下位ビットな。 それを混ぜると、 z = { y31, x31, y30, x30, ..., y1, x1, y0, x0 } という64ビット整数値になるわけだ。 地図系サービスはだいたいこんなのが多い。 465 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 22:58:35.49 ] >>464 で？　その64ビット整数値をどうする気だよ？ 466 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 23:01:13.24 ] 砂粒座標データはどう整理された状況で提供されるのかが気になる あるいは事前にデータを整えていいのか否かも 467 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 23:06:48.73 ] >>465 ソートしておけば、upper_bound lower_boundである程度漠然とした領域が拾えるだろ。 全座標の重さが平等でないと使えないやり方だけどな。 そういう想定を置けないなら諦めてR-Tree書けだな。 468 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 23:54:10.30 ] >>459 最近傍探索 ja.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2 2を一度だけ行い4を繰り返すのなら 3で同色の砂に囲まれている砂を取り除く方が効率が良いです。 469 名前：デフォルトの名無しさん mailto:sage [2012/09/11(火) 01:21:02.23 ] 皆様ご回答ありがとうございます。 >>467 x,yそれぞれ2bitで図を書いてみたら、なんとなく解りました。 座標は実数を想定していたのですが（説明不足ですみません）、 固定小数点数に近似すれば使えるんでしょうか。ありがとうございます。 あと、R-Treeはちょっと気になってたので、Wikipediaあたりから読んでみます。 >>468 おっしゃるとおり１〜２は1回だけ実行、4以降は繰り返し実行です。 最近傍探索は今日は寝るので明日読みます、ごめんなさい…。 >>459 をもう1回整理して書きます。 　 　１．2次元以上で、無限に広がるユークリッド空間があります。 　 　２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。 　 　　 　砂粒は実数の座標を持ちます。 　 　　 　砂粒に大きさは無く、また同じ座標に複数の砂粒が重なることもあります。 　 　３．ここより先では、砂粒を追加しません。 　 　　　　１〜３は1回しか実行しません。 　 　　 　振りかけた数、各色ごとの数、n回目に振りかけた砂粒の情報（座標や色）はいつでもO(1)で調べることができます。 　 　　 　ここまでは、砂粒のコピーをとってソートしたり、時間の掛かる計算もokです。 　 　　　　１〜３で与えられたり生成した情報は、もし必要無ければこの段階までに破棄できます。 　 　４．空間上の任意の座標を選びます。 　 　５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色か返します。 　 　　　　ただし、等距離または同一座標のときは赤黒どちらを返しても良く、 　 　　　　また、後で同一の検索をしたとき答えが変わっても良いです。 　 　　　　赤黒どちらかを返すだけで、座標を返す必要はありません。 　 　６．４〜５を繰り返します。 なんかめんどくさそうですよね…。自分でも考えてみます。 470 名前：デフォルトの名無しさん [2012/09/24(月) 19:34:54.06 ] ｢Ｃによるアルゴリズムとデータ構造｣(昭晃堂)って本いいですか？大学で教科書として使われてたんですが。 471 名前：デフォルトの名無しさん mailto:sage [2012/09/24(月) 19:47:47.61 ] その本今も持ってる どっかにしまってあるわ もう何年も前だから覚えてない 472 名前：デフォルトの名無しさん mailto:sage [2012/09/27(木) 23:34:39.11 ] 平面上に複数の点があり、各点を中心とした円で塗り潰すとした場合に、 『塗られていない領域を最小』にするために、最適な相互に接する円の半径を 求めるアルゴリズムってありますか？ ====以下、挫折した案==== 近傍の2点間の中点を、仮りの半径の最小値として求めて順次他の点 との中点を求めいって半径の最小値を更新して、これを初期値とする。 この時点では、最小値を更新したことで、他と接することが無くなった 円が生じるので、この半径を再度増加させれば．．． とか思ったのですが、局所的な部分しか見えていないし、そもそも 上で求めた最小値よりも、更に小さな半径とした方が適した場合も ある様にも思います。 473 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:06:32.99 ] >>472 こういうこと？ １．それぞれの円の半径はバラバラである ２．円と円が重なってはならない 474 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:12:29.39 ] >>472 > 『塗られていない領域を最小』 つまり一辺の長さが l の正三角形の各頂点が与えられた場合、それぞれ半径 (l, 0, 0) の円が欲しいわけだな？ 475 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:20:03.90 ] 凸計画問題として解いてしまうとか 476 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:24:20.85 ] >>472 >>473 が条件であるとして 外周部にあたる点の半径を出来る限り大きくするのが有効に思える 他の点との距離の最小値が最大となる点で最大の円を描くようにすればよさげ 477 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:47:33.75 ] あれか？水着の女の子の写真をうまい具合に水着部分だけ隠してあたかも裸に見えるっていうアレを作ろうとしてるのか？ 478 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 00:50:54.89 ] 全然違うだろ・・・ 479 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 01:41:17.58 ] 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ - YouTube www.youtube.com/watch?v=Q4gTV4r0zRs&feature=youtu.be で、肝心のアルゴリズムってなんなのよ 480 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 01:43:49.54 ] 点の集合をどこから持ってくるのかな とおもってたら >477 481 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 01:48:30.30 ] >>479 お姉さんがやってるのは総当りじゃないかな こんなん C言語なら俺に聞け（入門編）Part 107 toro.2ch.net/test/read.cgi/tech/1347156509/187 187 名前：186[sage] 投稿日：2012/09/14(金) 22:16:01.89 >>186 に一番簡単な袋小路の判定を追加してさらに倍速 codepad.org/k9Dw2VA5 482 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 01:49:43.41 ] >>481 お、そっちのスレで盛り上がってたのか。�dクス 483 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 01:57:35.54 ] >479 その高速アルゴリズムが正しいかどうか 検証するのに6年掛かるんですね判ります 484 名前：デフォルトの名無しさん mailto:sage [2012/09/28(金) 02:12:14.36 ] 9x9までは正しい解が出せたとしても10x10でも果たして正しい解が出せたかどうかは 485 名前：デフォルトの名無しさん [2012/10/04(木) 21:23:52.08 ] 任意の符号なし32bit値 Aに対して 下の関係を成り立たせる 32bit値を求めれるもの？ A = x + BitReverse(x) BitReverseはビット逆順演算 31b ⇔ 0b 30b ⇔ 1b 　　 ・・・・ 1b ⇔ 1b 0b ⇔ 31b 486 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:30:03.12 ] よく意味が分からない 487 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:32:58.97 ] xを0x00000000〜0xFFFFFFFFまでのAのリストを作ればいいんじゃね 488 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:43:33.99 ] 具体例で考えればいい A=1のときのxを求める A=2のときのxを求める 489 名前：デフォルトの名無しさん [2012/10/04(木) 21:44:05.80 ] >>486 分かりづらかったかも、すみません。 ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、 ｘの値を求めるには？ ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど） 490 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:45:22.64 ] 難しそうなアルゴリズムだ 491 名前：デフォルトの名無しさん [2012/10/04(木) 21:59:08.08 ] 連投すみませんです。自分の説明に絶望した・・。 unsigned int A； unsigned int x； // ？ A = x + reverse_bits(x); if (A == 0x3476edc0) { // この条件を満たすｘを求めるには・・？任意のAについてどうやって計算すればいいか・・・ } // 1101:0010 -> 0100:1011 ビット順序反転する関数 unsigned int reverse_bits(unsigned int v){ 　v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 　v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 　v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 　v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 　v = ( v >> 16 ) | ( v << 16); 　return v; } 492 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:14:13.06 ] >>485 無理だな。 A と X は 2^32 通り、X + Rev(X) も 2^32 通り。 ただし、X + Rev(X) はオーバーフローする分、実際の数は少ない。 よって、任意の A に対して X を求めることは無理。 493 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:15:25.15 ] 訂正。 ○ X + Rev(X) は 2^32 通り以下。 494 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:15:49.33 ] Javaならオーバーフローしない！ 495 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:16:38.89 ] 下位ビットが立ってたら上位ビットも立つ形になるんだし和で非対称になったとしても最下位ビットが 496 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:17:39.08 ] 更に訂正。 ○ X + Rev(X) は 2^31 通り以下。 X + Rev(X) = Rev(X) + Rev(Rev(X)) だから。 497 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:22:18.63 ] >>492 オーバーフロー分は切り捨てて良いのですが・・・無理でしょうか？ A = (unsigned int) ( x + reverse_bits(x) ); １元１次方程式に見えるので解があるような、 いやでも無いような・・・悶々としてます。 498 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:22:59.96 ] A = 0xFFFF FFFF みたいな形が一番、式を満たす X の数多いようだな。 499 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:23:25.14 ] 496の対称性があるから無理じゃね 500 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:24:25.45 ] さっさと487のいうように一覧にして全数字を網羅できるかチェックすれば早いのよ！（それじゃアルゴリズムじゃありませんが＞＜） 501 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:27:35.73 ] >>497 492,496を読んで、それでも一般には無理だと理解できない脳が怖い。 502 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:31:08.08 ] 496の言う対称性が分かればできる数字がほぼ半分しかないってことがわかる 503 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:33:39.78 ] A=X+Rev(X)なら Rev(X)=Yとすると A=Y+Rev(Y)=X+Rev(X)が成り立つ つまり同じ解を出すXが２通りあるってこと 504 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:38:19.54 ] >>503 うーん　そうですね。 ｘとAが１対多の関係がある時点でダメなのか・・・ 皆さんありがとうです 505 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 00:07:59.21 ] >>503 それは間違い 506 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 00:58:37.93 ] 簡単のため、2ビットの場合で考えてみる。 A = 00のときX = 00 A = 01のとき解なし A = 10のときX = 11 A = 11のときX = 01,10 解があれば解を返し、なければ解なしと出力するアルゴリズムって総当たり探索になるのかな？ それとも代数的に解けるのだろうか？ 507 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:01:28.13 ] オーバーフロー切り捨てを考慮するとなるとかなり複雑になりそう 508 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:08:57.90 ] A=000 X=000 A=001 X=011,110 A=010 X=101 A=011 X= A=100 X=010 A=101 X=001,100 A=110 X=111 A=111 X= 509 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:11:02.77 ] で、これ求めて何に使うわけ？ 510 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:14:16.72 ] 0ビット目だけは下位ビットからの繰り上がりで1に出来ないことから Aの0ビット目をみて 511 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:15:22.75 ] >>509 FFT関係だと思います 512 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:17:16.96 ] >>510 11は解があるよ 513 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:21:21.45 ] A=0000 X=0000 A=0001 X= A=0010 X=1001 A=0011 X= A=0100 X= A=0101 X=0111,1110 A=0110 X=0010,0100 A=0111 X= A=1000 X=1011,1101 A=1001 X=0001,1000 A=1010 X= A=1011 X= A=1100 X=0110 A=1101 X= A=1110 X=1111 A=1111 X=0011,1100,0101,1010 514 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:22:28.99 ] フーリエ変換か 515 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:27:14.69 ] nビット整数だとnが奇数でも偶数でも全ビットが1のものを除けば対称になってる 516 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:28:20.19 ] その対称の端のXはオールビットが0か1 517 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:31:36.52 ] >>513 これシンプルな計算で解の有無が判定できるのかね・・・不規則に見えるが 518 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:45:27.52 ] ^ をべき乗の記号として 2^((n+1)/2) 通りチェックする方法なら分かる 519 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:49:10.90 ] A=1111 X=0011,1100,0101,1010,0110,1001,0111,1000,0001,1110,1101,0010,1011,0100,1111,0000 520 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:54:10.07 ] >>519 反転じゃなくて逆順だよ？ 521 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:00:24.13 ] 489 デフォルトの名無しさん [] 2012/10/04(木) 21:44:05.80 ID: Be:     >>486     分かりづらかったかも、すみません。     ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、     ｘの値を求めるには？     ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど） 522 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:16:49.17 ] 質問者は反転と逆転の違いが 523 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:19:19.69 ] 例出すのも下手 わざとやってるだろ 524 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 12:41:22.64 ] 解いてみた 諸事情により 31 bit まで #module #defcfunc bitreverse int num, int bit, local rev repeat bit rev=(rev<<1)|((num>>cnt)&1) loop return rev #deffunc solve array result, int num, int bit, local result_num, local u_, local l, local m, local n dim result n=1<<((bit+1)/2) m=(1<<bit)-1 repeat n l=cnt u_=(num-l)&(n-1) x=l|bitreverse(u_, bit) if ((x+bitreverse(x, bit))&m)=num { result.result_num=x result_num++ } loop return result_num #global solve result, $ff, 8 repeat stat mes strf("%x", result.cnt) loop 525 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:18:10.35 ] HSP? 526 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:36:02.53 ] アルゴリズム記述用の抽象言語みたいなのってないのかな 527 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:48:32.32 ] 32bit全探索する気か 528 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:50:40.72 ] 8bitくらいまで>>513のように羅列していって何らかの傾向や法則性が無いか確かめられたらいいんだけどな 529 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 16:50:50.02 ] しょうがねぇなぁ〜 codepad.org/Kkm8uPyR 530 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 18:11:37.70 ] >>526 片言Algol知らんのか? 531 名前：デフォルトの名無しさん [2012/10/05(金) 20:26:48.63 ] "片言Algol"でググっても何なのか出てこないんですけどー"片言Algol"って何ですかー？ 532 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 20:54:44.01 ] 片言のAlgol 533 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 21:15:37.12 ] pidgin ALGOLも知らんとは！(怒 534 名前：デフォルトの名無しさん [2012/10/08(月) 00:42:46.73 ] pidgin ・・・　混成語 他の言語と混ぜて使うってこと？よけい混乱しないか？ 535 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 07:19:41.75 ] >>534 ある言語の、外人 植民地人向けカタコトOKバージョン。 満州国を作ったあたりでpidgin日本語を作ってた。 語尾を「〜アル」で統一とか。 廃れてしまったがモノはちゃんと完成し、教育もされたようだ。 マンガの中国人が「〜アルよ」と言うのはその名残らしい。 536 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 08:39:37.95 ] ゼンジー北京ってまだ生きてんの？ 537 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 19:17:57.21 ] codepad.org/dZ6OuG1e ghc f "101010" --2進 fx "12abcd"--16進 虫食い算を解く要領で１桁ずつ特定しています 538 名前：537 mailto:sage [2012/10/09(火) 00:34:47.45 ] codepad.org/ETbL5UUF 32bitでエラーに成るのを修正 A=B+(reverse B) rx B --> A fx A --> B rx "123456" -->"7c609e" fx "7c609e" -->["7a3440","7a2c40","723450","722c50","6a3448","6a2c48","623458","622c58","5a3444 ","5a2c44","523454","522c54","4a344c","4a2c4c","42345c","422c5c","3a3442","3a2c4 2","323452","322c52","2a344a","2a2c4a","22345a","222c5a","1a3446","1a2c46","1234 56","122c56","0a344e","0a2c4e","02345e","022c5e"] 539 名前：デフォルトの名無しさん [2012/10/14(日) 18:17:20.75 ] データ構造とアルゴリズムと設計パターンは、 ソフトウェア開発に必須の技術 540 名前：デフォルトの名無しさん [2012/10/14(日) 19:30:55.13 ] B木のようなプログラム文も、書けるようにならなければなりませんか？ 541 名前：デフォルトの名無しさん mailto:sage [2012/10/14(日) 20:07:16.63 ] プログラム文という言葉は初めて見たかも 542 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 00:01:49.62 ] ヒント翻訳ソフト 543 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 01:18:47.48 ] >>542 翻訳ソフト使うと何が解決するの？ 544 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 17:34:20.97 ] というかダイクストラ法とクラスカル法の違いって何？ 両方とも最小スパニング木を求める方法なのにお互い関係ないものなの？ ダイクストラで検索かけようとしても候補にクラスカルって出てこないし 逆もない。 クラスカルはプリムとセットで議論になるケースが多いけど。 誰か教えて。 545 名前：デフォルトの名無しさん mailto:sage [2012/10/18(木) 08:39:59.95 ] 定義が違うし出力も違う。 そして、「同じものを求める二つのアルゴリズムなら関係があるはず」と言うのは思い込み。 546 名前：デフォルトの名無しさん [2012/10/23(火) 21:57:07.56 ] クラスカル、プリム・・・重み付きで、その重みが最小となる全域木を求めるAG ダイクストラ・・・その経路までの最短キョリを求めるAG クラスカルは全てのノードを繋ぐ ダイクストラは最短ノードを選択 547 名前：デフォルトの名無しさん mailto:sage [2012/10/23(火) 22:46:30.76 ] 線形探索も立派なアルゴリズム。 548 名前：デフォルトの名無しさん [2012/10/29(月) 21:42:14.08 ] AGってなんなん？ 549 名前：デフォルトの名無しさん mailto:sage [2012/10/29(月) 21:46:33.53 ] GAなら知ってる 550 名前：デフォルトの名無しさん mailto:sage [2012/10/29(月) 23:57:14.35 ] GKなら乙 551 名前：デフォルトの名無しさん [2012/11/22(木) 18:39:52.58 ] 線分で出来てるポリゴンで、 線分がクロスしているときにも正しい面積を出す方法はありますか？ イメージ的には、魚と魚のシッポがある場合に、魚の面積を得る方法。 552 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 19:37:05.37 ] 単純に2分の1になるんじゃないの？ 553 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 20:07:37.68 ] ポリゴンの共通部分体積を計算しなきゃな。 554 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 21:22:43.29 ] クロスポイントで分割するしかないんじゃないの 555 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 23:20:34.69 ] 地震キター 556 名前：551 [2012/11/26(月) 14:06:33.84 ] あらかじめクロスポイントが分かってないとできない、 座標を適当に入れるだけだと魚かシッポか判断できない、 ってことですね？ 557 名前：デフォルトの名無しさん mailto:sage [2012/11/26(月) 14:23:38.70 ] 塗りつぶすんならそれ用のアルゴリズムもあるけどね 558 名前：551 mailto:sage [2012/11/26(月) 14:52:07.91 ] 塗りつぶさずに処理したいです。 559 名前：デフォルトの名無しさん mailto:sage [2012/11/26(月) 21:09:10.39 ] 半直線伸ばして線分と交差する回数の偶奇で判定できるかもしれない 560 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 11:40:37.00 ] 交点の座標を求めるのを厭わないなら、 交点も頂点の一つ（線分2本分なので二つ）に含めてしまえば、 普通に多角形の面積として求められるんじゃない？ 561 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 12:09:09.66 ] 交点がちょうど頂点上だったり、線分が重複していたり、 まあ頑張ってくれ 562 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:04:01.15 ] そこら辺の場合分けは地獄だな。 563 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:15:10.54 ] 面積求めるのにそんな例外事項は考慮する必要ない。 原点と、線分の両端点とで張る三角形の面積を、足したり引いたりするだけでしょ。 頂点どうしや頂点と交点が非常に接近してても問題ないし、 線分の全部や一部が重複してても問題ない。 564 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:23:49.89 ] あぁ、すまん、これは「交点が求まったら」という前提な。 交点を求めることそのものは、工夫がいるね。 565 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 16:54:57.32 ] 二回ループ 566 名前：デフォルトの名無しさん [2012/12/05(水) 12:33:15.73 ] 今あるn個の数値データの中から例えば１〜８個の数字を選んでｘ〜yの値にある組み合わせを作る というアルゴリズムを考えているのですが、こういうアルゴリズムは何法とかで検索すればいいんでしょうか? 取りあえず総合で聞いてみたのですが、スレ違いなら誘導していただければ幸いです。 567 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 12:33:45.43 ] あう・・・ age失礼しました。 568 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 12:42:43.84 ] combination (あるいは permutation) 569 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 13:24:52.20 ] >>568 ありがとうございます。 キーワードで調べてみます。 570 名前：デフォルトの名無しさん [2012/12/21(金) 10:45:15.05 ] ここで質問するべき事かわからないのですが、 適当な板もスレも見つからなかったのでお願いします。 Adobe illustratorでjavascriptを使って文字列の検索置換を行った時に 変更部分を目視で確認したいので置換した文字部分のみ色を変えたいのです。 正規表現を使って文字列置換するのは簡単なんですが、色を変えようとするとうまい方法が思いつきません。 100以上のパターンを検索置換しないといけません。 どんな考え方で作成したら良いのでしょうか？ 571 名前：デフォルトの名無しさん mailto:sage [2012/12/21(金) 10:53:39.57 ] toro.2ch.net/test/read.cgi/tech/1355011916/ 572 名前：デフォルトの名無しさん [2012/12/21(金) 10:59:58.44 ] >>570は誘導されたので移動します。 573 名前：デフォルトの名無しさん [2012/12/21(金) 13:05:37.93 ] 領海 574 名前：デフォルトの名無しさん [2012/12/24(月) 11:36:38.88 ] バカは死ね 575 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:10:58.26 ] ある整数の番号の範囲(例えば100〜999)があります。 要求によって番号を割り当てると、その番号は使用できなくなり 返却された番号はまた使えるようになります。 割り当て、返却を繰り返すと番号が断片化しますが その場合でも安定した速度で未使用番号を検索できるアルゴリズムはないでしょうか? 576 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:15:15.80 ] 未使用番号の連結リスト FATがやってるやつ 577 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:17:11.78 ] 膨大な数になったらどうするんです？ 578 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:40:50.83 ] 膨大さと使えるメモリと許される時間による 579 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:44:32.37 ] メモリやディスクブロックの割り当てに使われているような手法が応用できそう。 エクステントをツリーで管理するとか。 580 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:44:41.80 ] 例にしろ、100〜999って言っておいて、後から膨大とか後出しすぎ 581 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 23:15:24.37 ] そこでblock符号ですよ！ 圧縮にも使える便利なデータ構造でもある 582 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 23:44:43.26 ] 連続領域が必要ってわけでもなさそうだし、連結リストの何が不満なの？ 583 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 00:07:37.60 ] >>576でFA 584 名前： ◆QZaw55cn4c mailto:sage [2012/12/28(金) 01:09:30.09 ] >>576 FAT は未使用クラスタを連結リストにしていません。未使用マーク(0hとか）にするだけです。 585 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 08:49:08.74 ] 普通にリングバッファでキュー作ればいいだろ 何を難しく考えてるんだ 586 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 09:00:25.38 ] >>576 FATって同じところに何度もアクセスしてディスク壊しやすいアルゴリズムだっけ？ 587 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 11:03:29.79 ] FATへの書き込みは大量に発生するね。 588 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 11:46:18.52 ] HDDなら同じとこにいくらアクセスしても壊れんだろ FDDだとFATのところがすりきれたりするけど 589 名前：デフォルトの名無しさん [2012/12/28(金) 13:23:44.02 ] 安物のUSBフラッシュがデフォFATなのは、 適当に壊れて寿命と思って交換して欲しいから。 590 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 13:41:02.59 ] テーブル２つもってるし バッドセクタ機構もあるですしおすし 591 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 22:33:22.79 ] >>589 mjd? 592 名前：デフォルトの名無しさん mailto:sage [2012/12/29(土) 00:34:52.59 ] FATは実装が容易で特許料のような余計なコストがかからず いろんな機器の組み込みに使いやすいから 593 名前：デフォルトの名無しさん mailto:sage [2012/12/29(土) 00:55:36.80 ] 特許使用料については微妙 ドイツでMSがモトローラに勝訴したとか ロングファイルネームだけに対応するようにすれば大丈夫そうだけど 互換性に問題が出てくる 594 名前：デフォルトの名無しさん [2013/01/02(水) 23:38:19.70 ] NHK教育を見て40886倍賢くマターリ hayabusa2.2ch.net/test/read.cgi/liveetv/1357124586/ 595 名前：デフォルトの名無しさん [2013/01/04(金) 00:59:43.77 ] ヒープ作成の最大時間計算量の公式�婆*2^k=(n-1)*2^(h+1)+2をどなたか証明できますでしょうか？ hは木の高さ、nをヒープの大きさとします。 nの場合からn-1の場合を引けばできるんですがみたいなんですが、、、 596 名前：デフォルトの名無しさん mailto:sage [2013/01/04(金) 02:21:04.43 ] 最悪のケースで考えれば 597 名前：デフォルトの名無しさん [2013/01/09(水) 17:41:36.67 ] あと20分 岡野原大輔氏セミナー「ウェーブレット木の世界」 (番組ID:lv120540885) ttp://live.nicovideo.jp/watch/lv120540885 【会場のご案内】 2013/01/09(水) 開場:17:57 開演:18:00 〜概略〜 機械学習・情報圧縮・高速文字列処理、それらを生かした起業などで 注目の若手、岡野原大輔氏（PFI取締役副社長）のセミナーを配信します。 ビッグデータ時代のシンボル的な方の講演ですが、そこは統数研チャンネル、ガチの 技術的・学術的内容、しかも最新でわかる人には胸ドキの内容で行きます。 「ウェーブレット木」は「ウェーブレット変換」と名前は似てますが、あまり関係はありません。 文字列、時系列、二次元グリッド、グラフなど様々な種類のデータに対し、これまで実現が難しかった 多くの操作を効率的にサポートしつつ、必要な作業領域量は 元のデータ表現よりと同じか小さいという、万能のデータ構造です。 この講演では、基礎的な仕組みから応用例，最新の研究成果まで解説します。 参考書：岡野原大輔「高速文字列解析の世界」（岩波書店） 598 名前：デフォルトの名無しさん [2013/01/10(木) 20:45:56.19 ] Ｆ欄大学のアルゴリズムの問題 授業もろくに出てないから全くわからん 問題の意味すら理解できないんだが 「egg]を文字コードに直して101でなんか計算すればいいの？ eggを m=101としてハッシュ　→　解答　9 eeggを m=101としてハッシュ　→　解答　9 eeggを m=128としてハッシュ　→　解答103 アホな質問ですが、ほんとに困ってます 599 名前：デフォルトの名無しさん mailto:sage [2013/01/10(木) 21:01:33.23 ] ここじゃ宿題の相手はしてないよ 宿題スレに行けば親切なふりした誰かが学習機会をスポイルしてくれるかもね 600 名前：デフォルトの名無しさん mailto:sage [2013/01/10(木) 21:39:57.13 ] こっちで答えた方がお得 detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13100051018 601 名前：桃白白 mailto:sage [2013/01/10(木) 21:48:28.83 ] >>598 これでいんじゃね。 int hash(char* c, int m) { 　　int r = 0; 　　while (*c) 　　{ 　　　　r = r * 256 + *c; 　　　　c++; 　　} 　　return r % m; } 602 名前：デフォルトの名無しさん mailto:sage [2013/01/10(木) 21:54:36.12 ] それ静的解析かけてみろよ 603 名前：デフォルトの名無しさん [2013/01/10(木) 22:27:51.91 ] >>601 256ってどこからきたんですか？ この馬鹿にもっと詳しく教えて下さい 604 名前：デフォルトの名無しさん mailto:sage [2013/01/11(金) 00:20:29.77 ] >>601 *c >= 0x80 のとき、 > r = r * 256 + *c; はどうなるのか 605 名前：デフォルトの名無しさん [2013/01/19(土) 10:43:24.87 ] あげ 606 名前：デフォルトの名無しさん mailto:sage [2013/01/19(土) 13:28:45.73 ] you tubeで「新唐人テレビ」を検索して見てください。 新唐人テレビは中国の民主化を望む中国人自身によるテレビ局で、海外に拠点をおき、 中国共産党の圧力に屈する情けない日本のマスゴミよりもよっぽどまともなテレビ局です。 日本では中国共産党の圧力により報道出来ないニュースが沢山取り上げられています。 新唐人テレビのような勇気ある報道機関を広める事で、中共の圧力に屈し、 真実を伝えない日本のマスゴミのへなちょこぶりを浮き彫りにする事にもなります。 新唐人テレビを日本や在日中国人の間に広めて、 中共が日本に戦争をしかけてくる前に中共を内部崩壊させましょう！ 607 名前：デフォルトの名無しさん mailto:sage [2013/01/19(土) 13:43:23.76 ] 直リン貼るとまずいことでもある？ www.youtube.com/user/NTDJapanese www.ntdtv.jp/ ja.wikipedia.org/wiki/%E6%96%B0%E5%94%90%E4%BA%BA%E9%9B%BB%E8%A6%96%E5%8F%B0 608 名前：デフォルトの名無しさん mailto:sage [2013/01/19(土) 14:11:52.60 ] 法輪功かよ。 要はカルトじゃねーか。 反政府カルトを「よっぽどまとも」とかいう奴の頭のほうがマスゴミより1000倍ゴミだわ。 609 名前：デフォルトの名無しさん mailto:sage [2013/01/22(火) 18:31:54.62 ] 近交確認、リスト化て難しいな 610 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 20:56:41.94 ] リスト内の要素をグループ化するアルゴリズムを考えてるんだけど、 単純にソートアルゴリズムを使うよりも少ない計算量でできる？ [入力] 少なくとも大小の比較ができる要素がランダムに並んだリスト [出力] 同値な要素が必ず隣同士にあるリスト（入力と同じ要素数で、同じ要素を持つ） 出力のリストは上記の条件に合えば、どのような要素の並びでも構わない。 <例> 　入力 = [3, 5, 2, 3, 5, 2, 5, 2, 1, 5] 　出力例1 = [3, 3, 5, 5, 5, 5, 2, 2, 2, 1] 　出力例2 = [5, 5, 5, 5, 1, 3, 3, 2, 2, 2] もちろんソートアルゴリズムを使えば O(n log n) でできるんだけど、 ソートより条件が緩いから、もっと早くできるかな、と。 611 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 21:04:25.13 ] まとまってさえいれば、順番はどうなってもいいってことね 一旦ハッシュテーブルに突っ込んでから また取り出せばいいんじゃない？ 612 名前：610 mailto:sage [2013/02/02(土) 21:33:02.28 ] >>611 この条件しかない入力リストの要素から上手くハッシュ値が計算できたら、 テーブルへの挿入も取り出しもそれぞれ O(n) でできるから、 たしかに全体の計算量も O(n) でできると思う。 ただ、俺がプログラムすると利点を台無しにしてしまいそうで怖い。 上手いハッシュ値の計算は要素のタイプによって全然違うだろうし。 ヘボ計算で変な値だとテーブルに使うメモリ量がバカでかくなりそうだし。 今のところ候補第１号ということで、 上手くハッシュ値を計算できるか考えてみるよ。 理想は、クイックソートみたいに入力と同じサイズのリストしか必要ない、 というアルゴリズムなんだけどね。 これでソート以外のアルゴリズムを考えたが、O(n^2) のものしか思いつかない。 613 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 21:41:20.33 ] 比較する値の範囲が小さければ バケツソートすればいいよ 614 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 21:42:47.87 ] と思ったが、バケツソートとハッシュテーブルは大して差が無いか 615 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 21:54:04.64 ] 実際扱う入力値の配列は長さいくつ？ 何回実行する？ 616 名前：610 mailto:sage [2013/02/02(土) 21:59:44.83 ] もしかしたら誤解されているかもしれないけど、 入力リストの条件は「少なくとも大小の比較ができる要素を持つ」事しかないからね。 整数値とも浮動小数点値とも限らないよ。 （データのメモリアドレス値が取れるかどうかも、言語によるし） 比較する値の範囲、つまり何種類の要素があるかという情報は、 それこそハッシュテーブルを使うかして調べないと分からないからね。 >>615 ごめん、本当に実際に解決したかった問題はソートで解決した。 （その問題に限り、ソートを使うと、抱えていた他の問題も同時に解決できたから） 今は単に頭の体操で遊んでるだけ。 入力値の配列は長さと実行回数によってはソートより計算量は低くなる？ 617 名前：デフォルトの名無しさん mailto:sage [2013/02/02(土) 22:31:12.24 ] クイックソートより効率を求めるならO(n)しか道は無いしなあ ハッシュテーブルより効率よくするのは難しい気がする 618 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 01:42:19.05 ] >>610 あんまり良く判らないが 同じ値が複数ある数値をPivotにしてQuickSortのアルゴリズムで 振り分けたら必ず同値は隣に並ぶんじゃね？ 同値があるものを探すのに手間かかるけどね 619 名前：610 mailto:sage [2013/02/03(日) 14:47:22.77 ] >>618 いや、だから、「ソートアルゴリズムを使えば O(n log n) でできる」と >>610 に書いたんだが。 あと、結果のリストから同値があるものを探すのは今回は必要ないです。 あくまで目的（出力）は同値な要素が必ず隣同士にあるリスト。 >>617 たしかに O(n log n) よりもひとつ速いとなると O(n) しかないね。 ハッシュの方は試しに、要素の型を int に限定して、 std::unordered_set<int> を使ってやってみた。 残りのテンプレート引数はデフォルトで。 単純に、配列の要素を順に unordered_set に insert してから、 イテレータで順に取り出して元の配列に代入した。 配列の要素数は 10000000 個で、rand () % 3000 の値を入れた。 コンパイラは g++ (tdm64-1) 4.7.1 で、最適化オプションは O3。 qsort 関数は1秒で終わったが、ハッシュの方は15秒かかった。 話にならんかった。 やっぱ楽しないで、自分でハッシュ関数やアロケータを作って テンプレート引数に入れるべきか・・・ 俺の直感では単純なソートよりも条件は緩いはずなのに、 ソートと同程度のソートではないアルゴリズムが思いつかないのは意外だ。 620 名前：610 mailto:sage [2013/02/03(日) 14:54:47.84 ] >>619 > qsort 関数は1秒で終わったが、ハッシュの方は15秒かかった。 もしかしてテーブルサイズの拡張に時間を食っているのではと思い、 std::unordered_set<int> のコンストラクタに配列の要素数を渡したところ、 3.5秒に短縮された。 まぁ、それでも qsort より 3倍以上かかってるから意味は無いが。 621 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 15:55:52.48 ] ソートより条件厳しくないか？ 622 名前：610 mailto:sage [2013/02/03(日) 16:13:27.69 ] >>621 どの辺り？ 623 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 16:27:15.88 ] >>622 んー、ソートは大小比較だけが唯一の条件じゃん？ でも、>>610 って、移動位置も条件になってね？ 624 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 17:36:06.87 ] ハッシュがかなりぶつかってないのかなあ デフォルトのハッシュってどんなもんなんだろ 625 名前：610 mailto:sage [2013/02/03(日) 17:54:08.19 ] >>623 位置移動って、どういうこと？ ソートだって移動処理を伴うと思うが、そういうことではない？ 同値な要素が隣同士にあれば、どのような順番でもいいけど。 ソートは小さい方から順に並べないといけなくない？ 626 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:05:42.28 ] >>625 順番かんけいないの？ であれば、個数をカウントするだけでいいな 多分O(n)で行ける ってか、順番あってもカウントで行けるな 627 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:06:50.81 ] あっ、そうすると結局ハッシュか 628 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:07:56.28 ] >>625 ま、俺の勘違いっぽいので忘れて下さい すまんです 629 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:36:21.33 ] >>619 618なんだが、QuickSortを使うのではなくそのアルゴリズムを使うって話 QuickSortのアルゴリズムのキモの部分は、Pivotを決めてそれより大きいか小さいかでPivotの左右に振り分ける それを改良して、Pivotを同値がある数値にし、Compareを＝のみ真にして、真なら隣とスワップとする 同値が複数ある場合に備えて、1つスワップしたら、そのスワップする位置が内に1つずつズレていく そのPivotを同値のある物にしなければならないから検索が必要になるってこと 要素に入っている数値全てに対して行なってもいいけど総当りになるから検索したほうがいいかなってこと 例えば、3, 5, 2, 3, 5, 2, 5, 2, 1なら 同値のある5を右端とスワップして、そのプログラムに通すと 3, 2, 3, 2, 1, 5, 5, 5ってなる さらに3, 2, 3, 2, 1の部分を抜き出して左端に3を持っていきプログラムに通すと 2, 2, 1, 3, 3ってなる、2の場合も同じ 最終的に、1, 2, 2, 3, 3, 5, 5, 5ってなる、ソートされている状態だけど 3から始めたら、1, 2, 2, 5, 5, 5, 3, 3ってなる QuickSortのアルゴリズム部分を改良したら行けるんじゃないか？って話 630 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:37:24.80 ] 要素のサイズが大きいとハッシュテーブルの方が有利になったりしないかな あと、ハッシュテーブルのメモリ確保部分は工夫した方が良さそう 631 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:59:07.38 ] 検索なしでもいけるかも フローを書くと １）要素の最初の数値を左端に持っていきPivotとする ２）先頭から順番にPivotと比較して、＝ならPivotの隣とスワップする ３）Pivot位置をそのスワップしたものに移動する ４）要素全て調べたらPivot位置を１つ左にズラして、１）に戻る こんな感じかな 632 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:06:26.24 ] 連投すまん 単純に考えて最大O(n/2)で済むように思う 詳しい人あってる？ あ、書き忘れてた Pivot位置が２番目に来たらループ抜ける 633 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:12:36.63 ] ああ違うわ O(n^2)だわ… ソートしたほうが早いな… 634 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:16:41.44 ] これでよくね？ ideone.com/XdtCMM 635 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:18:28.48 ] バケツソートは既出だっつーの！ 636 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:30:12.09 ] ソートと違って、保存先へのポインタが必要だから、バケツより速くするのは無理な気がするぞ。 637 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:31:16.34 ] バケツソートでなく ・データの1個目と同じデータの数を求め、配列（）に保存 ・その過程で検索したデータも削除して元データスリム化　（不要？） ・データエンドまで繰り返し ・あとは求めたデータと数の配列から順に書き起こして終わり データの移動をせず、答えを改めて記述する点がキモ 638 名前：610 mailto:sage [2013/02/03(日) 19:35:05.13 ] >>629 >>631-633 じつは俺も左に集めていく方法で速いのがないか色々試してた。 最初に提案されてからハッシュテーブルの実装をしばらく渋ってたのはそのせい。 でも、どう考えても O(n^2) のしかできなかった。 まぁ、久しぶりに脳をフル稼働した気分だし、 自分的には失敗しても得るものはあった。 ところで、ソートより速いハッシュテーブルでの実装が現実的に可能か謎だ。 データを木構造で持ってたら、要素ひとつの挿入に O(log n) かかって、 それが要素数分必要だから、結局 O(n log n) になる。 これより速くするなら木構造ではなく配列で持つ必要があるけど、 要素の型やグループ数などに汎用性を持たせようとすると、メモリ量が見積もれんな・・・ 639 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:35:16.19 ] あぁ データエンドまででないな 重複をパスしてかつ求めた数の総量＝元データ数になったら終わり 640 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:36:45.82 ] >>637 >>634 641 名前：610 mailto:sage [2013/02/03(日) 19:40:49.33 ] >>634 どういう意味かもう少し説明しほしいです。 ググってみたけど、今回のことにどう関係するのかよく分からなかった。 642 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:46:10.70 ] >>641 どの数字がいくつあったか統計を取るということ。 643 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:47:44.20 ] >>641 ハッシュでバケットを C++ 実装してるだけだよ map 使ってるから、厳密にはハッシュじゃないけど ideone.com/XdtCMM 見たんだよね？ 644 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:55:38.84 ] mapだとO(n log n)になってしまうぞい 645 名前：610 mailto:sage [2013/02/03(日) 20:06:53.31 ] >>643 > 見たんだよね？ いや、ideone.com/XdtCMM でググっても何も出なくて、 ideone.com でググったら、どうもコード投稿サービスみたいな感じだから、 そこで XdtCMM を調べれば良いのかと思って [search] ボタンを探したが無くて、 諦めた。 >>634 の方法で時間を計ったら、qsort より 1.5 倍遅かった。 俺は >>619 で set（unordered_multiset）を使ってやったが、map の方が速かったのか。 あと今更すまん、>>619 は unordered_set って言ったけど unordered_multiset の間違い。 646 名前：610 mailto:sage [2013/02/03(日) 20:16:14.46 ] >>613 map を inordered_map に換えてみたら、qsort より6倍以上速くなった！ あとは、要素の型にどうやって汎用性を持たせるかだ。 qsort は void* の要素と型のサイズを引数に取る汎用関数なんで。 qsort みたいに要素１個につき1バイトずつ while でコピーする方法でやっても、 なお qsort より速くできるか・・・やってみるわ。 647 名前：610 mailto:sage [2013/02/03(日) 20:17:25.42 ] >>646 ごめん、アンカーミスった >>643 ね 648 名前：610 mailto:sage [2013/02/03(日) 20:18:56.60 ] >>640 連投すまん map を unordered_map に換えてみたら、です ちょっと興奮を冷ますわ 649 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:30:18.30 ] >>644 それはわかってるけど、考え方の具体例を示しただけだから STL なんだからコンテナ変えるだけでhash_map (標準ではないかな)でもなんでも試せるじゃん？ >>648 おめ！ 君の努力と探求心の賜物だね 650 名前：610 mailto:sage [2013/02/03(日) 20:31:59.19 ] void* 使った汎用化は面倒なんで、関数テンプレートにしたわ。 >>611 正直ハッシュは本当にできるか疑ってたが、できてしまったな。 ごめんね。 しかし set と違って map クソ速いな。 どこで差が出るのかちょっと興味出てきた。 651 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:45:47.82 ] unordered_multisetよりunordered_multimapが速いとかかなり衝撃的 何が違うんだ・・・ 652 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:52:21.18 ] >>651 コード晒した方が回答付きやすいぞ コンテナに問題があるかもしれないが、使い方に問題がある場合が圧倒的だよ 653 名前：610 mailto:sage [2013/02/03(日) 21:02:28.84 ] >>651 unordered_multiset と unordered_map の比較ね。 たぶん、multiset に挿入するのと map に挿入するのは同じだと思うんだ。 同じハッシュ関数や比較関数、アロケータを使ってるから。 違うのは、set に対して multi の機能を加えている部分ではないかと。 今ちょっと別のことやっててソースをまだ見てないから 間違ってるかもしれんが、multiset に「同じ値」を挿入すると、 そのタイミングで「同値要素格納用メモリ」がそのツリーノードに 確保されるのではないか。 というのも、コンストラクタでハッシュテーブルの スロットの最低数は指定できるが、マルチ特有の設定項目がない。 あと、俺が >>619 でやったのは、ハッシュテーブルから取り出す値の数も、 最初の要素数と同じだ。 でも、>>634 のはヒストグラムだから、取り出す処理は 理論上はグループ数だけ。 （別の言い方をすればツリーのノードはグループ数だけ） 要素数に対してグループ数が少ないほど、こちらの方が速い。 >>626 の意味が今更分かったw あとは、自分で unordered_multiset らのソースを眺めてみるよ。 みんな今までありがと。 たいへん勉強になったよ。 654 名前：610 mailto:sage [2013/02/03(日) 21:13:13.45 ] 俺、すげーバカだった。 ヒストグラム法じゃダメじゃん。 例えば要素の型が、 struct Himawari { 　int value; 　int id; }; で、value でしか比較しない場合、グループ化後、 同じグループの要素の id が全て同じになってしまう。 要素がint型とかfloat型とか、そういう単純な値ならいいけど。 655 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 21:46:02.02 ] >>654 実はそのケースもあると思ってた でも、ちょびっと工夫するだけで結構楽にできると思うよ 656 名前：610 mailto:sage [2013/02/03(日) 22:03:30.43 ] じゃあ、ちょびっと熟考してみる。 657 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 22:30:08.32 ] バケツソートで数を数えるのではなく テーブルに突っ込んでいけばいいのだが ハッシュ＝値そのものなハッシュテーブルと同じなのよねやってる事は 658 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:22:01.97 ] 要素数100万の配列をc++のstd::sortでソートすると 10秒ぐらいかかっちゃうんだけどこれって異常に遅いよね・・・ ちなみに要素の型はpair< long long, long long >なんだけど、 なにが問題なのか誰か分かる？ 659 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:26:09.16 ] コピー発生してる？ 660 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:35:04.67 ] 比較関数が遅いとか。 661 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:45:11.08 ] うーむむ・・ためしにint配列でやったら２秒ぐらいだった というか、蟻本の巨大ナップサック(p148)をそのまま写して、 最大のn=40でやってみたら10秒以上かかったけどいいのかなー どうやらソートに時間かかってんなーって感じなのよ こればっかりは自分の処理系？だけじゃなんともいえんのか・・・ 662 名前：デフォルトの名無しさん [2013/02/04(月) 18:41:17.92 ] 環境も何もかかずにいったい何がしたいのか。 663 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 20:11:22.72 ] コピーが遅いんだろ 664 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 22:20:18.86 ] 最適化有効にしてる？ 665 名前：661 mailto:sage [2013/02/04(月) 23:53:21.67 ] いやーすまぬ Releaseにしてビルドしたらすごく速くなったわ こんなに速度変わるとは 666 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 23:57:54.34 ] ・・・ 667 名前：デフォルトの名無しさん mailto:sage [2013/02/05(火) 00:24:44.09 ] 原因を解決したらもっと速くなりそうだな 668 名前：デフォルトの名無しさん mailto:sage [2013/02/05(火) 12:24:00.31 ] 色々酷いな 669 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 09:40:59.22 ] 結果報告しただけでもマシ 670 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 19:32:31.26 ] 2のべき乗の和で、例えば7は1+2+4で構成されてますが、 7から1,2,4が使われてると判定する良い方法はありますか? 671 名前： ◆QZaw55cn4c mailto:sage [2013/02/06(水) 19:34:59.98 ] >>670 繰り返し 2 で割りまくって余りをみていくしかないのでは？ 672 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 19:38:43.95 ] >>670 16進数で論理演算したら？ 673 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:09:47.71 ] >>670 & で1ビットずつ判定していけば 674 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:30:25.87 ] 値がdoubleかも知れないし 675 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:37:47.12 ] 整数にキャストすればいいだけ 676 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:38:52.35 ] 判定した値を何に使うかで違ってくると思う 例えばforeachに突っ込むなら判定処理は先延ばしにした方がいいだろうし 677 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 21:24:33.20 ] >>670 J言語だとこんなふう (#2^i.@#)#:7 1 2 4 (#2^i.@#)#:1234 1 8 16 64 512 678 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 22:04:58.56 ] J言語の書き込みなんて初めて見た 679 名前：670 mailto:sage [2013/02/07(木) 03:55:23.45 ] ビット演算で 2の0乗&7、2の1乗&7...で判定できるのですが、この方法だと3の冪乗1 3 9 27...のときに同じ方式が使えないですよね。 どう考えれば良いのでしょうか。。 680 名前：デフォルトの名無しさん mailto:sage [2013/02/07(木) 04:04:00.14 ] >>679 >>671 681 名前：デフォルトの名無しさん mailto:sage [2013/02/07(木) 07:17:09.20 ] まさか10進数の表示を自前でできないってことはないよね？ 3進数はその10を3に変えればいいだけ 682 名前：デフォルトの名無しさん [2013/02/07(木) 08:40:46.92 ] >>670 >>679 ここに 3 のベキ乗でも通用する良質の答えがある toro.2ch.net/test/read.cgi/tech/1358572977/31-

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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