データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 詳しいと言えるかどうかは別にしてAVL木に関する説明が分かりやすいと思ったのは次の本の該当箇所（§6.3）だ
浅野哲夫『データ構造』、アルゴリズムシリーズ１、近代科学社 (1992) 1つ言えるのはオブジェクト指向のなんかよりも
データ構造とアルゴリズムの方がよっぽど重要だということ。
昔はオブジェクト指向の勉強を頑張っていたけどそのときは
全然プログラミングがうまくならなかった。
現代の世の中はガチガチに設計されたライブラリを使って
コードを書くだけだから生半可なオブジェクト指向の知識なんて
ゴミ同然だよ。80年代90年代に考えられた思想とか、もうゴミに
なってしまった思想が多くて有害だよ。
結局現場でやることは「メソッドの使い方を求めてQiitaやStack OverFlowを
漁って成功するコードを見つけるまで疲れ果てる」ことに変わりはない。
せっかく勉強した内容が時代遅れで「裏切られる」ことのほうが多い。 一方、データ構造とアルゴリズムをガッツリと勉強してから
様々なデータ構造の使い方、問題の解決がうまくなった。
ブロックチェーンのアルゴリズムの理解や
データ分析の数学的演算がコーディング
できるようになってプログラミングが格段に楽しくなった。
スマートにオブジェクト指向で設計する力なんかより
「ゴリゴリとアルゴリズムを書く力」の方がよっぽど重要。
「再利用性」？「変更の影響」だって？そんなものゴミだね。
それは自分以外の人間のメリットのための技術であって、
自分へ還元されるためのメリットではない。
再利用性は自分の書いたコードなら信頼できるしコピペして使えばいい。
自分の書いたコードのコピペは全然ありだと思う。
適したメソッドが見つからなかったらQiitaを漁ったりせずに
自分でゼロから実装したほうが速い。
その場で手っ取り早くコードを生成しているから、
どんな既存コードにも頼っていないから俺の実装したコードは
依存性は低い。 ただし>>814-815は何かのアプリを作ったことはない >>815
一つ重要な視点を提供しましょうか
自分の記憶などあてになりません、3ヶ月前自分が書いたコードは、もはや他人が書いたコードとなんら変わりありません >>814-815はすでに解いたことのある問題なら
忘れたとしても、少し時間をかければ解けると考えている
つまり誰かが出した出題を解くという作業をしている >>>817, 818
自分のいつも使うアルゴリズムのパターンが身についていれば
そのパターンや命名規則から何をやっているかは解読できる。
読みにくくなるのは外部から取り込んだ機能の実行や
継承している部分。 >>819
やっぱり「解読」してるんだｗ
すでに証明済みの問題を自分の力で証明するという
お勉強をやってるだけだね 解読の工程は業務でも必要であるし
遊びとしても面白い
それが勉強になるならとても有益じゃん 「車輪」は大きさ、材質、シャフトの接合部の形、色…大まかな形や役割は似ているが微妙に違うものが無数にある。
ちょっとでもこれらの特徴がずれたものは他への転用を考えるとすぐに不具合となって使い物にならない。
車輪を最初に「発明」した人物はこれらの無数の車輪を全て発明したわけではない。
だから他の人が死ぬほど似たようなものを作っていたとしても自分で作る必要がある。
他人が作った車輪は無条件で役にたつわけがない、
手直しして組み込むより「自分の規格で」作った方が早い。 車輪が小さかったからゴム巻いたらなんとかなった
これがオブジェクト指向です 時代が違うからな。アルゴリズム考えてうんうん唸る時代は終わってるんだよ
今はそういうアルゴリズムが実装されたライブラリを組み合わせて
アプリを作る時代だってMITも言ってる
MIT｢今は基礎よりﾗｲﾌﾞﾗﾘ組み合わせてｱﾌﾟﾘ作る時代｣ [無断転載禁止]©2ch.net
https://medaka.5ch.net/test/read.cgi/prog/1462443213/
MITがSICPを教えなくなった理由
http://cpplover.blogspot.jp/2016/05/mitsicp.html
今日では、状況が変わっている。
今のエンジニアは、自分が完全に理解していない複雑なハードウェアのための
コードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する
巨大なライブラリ群の集合として存在している。
Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、
どのように組み合わせれば目的が達成できるのかを把握することに費やしている。
Sussman曰く、今日のプログラミングは、「より科学に近い。ライブラリを持ち寄って、
つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
そして、「目的を達成するために改造できるか」と考えるのだ」。
SICPの「合成による解析」という物の見方である、小さな、単純な部品を組み合わせて大きなシステムを作るということは、
もはや今日の状況にそぐわなくなった。今や、我々のプログラミングはつっつき回すことで行われている。 車輪の再利用だけ考えて車輪職人が居なくなるって話かな？ そうだね。そもそもソフトウェアは他の製品と違って
完全に同じものを複製するのに技術がいらないからね
コピーすればいいだけだし。
その点、何かを作る職人とはぜんぜん違うよね
そいういう寸分違わないものを作り出す職人は不要な業界 >>825
そして、今は鉄道以外のほぼすべてのタイヤの接地面はゴムです。
そういうところもオブジェクト指向と、似てますね。 >>826
この論理は完全にお花畑。
完全無欠のライブラリがありそれが唯一無二なら
つつっつき回すだけでいいだろうさ。
だけど現実はほぼ似たような機能で構文が違う、
それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
それに加わりローカルで作られた野良ライブラリがある。
当然人によってそれらの使い方の認識に齟齬が生まれる。
信用できるのは、自身の即興のデータ構造定義能力と、
アルゴリズム構築能力だけだ。 >>831
> だけど現実はほぼ似たような機能で構文が違う、
> それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
乱立しているからなんだっていうんだろう？
乱立してるから自分で作れってことにはならないよな？
何が言いたいんだろう
> それに加わりローカルで作られた野良ライブラリがある。
自分自身で作成したもの = 他人から見れば野良ライブラリだからね
野良ライブラリは作るべきじゃないね
だから乱立されている中のどれかを使うってことになるわけだけど
そういう結論を言いたかったんだよね？ >>831
データ構造作るだけだと付加価値が低いというか
ただの作業員でしかなくない？
新しい仮想通貨作るとかだったらすごいけど まあ言えるのは、データ構造やアルゴリズムを作るだけの仕事なんて無いってことだな
やりたいからといって、それで金がもらえるわけじゃない
金を出す方がやってもらいたいことをやって金が出る
似たようなものを自作して、乱立させたって
そんなものに金を出す人はいない >>835
うむ
>>834
やったことないやつには判らんよ >>827
いや、ちょっと違う
プログラマという職業が、車輪を一から設計できる職人群と
それを再利用する専門家へと二極化していくというお話だよ
この二極化は以前から言われていたことだけど、
それを天下のMITが言い切って行動に移したことに>>826の意義がある >>838
「職人」と「専門家」が逆ではないですか？ いや、逆ではないよ
MITは計算機工学に特化しているわけでもなく、
機械工学、ロボティクス、生産工学、データ解析といった
あらゆる工学分野の専門家を養成し輩出している
そういった(計算機工学を除く)大半の「専門家」の卵達にとって、
優先すべきは(旧コースでSchemを使って学んでいた)計算機の動作原理ではなく、
計算機の利用方法である、という趣旨
彼ら「専門家」は決して計算機工学の専門家ではないが、
それぞれの分野に特化した高度な専門技術を有し、
与えられた問題を解決する道具として計算機を効果的に活用できる どんな仕事でも、その道の研究者ってのはいるだろう。
例えば数学者とかな。だけど世の中で必要とされてるのは
塾の数学の先生だったりするわけさ
もっとも大学に行った人の殆どは、大学で専攻していたものとは
関係のない仕事をしているわけだけどな たとえばjsでオブジェクト構造をサーバに送りたいとする。
たったこれだけのことなのに邪魔くさい余計な機能が多すぎる。
わざわざ専用のクラスからインスタンス作って
専用の構文使ったりhttpヘッダー設定したりだ。
それでいてサーバ側では糞みたいな細かい仕様認識の違いでリクエストの内容が空だったりする。
サーバ側のコンフィグ見直したりjs側のコード見直したりするわけだ。
ログからライブラリのコード追っていくと大抵
過剰に技法使われてるから自ずと疑うべき探索
範囲は広くなる。
書き方はjQueryベースやangular typescriptなんかが混在してきて文法のちょっとした勘違いなんてのも生まれてくる。
だったらそんなライブラリ鼻っから信用しなけりゃいい。
ライブラリのインスタンスを介さずに多少原始的だが
文字列、数値 for文if文だけで大抵の問題は解決できる。
自力でJSON文字列に情報をぶち込んで送信してやれば、必ずサーバ側で取得できる。
サーバ側も下手なライブラリにパースさせないで自力でパースした方が慣れれば断然こちらの方が早い。
自力で作ったアルゴリズムは信用できるから
関数化しておいてまた似たような問題があったときに
使える。
俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
自分で作ったもの以外はそりゃ不便だろうよ。 > たとえばjsでオブジェクト構造をサーバに送りたいとする。
https://api.jquery.com/jquery.post/
$.post( "test.php", { name: "John", time: "2pm" } );
こうだね。で？ はい。このように他人の成果を利用して
目的を達成するのが今は重要って話です。 >>844
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
とりあえずお前が自力で作ったライブラリは
鼻っから信用しててないよ >>844
> 俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
> 自分で作ったもの以外はそりゃ不便だろうよ。
価値観の問題じゃない。単にお前が作ったコードに
バグがあるから使えないだけ。使わないんじゃない。使えない。
反論するならバグがない証拠を出すこと
テストコードをかけという話ね。
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
お前が書いたコードは鼻っから信用できない。するしないじゃない。できない。 みなさんお気づきだろうか
>>844と>>849は同じことを言っている jQueryはブラウザの差異を吸収するからね
同等のもの作ろうとしたら大変だよ
自前のコードを実装するのが汎用ライブラリを使うよりも早いとするなら
自前のコードは汎用ライブラリよりも機能が少ないものになる
要件がシンプルなら自作するのは効率が良いかもしれないね
システムをユーザのニーズに合わせてたら要件が複雑になり自作するメリットが得られない
ユーザがシステムの都合を忖度するならうまくいく
開発者にとっては桃源郷
開発者の幸せか、ユーザの幸せか
ぼくらはその選択を迫られてるんだ 役所が作る神エクセルなんてのはユーザがシステムの都合に合わせてる典型例じゃないか、自作コードに拘るのは神エクセルを作るのと変わらぬよ >>851
> 要件がシンプルなら自作するのは効率が良いかもしれないね
それは正しくない。要件はシンプルでも実装が大変なことがある。
そもそも「ライブラリの一機能の独自実装」などという要件は
実際には発生しない。これらは単に道具
要件を実装するのに、道具を使うか使わないかの問題
シンプルな要件でも、道具は使ったほうが効率は良いよ
もちろん道具を使えない人であれば、道具を使えるようになるまで時間が
かかるけど、それは素人がプロに速度でかなわないという人間の問題にすぎない
そう道具を使えないなら素人なんだよ。 >>850
同じことは言ってないな
>>844はよくわからないのはライブラリのせいだ
自分で作れば、そのライブラリよりもわかりやすくなるはずだ
って机上の空論を言ってるだけ りんごをむくのにピーラーを使うのもいいが、一度ナイフで剥くのを試すのも重要だし、かじってみるのもいい。
道具が解決する問題がなんなのか、体験することは、多くの人にとって有益だと思う（経験主義者） そこでピーラーを作るのは大変だとか見当違いの所に流れていくやつがいる。
ピーラー（ライブラリ）を使うか、ナイフを使うかだ
ライブラリ？中見たけどわけのわからないことをしてる
理解できない。ナイフのほうが単純だ。ナイフなら作れる。
なぜか作る話になってしまっている。 例え話は物事を理解してなくてもそれらしく見せるから知ったか振りが捗りますなあ MVC, DAO, O/Rマッピングの発展形として、
俺は「R/Rマッピング(リクエスト/リレーショナルマッピング)」を
提唱したい。
そもそもDB上のカラムと本当に対応付けたいのは画面上のname属性
なんだよなぁ。
オブジェクトを必ず介する必要はない。
(処理が込み入ってきたら定義してもいい程度。)
まず前提として、DBのカラム名とHTML上のname属性を
必ず同じキーにすることを前提とする。(HTML上に関係ない
キーがあっても問題はない。)
その前提の上でDBのカラム名一覧を先に取得しておき、
カラム名リストと、受信したname属性のキーをマッチングして、
マッチングした時にそのキーから取得した値をSQLに突っ込んで
クエリを行う。
こうすることによって、プログラミング言語処理の中で
具体的な「項目名」をほとんど登場させずに処理することができる。
自分でやったらすごく便利だった。
こうなるとそもそもモデルとかDAOとかいらなくね?
ってなって来たよ。
項目数がどんなに二十, 三十と並んでいようがダラダラと羅列しない。
特別な処理を入れたいときだけその項目のカラム名を使って
ifで分岐して日付変換とかをおこなう。
その特別な処理も日付,範囲系、選択肢系などパターンを押さえれば、
めちゃめちゃ簡素化できる。 あ、はい、4行ぐらいしか読んでないけど、
そのリクエストに含まれる名前 = オブジェクトのフィールド名なんだから
あんたが言ってるリクエスト = オブジェクトってこと
あとはストレージをなんにするかの話。
ODBMS（オブジェクトデータベース）を使えばそのまま読み書きできる
だけど、なんやかんやでリレーショナルデータベースを使わないといかんから
O/Rマッピングが必要になる >>886
あとRailsでも勉強しようね
普通は画面のname属性 = データーベースのフィールド名になってるから
（もちろん必要なら対応してないものも作れるけど） 二層CRUDオモチャ
昔から誰もが一回は考えるアイデアだよ
画面起点だとどうしてもアプリケーションロジックの居場所がないから簡単に作れてもアプリとしての価値が無い
DB起点だとSQLにアプリケーションロジックを埋め込んんで最低限のアプリの体裁は保てるけど保守性が最悪で使い物にならない
という理由から廃れた
なので今はオブジェクト指向の言語でモデルを書いてモデルから画面やDBを生成して微調整しようってのがスタンダード
これなら労力をかけずに豊かな振る舞いを持つアプリケーションを作れるしロジックがモデルに集まるから保守性も高い >>869
モデルを作るとしても処理が複雑になる部分だけ
部分的でいいんじゃないか？
全ての要素に対して網羅的にモデルつくって
セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
気がするんだが。
なにせ機能を複製する時にこれらのずらずら並んだモデルオブジェクト名や
キーの名前をを置換しなけりゃならない。
ならない。 > セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
それはJavaだけ
Javaが馬鹿げているだけ >>859
さてリンゴをむくか、
ピーラーがないと剥けないから探すか、
あれ、どこにしまったかな？
この引き出しにもこの棚にもない。
道具だらけで見つからない。
店に買いに行こう、たくさんのピーラーが並
んでいてどれを選ぼうか？
ようやく買ってきて構築しているけど、
どうや刃が付け替え式で色々な刃が付け替えられる
ようだ。
刃を買い忘れたからまた買いに行くか…
はぁはぁ…すごい刃を買ったぞ！今構築中だ。
おや？この刃はリンゴを剥く用途には対応して
ないようだ。もう疲れたしこれ無理だろ。
ピーラーが無いから俺にはリンゴを剥くのは
無理だ。前は引き出しにあったからむけたけど
今はできなくなった。
一方、いつも愛用のナイフで剥いてるならそう
はならない。
いつもポッケに入れているからなくさないし、
最悪自作で調達できる。
使い慣れてるからピーラー使うやつと遜色ないスピードで剥けるし形も綺麗に剥ける。 Rails なんか、全自動！
DB の表の構造が定義された、メタテーブルを参照して、
表の列名なども自動的に取得する >>870
それでずらずら並んで嫌だというなら、おまえのやり方だと画面定義もずらずらならぶし、テーブル定義やSQLがずらずら並んで更にわけわからなくなるだろ 最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。 NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ扱えるようになったし、
トランザクションあった方が便利なことやっぱり多いし、
SQLってなんだかんだ言って表現力高いし。 pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか？ AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。
誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。 >>897
どういう意味？
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ？)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構 論理的思考力を上げるために将棋をしなさい。数学など不要です。 >>898
数学科の数学と物理科の数学とコンピュータの数学は違う（笑） >>901
最適性の証明のことを言ってるの？
いずれにせよこの問題に限った話じゃないよね？
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。
>>902
違わない
算術、代数、幾何、解析だ全て 例えば、バブルソートには
数学の、えっと、幾何？の知識が必要だろ？
え？ レス数が900を超えています。1000を超えると表示できなくなるよ。
