データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/
【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://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 ttp://hissi.org/read.php/tech/20160619/YW80V0xnZlg.html
へんなのが居着いたな
981 ：デフォルトの名無しさん[sage]：2016/06/19(日) 12:16:06.94 ID:ao4WLgfX
>>980
いつも思うんだけれども，この碁の勝負，棋譜は公開されているの？
985 ：デフォルトの名無しさん[sage]：2016/06/19(日) 12:47:45.21 ID:ao4WLgfX
>>982
どこに貼ってあるかな？たぶん公開されてないんじゃないかな
986 ：デフォルトの名無しさん[sage]：2016/06/19(日) 12:59:15.60 ID:ao4WLgfX
http://blogs.yahoo.co.jp/ten_nan_91/35774553.html
988 ：デフォルトの名無しさん[sage]：2016/06/19(日) 13:02:20.35 ID:ao4WLgfX
ありがとう
1000：デフォルトの名無しさん[sage]：2016/06/19(日) 14:49:22.87 ID:ao4WLgfX
0 ruby って変な人が多いんだね，俺も今 ruby をマスターしようと必死ではあるが Haskellって勉強する意味ある？
実用性はないよね？ なぜ、HaskellやSchemeをありがたがる人がいるの？
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ？ MITのコンピュータの入門書もSchemeを使っていたりする。 言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。 haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ
一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要 >>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要
ライブラリを駆使するのが今のプログラマに求められている技術だからな。
MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい（たとえば、ロボットを制御するソフトウェアを書くなど） HaskellやSchemeの利点は？
少なくとも、分かりにくいよね。 >>14
>今日のプログラミングは、「より科学に近い。
ここは変だな
「より工学に近い。」
というなら判るが SICPをプログラミング初学者に教えるというのは確かに異様だよね。
やっとまともになったというだけの話。 コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの？ アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。 なんか計算の理論とかのほうが上みたいな感じじゃない？ コンピュータサイエンスで最も重要な科目は、コンパイラとかOS？ schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな javaでconsを表現するときにどうすればいいか知ってますか? >>28
アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。 >>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる 恵まれてない会社だと全員切る羽目になるって話だろｗ 31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな 日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの？ 日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。 >>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが 根幹のタームの綴りも知らん半可通に何を教われというのか >>44
そんな頭じゃ使いものにならんのも頷けるわ >>19
は？変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ？
そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ 何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった
今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね
アルゴリズムみたいにオーダー詰める楽しみはないけど… 両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。 vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる？ データ構造の基本は、以下の2つと、他にはハッシュがある
A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)
ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)
シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い どうも、お久しぶりです。スモモンガーです。（誰って感じだと思いますがそれで結構です）
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。
https://youtu.be/5m3kPHO2w98
以上、どうぞよろしくお願いします >>61
最初の数分見ましたが..
1) 何の探索なの？最初は「探索」と聞いて「グラフかな？」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね
2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います
3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います
また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です
4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね
以上、感想でした 64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます >>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。
まあ、原理は単純なアルゴリズムです >隣接するキーの最大値
これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。 >>61
印象としては
1. 要素間の差の最大値を求めるのに線形時間
2. 各要素の値の差が一定でないと性能を発揮しない（最大値を求めるのも含め）
3. 探索の最悪時間が線形時間、恐らく平均も線形時間
4. ソートされていなくても探索可能な条件が不明瞭
5. データの内容に探索コストが大きく左右される
例えば
1 2 4 9 15 24 100 120 1002 1225
とあった時、差の最大値は
1002-120=882
1002を探索すると
1002-1=1001, 1001/882=1
1002-2=1000, 1000/882=1
1002-4=998, 998/882=1
1002-9=993, 993/882=1
...
と線形時間になる（やり方あってるよね？）
演算している分、比較だけの線形探索より処理速度が遅くなる >>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます >>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる（ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる）
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う >>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います >>71
各要素間の差が一定であればO(1)、当たり前だけど、これは計算で求まる
各要素間の差の分布数が要素数に近づき、尚且つその落差が激しい場合
著しく線形時間になる
で、探索したい数値と差の最大値の商が1だった場合
その探索したい数値がある位置以下の数値探索はO(n)になる
データ列の後半に行くほど1回の演算で要素をステップする数が増えるけど
その移動は微々たるもの
データ列の内容に左右されることを差っ引いても、O(log n)からは程遠いと思う
詳しい計算は出来ないが、これを線形時間としても無理はないと思う
参考として
0 1 3 6 10 15 21 28 36 45
このデータ列では、15以下の探索はO(n)、
21は5回、28は4回、36は4回、45は3回の演算
結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな >>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ 確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回 最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか？もし、とんちんかんなこと言ってたらすいません。 >>74
www確かにそうかもしれませんね。
>>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。 状態遷移ってどういうステータス持てばいいの？
A と B のステータスがあって、お互いが切り替わるのに n秒 かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする
というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要？
過渡状態も状態？ >>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい >>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い 辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。 ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう？
x = xFactory.create(...);
y = yFactory.create(...);
if(x.typeCode() == X.Foo && y.typeCode() == Y.Hoge)
executeSpecial((Foo) x, (Hoge) y);
else if (...)
...
else
executeNormal(x, y); デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば 下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ 『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』
の優先度付きキューについてのプログラムについて質問です。
p.241の heapIncreaseKey(A, i, key) という関数内で、
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
というのがあります。
これがなぜ必要なのかが分かりません。
insert(key) を見れば分かるように、この本の使われ方では、
key < A[i] になることは決してありません。
よろしくお願いします。 完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。
ただ、作業やデバッグ用には必須であっても、その本の例示として必要か？と言われれば、確かにいらない気がする。 >>95-96
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の参考文献に
挙げられている『アルゴリズムイントロダクション』を見てみたら、全く同じプログラム
が載っていました。
完全にパクっていますね。
>>96
デバッグ用にどうして必要なのかが分かりません。
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか？
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。 >>98
こういうのが本当のパクり
訴えられたら負ける ■ このスレッドは過去ログ倉庫に格納されています
