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

1デフォルトの名無しさん 転載ダメ©2ch.net2016/06/19(日) 14:47:29.63ID:5KvSKdL/
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

                  京都大学霊長類研究所

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

745デフォルトの名無しさん2017/12/04(月) 13:54:02.89ID:fGqdieY2
>>740
好きなようにするのが自然

746デフォルトの名無しさん2017/12/05(火) 09:10:03.39ID:bL4Z2L1G
↓この仕様の RandomizedQueue の実装できる人いますか?

http://coursera.cs.princeton.edu/algs4/assignments/queues.html

747デフォルトの名無しさん2017/12/05(火) 09:40:42.14ID:71Ul9rRS
>>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ

748デフォルトの名無しさん2017/12/05(火) 09:45:48.47ID:afEItlvW
松坂君につきスルー推奨

749デフォルトの名無しさん2017/12/05(火) 12:21:40.49ID:bL4Z2L1G
あ、仕様Memory量の見積を勘違いしていました。

できそうですね。

Item 型のデータを格納する Linked List

Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。

750デフォルトの名無しさん2017/12/05(火) 12:25:30.33ID:bL4Z2L1G
あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。

どうすればいいんですかね?

もう少しだけメモリの制限が緩ければ実現可能ですが。

751デフォルトの名無しさん2017/12/05(火) 12:30:24.08ID:bL4Z2L1G
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.

752デフォルトの名無しさん2017/12/05(火) 13:24:03.96ID:bL4Z2L1G
あ、なんだ

簡単でしたね。

Item[] 型の Resizing Array を使えば、

メモリ使用量 〜 8*n

だから、4倍くらいメモリを無駄に使っても

48*n を超えませんね。

753デフォルトの名無しさん2017/12/05(火) 13:25:09.16ID:bL4Z2L1G
あ、なんだ

簡単でしたね。

Item[] 型の Resizing Array を使えば、

無駄が全くないときのメモリ使用量 〜 8*n

だから、4倍くらいメモリを無駄に使っても

48*n を超えませんね。

754デフォルトの名無しさん2017/12/05(火) 13:27:33.45ID:bL4Z2L1G
これから実装しますが、また100点満点中100点になりそうです。

755デフォルトの名無しさん2017/12/05(火) 13:43:27.58ID:bL4Z2L1G
あ、やっぱりだめですね。

dequeue の計算量がネックになりますね。

756デフォルトの名無しさん2017/12/05(火) 13:45:25.54ID:bL4Z2L1G
あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。

757デフォルトの名無しさん2017/12/05(火) 16:58:02.34ID:Z65eXqg0
本日のNGID:bL4Z2L1G

758デフォルトの名無しさん2017/12/05(火) 21:20:28.14ID:YaGuI/6t
経路探査でray cast algorithmというのがあるらしいんだが、わかりやすいサイトない?

759遊園2017/12/07(木) 01:30:59.64ID:AoT+leNM
おちんちん に ベロが届くアルゴリズムを教えて下さい。

760デフォルトの名無しさん2017/12/07(木) 09:29:15.88ID:lQf/9LHk
お金が儲かるアルゴリズムを教えてください

761デフォルトの名無しさん2017/12/08(金) 13:48:57.43ID:6WtIjESa

762デフォルトの名無しさん2017/12/09(土) 02:58:56.19ID:ouHX+Izy
>>760
「お金が儲かるアルゴリズム」で儲かる方法を書いた本を売る

763デフォルトの名無しさん2017/12/09(土) 09:08:05.27ID:hr/9uBAF
子供の言い返しみたい

764デフォルトの名無しさん2017/12/09(土) 12:25:33.81ID:GX7M220U
それは結構知能が高い子供だなw

765デフォルトの名無しさん2017/12/09(土) 16:48:02.91ID:oqulgHhz

766デフォルトの名無しさん2017/12/19(火) 17:58:55.99ID:E2JharMg
関数型言語ってUML使うんですか?
クラス図とかメソッドどう書くんだろうと

767デフォルトの名無しさん2017/12/24(日) 12:09:02.25ID:croU9pw3
ちょっと質問させてください。
状況: トータル1000行くらいある巨大メソッドの改修
言語; PHPだがどの言語でもそう関係のない内容

