- プログラミングのお題スレ Part5
202 :デフォルトの名無しさん[]:2014/10/05(日) 02:00:33.11 ID:RckF5d3d - 点を中心に半径5(直径10)の円を描いて、それを全点でやったら、
二重三重にカバーされてる所、どれとどれをカバーしてるが判明して あとは離散的な組み合わせをチェックする問題になるだろ?
|
- プログラミングのお題スレ Part5
204 :デフォルトの名無しさん[]:2014/10/05(日) 02:23:53.77 ID:RckF5d3d - 実数値のほうがプログラムの手間はヘリそうで、整数値のほうが計算量はヘリそうだが。
実数でも整数でも、円の詳細位置よりどの点をカバーしてるか。 点a1、・・・、anとして。 点a1を中心に半径5の範囲の別の点がなかったら、円の配置は1通りで確定。 別の点があったら、その2点を含む円を適当に移動させて、内部に含まれる点の個数で円の配置を分類。 そうすると、 a1にたいして配置{ p1、p2、・・・} a2にたいして配置{ q1、q2、・・・} などと求まって、p1=q2のときもあって、そのときはp1を選ぶと、a2の配置も確定。
|
- C言語なら俺に聞け(入門編)Part 126
474 :デフォルトの名無しさん[]:2014/10/05(日) 02:40:54.35 ID:RckF5d3d - ハッシュでいい。
別のにたとえると、例えば"国語"、"算数"、"理科"、"社会"という単語をカウントする問題と一緒だろ? ハッシュ値でも実値でも、値が幅広いとアクセスに時間が掛かるかメモリ確保が食うから、上位何ビットをインデックスにすると決めて (可変長の)2次元配列に格納するなどしたらいいんでは。 2次元目はstlのmapなどでも。vector(普通の配列)のほうがアクセス速いかも?
|
- C言語なら俺に聞け(入門編)Part 126
477 :デフォルトの名無しさん[]:2014/10/05(日) 02:58:01.21 ID:RckF5d3d - ハッシュテーブルは連想配列と呼ばれることもある。それはハッシュテーブルを、添え字に数字以外の文字列が利用できる配列と見なすことができるからだ。
例えば英文ドキュメントに登場する語彙の出現頻度を調べるような場合、「apple、banana……」などの具体的な単語をキーとして、それらの単語の登場回数を値に保存することができる。 キーが決まればスロット番号は一意に決まり、しかもその計算量は一定だ。 だから、データ量が膨大でもデータの挿入や参照は一定時間に収まる。これはハッシュテーブルの重要な特徴であり長所だ。 百科事典のような膨大なテキストデータを相手にするとなると話が変わってくる。 大きな百科事典に含まれる単語の種類は少なくとも数万個オーダーで、含まれる単語数は数千万オーダーとなるからだ。 http://www.atmarkit.co.jp/news/analysis/200803/24/semi.html コラム - クラウド時代のオープンソース実践活用 | 第18回 GlusterFSはMapReduceの夢を見るか http://www.school.ctc-g.co.jp/columns/nakai/img/column18_fig01.png http://www.school.ctc-g.co.jp/columns/nakai/nakai18.html
|
- C言語なら俺に聞け(入門編)Part 126
481 :デフォルトの名無しさん[]:2014/10/05(日) 09:21:23.78 ID:RckF5d3d - そこは自分も気になったが。万は書き間違いで兆とか億だったりとか?
|
- C言語なら俺に聞け(入門編)Part 126
482 :デフォルトの名無しさん[]:2014/10/05(日) 09:23:59.28 ID:RckF5d3d - 計算量が多い、計算時間が多い、計算に掛かる資源が多いなどでは?
ソートするよりカウントのほうが計算量は少ない。
|
- C言語なら俺に聞け(入門編)Part 126
489 :デフォルトの名無しさん[]:2014/10/05(日) 21:10:52.92 ID:RckF5d3d - 手軽な量のデータだったらいいけど。
カウントする問題でソートは効率悪いだろ。
|
- C言語なら俺に聞け(入門編)Part 126
495 :デフォルトの名無しさん[]:2014/10/05(日) 22:44:40.06 ID:RckF5d3d - C言語というよりも一塊の扱い方の問題だ。
「。\n」「.\n」で必ずしも分割するわけではないんだろ? 個人の好みの問題で、先に詳細な一塊の定義を決めろ。
|
- C言語なら俺に聞け(入門編)Part 126
496 :デフォルトの名無しさん[]:2014/10/05(日) 22:52:03.50 ID:RckF5d3d - それはサーバー依存。このへん。
HTTP入門 Range (要求) クライアントからサーバに対して、エンティティの一部のみを要求します。下記の例では、ページの最初の 1000バイト(0バイト目から 999バイト目)のみを要求しています。(→ Accept-Ranges、Content-Range、If-Range) Range: bytes=0-999 http://www.tohoho-web.com/ex/http.htm
|