データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「UI」とか外部の窓口になったり、
外部デバイスとの接続ポイントになるコネクタのことを言うじゃん。
オブジェクトの型のことを「インタフェース」なんて言ったら誤解を招くだろ。 >>695
interfaceには境界面とか接点の意味がある
クラスが持つ他との接点の意味で合ってる 外部の窓口になったり、外部デバイスとの接続ポイントになるのが抽象メソッドだから。
つまりそれしか定義されてないということは、インターフェースそのものと言っていいだろう。 デザパタスキル、エンベッデイドスキルなんやかや言うが、みんな大事な部分は閃きなんだがなぁ・・・
作曲と同じ。 閃き・・・ とどのつまり、神が書かせているという事。
そこを理解できない限り、そのプログラマーは聖職では無い。 神などと妄想するようになったら科学の全否定の始まり。無知が故の過ち。 神「共通化せよ――」
僕「はい」
神「ごめん間違えた――」
僕「うわぁぁああぁああ！！！」 以下で定義される写像 A : N × N → N を Ackermann 関数という。
A(1, j) = 2^j for j = 1, 2, 3, …
A(i, 1) = A(i-1, 2) for i = 2, 3, 4, …
A(i, j) = A(i-1, A(i, j-1)) for i = 2, 3, 4, … for j = 2, 3, 4, …
α(m, n) = min {i ≧ 1 | A(i, floor(m/n)) > log_2(n)}
で定義される写像 α : {(m, n) | m, n ∈ N, m ≧ n} → N を Ackermann 逆関数という。
なぜ、この α を Ackermann 関数の逆関数と呼ぶのでしょうか？ courseraのセジウィックとウエインの講義を受講しています。
プログラミングの課題のチェックが超厳しいですね。
'if' is not followed by whitespace.
「if」の後ろにスペースを入れないといけないなんて初めて聞きました。
そんなことまで強制されたらたまりませんね。 大概のプロジェクトで採用されてるスタイルだから従っとけ
スペース軽視するやつ多すぎ >>703
K&R2 に従っておけば文句が来ることはない
if ()
while ()
for () 一般的なコーディングルールには従ったほうがよい
最近の言語環境では放っておいてもツッコミ入れてくれたりもするが 業務システムでオブジェクト指向不要って意見はどう思いますか
大抵スパゲティークエリになってる印象ですが 途中からオブジェクト指向混ぜられても困るだろ
実行効率や記述効率は悪くたって別に構わないのだから（ここわかってない人多し）、プロジェクトに来た全員が理解利用できる書き方が最優先
無論技術的にも業務的にもうんこだが、そこを追求すべき場所ではないところで勝手に追及を始めるのはそれこそうんこのやること
ゼロからオーバーホールを提案してもよいが最後まで自己責任で看取れ >>709
サブクエリ五重の塔を見て上長にキツいと報告したら世界にはバベルの塔がいっぱいあるのに根をあげるなと叱られました
せめて何をしたいのかドキュメント欲しいと言ったらコードが全てだとも言われました
IT業界の厳しさを知りました courseraのセジウィックとウエインの講義の最初の課題であるパーコレーションだけど
backwashを防ぐにはどうすればいいんですか？ あ、分かりました。
virtual topにはつなぐがvirtual bottomにはつながないUF
virtual topにもvirtual bottomにもつなぐUF
を使えばいいんですね。 デザインパターンで規定されるいろいろなクラスがあるけど
これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
属すのか知りたい。
たとえばStateパターンがあった場合に、
・<<interface>>State
・ConcreteState x n
・Context
があったとき、
これらは、クラスを配置する場所的に
・プレゼンテーション層(UI層)
・App層
・サービス層
・ビジネスロジック層
・パーシステンス層
のどこの層として配置すればいいのか > デザインパターンで規定されるいろいろなクラスがあるけど
> これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
> 属すのか知りたい。
デザパタはレイヤ化アーキテクチャに属すものだという考え方が謎なんだけど >>719
どの層にも配置していいんじゃね
その層の機能とかを実現するのにそのデザインパターンが必要なら使えばいいのではないか
レイヤーとデザインパターンは独立に組み合わせ可能と思う デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う 1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。
そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。 めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか 答えは500以下です。
1 から 1000 までの整数を 2^n * (2*m + 1) の形で表す。
2*m + 1 の部分は、
2*0 + 1, 2*1 + 1, …, 2*499 + 1
の500個のパターンのいずれかに一致する。
よって、1 から 1000 までの整数の中から501個以上の異なる整数を選び出せば、
その中には、かならず、
2^n1 * (2*m + 1), 2^n2 * (2*m + 1)
という二つの整数が含まれる。
この二つの整数は一方が他方を割り切る。 どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？ >>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？ >>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ >>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。
ただ、本当に網羅できるのか証明はまだできてません。
これ以上はスレチも甚だしいので、独りで頑張ってみます。
流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。 >>729
整数を 2 で割れるだけ割ると 2^n * (2*m + 1) の形になります。
例：
120 = 2^3 * 15 = 2^3 * (2*7 + 1)
この場合、 n = 3, m = 7 です。 1 = 2^0 * (2*0 + 1)
2 = 2^1 * (2*0 + 1)
3 = 2^0 * (2*1 + 1)
…
999 = 2^0 * (2*499 + 1)
1000 = 2^3 * (2*62 + 1)
となります。
1, 2, …, 1000 をすべて
2^n * (2*m + 1)
という形に表します。
m は 0 から 499 までの 500 個の整数のどれかになります。
ですので、 1, 2, …, 1000 の中から 501 個以上の整数を取ってきて、それらすべてを
2^n * (2*m + 1)
という形に表すと、
2*m + 1
の部分が同じになるような異なる2つの整数があります。
2*m + 1 の部分は同じで、 2^n の部分が異なります。それら2つの整数は
2^n1 * (2*m + 1), 2^n2 * (2*m + 1) のようにあらわされます。 n1 < n2 と仮定して一般性を失いません。
2^n2 * (2*m + 1) は 2^n1 * (2*m + 1) で割り切れます。 2^n2 * (2*m + 1) ÷ 2^n1 * (2*m + 1) = 2^(n2-n1) 500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？ >>726
{501, 502, …, 1000} でもOKですね。 >>735
ceiling(n/2)
ではないでしょうか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
java.util.List
java.util.Stack
java.util.Queue
は最低だそうですね。
Best practices: Use our implementations of Stack, Queue, and Bag.
だそうです。 最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？
また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
なんかやけに課題が厳しくないですか？ セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？ courseraのセジウィックとウエインの講義を聴講している人はいますか？ >>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ あ、仕様Memory量の見積を勘違いしていました。
できそうですね。
Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。 あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。
どうすればいいんですかね？
もう少しだけメモリの制限が緩ければ実現可能ですが。 Performance requirements.
Your randomized queue implementation must support each randomized queue
operation (besides creating an iterator) in constant amortized time.
That is, any sequence of m randomized queue operations (starting from an empty
queue) must take at most cm steps in the worst case, for some constant c.
↑これと↓を両立させることはできるのでしょうか？
A randomized queue containing n items must use at most 48n + 192 bytes of
memory. あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
メモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
無駄が全くないときのメモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 これから実装しますが、また100点満点中100点になりそうです。 あ、やっぱりだめですね。
dequeue の計算量がネックになりますね。 あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。 経路探査でray cast algorithmというのがあるらしいんだが、わかりやすいサイトない？ おちんちん に ベロが届くアルゴリズムを教えて下さい。 >>760
「お金が儲かるアルゴリズム」で儲かる方法を書いた本を売る 関数型言語ってUML使うんですか?
クラス図とかメソッドどう書くんだろうと ちょっと質問させてください。
状況: トータル1000行くらいある巨大メソッドの改修
言語; PHPだがどの言語でもそう関係のない内容
・まずコントローラのアクションメソッドがあって
public function action(引数){
/* 500行くらいの既存コード */
/*今回改修を加えたい50行位のコード */
/* 500行位の既存コード */
}
となっている。 ・ここで、改修要件は、中間にある「/* 50行くらいの既存コード */」を
if文で分岐させて分岐次第で違う処理を入れる。というもの。
したがって、
public function action(引数){
/* 500行くらいの既存コード */
if(条件1){
/* 新規追加コード */
if(条件1-1){
/* 新規追加コード */
}else{
/* 既存コード */
}
}else if(条件2){
/* 新規追加コード */
}else{
/* 既存コード */
}
/* 500行位の既存コード */
}
みたいにひたすら条件分岐して既存コードと新規追加コード
が何回も実行されるようにしたい。 ・ここで、俺は「/* 既存コード */」の中身を知っている必要は
ないと思った。だから、このコードの詳細を読まずに「func()」
として「action()メソッド内部」に切り出した。
・外部に切り出したのではなく、内部に切り出したのはその処理が
他のアクションメソッドでは共有されるような汎用的なものではないだろうと
判断したのと、そのメソッド内で処理を追いやすいようにというのを
優先させたため。何より、その処理内で使っている関数内ローカル変数の
依存性の関係上そうせざるを得ないと思った。
public function action(引数){
/* 500行くらいの既存コード */
private function __legacy(){
/* 50行くらいの既存コード */
}
if(条件1){
/* 新規追加コード */
if(条件1-1){
/* 新規追加コード */
}else{
__legacy();
}
}else if(条件2){
/* 新規追加コード */
}else{
__legacy();
}
/* 500行位の既存コード */
} ・【訂正】上記で「func()」として切り出したと言っているが、
「__legacy()」に変更しました。すみません。
・上記のように改修した所、レビューを受けたときに怒られた。
・まず、「この__legacy()の中身ちゃんと読んだ? 把握して書いている?」
という指摘。
・そして「ここメソッド内だけどどうして関数定義しているの？
他の人そんなことしてないでしょ。どうして変わったことするの？」
という指摘。
・まず1つめの指摘に対して異議がある。
ブラックボックス化しなければ大規模なコードは書けないんじゃない？
ということが言いたい。ライブラリとかフレームワークの機能も全部
先に中身をよくよく読んでおかなければ使ってはいけないことになるじゃん。
・2つの指摘に対して、
「周りの人がやっていること」が正しいとは思えない。
処理を切り出していないから1000行もある巨大なメソッドになっていて、
汚いコメントで汚しながら機能追加しまくっているんじゃないのかと。
ローカル変数を使いまくりの同じ処理を何回も実行するのに
他に良い手段があるとしたら皆さんに教えて頂きたい。 汎用的でない50行のコードをコピペしてるんなら関数化してもインライン化してもどっちもどっちだな
DRYを意識したのかもしれんがKISSが抜けてる
それにブラックボックスが許されるのは有名なライブラリやフレームワークのようなテストにテストを重ね、かつ多くの利用者による実績があるものだけだよ
社内コードなんて大概クソコードだしブラックボックスにしても後で痛い目を見るのは自分や他の開発者
何なら単に今把握するだけじゃなくて、未来の自分や開発者のためにわかりにくいところをコメントで説明書きしてもいいくらいだ
あと関数内関数より無名関数を変数に代入した方がいいんじゃね
そもそも新規追加したif文も詳細はわからないがデータよりもロジックに寄っててわかりにくそうな匂いがプンプンする
それに上司には理由を聞かれてるんだから同じローカル変数に別の値を入れて使い回すことの危険性、関数化による参照透明の確保や保守性、メンテナンス性の向上を論理的に答えればいいだけ >>770
レビュアーが言ってることを正しいと仮定すれば
・1つ目の指摘は既存のコードがカプセル化されてないからだ
・2つ目の指摘はリファクタリングするだけの時間やお金や技術がないからだ
という前提が必要になるから、まあそういうことなんじゃなかろうかと
残念なコードっていうのはあるからね
それを修正する費用と修正して得られる効果を比較対照して
これだけの効果があるんだからこうするべきだと提案をまとめて
説得するのがいいのだろうけど、技術に理解のある人がいないとなかなか難しいね
レビュアーの立場で考えると以下の作業があるんじゃないかと
・改修要件を満たす改修
・既存のコードをカプセル化する
・リファクタリングする
レビュアーは既存のコードとの一貫性を維持しつつ
改修要件を満たす最小の改修をやって欲しいのだろうね
たとえ汚らしいコードであってもいままで動いてきた実績があると
変更に対しては既存のコードをできるだけ変えないようにと保守的になるものだよ
レビュアーがそれをきちんと説明できればいんだけど
コードはクソ、レビュアーもクソなんてことはザラにあるんですよこれが >>771 なるほど勉強になります。
少し質問したいが、
・「KISSが抜けている」と言うのはどこらへんでしょうか？
・関数内関数と無名関数の変数化の違いがわからないので教えてください。
(面倒なら調べます。)
・あなたならどう対応する？
・「理由を聞かれてるんだから答えればいいだけ。」
→多分論理的に説明したら「じゃあもう何も教えないよ。好きにやって」
が返って来ると思われる。
そう言われると、必要な情報も来なくなるし聞けなくなる。 >>772
なるほど、俺自身が「既存コードのカプセル化」と
「改修要件」という概念と「改修要件を最小に満たす」という
ことについて詳しくないことに問題がありそうだね。
ありがとう、ここらへんをキーワードにして調べてみます。 >>773
多分もっと細かく汎用的な(publicにできる)関数の集まりに分解して、汎用的でない部分は最小限に出来るんじゃないかなーって思った
実際のコード見てないから予想だけど
関数内関数だとわざわざprivateかけないと外からアクセス出来ちゃうし、元の親関数抜けても子関数が死なない
そもそも上司とあんまり仲良くないの？
論理的にメリットを売り込んだときに感情論で否定されるくらいの関係性だと下っ端プログラマーはしんどいよ？
まぁ俺ならその段階なら折れて普通にコピペして、もっと実績残して仲良くなってから似たような案件のときに改めて売り込むかな ひとつのメソッドに1000行も書かせる会社はまず危ない
アルゴリズムとかそれ以前 >>775
なるほど、「まるまる関数化」というのが
ちゃんと機能を意識してカプセル化していないってことか。
一応privateは欠けているけど、関数オブジェクトと
関数定義の違いはあまり詳しくないね。そうか、親関数が抜けたとき
子関数が死ぬか否かの違いがあるわけね。
入りたてだから人間関係はいいも悪いもない。
ただ、本来責任ある人はバタバタしていて、経験ある人が自分の意志で
新人のレビューをバラバラに行っている感じ。
>>776
会社がそうさせているというよりはそれぞれの人員が
これまでの追加の仕方を真似て機能追加した結果メソッドがブクブクと太っている
という状況に見える。
メソッド内で各追加機能がコメントで区画されていてそれなら
別関数にすりゃいいのにって思っている。
俺をレビューした人も、別に会社の工程でそうなっているわけでなく、
進捗を見たかったからだと思うが、書き直しを要求してきて困惑している。
ただ彼は業務要件については圧倒的に俺より詳しいから無視すべきではないと
思っている。 >>777
カプセル化はオブジェクト指向において関連するものをまとめる作業だから、ちょっと違うかな？
どちらかというと今回の話は関数型プログラミングの考え方に近い
まぁぶっちゃけ職場のコードなんて割り切らんとやってけんよ
出世してコーディングスタイルに口を出せるようになる日を待つしかない >>777
そんな仕事を放置する会社、と言うことだ 名前だらけのコードってどうやって解読すればいいんだ？
変数化するとそのデータの型が何なのか物量的にどれだけの
規模が格納されているかが見えない。
もちろんログに吐けば見えるが、吐き出さなければパッと見で
何をどう処理しているのか分からない。 関数型言語の仕様書ってUMLで良いの?
データと振る舞い分離してるからクラス図使って良いのかなと >>783
英語敷居たけえ
まあデータと振る舞いを書いたクラス設計は関数型言語でも同じように使えるし問題ないか 今どきデザインパターンって死語なの？
ちょっと参照したいことがあって書店でデザインパターンの本を探したけど見つからなかった。
リファクタリングの本はあって多少はデザインパターンの話も出てきたけど。
結局は家に帰ってから10年前に買ったデザインパターンの本を参照するしかなかった。 ブームが去っただけかな？
銀の弾丸などないと気がついただけ デザパタは元々バカの為にまとめられたものだったけどバカには無理だった代物
一方リファクタリングはバカ程好むからなかなか廃れない 21世紀最新のデザインパターン本て誰か書かないかね
Singleton→大抵はstaticでOK
みたいなの デザインパターンて結局何だったんだ？
高い本まで買ったがほとんど身に付かなかったな >>793
もともと C++ 界隈で発生したテーマですので、C++ をやっているとデザパタの意義がよくわかります
C++ は細かしいことまで自分で記述しなければならないので、こういう大枠思考がもてはやされたのだと思います ■ このスレッドは過去ログ倉庫に格納されています