・まずコントローラのアクションメソッドがあって

public function action(引数){

/* 500行くらいの既存コード */

/*今回改修を加えたい50行位のコード */

/* 500行位の既存コード */
}
となっている。

768デフォルトの名無しさん2017/12/24(日) 12:16:40.00ID:croU9pw3
・ここで、改修要件は、中間にある「/* 50行くらいの既存コード */」を
  if文で分岐させて分岐次第で違う処理を入れる。というもの。
  したがって、

public function action(引数){

  /* 500行くらいの既存コード */

  if(条件1){
    /* 新規追加コード */
    if(条件1-1){
      /* 新規追加コード */
    }else{
      /* 既存コード */
    }
  }else if(条件2){
    /* 新規追加コード */
  }else{
    /* 既存コード */
  }

  /* 500行位の既存コード */
}

みたいにひたすら条件分岐して既存コードと新規追加コード
が何回も実行されるようにしたい。

769デフォルトの名無しさん2017/12/24(日) 12:22:57.90ID:croU9pw3
・ここで、俺は「/* 既存コード */」の中身を知っている必要は
 ないと思った。だから、このコードの詳細を読まずに「func()」
 として「action()メソッド内部」に切り出した。
・外部に切り出したのではなく、内部に切り出したのはその処理が
 他のアクションメソッドでは共有されるような汎用的なものではないだろうと
 判断したのと、そのメソッド内で処理を追いやすいようにというのを
 優先させたため。何より、その処理内で使っている関数内ローカル変数の
 依存性の関係上そうせざるを得ないと思った。

public function action(引数){

  /* 500行くらいの既存コード */

  private function __legacy(){
    /* 50行くらいの既存コード */    
  }

  if(条件1){
    /* 新規追加コード */
    if(条件1-1){
      /* 新規追加コード */
    }else{
      __legacy();
    }
  }else if(条件2){
    /* 新規追加コード */
  }else{
    __legacy();
  }

  /* 500行位の既存コード */
}

770デフォルトの名無しさん2017/12/24(日) 12:31:59.59ID:croU9pw3
・【訂正】上記で「func()」として切り出したと言っているが、
  「__legacy()」に変更しました。すみません。
・上記のように改修した所、レビューを受けたときに怒られた。
・まず、「この__legacy()の中身ちゃんと読んだ? 把握して書いている?」
 という指摘。
・そして「ここメソッド内だけどどうして関数定義しているの?
 他の人そんなことしてないでしょ。どうして変わったことするの?」
 という指摘。

・まず1つめの指摘に対して異議がある。
 ブラックボックス化しなければ大規模なコードは書けないんじゃない?
 ということが言いたい。ライブラリとかフレームワークの機能も全部
 先に中身をよくよく読んでおかなければ使ってはいけないことになるじゃん。

・2つの指摘に対して、
 「周りの人がやっていること」が正しいとは思えない。
 処理を切り出していないから1000行もある巨大なメソッドになっていて、
 汚いコメントで汚しながら機能追加しまくっているんじゃないのかと。
 ローカル変数を使いまくりの同じ処理を何回も実行するのに
 他に良い手段があるとしたら皆さんに教えて頂きたい。

771デフォルトの名無しさん2017/12/24(日) 13:24:11.47ID:d+M5RyEv
汎用的でない50行のコードをコピペしてるんなら関数化してもインライン化してもどっちもどっちだな
DRYを意識したのかもしれんがKISSが抜けてる
それにブラックボックスが許されるのは有名なライブラリやフレームワークのようなテストにテストを重ね、かつ多くの利用者による実績があるものだけだよ
社内コードなんて大概クソコードだしブラックボックスにしても後で痛い目を見るのは自分や他の開発者
何なら単に今把握するだけじゃなくて、未来の自分や開発者のためにわかりにくいところをコメントで説明書きしてもいいくらいだ

あと関数内関数より無名関数を変数に代入した方がいいんじゃね
そもそも新規追加したif文も詳細はわからないがデータよりもロジックに寄っててわかりにくそうな匂いがプンプンする

それに上司には理由を聞かれてるんだから同じローカル変数に別の値を入れて使い回すことの危険性、関数化による参照透明の確保や保守性、メンテナンス性の向上を論理的に答えればいいだけ

