データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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

**デフォルトの名無しさん** · 2016/06/19(日) 14:52:46.31

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

**デフォルトの名無しさん** · 2016/06/19(日) 15:04:05.74

>1 乙

**デフォルトの名無しさん** · 2016/06/19(日) 16:13:42.43

>>2
え、変なのはお前だろ。http://hissi.org/read.php/tech/20160619/NUt2U0tkTC8.html

**デフォルトの名無しさん** · 2016/06/19(日) 17:17:34.69

ruby って変な人が多いんだね，俺も今 ruby をマスターしようと必死ではあるが

**デフォルトの名無しさん** · 2016/06/19(日) 17:37:31.60

>>2
盛大な自演だったってこと？

**デフォルトの名無しさん** · 2016/06/19(日) 19:39:00.16

Haskellって勉強する意味ある？
実用性はないよね？

**デフォルトの名無しさん** · 2016/06/19(日) 19:46:20.75

雇われプログラマには不要

**デフォルトの名無しさん** · 2016/06/19(日) 20:49:00.89

なぜ、HaskellやSchemeをありがたがる人がいるの？
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ？

**デフォルトの名無しさん** · 2016/06/19(日) 20:49:49.63

MITのコンピュータの入門書もSchemeを使っていたりする。

**デフォルトの名無しさん** · 2016/06/19(日) 20:59:07.46

言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。

**デフォルトの名無しさん** · 2016/06/19(日) 23:46:31.97

haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ

一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

**デフォルトの名無しさん** · 2016/06/20(月) 00:15:53.04

>>12
マジかよ

**デフォルトの名無しさん** · 2016/06/20(月) 00:57:04.30

>>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

ライブラリを駆使するのが今のプログラマに求められている技術だからな。

MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい（たとえば、ロボットを制御するソフトウェアを書くなど）

**デフォルトの名無しさん** · 2016/06/20(月) 06:52:18.91

HaskellやSchemeの利点は？
少なくとも、分かりにくいよね。

**デフォルトの名無しさん** · 2016/06/20(月) 08:05:44.62

オブジェクト指向程ではないけどな

**デフォルトの名無しさん** · 2016/06/20(月) 12:30:23.83

エンジニアの選定時の足切りにちょうどいいよ

**デフォルトの名無しさん** · 2016/06/20(月) 18:11:51.85

その基準で剪定できるのはかなり恵まれてる気が

**デフォルトの名無しさん** · 2016/06/20(月) 18:23:24.04

>>14
>今日のプログラミングは、「より科学に近い。

ここは変だな
「より工学に近い。」
というなら判るが

**デフォルトの名無しさん** · 2016/06/20(月) 18:31:26.30

SICPをプログラミング初学者に教えるというのは確かに異様だよね。

やっとまともになったというだけの話。

**デフォルトの名無しさん** · 2016/06/20(月) 18:35:05.72

コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの？

**デフォルトの名無しさん** · 2016/06/20(月) 18:50:31.57

アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。

**デフォルトの名無しさん** · 2016/06/20(月) 18:52:50.90

なんか計算の理論とかのほうが上みたいな感じじゃない？

**デフォルトの名無しさん** · 2016/06/20(月) 18:53:47.25

コンピュータサイエンスで最も重要な科目は、コンパイラとかOS？

**デフォルトの名無しさん** · 2016/06/20(月) 18:53:55.59

自演乙

**デフォルトの名無しさん** · 2016/06/20(月) 19:14:10.85

>>18
この道３０年の修業でようやく一人前

**デフォルトの名無しさん** · 2016/06/20(月) 20:44:30.75

寿司職人乙

**デフォルトの名無しさん** · 2016/06/20(月) 20:58:16.94

schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな

**デフォルトの名無しさん** · 2016/06/20(月) 21:06:41.52

>>28
javaでよくない？

**デフォルトの名無しさん** · 2016/06/20(月) 21:24:25.76

javaでconsを表現するときにどうすればいいか知ってますか?

**デフォルトの名無しさん** · 2016/06/20(月) 21:29:28.84

>>28

アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。

**デフォルトの名無しさん** · 2016/06/20(月) 21:47:01.99

>>27
植木職人

**デフォルトの名無しさん** · 2016/06/20(月) 22:10:02.53

>>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる

**デフォルトの名無しさん** · 2016/06/20(月) 22:22:55.57

恵まれてない会社だと全員切る羽目になるって話だろｗ

**デフォルトの名無しさん** · 2016/06/20(月) 22:43:48.30

31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな

**デフォルトの名無しさん** · 2016/06/20(月) 22:49:30.47

引用できないやつに言われると

**デフォルトの名無しさん** · 2016/06/20(月) 22:50:33.93

スマホで>>うつのめんどいんだよ

**デフォルトの名無しさん** · 2016/06/22(水) 04:43:48.40

日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
http://news.mynavi.jp/news/2016/06/21/172/

新型半導体コンピュータの実用化に向けて、
要素間の複雑なつながりを規則的な構造に自動変換する前処理アルゴリズムを開発
http://www.hitachi.co.jp/New/cnews/month/2016/06/0621a.html

関連記事
日立、量子コンピュータに匹敵する性能の室温動作の新型コンピュータを試作
http://news.mynavi.jp/news/2015/02/23/121/

**デフォルトの名無しさん** · 2016/06/22(水) 07:14:40.76

日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの？

**デフォルトの名無しさん** · 2016/06/22(水) 07:53:05.39

