- 1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net]
- 【関連スレ】
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/
アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html
- 604 名前：デフォルトの名無しさん mailto:sage [2014/06/28(土) 22:27:38.54 ID:DAhf0dEp.net]
- 作家になったエンジニア
matogrosso.jp/engineer/engineer-01.html
＞藤井 コードはわかる、というか、数式での理解が苦手なんです。数式で見ても
＞よくわからないんですが、コードになったアルゴリズムで見れば「あぁ！」って
＞腑に落ちる。群とか集合とかの処理の方法なんかもコードで見たほうがわかるんですよね。
こんなことってあるの？
数式でわからないものが、コードで書いたらわかったなんて経験ないんだけど。
そういう人もいるのか、単にハッタリなのか？
- 605 名前：デフォルトの名無しさん mailto:sage [2014/06/28(土) 22:45:54.42 ID:S3hAxR/5.net]
- 知らない・慣れない記号でわんさか書かれたものよりはコードのほうが……かもね
- 606 名前：デフォルトの名無しさん mailto:sage [2014/06/28(土) 23:18:32.01 ID:Wnh+uZwR.net]
- 記号を覚えてなかったり
上とか下とか小さく書いてあったりするのが
英単語混じりで一列に並ぶから
- 607 名前：デフォルトの名無しさん mailto:sage [2014/06/29(日) 00:10:58.39 ID:jxL17uOJ.net]
- 微分方程式だといまいちピンとこないのが、
差分方程式に変形してプログラムにまでなればなんとなく、とか。
ただ、あまり良いことじゃない。抽象を扱えない頭だと、後々苦労する。
- 608 名前：デフォルトの名無しさん mailto:sage [2014/06/29(日) 00:45:43.60 ID:osp1rgt9.net]
- 狂気のマッドコーダー、鳳凰院凶真だっ！フゥーハハハ！
機関の妨害が入っているようだな
そのようなものに私が屈すると思ったかっ！
全ては脱アルゴリズムの選択だっ！
エル・プサイ・コングルゥ
オカリンは凄いね～ｗｗｗｗｗ
- 609 名前：デフォルトの名無しさん mailto:sage [2014/06/29(日) 02:56:13.63 ID:6ywxiUqJ.net]
- 「CERNだけど何か質問ある？」でCERNが「シュタインズ・ゲート」に触れ大盛り上がり
gigazine.net/news/20140623-ama-cern/
- 610 名前：デフォルトの名無しさん mailto:sage [2014/06/29(日) 09:17:18.99 ID:TGhI+LW9.net]
- >>604
数式をプログラムコードにして実行すると、計算結果の数値やグラフを見てイメージがつかめる、っていうなら判る。
- 611 名前：デフォルトの名無しさん [2014/07/01(火) 03:58:16.28 ID:VC0m3k7v.net]
- JavaScriptで、2分木を書こうと思ったが、
1-100をこの順番で追加したら、rootが1となり、
どんどん右側へ追加されていき、
直線となって、2分木にならない
B-Tree, 赤黒木は、どうやって木の高さをそろえているの？
- 612 名前：桃白白 ◆9Jro6YFwm650 [2014/07/01(火) 05:55:58.42 ID:zDJRF/6W.net]
- >>611
左の子が親より小さく、右の子が親より大きいって
いうのが満たされてれば、一直線となっても立派な2分探索木でござるよ。
効率は悪いけど。
B-Treeはノードが持つ子の数に制限を設けて、子の数がいっぱいになったら
ノードを分割していく感じ。すべてのリーフノードの高さは同じになる。
赤黒木は色をチェックして平衡化を行ってく。
黒ノードがB-Treeのノードに対応するから、黒ノードの数が左右で同じになる。
- 613 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 07:36:37.26 ID:NR0eMQV0.net]
- >>611
アルゴリズムの本を1冊は持っておけ
- 614 名前：デフォルトの名無しさん [2014/07/01(火) 08:44:01.18 ID:G0peUy8I.net]
- で、出た～本持っとけ言奴
- 615 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 09:36:03.07 ID:NR0eMQV0.net]
- >>614
その煽りの面白さがおじさんにはさっぱりわからんわ
- 616 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 11:14:27.31 ID:/zCy2KR2.net]
- ネットに転がってるpdfで良いです。
- 617 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 12:19:37.68 ID:29jmPgpF.net]
- >>614
「知的でタメになるつっこみの仕方」
監修・吉本興業
を一冊持ってろ
- 618 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 14:15:02.29 ID:WdBXMFPF.net]
- おじさんの くちさきから いてつくはどうが ほとばしる！！
- 619 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 19:19:42.82 ID:XUFkTk0Y.net]
- >>611
まず木の回転は順序保ったまま高さを調整できる。
あとは回転をどういう条件でやるかで赤黒木・AVL木とかに分かれる。
B木は二分木じゃないのでまた別
- 620 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 21:26:27.54 ID:lJh4uqZb.net]
- >>611
平衡二分木なら、まず原理が簡単なAVL木を勉強しよう。
次にspray木。
次に2-3-4木(これは二分木ではない)、赤黒木(2-3-4木の二分木化)。
- 621 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 22:02:39.89 ID:iG7VjtU1.net]
- 「代数的構造」買ったけど難しいな
頭が固くなってきているせいか、なかなか辛い
- 622 名前：デフォルトの名無しさん mailto:sage [2014/07/01(火) 22:07:09.65 ID:wjCbvLq3.net]
- >>617
そのレスを見るとあまりタメにならなそうな気が…
- 623 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 08:28:35.69 ID:s8DtebR3.net]
- 脱アルゴリズムってなんなん？
- 624 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 08:32:51.18 ID:8QRdpiH3.net]
- >>623
あぼーん推奨ワード
- 625 名前：612 [2014/07/02(水) 12:59:56.47 ID:UOkv1KGW.net]
- 2分木の木の高さをそろえる方法まで、
載せている本なんて、無いだろ？
載っていたら買うけどさー
載せられないということは、かなり難しいと言うこと
- 626 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 14:24:59.48 ID:IpihKmr8.net]
- つ アルゴリズムC・新版―基礎・データ構造・整列・探索、R. セジウィック
www.amazon.co.jp/dp/4764903091/
- 627 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 20:13:43.24 ID:FQajgQTr.net]
- アルゴリズムとデータ構造、岩波講座
にも、載ってた気がする
実家に置いたままだわ
- 628 名前：612 mailto:sage [2014/07/02(水) 23:26:01.30 ID:UOkv1KGW.net]
- R・セジウィックの20年前のアルゴリズムC++の本を見たら、
2分木の回転については、10行ほどしか載っていなかった
プログラミング・コンテスト・チャレンジブックにも、
2分木の回転・平衡化は載っていない
オライリーの「入門 データ構造とアルゴリズム」には、
AVL木の回転について、図入りの説明が載っていた
でも赤黒木を詳細に説明した本は無い
Linuxのタスクディスパッチで使っているのに
ところで2分木で、nullの代わりに、
番兵を使っているものがあったが、
番兵を使った方がよいのか？
- 629 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 23:48:15.85 ID:sVSUUVOR.net]
- ぶっちゃけググった方が早い…
木の回転 https://ja.wikipedia.org/wiki/%E6%9C%A8%E3%81%AE%E5%9B%9E%E8%BB%A2
AVL木 www.geocities.jp/m_hiroi/light/pyalgo12.html
赤黒木 www.geocities.jp/m_hiroi/light/pyalgo16.html
番兵は性能よりもコードをシンプルにするためのもんだし、お好みでどうぞ
- 630 名前：デフォルトの名無しさん mailto:sage [2014/07/02(水) 23:56:44.88 ID:RK8C0ZnB.net]
- >>629
いやいや、シンプルになっても終了条件が見えなくなってリーダビリティ下がるでしょ。
前処理と後始末がいることも多いしコメント必須になる。
性能上がらないなら使うもんじゃない。
- 631 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 00:11:23.34 ID:qo0RbgmN.net]
- えー。しかし番兵なんて所詮ゴミみたいな定数倍最適化にしかならんしなあ
多少短く書ける以外に価値がほぼないから、趣味の領域かと
- 632 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 00:24:13.05 ID:qo0RbgmN.net]
- そういう意味ではNull Objectパターンやnilも番兵の亜種っぽいな
使い方次第で可読性が下がるし
- 633 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 08:34:15.19 ID:5WHzWYtz.net]
- 脱アルゴリズム・・・・・
- 634 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 09:12:49.19 ID:xp4LuS6y.net]
- 宣言型言語の制約プログラミングや論理プログラミングなら
アルゴリズムを必ずしも記述する必要はないが、
結局糞みたいな処理速度にならないために隠蔽されたアルゴリズムを
意識せにゃならなくなるから脱アルゴリズムは飛ばし過ぎ
- 635 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 10:39:28.42 ID:QCtThtAw.net]
- どんなプログラム書いても、それアルゴリズムになるから
アルゴリズムってそういうものなんだけど
- 636 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 11:07:32.82 ID:HJPE9W5O.net]
- >>631
最近のCPUじゃあ定数倍最適化にもならないんじゃない？
分岐の投機的実行があるから。
- 637 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 13:02:24.53 ID:jKZw1Onx.net]
- 分岐予測が当たると早い、という石で、直感に反する順序で判定を並べたほうが
良い場合もあるという報告があったし(※)、正直、個々の機械で実アプリで
確かめない限り、何も言えん。
ただ、勉強としては色々なモディファイがあるというのは抑えておいた
ほうが良い。速度だけじゃなくモディファイが要ることはよくある。
(※)
普通は、確率が50%→25%→12.5%→....といった順に並べたほうが、先に結果が
確定するから速い、というのが定石なのだが、そうすると分岐予測的には最悪に
なるので、確率が低いほうから ...→12.5%→25%→50%のように並べたほうが速い
プロセッサがある。
- 638 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 14:32:49.20 ID:2p/tvR1B.net]
- >>637
>12.5%→25%→50%のように並べたほうが速い
ほうほう、なるへそ
- 639 名前：デフォルトの名無しさん [2014/07/03(木) 15:25:04.31 ID:H6q9tJaf.net]
- 脱アルゴリズムとか馬鹿なんじゃねえの
- 640 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 17:09:24.39 ID:/vji65t/.net]
- 正直、あの記事の主は病人だと思う。
- 641 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 17:13:20.97 ID:0MY1anpd.net]
- 脱プログラミング、人差し指でディスプレイのあっちこっちから引っ張るとプログラムができる
- 642 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 17:43:08.65 ID:LtdUn3Av.net]
- 人差し指でディスプレイのあっちこっちから引っ張ることがプログラミング作業となるだけであって
- 643 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 18:40:39.03 ID:jKZw1Onx.net]
- だからそれはこっちでやれ
peace.2ch.net/test/read.cgi/tech/1403215505/l50
- 644 名前：デフォルトの名無しさん mailto:sage [2014/07/03(木) 23:43:57.28 ID:Tn3/IHEN.net]
- >>637
最近は実行時プロファイル取ってJITします。
- 645 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 01:16:13.84 ID:FWLzKTbt.net]
- >>625
＞2分木の木の高さをそろえる方法まで、
＞載せている本なんて、無いだろ？
上にもでてる、岩波の「アルゴリズムとデータ構造」石畑清のをみたいけど、
この話題、AVL木、B木で数十ページつかって詳しく解説してたよ。
というかこのあたり読んでなかった。
やっぱ日本人の書いたアルゴリズム本のなかでこれは良い方だと思う。
- 646 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 07:29:05.29 ID:llTgxSpv.net]
- おまえら、頭いい風のトンチキ。数学やれ。
- 647 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 07:55:14.81 ID:Mhkj+G22.net]
- やはり、2分木の回転を説明した本はなさそう
Webに載ってる情報で我慢するしかないのかー
- 648 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 08:04:47.39 ID:iKaePYIV.net]
- (ﾟДﾟ) ﾊｱ??
- 649 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 08:26:55.29 ID:gfxFeYJy.net]
- 木の二重回転だるい。あるとなしでどの程度違うんだろ？
親への参照をもたせると参照のはりかえがかなり複雑になる
- 650 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 09:38:02.44 ID:S//BcKLx.net]
- 岩波の「アルゴリズムとデータ構造」石畑清
"Algorithms" Robert Wayne, Kevin Sedgewick
どっちも amazon の書評わろす
- 651 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 11:56:44.81 ID:twdVMSox.net]
- 「アルゴリズムとデータ構造」
とか
「データ構造とアルゴリズム」
ってタイトルの本多過ぎ
- 652 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 12:00:57.86 ID:mFyW8OWx.net]
- データ構造は重要
- 653 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 12:09:47.36 ID:twdVMSox.net]
- そこは否定してない
一字一句完全に同じタイトルの本がいくつもありすぎて紛らわしいので
もっと工夫すれば良いのにと思った
- 654 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 13:48:11.44 ID:woY7u5MP.net]
- >>647
>>649
sedgewick読めばいいのに。
この人はアルゴリズム解析屋だからそのへんは結構しっかり書いてる。
Knuthのところ出身。
- 655 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:02:33.27 ID:sBqWnM4N.net]
- >>647
Niklaus Wirth: 「アルゴリズム+データ構造=プログラム」日本コンピュータ協会
浅野哲夫: 「データ構造」近代科学社
桐山清: 「C言語によるデータ構造とプログラム書法」森北出版
近藤嘉雪: 「定本 Cプログラマのためのアルゴリズムとデータ構造」ソフトバンク
渡邊敏正: 「データ構造と基本アルゴリズム」共立出版
のどれにも、AVL木（バランス木）の回転の解説あるよ
- 656 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:19:55.17 ID:woY7u5MP.net]
- 今時Wirth先生の本はないわ。
均衡二分木はあまり実行効率が良くないAVL木中心だし、
多分木派生の二分木は赤黒じゃないし。
しかも言語がPascal。
言語屋さんだけあってコードは綺麗。
- 657 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:27:00.41 ID:iKaePYIV.net]
- 『アルゴリズム・イントロダクション』読め。
総合版は武器にもなってお得だぞ。
- 658 名前：デフォルトの名無しさん [2014/07/05(土) 10:32:09.33 ID:5deLSK6V.net]
- セジウィックのアルゴリズム本もわかりやすくておすすめ
- 659 名前：デフォルトの名無しさん mailto:sage [2014/07/05(土) 13:44:41.02 ID:R8cFDXwQ.net]
- アルゴリズム・イントロダクション
セジウィック新版
の二択だな。
アルゴリズム・イントロダクションをちら見してみて挫折しないようならこっちやればいい。
この二冊ほどしっかり書けてる本はほとんどない。TAOCPは実装言語が独自すぎて除外。
- 660 名前：612 mailto:sage [2014/07/06(日) 02:00:23.53 ID:+YGfR2l7.net]
- >>645
石畑清のは、AVL木の回転について、図入りの説明がある
ただし、25年前の本で、ソースコードがPascal
- 661 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 03:16:22.62 ID:3qD8tN7V.net]
- 石畑清の本はいいよやっぱり。説明が細かいし。
しかしPascalだから困るという意見が結構多いのが不思議。
アルゴリズムを説明するためのたかが数十行のコード、言語仕様やライブラリに
深く依存しているわけでもないプログラム読むのにそんな苦労するのか？
疑似コードとして読めばいいでしょ。俺もPascal知らんけど充分理解できるよ。
もひとつ言っとくと、石畑清の本、巻末にちゃんとCとLISPのコード例も付録
で載ってるんだよ。ほんとは持ってないんじゃないのお前ら？
コピペしかできない知恵遅れにも安心（笑）
- 662 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 07:43:12.94 ID:ETigXUGg.net]
- Pascalは配列添字が1から始まるから、他の言語に移植するときに、
Off by one エラーに注意しながら書き直す必要がある。
これが面倒。
- 663 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 09:25:03.24 ID:PgwRX7N+.net]
- >>662
1オリジンを他のオリジンに直すだけだろう？簡単な線形変換をかますだけなのでは？
ま、2オリジンに書き直すなら多少のぐちゃぐちゃは厭わないが、1オリジンを0オリジンにわざわざ直す必要もない
- 664 名前：デフォルトの名無しさん [2014/07/06(日) 23:35:38.44 ID:I8o/e02M.net]
- 大学のアルゴリズムの講義の教科書が石畑Pascal本だ
- 665 名前：デフォルトの名無しさん mailto:sage [2014/07/07(月) 06:33:10.27 ID:iqLntt6B.net]
- ６６６
- 666 名前：デフォルトの名無しさん mailto:sage [2014/07/07(月) 12:41:09.24 ID:mcdr45lP.net]
- AVL木は挿入や削除で必要になる回転が多いので遅い。
バランスしてるからオーダーは良いが、
オーダーを計算する時に無視する定数部が悪い。
均衡二分木がAVL木しか書いてない本はとてつもなく古い。
- 667 名前：612 [2014/07/07(月) 23:46:14.44 ID:dH0g1YaP.net]
- >>661
漏れは研究家で、本はプログラミング・コンテスト・
チャレンジブックしか持っていない
漏れは立ち読みするから、誰よりも厳しいよw
まず図を載せていない著者を評価しない。
そういう著者はコピペしているだけで、
本当にアルゴリズムを作っていないかも
いかに読者に解かりやすく説明できるか？
まず図を作る段階で、戦いは始まっている
- 668 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 00:19:27.31 ID:WA0uMVhU.net]
- 入門 データ構造とアルゴリズム
www.oreilly.co.jp/books/9784873116341/
＞インド工科大学（IIT）と企業の両方で豊富な経験を持つインド人著者による、
＞実例豊富なデータ構造とアルゴリズムの解説書。
この本の評価どうですか？
- 669 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 03:59:34.21 ID:KMzZlwYF.net]
- 目次を見る限り、インド人ってネタを活かしてるようには見えないな
- 670 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 06:23:28.25 ID:C3Ow5lln.net]
- 漏れは研究家でw
誰よりも厳しいよww
評価しないwww
- 671 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 08:35:30.86 ID:+1SkhcPX.net]
- 朝からニヤリとさせてもらった
さて働こう…
- 672 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 20:48:31.13 ID:KjaCWqA1.net]
- >>666
不正確だ
挿入で必要な木の回転は、ただの一回だけ、問題は削除だね。これは AVL も赤黒木も同じ
削除が頻繁におこなわれるのなら、左右のバランスのゆるい赤黒木がいいね
- 673 名前：デフォルトの名無しさん mailto:sage [2014/07/09(水) 00:42:28.78 ID:nWprtmY/.net]
- インド人嘘つかない
- 674 名前：デフォルトの名無しさん [2014/07/09(水) 23:39:21.70 ID:8efLPFpl.net]
- アルゴリズムの名著にはPascalで書かれた本も多いし、Pascalもひと通り勉強したほうがいいんだろうか？
- 675 名前：デフォルトの名無しさん mailto:sage [2014/07/09(水) 23:51:22.77 ID:9Qxa4e89.net]
- pascalはCというかPL/I系統の言語が出来るなら読むのはそんなに難しくない。
- 676 名前：デフォルトの名無しさん mailto:sage [2014/07/10(木) 13:54:07.94 ID:iLbfPtwr.net]
- CがPL/I系統？
ていうかPascalないしAlgolは、いちいち勉強なぞしなくとも読むのにそうは苦労しないだろ。
Algolには名前呼びとか変な機能があるが、普通はそういうトラップは回避して説明に使うから。
- 677 名前：デフォルトの名無しさん [2014/07/16(水) 08:34:15.83 ID:uBdPgdk4.net]
- qiita.com/kenokabe/items/13ea8d2da6adce1b3b9a
関数型プログラミングとオブジェクト指向の抜き差しならない関係について整理して考える
お、これはなかなか優秀な人が現れたな。わかりやすい良エントリ。
- 678 名前：デフォルトの名無しさん mailto:sage [2014/07/16(水) 09:49:46.76 ID:VblCYr0v.net]
- >>677
スレ違いです。こちらへどうぞ。
【毛の壁】脱アルゴリズム宣言【FXST】
peace.2ch.net/test/read.cgi/tech/1403215505/
- 679 名前：デフォルトの名無しさん mailto:sage [2014/07/16(水) 23:55:51.33 ID:FEyT2AKy.net]
- アルゴリズムを学ぼう (アスキー書籍)
川中 真耶
www.amazon.co.jp/dp/B00JGI5H2I/
Amazonのレビューでも評価低いけど、この本意外に良書やね。
もっとレベルが低いのかと思ってたけど、二分木だとAVL木の回転とかまで
ちゃんと説明している。
ただ、レビューでも触れられているけど、ストーリー仕立てにする意味が
ほとんどないというか、単純につまらない。
こういうのが受けると思ったんだろうけど、キャラクターにも魅力がない。
Kindle版だと安いから買って読む価値はある。
- 680 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 00:43:35.51 ID:YW/aq4b0.net]
- アルゴリズムを学ぼう サポートページ
https://sites.google.com/site/adtalgo/home
- 681 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 10:13:30.44 ID:S7UqHs8v.net]
- >>679-681
【これは】重大な誤り【ひどい】
１つ本当にひどい誤りを含んでおりました。本当に申し訳ありません。恥ずかしくて夜も寝られません。
P. 33
O(aN) = O(eN)
この文章の記述は大嘘です。デタラメです。
指数の底を変えることは出来ません。
そもそも数式の展開も誤っています。
指数の場合も同様で～～となる。の文を削除。
わろ・・・えない
- 682 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 18:39:54.82 ID:FWtSwDTq.net]
- あまり話題にならないけど丸善から出ている黄色い表紙の装丁のアルゴリズム本でオススメある？
お前らには難しくくて縁のない本が多い？
- 683 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 19:43:15.82 ID:8B88F9S3.net]
- |￣｀`''- ､
| ｀ﾞ''ｰ- ､ ＿＿＿＿＿＿__
| ,. -‐ ''´￣￣｀ヽ､＿ /
|, - '´￣ ｀ヽ、 /
／ ｀ヽ､ヽ /
_/ ヽヽ/
／ / / / / / ヽﾊ
く / /! | 〃 _/__ l| | | | | | | ||ヽ
＼l// / | /|'´ ∧ || | |ｰ､|| | | l | ヽ
/ハ/ | | ヽ/ ヽ | ヽ | || /|ヽ/! |/ | ヽ
/ | ||ヽ { ,r===､ ＼| _!V |// // .! |
| || |l |ヽ!'´￣｀ﾞ , ==ミ､ /イ川 |─┘
| ﾊ|| || | """ ┌---┐ ｀ / // |
V !ヽ ト! ヽ､ | ! / //| /
ヽ! ＼ハ` ､ ヽ､__ノ ,.イ/ // | /
┌/）/）/）/）/）/）/）/）/）/）lｰ/ ` ー‐┬ '´ レ//l/ |/
|（/（/（/（/（/（/（/（/（/（/│|| |＼ 〃
r'´￣ヽ. | | ト / ＼
/ ￣｀ｱ | | | ⌒/ 入
〉 ￣二) 知ってるが | | | ／ ／/ ヽ
〈! ,. -' | | ヽ∠-----', '´ ',
| ＼| | .お前の態度が | |<二Z二￣ ／ ',
| | | _r'---| [ ｀`ヽ､ ',
| | | 気に入らない >-､__ [ ヽ !
＼.| l. ヽ､ [ ヽ |
ヽ| ＼ r' ヽ､ |
- 684 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 22:33:37.10 ID:3rueaPG+.net]
- そう言わず教えろよ
- 685 名前：デフォルトの名無しさん mailto:sage [2014/07/21(月) 20:25:53.74 ID:Ecx8KQMM.net]
- 本ばかり読んでないで実践しろよ
- 686 名前：デフォルトの名無しさん mailto:sage [2014/07/23(水) 01:29:55.54 ID:dHvcLkvH.net]
- 結城浩の「Java言語で学ぶデザインパターン入門」ってオリジナルと増補改訂版って
買い直した方がいいぐらい違いが大きいんですか？
- 687 名前：デフォルトの名無しさん mailto:sage [2014/07/23(水) 08:13:43.33 ID:Qr1azPSk.net]
- Cookieを使わずにユーザーを追跡する仕組みが普及しつつある
it.slashdot.jp/story/14/07/22/0613210/
- 688 名前：デフォルトの名無しさん mailto:sage [2014/07/24(木) 22:18:02.88 ID:wzSFtnz7.net]
- GoFは言語が未熟だった時代の名残のようなもの
現代的なほとんどの言語（特に動的型付言語）では、多くのパターンが適用できない
（適用しても、バッドパターンにしかならない）
Javaなどの一部の古めかしい静的型付言語では、まだ頼る余地は残っていたが
そのJavaでさえも関数型の要素を取り入れ、設計が大幅に変わってきている
GoF自体の改定でもなければ、改めて学ぶ価値はない
- 689 名前：デフォルトの名無しさん mailto:sage [2014/07/24(木) 22:53:43.17 ID:GcACTNu8.net]
- なんだ本人が来たのか（笑）
- 690 名前：デフォルトの名無しさん mailto:sage [2014/07/29(火) 17:13:50.87 ID:qGOKoo8w.net]
- 突然ですが質問させてください
重みなし無向グラフの場合、ダイクストラ法より反復深化の方が計算量少なくて済むんですか？
- 691 名前：デフォルトの名無しさん mailto:sage [2014/08/19(火) 13:41:16.96 ID:46ZruSDn.net]
- アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
gigazine.net/news/20140819-visualgo/
- 692 名前：デフォルトの名無しさん mailto:sage [2014/08/31(日) 09:31:36.46 ID:TsfChlj7.net]
- 「アルゴリズムを学ぼう」は続の方が面白いな。
- 693 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 13:15:21.81 ID:bjSSfYoR.net]
- qiita.com/kenokabe/items/821ce4020644372b648c
＞「アルゴリズム」とは「バズワード」であり、「一般的に命令型プログラミング
＞パラダイムを指し示す」のであり、その他の使用は一般的ではない、ということ
＞です。
勉強になるな。このページ。
- 694 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 15:45:42.81 ID:FbNt5hSi.net]
- >>693
どこらへんが？
- 695 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 16:00:30.06 ID:r0J72yK/.net]
- >>693 毛の壁は隔離スレから出るんじゃねぇよ
peace.2ch.net/test/read.cgi/tech/1403215505/l50
- 696 名前：デフォルトの名無しさん mailto:sage [2014/09/16(火) 02:48:17.06 ID:BRRsQsEe.net]
- そんな意地悪言うなよ。
- 697 名前：デフォルトの名無しさん mailto:sage [2014/10/07(火) 20:54:36.34 ID:3NSGj8n/.net]
- 死ねゴミ共がw
- 698 名前：デフォルトの名無しさん mailto:sage [2014/10/13(月) 00:56:00.10 ID:hQ/UKOA3L]
- なぜか放置されてる合法ハーブのサイト
www.unitepopulaire.org/
unepsefalliance.org/
www.love-salvia.com/
xn--ccke7d0a7en7a6d6eqb4l.com/
www.esodam.org/
herb-patio.jp/
xn--edkpew5hb5jf4159d0glkskyw0ckwox9v.com/
- 699 名前：デフォルトの名無しさん [2014/10/24(金) 21:39:41.30 ID:VyYUZ4Z5.net]
- カリー化とは何でしょうか？
- 700 名前：デフォルトの名無しさん mailto:sage [2014/10/24(金) 21:46:02.67 ID:zvGM4ELq.net]
- 「大抵のものはカレー味にしとけば失敗しない」という理論
- 701 名前：デフォルトの名無しさん [2014/10/24(金) 21:54:38.69 ID:VyYUZ4Z5.net]
- なるほど深いですね
- 702 名前：デフォルトの名無しさん mailto:sage [2014/11/25(火) 23:14:09.49 ID:ghl2SNY1.net]
- は？
- 703 名前：デフォルトの名無しさん mailto:sage [2014/11/26(水) 16:03:51.97 ID:cap+vDqw.net]
- ねんまつ
- 704 名前：デフォルトの名無しさん [2015/02/04(水) 10:21:19.15 ID:QfhTV/If.net]
- 1うんこ
- 705 名前：デフォルトの名無しさん mailto:sage [2015/02/21(土) 15:18:37.61 ID:Bqyo/mYz.net]
- 「オブジェクト指向のこころ」って原題とは何も関係ない変な題名で誤解されているけど、実はデザインパターンの良書だよね
結城本みたいなトイプログラムじゃなくてちゃんと仕事に活かせるコードや考え方が載ってる
もっと評価されるべき本だと思う
- 706 名前：デフォルトの名無しさん mailto:sage [2015/02/21(土) 17:25:01.22 ID:Qj5PkULS.net]
- まるち
- 707 名前：デフォルトの名無しさん [2015/03/16(月) 00:54:31.01 ID:pKR+yvmi.net]
- アルゴリズム！重要度を増していく、今までも、そしてこれからも
- 708 名前：デフォルトの名無しさん mailto:sage [2015/03/16(月) 01:07:48.91 ID:EXoRrBXi.net]
- 増しません、基本ではあるが
- 709 名前：デフォルトの名無しさん mailto:sage [2015/03/16(月) 06:58:50.72 ID:dto99C0o.net]
- 関数型が来る！とかと同じようなアレだな
- 710 名前：デフォルトの名無しさん mailto:sage [2015/03/19(木) 20:04:29.25 ID:rGfQi3lS.net]
- グーグル・アルゴリズム
アマゾン・アルゴリズム
アルゴリズム体操
- 711 名前：デフォルトの名無しさん [2015/03/23(月) 20:17:07.02 ID:v5lqXW2+.net]
- >>662
あんたなあ･･･ ハァ。
線形代数の教科書の行列、ベクトルは全部、添字１からだろ。
それをC言語では０から始めなければならないから「１つズレ」の
バグがでるんだろう。
あんたの言ってることは本末転倒だ。この田分け！
唯一の例外がFFT。唯一、添字が一定成分に対応した0から始まるから
- 712 名前：デフォルトの名無しさん mailto:sage [2015/03/23(月) 23:50:39.23 ID:VDUQlxD5.net]
- >>711
おらの教科書では自然数は 0, 1, 2, ....
- 713 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 00:52:58.38 ID:MX5B1wfa.net]
- 自然数の定義の話題は宗教戦争に発展するのでNG
- 714 名前：デフォルトの名無しさん [2015/03/24(火) 01:10:04.30 ID:Ve+M57ZM.net]
- 自然数が初等的算術を展開するのに必要十分な集合じゃないと困るでしょ。
算術の基礎になれないような集合に「『自然』数」なる名称を与えて特別視する理由がない。
で、0なしの{1,2,...}ではペアノ算術のモデルすら構成できないんだから、
自然数に0入ってなきゃ困ります。
- 715 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 02:16:41.68 ID:qocM3p7p.net]
- そういや空集合もあらゆる集合の部分集合だもんな
自然数にもゼロが会った方が自然な気はするな
- 716 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 03:17:40.76 ID:O1VRnX3O.net]
- 正直そういうことはどうでもいい
ただ正の整数と同じ意味なら言葉が勿体無いから０も入れればいいじゃん
- 717 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 12:37:46.16 ID:c6mpFC05.net]
- なに、実は >>711 が田和けであることを示せばいいだけの話
- 718 名前：662 mailto:sage [2015/03/24(火) 20:19:23.88 ID:aWlBWbGCG]
- アセンブリ言語を使ったこともない奴がデカイ面できるようになったんだな。
2chも本格的に終わってるわ。
などどscで書いてみる。
- 719 名前：あ mailto:sage [2015/04/04(土) 09:36:37.38 ID:zehumhhz.net]
- 1～6の整数がランダムに並んでいる時、これを最小手順で並べ替える
アルゴリズム知ってる人、思いつく人いたら教えてほしい
隣で比較する基礎の解放ではなく最小手順
5,6,3,2,4,1 → 1,2,3,4,5,6 にする最小手順
- 720 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 09:42:25.65 ID:QuAhdSHj.net]
- ソート自体不要
結果として1,2,3,4,5,6を返せばいいｗ
- 721 名前：あ mailto:sage [2015/04/04(土) 09:46:00.61 ID:zehumhhz.net]
- それだと6回かかるでしょ
- 722 名前：あ mailto:sage [2015/04/04(土) 09:49:01.47 ID:zehumhhz.net]
- あ、ごめん。ついwを付けられて
上では1-6って書いたけど、0-99の100個の数字を最小回数でソートしないと
いけない問題に今ぶつかってて。誰か賢い人いたら助かるなーって思って書いてみた
- 723 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 10:00:43.23 ID:QuAhdSHj.net]
- >>721
1,2,3,4,5,6と決まった数字がランダムに並んでだけだよね？
どうランダムに並んでようが、ソート結果は常に1,2,3,4,5,6になるんだから、
最初からその結果を用意しておいて、どういう並びであってもそれを１回返せばいい
ということ。
宿題の意図としては求めてないだろうから無視していいけどね。
- 724 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 10:12:22.71 ID:8tbUo2zR.net]
- ソートのアルゴリズムなんてググればいくらでも解説されてるでしょ
ttp://www.it-shikaku.jp/top30.php?hidari=02-02-02.php&migi=km02-02.php
それじゃ何か足りないの？
- 725 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 11:37:48.38 ID:9IYCOCMd.net]
- >>719
sleepsort
- 726 名前：あ mailto:sage [2015/04/04(土) 16:50:06.49 ID:zehumhhz.net]
- >>724
ありがとう、平均回数も乗ってるこのページ凄い役だった
とりあえず、これでやってみる。>>725 何、これ初めて見たｗ
みなさん、ご協力本当に感謝します。
- 727 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:12:22.13 ID:vj4bzuy0.net]
- sleep sort は、bucket sort とみなすべきだろうし、1,2,3,45,6を返すっていうのもそうだよね。
質問者の質問の意味は、最小 sorting network を求めろってこと？
- 728 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:26:57.58 ID:w5ibkrLo.net]
- 最小置換手順が欲しいと推測
- 729 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:55:13.09 ID:vj4bzuy0.net]
- ああ、なるほど。そしたら最長増加部分列求めりゃ良いね。
- 730 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 22:21:32.50 ID:bg9jdXhF.net]
- て、手順としてどのようなオペレーションが許容されるかで変わりますね。当たり前だけど。一手順で、隣接のスワップしか許さないのか、任意の場所のスワップを許すのか、任意の繋ぎ変えを許すのか、任意の一つの数字を任意の場所に入れることを許すのか。
- 731 名前：デフォルトの名無しさん mailto:sage [2015/05/16(土) 22:03:28.98 ID:y/t4uXt/.net]
- 日本人はスマホとかコンビニとか省略するのが好きだけど
検索アルゴリズム的にはスマートホン、コンビニエンスストアの方が１０倍早く検索できるんだよな。
記憶力をよくしたかったら、省略するのをやめましょうね。
- 732 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 05:07:39.56 ID:M9Jld2yx.net]
- ア････
あ･思い出した
ア､はいいよね
- 733 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 06:49:06.78 ID:MQbFTiCx.net]
- >>731
面白い脳味噌してるなコイツ
- 734 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 12:03:39.74 ID:Cq+Owzl6.net]
- >>731
理屈が分からないのですが、もう少し詳しく説明していただけませんか。
同趣旨のことを解説したネット上の記事を紹介していただけるだけでも構いません。
- 735 名前：デフォルトの名無しさん mailto:sage [2015/05/18(月) 10:30:22.61 ID:DlA37DUd.net]
- でかい方が見つけやすいでしょ
- 736 名前：デフォルトの名無しさん mailto:sage [2015/05/18(月) 20:00:18.97 ID:qgceviCB.net]
- >>735
それでは曖昧すぎて説明になっていないんじゃないかな。
どのようなデータ構造に対してどのようなアルゴリズムで検索するときに、
検索対象「スマホ」よりも検索対象「スマートホン」の方が10倍早いと言っているのか。
こういうのを話す場でしょ、ここは。
まぁ元々が曖昧だから、>>731以外だれも説明できないとは思うが。
- 737 名前：デフォルトの名無しさん mailto:sage [2015/05/30(土) 23:11:38.07 ID:GbYkPqTc.net]
- >>731
は収録数の少ないシソーラス辞書しか持っていないらしい
- 738 名前：デフォルトの名無しさん [2015/07/30(木) 16:31:15.15 ID:gNKRMuak.net]
- A スター アルゴリズムの計算について質問をしたいのですがいいでしょうか？
- 739 名前：デフォルトの名無しさん mailto:sage [2015/07/30(木) 19:32:45.75 ID:StheyCIu.net]
- 別に断る必要は無い
解る者が居れば答えるし、そうじゃなければ放置されるだけ
- 740 名前：デフォルトの名無しさん mailto:sage [2015/07/30(木) 20:18:42.09 ID:oAGEjgo8.net]
- ｇｇｒｋｓ ↓
- 741 名前：デフォルトの名無しさん [2015/07/31(金) 14:17:38.86 ID:qB8zjiMb.net]
- 開始地点と到着地点を入れ替えても同じサイズの経路が出来ます。
そしてそれは地図を斜めに線分したものに対象である。
そのときの計測時間が余りにも違うのですが、これは何が主な原因でしょうか？
ttp://gmdev.xrea.jp/st/up/1090.png
ttp://gmdev.xrea.jp/st/up/1091.png
- 742 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 15:24:20.10 ID:qnWPb5RQ.net]
- >>741
左上から順に探索してるから開始位置によって処理時間違うとかかな？
マップを上下/左右反転して同じコース走らせてみたらもう少し詳しくわかるかも
- 743 名前：デフォルトの名無しさん [2015/07/31(金) 18:33:06.81 ID:qB8zjiMb.net]
- 上下反転でも上記と同じような動きになってしまいました。
ttp://gmdev.xrea.jp/st/up/1092.png
ttp://gmdev.xrea.jp/st/up/1093.png
左右はまだ試していませんが多分同じ結果になるかと。
一応補足として、# of calclation は
while (!openList.isEmpty()) {
count++; ....
です。
上下反転したときの経路は元と違って同じですし。
しかし、この四つの中で違うのは時間だけでほかは経路サイズも、#も一緒っていう。
Ａ＊って元々こんな特性なんでしょうか？
- 744 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 19:02:30.87 ID:km5orOmS.net]
- >>743
これ斜め移動できるっぽいのに何で真ん中通らないの？
- 745 名前：デフォルトの名無しさん [2015/07/31(金) 19:13:51.36 ID:qB8zjiMb.net]
- 一応、壁に阻まれている設定なので、斜め移動は可能ですが、そのような経路は取らない様にしています。
家の隅を思い浮かべてもらえればいいかと思います。
- 746 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 22:14:18.76 ID:pNhxtvtu.net]
- てきとーだけど、
時間が掛かる方はスタート位置から全方向に探索し始めるけど、
もう一方は限定されてるから、その辺の違い？
- 747 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 22:43:26.98 ID:rVmFBF2u.net]
- 探索木の根元（付近）がよく茂ってるか否かか
- 748 名前：デフォルトの名無しさん mailto:sage [2015/08/01(土) 00:40:27.40 ID:hEjnOg+p.net]
- オープンリストとか見られるようにしたらどう探索してるか一瞬でわかるよね
- 749 名前：デフォルトの名無しさん mailto:sage [2015/08/02(日) 19:09:42.88 ID:vmnF+S0U.net]
- スタート位置からの経路が多いかどうかかなあ
もっと単純なマップから少しずつ複雑化して試してみたら？
□□□□□□□
□□□□□□□
Ａ□□□□□Ｂ
□□□□□□□
□□□□□□□
↓
□□□□□□□
□□□■□□□
Ａ□□■□□Ｂ
□□□■□□□
□□□□□□□
↓
□□□□□□□
□■■■□□□
Ａ□□■□□Ｂ
□■■■□□□
□□□□□□□
こんな感じで
- 750 名前：デフォルトの名無しさん [2015/08/03(月) 16:26:23.97 ID:JJqkNluJ.net]
- 遅くなってすみません。
オープンリストをみて見ると、探査時間が遅いほうが根元（付近）がよく茂っていました。
原因が判明してスッキリしました。ありがとうございます。
一応これでＡ＊の実装は終了しようと思います。最適化は時間かかるし、ほかのアルゴリズムも組んでみたいので。
>>749
一本道の迷路で試したところ、経路の大きさが9と探査のとき、時間が半端なくかかってしまいました。
多分複雑なマップはＡ＊には向いていないのかもしれません。
同じ経路探査として、こんなのを見つけたのですが、ゲームに使うとしたらこっちのほうが面白そう。
ttp://codezine.jp/article/detail/94
てか、
- 751 名前：デフォルトの名無しさん mailto:sage [2015/08/03(月) 19:33:29.19 ID:MJUDpxg+.net]
- 深さ優先・幅優先探索で、
キャッシュに乗りやすいなどの、
メモリ特性が異なるのかも
キャッシュ的には、直前に使ったアドレスを、
繰り返し使って、廃棄する方が、
使用メモリも少なくて、速いのだろう
- 752 名前：デフォルトの名無しさん mailto:sage [2015/08/03(月) 20:24:42.14 ID:t5WJQOuJ.net]
- A*は複雑な迷路より広くて何も無い方が苦手だと思うけど
- 753 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 02:23:14.81 ID:TrY1gttZ.net]
- 何も無かったら一直線にゴールに向かうだけでしょ。
- 754 名前：デフォルトの名無しさん mailto:age [2015/08/04(火) 05:58:48.09 ID:r3CWXwbp.net]
- 迷路ジェネレーター
jsdo.it/jagarikin/bNMK
- 755 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 07:41:15.54 ID:Ryo/DS3S.net]
- どうやって一直線に向えるんだｗ
人間は目で見てゴールまでの経路を探索するからそれが分かるんだけどさ。
こういうアルゴリズムは、例えるなら一歩先しか見えない状態で、
進める全方向に枝葉を伸ばして探索していくから、
何も無いとパターンが増えて時間が掛かるんだよ。
ちなみに。ゲームで使われるてるし、カーナビとかグーグル地図のルートだとか、
ネットのサーバーまでのパケットが通る通信経路とかの探索で使われている。
- 756 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 07:53:11.90 ID:TrY1gttZ.net]
- A* ってのは、各点からゴールまでの直線距離なんかを元に、一番有望そうな枝から探索するアルゴリズムなんだよ。
何も無い状態なら、一番距離が小さくなる枝が選ばれ続けるから、一直線だよ。
- 757 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 07:57:35.38 ID:faHT6mnE.net]
- >>756
A*の探索範囲
https://www.youtube.com/watch?v=moUOV-zzJ0Q
- 758 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 09:30:31.14 ID:TrY1gttZ.net]
- >>757
その動画、 0:05 あたりの探索範囲が怪しい。
明らかにゴールから遠ざかるような点も探索してる。
どこか間違えてると思う。
https://www.youtube.com/watch?v=DINCL5cd_w0
あたりのほうが適切そう。
- 759 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 10:06:00.63 ID:faHT6mnE.net]
- >>758
確かに少しおかしいけど
障害物が無い空間でも最大でひし形のような範囲を探索するはず
- 760 名前：デフォルトの名無しさん mailto:sage [2015/08/05(水) 00:37:22.34 ID:GWKF7o0G.net]
- 斜め移動で菱形に広がるのは、複数の枝が同点一位で並んだとき、古いのから探索した場合なんかに起きる問題だよ。
新しいのから探索すると起こらない。
- 761 名前：デフォルトの名無しさん mailto:sage [2015/08/05(水) 02:01:34.48 ID:+qWU8RMV.net]
- _***_____***_
**A***_***B**
_***_____***_
橋本環奈が出ている、NHKのアルゴリズム子研究所で、
カーナビの経路探索で、ダイクストラ(または、A*)で、
AB両点から探索しているのを見たけど、
ABの回りも、少し探索していた
- 762 名前：デフォルトの名無しさん mailto:sage [2015/08/05(水) 07:27:53.77 ID:yAAa1oiV.net]
- >>760
いやコストの問題だろ
直線距離＋正確なコストだから
斜めだと正確なコスト分少し伸びるんだよ
だから明らかに遠ざかるような探索もする
- 763 名前：デフォルトの名無しさん mailto:sage [2015/08/05(水) 23:00:40.63 ID:GWKF7o0G.net]
- >>762
そっちの問題だと、菱形に広がるパターンにはならない気がする。
ちなみに、そっちの問題は、直線距離の代わりに適切な距離を使えれば防げる。
上下左右にしか動けないならマンハッタン距離とか。
- 764 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 19:15:00.05 ID:iWaQs0bI.net]
- アルゴリズムの発表ってしていいかな。学会でもしたんだが受けが悪くて。
- 765 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 19:16:45.23 ID:Wv3ZRkcl.net]
- 気になるからしてみ
- 766 名前：スモモンガー mailto:sage [2015/09/12(土) 19:31:58.04 ID:iWaQs0bI.net]
- ではお言葉に甘えて
sumomonga.at-ninja.jp/reseach/kangaroo/head.html
アルゴリズムの原理は単純で探索中の辺やレコードとの距離を隣接するの辺やレコード間の値の差の
最大値で割ってその数分進めば探索の辺やレコードを飛び越えないということなんだ。
単純なアルゴリズムだからもうすでに先駆者がいないかどうか調べてみたんだが一応今のところ
発見できなかった。もし、既出だったらスマソ。
もともとは多角形と直線の交点を求めるために作ったんだが今は探索のアルゴリズムに応用できないか
と考えている。まあ、ぶっちゃけバイナリサーチを使えばいいんじゃないかといわれそうだが。
正直上のホームページの説明も分かりにくいと思うから（俺は説明が下手なんだスマソ）ダウンロードペーから
ダウンロードして直接ソースみたほうがこのスレの住民ならわかると思う。
なんか長文になってすまん。
どうぞよろしくお願いします。
- 767 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 19:32:59.56 ID:64Xb/9UR.net]
- 色覚異常者臭い配色だな
- 768 名前：スモモンガー mailto:sage [2015/09/12(土) 19:35:17.81 ID:iWaQs0bI.net]
- あと、情報処理学会の会員の方がいたら、グラフィックスとCAD研究会で”多角形と図形の交点の高速算出”
って題名で論文出しているからそっちのほうが少し説明がまとも
- 769 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 19:38:40.39 ID:iWaQs0bI.net]
- すまん、俺は芸術的センスは皆無なんだ。
- 770 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 19:59:23.62 ID:Wv3ZRkcl.net]
- > よって飛び越えないためにはkをY/lを越えない最大の整数にすれば大丈夫に思えます。しかし、一つ飛び越えたということは交わったということなので実際には(Y/l+1)を越えない最大の整数にすればいいのです。
ここの Y は X じゃね。ていうか Y は k の関数 Y(k) じゃね。
ソースにコメントつけたらどうだ。
構造体 line の int a,b,c とか意味が分からん。あとラムダは lambda な。
二乗するのに pow() とか使ってんな。ていうか直線との距離に sqrt なんていらんだろ。単位法線との内積を取れ。
- 771 名前：スモモンガー mailto:sage [2015/09/12(土) 20:23:27.44 ID:iWaQs0bI.net]
- >>770
わざわざ下手な説明と汚いソース読んでいただきありがとうございます。確かに、Y/lじゃなくX/lですね。
今夜中に直しておきます。ただ、Yはkだけに依存するものではないので、Y(k)とするのはまちがっていると思います。
構造体のa,b,cはax+by+cのa,b,cです。直線との距離は単位法線との内積をとったほうが確かに早そうですね。
二乗はpowを使わないほうがいいんですか。勉強になります。ソースコードのほうはちょっと俺の力
ではすぐ直せそうにないので明日直そうと思います。あらためてになりますが、読んでいただいてありがとうございます。
- 772 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 21:06:00.39 ID:Yzh+CkQk.net]
- ci.nii.ac.jp/naid/170000087534
ci.nii.ac.jp/naid/170000087558
どっちも内容同じ？
- 773 名前：デフォルトの名無しさん mailto:sage [2015/09/13(日) 09:11:22.28 ID:n3zvmQA3.net]
- ハロー "Hello, World" OSと標準ライブラリのシゴトとしくみ 単行本 – 2015/9/12
www.amazon.co.jp/dp/4798044784/
こんなのでた。
面白そう。
- 774 名前：スモモンガー mailto:sage [2015/09/16(水) 21:09:13.76 ID:k300cqkh.net]
- とりあえずソース直しました。
>>772
私は二つ投稿してないんですが（汗）一回修正入れたんでそのせいかもしれないです。新しいほう
が間違えがないんじゃないかと思います。
- 775 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 01:36:24.28 ID:h/C+p+kS.net]
- 毎日変わる文字列がどのパターンに当たるか判定するソフトを作りたいんですが、
どの言語を使えばいいですか？
宝くじの攻略に使いたいんですが
htmlとVBを10年前にやったことがある程度の能力しかありません
0 7 ② 3 ⑤ 6 8 ⑨ ① 4
と毎回不規則に並んでいる数字から毎回不規則に4つ選び、
該当の2591の形がどのパターンなのかを判断するというソフトです
さらにこのとき選ばれた2591を別の不規則の数列に当てはめたときも判定するようにしたいです
0 ② 4 6 8 ① 3 ⑤ 7 ⑨
この数列のときはどの形なのか・・・という具合にです
これを平日の間手動でやるのは限界があったので
- 776 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 09:31:31.86 ID:8C/CtMhx.net]
- アルゴリズムだろ、馬鹿には無理だが
- 777 名前：デフォルトの名無しさん [2015/09/17(木) 15:49:14.71 ID:jeXjMZOh.net]
- アルゴリズムの勉強って何をすればいいの？
何も見ずに書けるようになるとか？
- 778 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 16:56:57.71 ID:RFJKEvXv.net]
- とりあえずwiki行ってリンク辿れば？
- 779 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 17:07:55.21 ID:ylAQcAdL.net]
- >>775
どういう処理がしたいかよくわからんけど
データがすくないならスクリプト言語，多いんならC++でも使えば？
- 780 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 00:53:57.52 ID:kZ1aVgi2.net]
- >>777
セジウィックや、オライリーのインド人の本など、
アルゴリズムの本は、一杯出ている
>>775
丸で囲んだ数字などの、
MS-CP932の機種依存文字を使うな。
これらは、Shift-Jisにも属さない文字
- 781 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 02:38:17.41 ID:YgOe18Uv.net]
- 囲み数字はShift_JISX0213に入ってるんだよなあ
Shift-Jisとかいう独自規格のことは知らないけど
- 782 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 17:33:44.18 ID:uevEmGa3.net]
- >>780
オライリーの本調べてみたら問題がたくさんのってるようですね。
解いて勉強すればいいということですか
- 783 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 20:20:23.43 ID:7AiId5VK.net]
- >>782
とりあえず解いていけばよい
まずは既存のアルゴリズムを知ること
そして問題に対して適切なアルゴリズムを適用して解決できるようになること
- 784 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 22:37:30.79 ID:U/4/CI9X.net]
- >>783
やってみます。ありがとうございます。
- 785 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 08:38:55.46 ID:mo1gDnuH.net]
- 宝くじの攻略とか言ってる段階で確率論でも学んだほうがいいのでは？
- 786 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 08:49:47.26 ID:g55jIHl1.net]
- 確率論学んだからって狂人が正気に戻る訳でもあるまい。
- 787 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 09:12:37.94 ID:h/dwjgiw.net]
- 宝くじが夢を買うってことなら、この人は夢をプログラミングしてるんだよ。
- 788 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 09:22:06.02 ID:5cHEEdwc.net]
- 獏は夢を食べます
- 789 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 13:08:11.01 ID:hRep6fdc.net]
- >>786
確率のいい教科書はありませんか測度論までケアしてくれるやつ
- 790 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 13:48:42.32 ID:ZXXgaQ/P.net]
- >>789
・測度と積分 入門から確率論へ
・はじめての確率論 測度から確率へ
この辺りを読まれてはいかがでしょうか。
- 791 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 16:19:22.10 ID:hRep6fdc.net]
- >>790
上の奴って品切れみたい，空手踊りとか肉体系で楽しそうだね
- 792 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 17:05:20.53 ID:hheo9oaF.net]
- 測度と確率 小谷
プロ仕様だけど
- 793 名前：デフォルトの名無しさん [2015/10/06(火) 19:59:51.30 ID:uxUTfTFS.net]
- 受ける会社大丈夫？
下記の条件が全て当てはまる会社にご注意下さい。
・IT系 in tokyo
・「社名 労基」でググると過去の2chスレが出てくる
・転職会議で2.5点
- 794 名前：デフォルトの名無しさん mailto:sage [2015/10/08(木) 08:03:53.85 ID:Np+b0DPs.net]
- >>785
ナンバーズ4っぽいから、期待値の高い組み合わせを出したいんだろう。あれ、誕生日で買ったら当たっても安いんだよね。
- 795 名前：デフォルトの名無しさん mailto:sage [2015/10/18(日) 19:20:01.26 ID:mdnTkxCG.net]
- 保守
- 796 名前：デフォルトの名無しさん mailto:sage [2015/10/21(水) 12:58:47.56 ID:ngwDS6AM.net]
- BOOK・OFFで
2200円のこれを200円で買った俺って勝ち組？
i.imgur.com/6zlSiQq.jpg
- 797 名前：デフォルトの名無しさん mailto:sage [2015/10/21(水) 13:08:25.20 ID:Zr5MZtBC.net]
- ゴミにはビタ一文出すな
- 798 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 13:45:30.59 ID:8+WZrGwR.net]
- サッカーや野球のようなゲームがあったとします。
選手は毎年どんどん出現してきて、引退した選手もファイルに残ります。
ファイル名は必ずユニークなIDで、同じファイル名は存在しません。
ここまで仕様確定です。
もし、Aチームの選手はAフォルダに格納される方式を取ったとき、
チームに所属する選手はすぐ出せると思います。
しかし特定の選手を探したいときは難しくなります。
(例えば1990年の得点王選手のIDが記録されていたとして、そのIDにアクセスするのは若干めんどうです)。
そして、引退した選手も保存されるので、ファイルは一方的に増えて行きます。
100万や200万、1000万になるかもしれません。(どのくらいかは知りません)。
確実にアクセスは遅くなり、間違った方法だと検索も大量に取られます。
どのファイルがどこのフォルダに保存されてるのか記載するにしても、もしも仮にDが1億も並んでるとアホの極みと思うわけです。
良さそうな方法考えてください。
- 799 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 13:49:09.94 ID:vcVH8w6b.net]
- データベース使え
- 800 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 15:20:54.63 ID:eH4IcMDe.net]
- チームが買収されたり合併されたらどうすんの
- 801 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 18:50:14.31 ID:yGf9dC8a.net]
- >>798
データベース使え案件だけど無理なら自前で
選手IDをキーにしたB+木のインデックスファイルをつくり
それから検索する
- 802 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 22:26:55.40 ID:RIZFllKe.net]
- オンメモリに収まる量ならともかく
外部データ連携するB+木とか自前で用意する方がリスク高いんじゃないの
しかも用途が野球なら実際に必要になる18人と監督+α以外ほぼ無駄データなわけで
そんなもんをまじめに管理するよりゲームの面白さに注力しろって意味でも
DB使え
- 803 名前：デフォルトの名無しさん mailto:sage [2015/11/01(日) 20:12:40.65 ID:MVvuxbKY.net]
- おまえらがいってることがすでにわかんねーよ
- 804 名前：デフォルトの名無しさん mailto:sage [2015/11/01(日) 20:16:08.48 ID:cyCCNHZp.net]
- 登場選手はなんと1000万人！
面白いのかそれ？ｗ
- 805 名前：デフォルトの名無しさん mailto:sage [2015/12/01(火) 15:30:58.86 ID:jz4WAacM.net]
- セジウィック4版が和訳されるのっていつ頃かな？
- 806 名前：デフォルトの名無しさん mailto:sage [2015/12/02(水) 19:19:28.88 ID:A58rIrCf.net]
- 実装したいアルゴリズムの名前がわからないので教えてください
知りたいのは以下の様なものです
---
for (int i = 0; i < 10; i++)
do_something(i);
これをクラスに展開して
int i = -1;
static bool Next() { ++i < 10; }
static int Value { get { return i; } }
static void Main() {
while (Next())
do_something(Value);
}
---
このように変換する方法について調べたいのです
実際に欲しいのはN重ループをフラットに繰り返しで処理する方法です
自力で解こうとしたのですが、どこかで勘違いをしているようで、うまく動いてくれません
名前が分からないと調べようがないので助けてください
- 807 名前：デフォルトの名無しさん mailto:sage [2015/12/02(水) 22:20:37.79 ID:yyIVeakG.net]
- イテレーターで抽象化したいってことかな
- 808 名前：デフォルトの名無しさん mailto:sage [2015/12/03(木) 00:25:03.13 ID:74Kx8KXh.net]
- >>807
そうです
Iteratorパターンというのですか？
このパターンについて調べてみたのですが多重ループを解く方法については記述が見当たりませんでした
- 809 名前：デフォルトの名無しさん [2015/12/03(木) 15:48:13.76 ID:5y9yFaIO.net]
- イタレーターを二つ以上用意する
- 810 名前：uy ◆Qawu9.2l1E mailto:sage [2015/12/03(木) 18:57:59.03 ID:tK7Nyube.net]
- ヒント：ruby
- 811 名前：805 mailto:sage [2015/12/03(木) 20:32:43.77 ID:74Kx8KXh.net]
- 木構造+イテレータでぐぐって解決しました
ありがとうございました
- 812 名前：デフォルトの名無しさん mailto:sage [2015/12/08(火) 20:54:01.39 ID:vWrFkfhW.net]
- デザパタ実践したらファクトリだらけになったんだがこんなもんなのかな
- 813 名前：デフォルトの名無しさん mailto:sage [2015/12/08(火) 23:56:43.50 ID:/pdSfCvK.net]
- >>812
ありがち
デザパタ厨のやつが作ったクラスが
全部createInstanceだらけで使いにくいだけのクソが出来上がってた
まさに早すぎる抽象化
やるならせめてDIとかリフレクションや
アノテーションを使えやって思った
- 814 名前：デフォルトの名無しさん mailto:sage [2015/12/11(金) 12:43:43.71 ID:fYAYo2Es.net]
- 数学っぽい問題なのですが、
n = 100のとき以下の３つの条件を満たす単位分数の組みを考える
1/n1 + 1/n2 + ....+ 1/nk ＝ 1 （１）
n1 + n2 +....+nk = n （２）
n1 < n2 < ....<nk （３）
これをプログラミングを用いて解きたいのですが、いい方法が思い浮かばなくて困っています
何か方法ありましたら、教えてください
- 815 名前：デフォルトの名無しさん mailto:sage [2015/12/14(月) 23:31:43.15 ID:R0gDPv6y.net]
- 簡単な乱数生成のアルゴリズムで、線形合同法と言うのがあります。
数学のループ記述はよく分からないので、プログラム風に書くとこうです。
x = (a * x + b) % mod;
xが上書きされて何度も順番に使用さていると言う意味です。
% mod は割った余りです。
32bit環境なら
mod = 2 ** 32;
となっています。(つまり上記の式は32bitで表現できる最大値未満の乱数がxとして算出され、次の乱数生成にまた使用されます)。
64bit環境なら
mod = 2 * 64;
となっています。
x の初期値は何が入っていても構いません。(例えば式の初回使用時などに適当な値を入れます。例えば今の時間とか)。
a と b は定数で、これを何に設定するかによって乱数が良質であるか悪質であるか、また使える周期の長さが変わります。
周期が長くて良質な物を出すとき、これに何を設定すると良いのか分からないので教えてください。
32bit用と64bit用の両方をお願いします。
ちなみに、それを考えるのがどの程度大変 (または簡単) なことか分からんで質問してます。
- 816 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 18:58:35.99 ID:y7r4C3dc.net]
- https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
例から適当に拾え
てか 線形合同法 定数 あたりでググればソースと解説があるだろ
- 817 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 19:00:49.31 ID:GmzcEDm2.net]
- MT使え
- 818 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 21:14:19.01 ID:rY8ZFzdV.net]
- >>816
>>817
ありがとうございます
- 819 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 02:29:13.85 ID:WaYE86JM.net]
- >>814
それ解はあるの？ 無限に続くのでは？
- 820 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 08:55:42.31 ID:2+dP2nJG.net]
- >>819
単位分数って言ってるんだから、各 nk は 1 以上の整数だ。
条件 (2) によって nk は有限個しかないよ。
この条件を満たす解が存在するかどうかは知らん。
アルゴリズム的にはどうなんだろうな。
単純に条件 (2) と (3) に合うものを 1/2 + 1/98 から順に網羅していって、
条件 (1) に合うものをピックアップしていくというのはクソ遅いかな。
もちろん、浮動小数点でやったら誤差が出るから、すべて整数計算だけど。
- 821 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 11:58:26.07 ID:oLnMv084.net]
- その方針だと何れにせよnのdistinct partitionの全体を走る必要がある。
「よい」アルゴリズムのオーダーは知らないけど, 分割数の漸近公式だけ見れば少なくとも準指数時間アルゴリズムになる
- 822 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 14:39:33.46 ID:oLnMv084.net]
- やってみた, (2, 6, 7, 8, 21, 56), (3, 5, 6, 8, 9, 24, 45), (3, 4, 7, 8, 12, 24, 42)の3組だけらしい
- 823 名前：デフォルトの名無しさん mailto:sage [2016/01/04(月) 07:49:13.32 ID:quO35K88.net]
- 遺伝的アルゴリズムの無料電子テキスト日本語版が無い
日本の人工知能はクソ
- 824 名前：デフォルトの名無しさん mailto:sage [2016/01/04(月) 12:41:00.87 ID:21yj4oPz.net]
- 北野某に聞けよｗ
- 825 名前：デフォルトの名無しさん mailto:sage [2016/01/05(火) 21:09:57.94 ID:i0IFFoJB.net]
- 人工知能予算は懐の中に消えていきました
- 826 名前：デフォルトの名無しさん [2016/01/20(水) 23:38:29.66 ID:epdaSdlJ.net]
- オライリーの入門データ構造とアルゴリズム、原著のアマゾンレビュー見たら間違いがものすごい多いらしいけど翻訳は直ってるの？
- 827 名前：デフォルトの名無しさん mailto:sage [2016/01/21(木) 22:44:56.10 ID:vB+/Osfo.net]
- いいえたとえ明らかに間違いだ確信しても悪だと感じてもそれを正確に翻訳するのが翻訳家の仕事なのです
翻訳家ごときが主張を勝手にねじまげてはいけないのです
- 828 名前：デフォルトの名無しさん mailto:sage [2016/01/22(金) 00:08:33.24 ID:raZVxvb6.net]
- そりゃそうだな
もしもエラッタが出てるとしてもそれも反映するんじゃなくエラッタとして翻訳して付けるだろうし
- 829 名前：デフォルトの名無しさん mailto:sage [2016/01/23(土) 22:24:00.13 ID:gfbrLyNS.net]
- >>827
昔、「フォトンマッピング」という、
原著の間違い（計算式も含め）が大量に修正されていて、
挿絵まで挿入されて、しかも原著より安いという驚きの翻訳本があった。
まぁ、原著に間違いが多かったのには、それなりの訳があったんたが。
- 830 名前：デフォルトの名無しさん mailto:sage [2016/01/24(日) 04:41:54.83 ID:QDUQ11dL.net]
- 日本の報道は捻じ曲げすぎるよね
海外の出来事のほとんどがまともに入って来ない
- 831 名前：デフォルトの名無しさん mailto:sage [2016/01/24(日) 06:35:32.21 ID:4ZCEMBL4.net]
- ロイターあたりを眺めるのか？
- 832 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 00:49:21.41 ID:DXoTpOvl.net]
- >>827
お前の言ってることは実社会を無視した単なる教条主義
翻訳にしろ何にしろ他人に役立つ仕事をするのに必要なのはpragmatismだよ
ニートして自分の部屋にこもってないで偶には人様の役に立つ仕事をしに外に出ろよ
- 833 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 06:29:16.92 ID:8H4JYu/t.net]
- ずいぶんでかいつりばりだなぁ
- 834 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 11:08:55.31 ID:qRGGYULG.net]
- >>827
原著者に問い合わせるだろう普通ｗ
- 835 名前：デフォルトの名無しさん mailto:sage [2016/01/29(金) 04:26:25.65 ID:1+b9HDsX.net]
- 機械翻訳だと中身の検証なんてしないよ
集合知プログラミングという悪しき前例もあるし
- 836 名前：デフォルトの名無しさん [2016/02/07(日) 12:46:18.16 ID:l17BC95H.net]
- 既存のDBがあり顧客都合によりDBレイヤの変更が許されない
要望ではUIレイヤを総入替してAPレイヤをリファクタリングしたいということになっています
しかし現実ではそもそもUIとAPとDBが密結合していてレイヤという概念は存在しません
こういった案件で役立つアーキテクチャスタイルやパターンは何でしょうか
DBの変更が効かないのでドメインモデルパターンは実質不可能です
全てを諦めて貧血モデルとトランザクションスクリプトを使うしかないのでしょうか
リファクタリング案件なのにコードが綺麗になる未来が見えません
- 837 名前：デフォルトの名無しさん mailto:sage [2016/02/07(日) 15:38:18.60 ID:Ah5srJ1t.net]
- >>836
なんとかレイヤってからには基本設計レベルでは元々レイヤはあったんでしょ
それらが実際は密結合しているのが嫌なんでしょ
つまりレイヤを疎結合にするのが目的なわけでしょ
だからUIレイヤを総入替するわけでしょ
将来的なリファクタリングを見据えて疎結合にするのが先なんじゃないの
コードが綺麗とかリファクタリングするとかはその先の話でしょ
- 838 名前：デフォルトの名無しさん mailto:sage [2016/02/07(日) 16:19:13.81 ID:Ah5srJ1t.net]
- あーそれとリファクタリング案件なんて誰が言ってるのか知らんけど
現実にリファクタリングにお金払う会社なんて存在しないからね
たぶん内部事情に詳しい客とか上の人とかが強調して言ってるだけで要件ではないよね
リファクタリングなんて曖昧な言い方は止めて上手いこと見積りに含めないと
現実には行われない可能性が高いね
- 839 名前：デフォルトの名無しさん [2016/02/28(日) 14:04:19.66 ID:kcbLGyy1.net]
- リポジトリパターンなるものを知って使ってみたのですがこれ遅すぎませんか？
テキストファイル用のリポジトリから集約を全件取得
オラクルDB用のリポジトリに対して取得した各集約を保存して最後にコミット
という何気無い処理にもかなり時間がかかっています
リポジトリパターンは業務用システムで実用に耐えうるのでしょうか
- 840 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 21:39:59.71 ID:rqKeW9kJ.net]
- >>839
考え方がおかしい
それってあくまでも層が違うモジュールをぶった切って設計やテストをしやすくするって用途だから
業務の永続化手段として使うものじゃないよ
- 841 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 22:00:28.10 ID:cktW2eh6.net]
- >>840
よくわかりません
一般的な業務用システムでは永続化層を設けないのですか？
- 842 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 23:13:58.36 ID:rqKeW9kJ.net]
- そういうことじゃなく
まあ遅いって判断してるわけだから
何かやり方がおかしいんだよ
- 843 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 23:21:17.03 ID:GBJ/TPKE.net]
- >>839
リポジトリパターンが遅いっていう忌みがわからんｗ
じゃあそのまんま同じ処理を他のやり方でやったら普通に早いの？
- 844 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 00:06:09.33 ID:XUzsrygn.net]
- >>843
バルクコピーを使うと高速になります
ですがこれはリポジトリパターンでは使えそうにありません
- 845 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 00:31:30.59 ID:2q2DW/zb.net]
- それパターンなんて関係なくて、バルクコピーなら速くてインサートは遅いってだけじゃん。
- 846 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 10:54:35.48 ID:LDxMFaxC.net]
- >>844
そのまんま同じ処理でって言ってるじゃん
バルクコピーしたら処理変わってんだろｗ
リポジトリパターンがその他の設計パターンで実装したものより遅いのかって聞いてんの
- 847 名前：デフォルトの名無しさん [2016/03/14(月) 14:56:36.24 ID:IZ2LWlGv.net]
- 質問です。たとえば以下のようなファイル名のリストがあったときに、ファイル名の類似性によってグルーピングするような一般的なアルゴリズムって何があるでしょうか?
検索キーワードだけでも教えてもらえると助かります!
123-456.zip
書類-1.doc
書類-2.doc
456-789.zip
→グループ化
123-456.zip
456-789.zip
書類-1.doc
書類-2.doc
- 848 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 16:02:15.36 ID:9C/zUDR9.net]
- つベイズ
- 849 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 16:04:35.86 ID:9b9aepwB.net]
- 拡張子で分けてるだけじゃないの？
- 850 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 18:51:10.95 ID:4xYadpbt.net]
- 正規表現である程度のパターンごとに表現する。
- 851 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 19:19:25.61 ID:DzDVqAyb.net]
- 男の娘はどちらに分類されるべきかとか考えると趣向による問題だし一般的な分類は無理なんじゃないかな
文字種とかで類似度の高いペアに分けるぐらいでしょ
- 852 名前：デフォルトの名無しさん [2016/03/16(水) 00:01:25.62 ID:MRypUzWZ.net]
- >>847
レーベンシュタイン距離とか
- 853 名前：デフォルトの名無しさん [2016/04/05(火) 16:33:18.67 ID:m6kqb6v+.net]
- ダイクストラのアルゴリズムの正しさの証明がよく分からないのですが、
何かいい本はありますか？
- 854 名前：デフォルトの名無しさん [2016/04/05(火) 16:46:05.13 ID:m6kqb6v+.net]
- imgur.com/MdPoKq5.jpg
imgur.com/PRjr5CT.jpg
imgur.com/41t2x4S.jpg
↑ダイクストラのアルゴリズムの正しさの証明についてですが、
3枚目の赤で囲ったあたりが分かりません。
この証明、分かる人いますか？
- 855 名前：デフォルトの名無しさん [2016/04/05(火) 16:50:41.63 ID:m6kqb6v+.net]
- 3枚目の画像で、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、その後、このことは証明中で使われていないように見えます。
これは何なんでしょうか？
- 856 名前：デフォルトの名無しさん [2016/04/05(火) 16:58:30.51 ID:m6kqb6v+.net]
- 3枚目の画像に、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、
d(x) ≦ d(y) + l(y, x)
ということしか言えないかと思います。
これについてはどうですか？
- 857 名前：デフォルトの名無しさん mailto:sage [2016/04/06(水) 00:31:36.30 ID:pFDX1Wjl.net]
- (b)のyとxについては(a)のwとvと同じかと。最短経路上にあると仮定してるから＜はありえない。
これに別途証明を与える必要があるかどうかは別として。
- 858 名前：デフォルトの名無しさん [2016/04/06(水) 08:08:37.20 ID:QfbBfCGx.net]
- >>857
ありがとうございます。
>>855
の疑問についてはどうでしょうか？
どうも使われていないように思います。
- 859 名前：デフォルトの名無しさん mailto:sage [2016/04/06(水) 09:08:25.64 ID:loGBTR8N.net]
- >>858
「v が先に取り出されたという話ですすめてるのに、d(x) < d(v) となるような x (図にもあるとおり、この x はまだヒープから取り出されてないので、V’ には属さない) があるのはおかしい」
ってことを言いたいんだろうけど、ややこしいね。
y も持ち出さないと d(x) = d(y) + l(y, x) が最短ですってことが言えないんじゃないのかな。
- 860 名前：デフォルトの名無しさん [2016/04/06(水) 23:05:03.06 ID:QfbBfCGx.net]
- >>859
ありがとうございます。
-------------------------------------------------------------------
imgur.com/X6aS3J5.jpg
imgur.com/UyANGwz.jpg
優先度付きキュー（プライオリティーキュー）について質問です。
2枚目の画像に、優先度付きキューへキーを追加する insert(key) の疑似コードが書いてあります。
以下にそれを書きました。
insert(key)
■■H++
■■A[H] = -INFTY
■■heapIncreaseKey(A, H, key)
heapIncreaseKey(A, i, key)
■■if key < A[i]
■■■■エラー：新しいキーは現在のキーより小さい
■■A[i] = key
■■while i > 1 && A[parent(i)] < A[i]
■■■■A[i] と A[parent(i)] を交換
■■■■i = parent(i)
- 861 名前：デフォルトの名無しさん [2016/04/06(水) 23:05:47.70 ID:QfbBfCGx.net]
- さて、質問ですが、なぜ、A[H] = -INFTY などとわざわざ代入しているのでしょうか？
heapIncreaseKey の一番最初の if 文は必ず偽になりますから無意味であるように思います。
なぜこのような無駄なことをしているのでしょうか？
以下のようなコードになぜしないのでしょうか？
insert(key)
■■H++
■■i = H
■■A[i] = key
■■while i > 1 && A[parent(i)] < A[i]
■■■■A[i] と A[parent(i)] を交換
■■■■i = parent(i)
- 862 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 00:15:40.81 ID:pUEgfdfM.net]
- if 変数
else
などと条件分岐すると、速度も遅いし、
ややこしくてバグも増えるから、条件分岐を減らす
配列の番兵なども同じ
- 863 名前：デフォルトの名無しさん [2016/04/07(木) 02:46:40.63 ID:D2Sjbg8N.net]
- >>862
ありがとうございます。
すみませんがよく分かりません。
if 変数
else
などとしているのは、むしろ -INFTY を代入しているコードのほうではないでしょうか？
- 864 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 03:52:09.66 ID:BbGPO0PR.net]
- >>861
優先度ヒープは一度キューに入れたオブジェクトやタスクの優先度を後から変更できた方が実用性が高いんだけど、その2ページだけなら必要ないかも。
その書き直したコードでも大丈夫かもしれない。
アルゴリズムとしてはどの本にも同じようなことが書いてあるのは当然なんだけど、 実は全く同じ擬似コードがコルメン本にある。
バイブル的な本だからそこからパクってきたのかもしれない。
もし大学の情報系の生徒だったりITの仕事で使うなら、コルメン本(アルゴリズムイントロダクション)を進める。
2冊で1万円近くなるし、ページ数も多いものの、解説や証明は丁寧だし版も重ねてるから誤訳や誤字も少ない。証明の解説も詳しい。
他の本でわからないと結局そういった名著を当たることになる。
- 865 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 04:55:53.13 ID:pUEgfdfM.net]
- もし変数aに値が入っていないと、一々、nil, undefined のチェックが必要になる。
それが面倒だから、初期値を代入している
if a{
aに値が入っている時だけ、処理する
}
漏れも、JavaScriptで配列を使って、2分ヒープを作ってみたので、参考にして
2分ヒープ(BinaryHeap)
jsdo.it/michihito/bGH5
- 866 名前：デフォルトの名無しさん mailto:sage [2016/04/08(金) 18:59:01.77 ID:QHM1+lud.net]
- カードゲームのaiを実装したいんですが、
行動に対する評価値を２分構文木に入れていくっていうロジックはありですか？
あと、行動すると巻き戻せない、シミュレートできないので、どうしようかなと。
行動に対するロールバックも実装しなければいけないでしょうか？
- 867 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 04:09:29.14 ID:MwGqsbeb.net]
- >>866
どういうルールのゲームで、どういった種類の「行動」があって、どうして2分構文木(2分木じゃないの?)になったの？
- 868 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 13:01:51.57 ID:FoBfIIvs.net]
- >>867
基本的にはカードを出す(呪文を唱える、モンスターを出す)、物理攻撃する、パスするぐらいですかね。
あ、２分探索木じゃ行動が2つじゃないから駄目な気がしてきました。
- 869 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 14:42:40.27 ID:MwGqsbeb.net]
- >>868
AIで探索木的なのを考えてるならA*を勉強してみるといいかも
- 870 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 15:13:16.75 ID:LJnl+JdY.net]
- A* は解領域にマッチしたヒューリスティック関数を決めてあげるのが大変だ‥
- 871 名前：デフォルトの名無しさん [2016/04/09(土) 19:20:31.07 ID:aVoK2gcj.net]
- カードのシャッフルアルゴリズムって
どうしようかと悩みだすと結構悩むなぁ
- 872 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 22:57:17.76 ID:O9j9lH5Y.net]
- >>871
一番シンプルなのは
配列からランダムに
取って戻すのを繰り返す
- 873 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 00:15:07.59 ID:8wDwAIGa.net]
- >>871
悩むなぁとか言ってるけど、他の質問も見てると自分で何も考えてないよね？誰かがヒントと方向性示してくれるのを待ってるだけで。
- 874 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 00:17:50.87 ID:tVvAXki7.net]
- おいおい。頭空っぽの奴に自分で考えろとか酷いこと言うなあ
- 875 名前：デフォルトの名無しさん [2016/04/10(日) 08:38:44.69 ID:oXSlNHSo.net]
- >>864-865
あるがとうございました。
- 876 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 10:29:49.38 ID:viI7M/4y.net]
- >>871
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC_-_%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB
- 877 名前：デフォルトの名無しさん [2016/04/16(土) 19:09:43.89 ID:RkF64Ds4.net]
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
の「領域探索」が分かりません。
どうして↓のような2分探索木を作り利用するのですか？
imgur.com/uRbPFzt.jpg
imgur.com/TSevr6v.jpg
- 878 名前：デフォルトの名無しさん [2016/04/16(土) 19:11:14.59 ID:RkF64Ds4.net]
- location ではなく x の値をノードに持たせないのはなぜでしょうか？
- 879 名前：デフォルトの名無しさん mailto:sage [2016/04/18(月) 11:03:47.60 ID:Jl/B9TZo.net]
- >>877
2分探索木を使う理由は探索時間を早くするためでしょう。
うまくいけば探索数が半分になるから
>>878
二分探索木をn個の配列で実装しているので、配列の添え字をxにする方法は
xが大きな数だったり整数でなかったりの場合に都合が悪いから
ただこれデータがソートされていることが前提だよね。そのまま二次元に
展開できるのかな
- 880 名前：デフォルトの名無しさん [2016/04/18(月) 20:25:41.28 ID:6VYHQoTT.net]
- >>879
半分どころじゃなくて log n でしょ。
配列の添え字じゃなくて配列の中身をなぜ x にしないのか聞いているんじゃないの？
- 881 名前：デフォルトの名無しさん [2016/04/18(月) 20:30:02.32 ID:6VYHQoTT.net]
- 多分、 location の値を配列に入れているのは、2分探索木の
左右のバランスがよいことが保証されるからじゃないの？
- 882 名前：デフォルトの名無しさん [2016/04/19(火) 10:53:36.63 ID:b4Mb+Ui9.net]
- >>877-878
2次元以上に拡張するためにはそのようにする必要がある。
- 883 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 01:45:04.87 ID:jf1w54Av.net]
- 木のバランス取れて初めて使えるレベルだろ
状況によっては木構造なんか作らず線形に探索した方が速いし
- 884 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 12:27:46.43 ID:9Ocgrhnl.net]
- >>883
状況によっては木構造の方が速くて線形に探索した方が遅い状況も作れるな
- 885 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 13:48:32.88 ID:6r15gyc9.net]
- >>883
では、どういう状況の場合に線形探索を利用するのか先生から説明をどうぞ
- 886 名前：デフォルトの名無しさん [2016/04/21(木) 14:08:39.31 ID:0vzabbti.net]
- MIT系の『Introduction to Algorithms』
と
Princeton系の『Algorithms』
どっちがおすすめ？
- 887 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 14:19:32.38 ID:TG5MxLgd.net]
- >>886
頭がいいなら前者、バカなら後者
- 888 名前：デフォルトの名無しさん [2016/04/22(金) 08:39:42.12 ID:pemVeZaH.net]
- Introduction to Algorithms
って当たり前のことをループ不変とかを使って説明しているよね。
はっきりいってくどい。
- 889 名前：デフォルトの名無しさん [2016/04/22(金) 20:17:37.76 ID:pemVeZaH.net]
- AlgorithmsはJavaのソースコードが載っていて具体的。
- 890 名前： ◆QZaw55cn4c mailto:sage [2016/04/22(金) 23:06:44.42 ID:DMiaofP1.net]
- >>883
バランスを常にとるように作ることはできる
- 891 名前：デフォルトの名無しさん [2016/04/23(土) 10:50:53.22 ID:M5Qy0F9U.net]
- >>888
Introduction to Algorithmsは確かにくどくて読みにくい。
別に難しい本でもない。
- 892 名前：デフォルトの名無しさん [2016/04/23(土) 10:51:34.32 ID:M5Qy0F9U.net]
- 結論は、
Donald E. Knuthの本が一番。
- 893 名前：デフォルトの名無しさん mailto:sage [2016/04/23(土) 16:24:35.42 ID:jNieRcbT.net]
- 終了
- 894 名前：デフォルトの名無しさん [2016/04/24(日) 09:33:35.68 ID:jhscNiw7.net]
- 日本人著者によるアルゴリズムの本で一番いい本って浅野孝夫の情報の構造っていう本。
石畑清の本ってAVL木の説明が出鱈目だってAmazonのレビューに書いてあった。
- 895 名前：デフォルトの名無しさん [2016/04/24(日) 09:37:13.46 ID:jhscNiw7.net]
- ところでPascalで書かれている本が多いのはなぜ？
Cのほうが分かりやすくない？
- 896 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 09:42:22.03 ID:HSA/nLEW.net]
- pascal は学術系なんだよ。
- 897 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 11:11:12.52 ID:Z/fpIQVL.net]
- 処理のフローが書いてあるだけだろ
- 898 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 13:30:26.41 ID:n5HZWl0r.net]
- >>892
あれは回答とかあっさりしすぎなとこあるだろ。。
- 899 名前：デフォルトの名無しさん [2016/04/24(日) 18:45:27.10 ID:jhscNiw7.net]
- エイホホップクロフトウルマンのデータ構造とアルゴリズムを図書館から借りてきて
読んでいるけど、説明がいい加減すぎる。
- 900 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 23:44:13.95 ID:pid8Qk86.net]
- 入門 データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著
セジウィック・石畑清が定番
川中真耶も、赤黒木の説明だったかな？ わかりやすかった
- 901 名前：デフォルトの名無しさん [2016/04/25(月) 08:06:15.68 ID:rnP5hl5x.net]
- Karumanchiの本はこうすればいいということしか書いていない。
なぜそうすればいいかが全く書かれていない欠陥本。
- 902 名前：デフォルトの名無しさん [2016/04/26(火) 10:56:55.51 ID:JtHly74d.net]
- 石畑清の本は説明が面倒なところは容易に分かるとかいって逃げている。
- 903 名前：デフォルトの名無しさん [2016/04/27(水) 09:48:32.30 ID:Sdx3kEFz.net]
- >>894
浅野孝夫のその本、最高だな。
超詳しく省略なく書いてある。
書きすぎとかいう批判が出そうなくらいだな。
- 904 名前：デフォルトの名無しさん [2016/04/30(土) 11:02:54.99 ID:jYDzAJS5.net]
- アルゴリズムイントロダクションを買おうと思うんだけど、
総合版にするか第1巻第2巻のみにするかで迷っている。
後半の特殊なアルゴリズムはいらないような気もするし。
なんで総合版って割高なの？
- 905 名前：デフォルトの名無しさん mailto:sage [2016/04/30(土) 18:06:23.76 ID:YBbs5n7s.net]
- 総合版ってあの鈍器だっけ。
- 906 名前：デフォルトの名無しさん [2016/04/30(土) 19:17:12.58 ID:jYDzAJS5.net]
- 総合版を買うことにしました。
- 907 名前：デフォルトの名無しさん [2016/05/01(日) 13:40:03.98 ID:tKi6j9CT.net]
- 匿名通信（Tor、i2p等）ができるファイル共有ソフトBitComet（ビットコメット）みたいな、
BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al
ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできないアスペルガーｗ
The Covenant Project
概要
Covenantは、純粋P2Pのファイル共有ソフトです
目的
インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します
特徴
Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)
接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
ｑ
- 908 名前：デフォルトの名無しさん [2016/05/01(日) 20:44:59.79 ID:u3cieUqF.net]
- >>903
ポインタを使っていないのはなぜなんだろうか？
Pascalってポインタを使えるよね。
- 909 名前：デフォルトの名無しさん mailto:sage [2016/05/01(日) 21:24:53.98 ID:JP6hgmB0.net]
- >>908
可能な限り参照で済ませる文化だったかと
- 910 名前：デフォルトの名無しさん [2016/05/02(月) 03:02:21.21 ID:/Hk1TQTD.net]
- 古いからと否定する気はないけど今なら良い書籍が沢山有る気がするぜ
どれがそうなんだって言われたら困るけど２０年前よりはいい本が出てる気がする
- 911 名前：デフォルトの名無しさん [2016/05/02(月) 09:17:48.88 ID:F0I20g+z.net]
- >>910
そうか？
日本語の本では、アルゴリズムイントロダクションくらいしか思い浮かばない。
ほかに新しくていい本なんてあるか？
- 912 名前：デフォルトの名無しさん [2016/05/02(月) 13:17:36.23 ID:F0I20g+z.net]
- 比較的新しい本でいい本っていうと、翻訳系以外だと全く思い浮かばないんだが。
- 913 名前：デフォルトの名無しさん [2016/05/02(月) 18:10:09.56 ID:F0I20g+z.net]
- 浅野孝夫の本はクイックソートとか載っていないのがいいね。
- 914 名前：デフォルトの名無しさん mailto:sage [2016/05/03(火) 10:25:55.27 ID:xwMa7zwR.net]
- アルゴリズムイントロダクションって具体的にどれくらい難しいですか？（予備知識の多さではなく理解の難しさ）
数学科向けの数学書ぐらい？
- 915 名前：デフォルトの名無しさん [2016/05/03(火) 14:57:28.35 ID:bxMOJzqX.net]
- 簡単。
- 916 名前： ◆tAo.kQ2STk mailto:sage [2016/05/03(火) 15:46:52.15 ID:CPxVolRD.net]
- ちょっとOS書いてるんだけど
可変長かつ連続したメモリ領域が本当に必要になるケースはOSレベルではそんなに無いって事を仮定して
・メモリ全体を1つ16バイトのチャンクに分ける
・各チャンクのアドレスの下4ビットが常に0になるので、普段はアドレスを4ビット右シフトした値を識別子として保持する
としてアロケータを組んでみてます。
32ビットの識別子で36ビット(64GiB)の空間を扱えるって利点の他に
x86_64のglibc mallocが1確保に対し管理領域として追加で8 Bytes消費するのと比較して、
こちらは16バイトの確保に対して管理領域として1ビット必要なので
glibc mallocで1024バイトの連続した領域を確保するのと同じ利用効率になり、かつ
「ポインタ」の保存に必要な領域が半減するという利点があります。
アドレスの算出にシフト演算が必要な点と、
基本的なデータ構造(list, set, map, hash, ...)を
1個16バイトのチャンクの組み合わせとして表現するのがちょっと手間である事
連続したメモリ領域の確保に別なアロケータが必要である事が主な欠点です。
実際には、4KiB単位の連続したメモリ領域をアロケータが面白みもない方法で確保して、
その中身をチャンクとして分割し、先頭2チャンクを管理領域にして確保/開放を行うという実装にしています。
連続したメモリ領域が本当に必要でも、4KiBあれば十分と今は仮定しています。
こういう方法ってこのスレ的には既出？
- 917 名前：デフォルトの名無しさん [2016/05/03(火) 18:42:53.59 ID:bxMOJzqX.net]
- >>914
日本人の書いた薄っぺらい教科書よりも簡単。
- 918 名前：デフォルトの名無しさん mailto:sage [2016/05/03(火) 18:52:57.38 ID:k0lWibxS.net]
- >>914
ページ数は多いものの、説明は丁寧だから難しいということはない。大学の1,2年向け。
一冊の小さくまとまった教科書と違って説明を端折ったりしてないから、途中でわからなくなって結局別の本を買い足したりする必要がない
- 919 名前：デフォルトの名無しさん [2016/05/03(火) 19:03:24.76 ID:bxMOJzqX.net]
- ただ、直観的に明らかな事実もわざわざご丁寧に説明していてうざい。
- 920 名前：デフォルトの名無しさん [2016/05/03(火) 20:50:04.37 ID:bxMOJzqX.net]
- 浅野孝夫の『情報の構造』に載っているプログラム例がエレガントで感心した。
- 921 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 08:24:35.18 ID:PCMiFBXM.net]
- >>917-919
ありがとうございます
- 922 名前：デフォルトの名無しさん [2016/05/04(水) 12:49:25.38 ID:A2cfTnr6.net]
- >>920
浅野孝夫のその本は説明が粗雑なところを詳細なプログラムを読むことで補完しなければならないところが難点。
- 923 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 15:23:50.62 ID:OcRpngHJ.net]
- .>>916
さっぱりわかんね
要するにビットマップで管理するってことか？
勝手にやれとしか
- 924 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 16:00:56.01 ID:p+LvbHBp.net]
- >>923
要するに、32ビットのポインタで64GiBの領域を使えるって事
普通は64ビット版のプログラムはポインタを64ビットに拡張するんだけど、
木構造のようなポインタを多用するデータ構造の場合は
32ビット版と比較してメモリの効率が半減するデメリットがある。
この方法だと、メモリ効率を落とさずに4GiBを超えるメモリ領域を同時に使える。
既出かどうか(或いはもっと良い方法があるか)知りたかった
- 925 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 16:38:51.07 ID:WruTeJWf.net]
- アロケータが確保する分にはいいとして、任意のポインタをどう表現するのかねぇ
- 926 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 17:24:52.95 ID:p+LvbHBp.net]
- 任意のポインタを、アドレスを4ビット右シフトした値として表現する。
ポインタが指す先は常にチャンク境界(16バイト)にアラインメントされてて、
ポインタを使うときは4ビット左シフトしてアドレスに変換してから使う。
「ポインタを変数とかに代入してとっておくこと」と「ポインタをデリファレンスして他所から値を持ってくること」を分けて考えてる。
1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。
https://github.com/pixie-grasper/operating-system/blob/master/kernel/objects.asm
- 927 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 17:35:44.12 ID:ypA5W//n.net]
- >>916
よくわかんねーけどやめたら
- 928 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 17:37:59.32 ID:WruTeJWf.net]
- >1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。
やっぱりそうなるんだ。
ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。
- 929 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 17:56:42.05 ID:p+LvbHBp.net]
- > ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。
OS内に何らかの言語のインタプリタを実装して、
所謂ユーザーモードで動くプログラムは全てその言語で走る、というのを考えてる。
全てがシェルスクリプト、みたいな感じ。
で、そのインタプリタは数と文字列とハッシュを扱えれば良いと思っていて
ハッシュをAVL、文字列をrope構造なんかの木構造で実装するとすれば
16バイトってサイズは各ノードに情報を格納するのに丁度いいサイズではあるのよ。
ropeってのはこれな。
https://en.wikipedia.org/wiki/Rope_(data_structure)
その考えで行くと、あんまり無駄は出ないんじゃないかなとは思う。
勿論実行速度は多少犠牲になるけどね。
- 930 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 18:36:41.93 ID:VTHyhTWb.net]
- >>916
FATの考え方だね。
メモリ管理でも応用できる気はするけど。
- 931 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 19:24:52.99 ID:WruTeJWf.net]
- OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。
確かにLISPのConsCellの持ち方に似てはいるが。
- 932 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 20:55:58.55 ID:I71ZCmWZ.net]
- 16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。
WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと
同じような気がするのだが。
- 933 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 22:32:04.59 ID:p+LvbHBp.net]
- >>931
> OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。
正確には、OSが内部で使うアロケータの話。
malloc/freeとは仕様が違うっていうか前提からして噛み合わない。関数が返す領域のサイズが固定だから。
とここまで書いて、「常に1チャンクだけ確保して返す」とは明確には言ってなかったことに気付いた。ごめんよ。
incしてorするコードが根底にあるから忘れてたわ。
>>932
> 16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。
16バイト境界でしか返さないって条件だと、16バイトの確保の為に追加で8バイトとか必要になる。
malloc/freeの仕様上、どうしても何バイト確保してあるかって情報をヒープ側に保持する必要があるからね。
開放する時点で何バイト確保されているかが自明で、かつ固定長ならば1ビットで済む。
> WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと
操作の意味はそれと同じかも。中身は全然違うだろうけど。
- 934 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 23:32:14.08 ID:I71ZCmWZ.net]
- なんか似たような話を最近見た気がしたがこれだった。
codezine.jp/article/detail/9325
- 935 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 23:54:19.41 ID:NIqCX6OH.net]
- ホント最近の記事だな。
- 936 名前：デフォルトの名無しさん [2016/05/05(木) 20:14:53.64 ID:Rts6L3H5.net]
- 浅野孝夫の『情報の構造』の赤黒木のプログラムがすごすぎる。
名人芸の域に達している。
- 937 名前：デフォルトの名無しさん mailto:sage [2016/05/06(金) 02:45:47.47 ID:iu7snuDE.net]
- >>916
ObjectIDに、32bitメモリアドレスを使っている言語では、
使わない下位4bitを、nil, undefined, true/false などに使っている
- 938 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 00:38:26.53 ID:fVgrqlwf.net]
- gof本の「オブジェクトのクラス」、「パラメータ化」という表現がよくわからん
- 939 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 09:44:21.83 ID:vQZ70y3E.net]
- >>938
よくわからん、じゃねえよ
教えてくださいってちゃんと言えよカス
- 940 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 14:50:16.86 ID:bh4nZJj2.net]
- クラスのインスタンスを引数として渡すってことじゃねーの。
つまりポリモーフィズムよ。
|
 |