772デフォルトの名無しさん2017/12/24(日) 13:31:29.00ID:ZUclbhk1
>>770
レビュアーが言ってることを正しいと仮定すれば
・1つ目の指摘は既存のコードがカプセル化されてないからだ
・2つ目の指摘はリファクタリングするだけの時間やお金や技術がないからだ
という前提が必要になるから、まあそういうことなんじゃなかろうかと

残念なコードっていうのはあるからね
それを修正する費用と修正して得られる効果を比較対照して
これだけの効果があるんだからこうするべきだと提案をまとめて
説得するのがいいのだろうけど、技術に理解のある人がいないとなかなか難しいね

レビュアーの立場で考えると以下の作業があるんじゃないかと
・改修要件を満たす改修
・既存のコードをカプセル化する
・リファクタリングする

レビュアーは既存のコードとの一貫性を維持しつつ
改修要件を満たす最小の改修をやって欲しいのだろうね

たとえ汚らしいコードであってもいままで動いてきた実績があると
変更に対しては既存のコードをできるだけ変えないようにと保守的になるものだよ

レビュアーがそれをきちんと説明できればいんだけど
コードはクソ、レビュアーもクソなんてことはザラにあるんですよこれが

773デフォルトの名無しさん2017/12/24(日) 13:35:53.06ID:croU9pw3
>>771 なるほど勉強になります。
少し質問したいが、
・「KISSが抜けている」と言うのはどこらへんでしょうか?
・関数内関数と無名関数の変数化の違いがわからないので教えてください。
 (面倒なら調べます。)
・あなたならどう対応する?
・「理由を聞かれてるんだから答えればいいだけ。」
 →多分論理的に説明したら「じゃあもう何も教えないよ。好きにやって」
  が返って来ると思われる。
  そう言われると、必要な情報も来なくなるし聞けなくなる。

774デフォルトの名無しさん2017/12/24(日) 13:38:47.27ID:croU9pw3
>>772
なるほど、俺自身が「既存コードのカプセル化」と
「改修要件」という概念と「改修要件を最小に満たす」という
ことについて詳しくないことに問題がありそうだね。
ありがとう、ここらへんをキーワードにして調べてみます。

775デフォルトの名無しさん2017/12/24(日) 13:55:23.50ID:d+M5RyEv
>>773
多分もっと細かく汎用的な(publicにできる)関数の集まりに分解して、汎用的でない部分は最小限に出来るんじゃないかなーって思った
実際のコード見てないから予想だけど

関数内関数だとわざわざprivateかけないと外からアクセス出来ちゃうし、元の親関数抜けても子関数が死なない

そもそも上司とあんまり仲良くないの?
論理的にメリットを売り込んだときに感情論で否定されるくらいの関係性だと下っ端プログラマーはしんどいよ?
まぁ俺ならその段階なら折れて普通にコピペして、もっと実績残して仲良くなってから似たような案件のときに改めて売り込むかな

776デフォルトの名無しさん2017/12/24(日) 16:09:59.00ID:RfRGBvGh
ひとつのメソッドに1000行も書かせる会社はまず危ない

アルゴリズムとかそれ以前

777デフォルトの名無しさん2017/12/24(日) 16:57:23.08ID:croU9pw3
>>775
なるほど、「まるまる関数化」というのが
ちゃんと機能を意識してカプセル化していないってことか。
一応privateは欠けているけど、関数オブジェクトと
関数定義の違いはあまり詳しくないね。そうか、親関数が抜けたとき
子関数が死ぬか否かの違いがあるわけね。
入りたてだから人間関係はいいも悪いもない。
ただ、本来責任ある人はバタバタしていて、経験ある人が自分の意志で
新人のレビューをバラバラに行っている感じ。

>>776
会社がそうさせているというよりはそれぞれの人員が
これまでの追加の仕方を真似て機能追加した結果メソッドがブクブクと太っている
という状況に見える。
メソッド内で各追加機能がコメントで区画されていてそれなら
別関数にすりゃいいのにって思っている。
俺をレビューした人も、別に会社の工程でそうなっているわけでなく、
進捗を見たかったからだと思うが、書き直しを要求してきて困惑している。
ただ彼は業務要件については圧倒的に俺より詳しいから無視すべきではないと
思っている。