>>39
まともとは？

**デフォルトの名無しさん** · 2016/06/22(水) 07:59:50.23

日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。

**デフォルトの名無しさん** · 2016/06/22(水) 08:00:26.15

杉原厚吉の本は特にひどいと思った。

**デフォルトの名無しさん** · 2016/06/22(水) 11:07:15.76

>>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる

**デフォルトの名無しさん** · 2016/06/22(水) 12:53:15.55

まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが

**デフォルトの名無しさん** · 2016/06/22(水) 13:50:41.86

>>44
1単語に3箇所もミス入れるなよ

**デフォルトの名無しさん** · 2016/06/22(水) 14:13:53.39

根幹のタームの綴りも知らん半可通に何を教われというのか

**デフォルトの名無しさん** · 2016/06/22(水) 14:17:48.79

3ヶ所もあると誤り訂正も利かないんじゃまいか

**デフォルトの名無しさん** · 2016/06/22(水) 14:22:16.34

バースト発生させんな

**デフォルトの名無しさん** · 2016/06/22(水) 15:16:40.79

????????????

**デフォルトの名無しさん** · 2016/06/22(水) 21:44:16.49

>>44
そんな頭じゃ使いものにならんのも頷けるわ

**デフォルトの名無しさん** · 2016/06/22(水) 22:23:26.91

こんな揚げ足とりの老害から何を学べと?

**デフォルトの名無しさん** · 2016/06/22(水) 22:52:24.12

馬鹿の自己紹介されても困る

**デフォルトの名無しさん** · 2016/06/24(金) 11:47:43.21

>>19
は？変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ？

そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ

**デフォルトの名無しさん** · 2016/07/15(金) 12:10:18.78

何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな

**デフォルトの名無しさん** · 2016/07/16(土) 08:00:53.05

アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね

アルゴリズムみたいにオーダー詰める楽しみはないけど…

**デフォルトの名無しさん** · 2016/07/18(月) 09:37:52.19

両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。

**デフォルトの名無しさん** · 2016/07/21(木) 23:06:49.37

vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる？

**デフォルトの名無しさん** · 2016/07/22(金) 07:32:19.08

データ構造の基本は、以下の2つと、他にはハッシュがある

A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)

ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)

シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い

**デフォルトの名無しさん** · 2016/07/26(火) 06:56:53.95

letの時代がもうすぐそこまで来ているよね

**デフォルトの名無しさん** · 2016/07/26(火) 14:27:18.12

let
-------
　λ

**スモモンガー** · 2016/09/23(金) 22:08:49.88

どうも、お久しぶりです。スモモンガーです。（誰って感じだと思いますがそれで結構です）
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします

**デフォルトの名無しさん** · 2016/09/23(金) 22:16:41.76

誰だ

**デフォルトの名無しさん** · 2016/09/23(金) 22:42:52.63

帰れ

**デフォルトの名無しさん** · 2016/09/24(土) 09:14:59.70

>>61
最初の数分見ましたが..

1) 何の探索なの？最初は「探索」と聞いて「グラフかな？」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね

2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います

3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います

また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です

4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね

以上、感想でした

**デフォルトの名無しさん** · 2016/09/24(土) 09:32:41.92

64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます

**デフォルトの名無しさん** · 2016/09/24(土) 09:49:16.96

動画見るの面倒だから3行で説明して

**デフォルトの名無しさん** · 2016/09/24(土) 09:53:53.39

ご
み
だ

**デフォルトの名無しさん** · 2016/09/24(土) 09:55:26.18

>>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。

まあ、原理は単純なアルゴリズムです

**デフォルトの名無しさん** · 2016/09/24(土) 10:46:59.06

>隣接するキーの最大値

これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。

**デフォルトの名無しさん** · 2016/09/24(土) 10:49:01.89

>>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
...
と線形時間になる（やり方あってるよね？）
演算している分、比較だけの線形探索より処理速度が遅くなる

**デフォルトの名無しさん** · 2016/09/24(土) 11:09:23.58

>>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます

**デフォルトの名無しさん** · 2016/09/25(日) 01:17:16.51

>>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる（ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる）
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う

**デフォルトの名無しさん** · 2016/09/25(日) 09:29:52.06

>>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います

**デフォルトの名無しさん** · 2016/09/25(日) 12:26:29.96

>>67
ごめん
みたけど
だめだこりゃ

**デフォルトの名無しさん** · 2016/09/25(日) 12:52:11.14

>>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回の演算

結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな

**デフォルトの名無しさん** · 2016/09/25(日) 14:20:01.83

>>74
８８

**デフォルトの名無しさん** · 2016/09/26(月) 13:42:01.27

>>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ

**スモモンガー** · 2016/09/26(月) 20:32:40.67

確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回　最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか？もし、とんちんかんなこと言ってたらすいません。

**デフォルトの名無しさん** · 2016/09/26(月) 20:37:55.45

>>74
www確かにそうかもしれませんね。
>>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。

**デフォルトの名無しさん** · 2016/10/16(日) 18:51:48.49

状態遷移ってどういうステータス持てばいいの？

A と B のステータスがあって、お互いが切り替わるのに n秒かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要？
過渡状態も状態？

**デフォルトの名無しさん** · 2016/10/17(月) 07:56:46.27

>>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい

**デフォルトの名無しさん** · 2016/10/17(月) 15:43:18.44

>>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い