778デフォルトの名無しさん2017/12/24(日) 17:21:20.21ID:d+M5RyEv
>>777
カプセル化はオブジェクト指向において関連するものをまとめる作業だから、ちょっと違うかな?
どちらかというと今回の話は関数型プログラミングの考え方に近い
まぁぶっちゃけ職場のコードなんて割り切らんとやってけんよ
出世してコーディングスタイルに口を出せるようになる日を待つしかない

779デフォルトの名無しさん2017/12/24(日) 18:02:16.50ID:ZlmBMffH
>>777
そんな仕事を放置する会社、と言うことだ

780デフォルトの名無しさん2017/12/26(火) 20:02:37.53ID:IVX+3dWv
名前だらけのコードってどうやって解読すればいいんだ?
変数化するとそのデータの型が何なのか物量的にどれだけの
規模が格納されているかが見えない。
もちろんログに吐けば見えるが、吐き出さなければパッと見で
何をどう処理しているのか分からない。

781デフォルトの名無しさん2017/12/26(火) 22:58:59.01ID:SjDDNmHA
俺は君の話が見えない

782デフォルトの名無しさん2017/12/27(水) 07:26:44.87ID:uxDwhrz8
関数型言語の仕様書ってUMLで良いの?

データと振る舞い分離してるからクラス図使って良いのかなと

783デフォルトの名無しさん2017/12/27(水) 08:35:11.41ID:F/9ZaRBN
>>782
ちょうど stackoverflow に同じトピックがありました。
参考にしてください。
https://stackoverflow.com/questions/2457903/can-uml-be-used-to-model-a-functional-program

784デフォルトの名無しさん2017/12/28(木) 07:02:18.99ID:THqyhi+6
>>783
英語敷居たけえ

まあデータと振る舞いを書いたクラス設計は関数型言語でも同じように使えるし問題ないか

785デフォルトの名無しさん2018/01/10(水) 18:14:12.30ID:hBlQ00sP
http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

↑この問題分かる人いますか?

786デフォルトの名無しさん2018/01/10(水) 18:27:49.76ID:1dOsaXCv
粗探しは止めたのか?

787デフォルトの名無しさん2018/02/03(土) 08:08:45.43
今どきデザインパターンって死語なの?
ちょっと参照したいことがあって書店でデザインパターンの本を探したけど見つからなかった。
リファクタリングの本はあって多少はデザインパターンの話も出てきたけど。
結局は家に帰ってから10年前に買ったデザインパターンの本を参照するしかなかった。

788デフォルトの名無しさん2018/02/03(土) 08:51:29.86ID:KIp4GWtx
ブームが去っただけかな?
銀の弾丸などないと気がついただけ

789デフォルトの名無しさん2018/02/03(土) 09:20:07.32ID:i7L7gFeB
今更デザインパターンについて新しい本なんて不要

790デフォルトの名無しさん2018/02/03(土) 12:22:10.78ID:ROxRBp/z
デザパタは元々バカの為にまとめられたものだったけどバカには無理だった代物
一方リファクタリングはバカ程好むからなかなか廃れない

791デフォルトの名無しさん2018/02/03(土) 19:53:28.27ID:4eWkMwg8
21世紀最新のデザインパターン本て誰か書かないかね
Singleton→大抵はstaticでOK
みたいなの

792デフォルトの名無しさん2018/02/03(土) 20:04:20.16ID:gMMiWrqd
>>791
それ以外に何か書くことあんのか?

793デフォルトの名無しさん2018/02/04(日) 00:33:23.10ID:P/Ibpspu
デザインパターンて結局何だったんだ?
高い本まで買ったがほとんど身に付かなかったな

794 ◆QZaw55cn4c 2018/02/04(日) 00:43:54.12ID:p5zvJFKF
>>793
もともと C++ 界隈で発生したテーマですので、C++ をやっているとデザパタの意義がよくわかります
C++ は細かしいことまで自分で記述しなければならないので、こういう大枠思考がもてはやされたのだと思います

795 ◆QZaw55cn4c 2018/02/04(日) 00:44:42.44ID:p5zvJFKF
ああ、でも C++ はテンプレートの世界観に移行してしまったので、デザパタ、今はあんまり使いません!

新着レスの表示
レスを投稿する