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

1 ：2013/03/03 〜 最終レス ：2013/10/14

【関連スレ】
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

2 ：

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

3 ：

>>2
アイRw

4 ：

データ構造,アルゴリズムとデザインパターンは全然別のものだと
思っているのは私だけか。

5 ：

俺もそう思ってた。

6 ：

こっ…これは…

7 ：

どうでもいいが

8 ：

あげ

9 ：

デザパタとか言ってみたいお年頃なんだろ

10 ：

アルゴリズムって言ってみたいお年ごろと何が違うのかわからんが。

11 ：

デザパタはJavaのキツキツの制限を緩めるための苦し紛れの小細工

12 ：

アルゴリズムは科学
デザパタは工学
アルゴリズムは技術
デザパタは技能
アルゴリズムは理論
デザパタは療法
どれにしようか迷ったけど面倒だから全部書いた

13 ：

CTMCPすら読まずにオレ様定義を開陳し合う場となりました。

14 ：

デザパタは本来ならマクロ等で抽象化すべきところを
言語側の表現能力が低いために出来ず、結果として
似たパターンを繰り返し書く羽目になったパターンのカタログ集

15 ：

まぁ、確かに言語の補助が弱いのをプログラマの経験則から解決策として残されているものが多いわな。
現に、Javaなんかでは、singltonとかメンドクサイ事が必要だけど、C#とかでは、何のことも無かったりするし。

16 ：

それデザインパターンの考え方と
パターンの実装をごっちゃにしてるだろ。
アルゴリズムで言えば、C言語だとバブルソートは面倒くさい処理が必要だけど、
ある言語なら、bubble_sort関数呼ぶだけで済むしって言ってるようなもんだろ。

17 ：

デザインパターンって
データ構造とアルゴリズムを合わせたようなものだと思う。

18 ：

アルゴリズム＋データ構造＝プログラム
と昔から決まっておるのじゃ

19 ：

相変わらず知識に溺れたバカばっかりw
ウザウザw

20 ：

>>16
全然違う
なぜならC言語でもバブルソートは関数として抽象化できるから
一度書いたら何度も繰り返し書く必要は無い

21 ：

Strategyパターン
クロージャがある言語なら、ただ単にクロージャを渡すだけの普通のコードで、
名前を付ける必要すら感じない
どっかのゴミ言語ではこんな感じになってしまうが
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:StrategyPatternClassDiagram.svg

22 ：

いや「特定のパターン」はそうだろうけど、
別のパターンはそうとは限らないだろ。
一つを語って、全てが無意味だとなんで思った？

23 ：

>>21
それ、クロージャがある言語でも大差ないと思う。
関数が第一級の言語だと、クラス図として関数も扱わないといけないはず。
で、クラス図に対応する、関数図は関数のシグネチャ。
明示的には継承とは書かないけど、決まった関数のシグネチャを継承した（同じに合わせた）
関数を作るから
[Strategy]
　　↑
[ConcreateStrategyA]
の代わりに、
[引数一つの関数]
　　↑
[実装関数]
こうなってるだけじゃないかな。

24 ：

そういう問題じゃない感

25 ：

http://www.amazon.co.jp/dp/4797304952/
定本 Cプログラマのためのアルゴリズムとデータ構造 近藤嘉雪著

この本もわかりやすいお

26 ：

データ構造とプログラミング（'13）
http://www.ouj.ac.jp/hp/kamoku/H25/kyouyou/B/joho/s_1570048.html

27 ：

死んでしまえクズ共がw

28 ：

前スレの後半のような良スレになればいいなw

29 ：

Wordとかのエディタの「元に戻す」「Undo」機能ってどうやって実装されてるんですか？
Mementoパターンなるものをwikiで調べたんですが、Wordとかの大きな文書だと、
一つのstateのデータ量が多すぎて、すぐにメモリが足りなくなって破綻しそうな気がするんですが・・・
http://ja.wikipedia.org/wiki/Memento_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3

30 ：

全体のコピーじゃなくて差分と操作内容

31 ：

>>29
そこいらは腕の見せ所だから色々な実装がある。と言うのが
普通の答えだと思いまする。
結果データではなく、verbとパラメーターをリング状に記憶
させるという実装はしたことがある

32 ：

A→Bへの変化が起きるとき、B→Aへと戻る動作Δを登録していく。
Undo時に動作Δを呼び出す。

33 ：

wordの文書って画像いれなきゃ
数十キロしかないだろ？

34 ：

バカスレw
バカ共がまた知識ぶって騒いでやがるw
Rゴミクズw

35 ：

リロケータブル形式で記憶しておけばメモリだけでなくファイル等も利用することが可能。
作業途中の状態保存にも使えて便利。

36 ：

stack.push(deflate(操作前のデータ xor 操作後のデータ))
とか思い付いたけどどうよ？

37 ：

簡単にジャーナルを取れるのに差分計算するとか
アホの極み

38 ：

C++でstateパターンを実装していたんだが、実はCライクに関数ポインタを使った実装のほうが短くて簡潔書けることがわかった。でも他人が見たら何をやっているのかわかりづらいかもしれないから、多少手間になっても決まったデザインパターンでやるほうがいいのかもしれない。

39 ：

>>29
UndoでMementoってのは、実は多くの場面で使いにくいんじゃないかなーって思ってる
Adobeのアンドゥは無限回じゃないけど、あれはこのパターン使ってるのかな

40 ：

WikipediaのクイックソートのC言語での実装で、
whileループの最後の i++; j--; はなぜ必要なんですか？
ｈｔｔｐ:／／ja．wikipedia．prg/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88#.E5.AE.9F.E8.A3.85.E4.BE.8B.EF.BC.91
全角．はリンク禁止回避

41 ：

>>40
i++; j--;がないと仮定すると
a[i]がpivotと同じ値だったらiが進まない。
a[j]がpivotと同じ値だったらjが進まない。
効率が悪い、無限ループになる恐れがある。
なので、i++; j--;は無限ループを回避するために必要であるか、
または、効率を良くするために必要なのである。桃白白はそう思うのである。

42 ：

なくても問題ないが

43 ：

まだやってるw
さっさとRw

44 ：

入門 データ構造とアルゴリズム [大型本]
Narasimha Karumanchi (著), 黒川 利明 (翻訳), 木下 哲也 (翻訳)
この本はおすすめですか？
http://www.amazon.co.jp/dp/4873116341

45 ：

>>44 が何者かによる。学生さんならいいんじゃない？プロならう〜ん…個人的にはいらないかな(買わなかった)

46 ：

>600弱の練習問題とその解
・・・ｗ

47 ：

プログラミングの宝箱っていう本、誤りが多すぎる。
なんで売れているの？

48 ：

真の宝の周りにはたくさんの偽りの情報が紛れているものさ

49 ：

世の中、見た目で判断する人が多いから

50 ：

見た目は大事

51 ：

プログラミングの宝箱っていう本、見た目がいいの？
見た目がいいってどういうこと？

52 ：

杉原厚吉のデータ構造とアルゴリズムの本ってソートのプログラムも
載っていないんだね。だめだめ。

53 ：

セジウィックの本もどこがいいのか分からない。
プログラムが読みにくいし。
やっぱりクヌースの本が一番いいのかな。

54 ：

>>47
その本、クイックソートのプログラムが間違っているよね。

55 ：

>>47
そもそも売れてるの？

56 ：

ソフトバンククリエイティブの本っていい加減な本が多いような気がする。

57 ：

ところでアマゾンのランキングって何のランキングなの？
たとえば、アルゴリズムの本のランキングを見るとどう見ても売れていない
ような絶版の中古本がランクインしていたりする。

58 ：

ところで、MITのOpen Coursewareで勉強している人はいない？

59 ：

柴田望洋のアルゴリズムとデータ構造の本、レベル低すぎ。
なんなの望洋ってｗ

60 ：

>>58
どのコース？

61 ：

見慣れない本質不必要な単語が頻出するから
講義系のテキストは却下だな

62 ：

まだ下の上二つを見始めたところです。英語はよく分かりませんが、板書を見て大体
分かります。見ている（見た）人がいたら質問とか今後すると思うのでお願いします。
Pythonによるプログラミングの入門の講義。レベルが低い。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/
コンピューターサイエンスのための数学。レイトン教授が最高に面白い。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/
まだ見てないけど、和田英一が訳した有名な教科書の著者の講義。まだ見ていない。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/
アルゴリズム入門2005年。まだ見ていない。リベストらの有名なアルゴリズムの教科書の著者が講義。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
アルゴリズム入門2011年
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

63 ：

>>62
アルゴリズムの講義なら Coursera や Udacity あたりに新しいのがいっぱいあるぞ。セジウィックが講義してるのもあるし。
https://www.coursera.org/courses?orderby=upcoming&search=algorithms
そういう自分も Coursera の前は>>62の最後のコースでアルゴリズム勉強したわ。
古いからちょっと画面が小さいんだよねー。

64 ：

>>63
情報ありがとうございます。そっちも視野に入れたいと思います。

65 ：

Rゴミ共がw
Rゴミ共がw

66 ：

オライリーから出たインド人のアルゴリズムとデータ構造の本、最悪。
説明もほとんどなしにコードと問題が載っているだけ。
買ってはいけない。

67 ：

>>66
コードと問題が説明になっているのだろう。

68 ：

あれは演習問題集だから…

69 ：

資格勉強に役立つ？

70 ：

就職や昇級に反映されるなら役立つ
そうでなければ趣味

71 ：

アルゴリズムやデザインパターンって公式的に覚えてしまったら、
中身がどうなっているかどうか知っていようといまいと生産性は変わらない。
ただ中身を知っていると、何かトラブルが起きたり、
それらを組み合わせて新しいことを覚えなくてはいけないときに差が出てくる。
が、今時はそういうことはかなり稀なので、機械的に覚えてしまって、
さっさと人を使う立場になってしまう方が悩まなくていいかも。

72 ：

>>71
トンチンカンなこと言ってるぞ？ ライブラリレベルまで落とし込まれているような
アルゴリズムならともかく、デザインパターンは公式的に覚えて使えるもんじゃ
ないぞ。中身の実装方法はともかく、GoFのデザインパターンですら、複数
組み合わせて使うのが普通なのに。

73 ：

effective javaのいってんじゃねーの
俺ってやさしい

74 ：

>>66
君、アマゾンのレビューを書いた人？
星一つしかついてなかったｗ

75 ：

率直に言って、C++という言語はデータ構造を分からせるのには向かない。
内容は時間的/空間的計算量という評価に徹してデータ構造とその読み出し方を
解説したもので、むしろ優れた本だと思う。

76 ：

>>75
普通の大学で使うような教科書のほうがいいと思う。
エイホ・ホップクロフト・ウルマンのアルゴリズムとデータ構造とか
MITの教科書とか。

77 ：

Ahoの本は良いな
はずれがない

78 ：

クヌースの本も読んだほうがいい？
クヌースの本はプログラマ必読の書らしいけど

79 ：

>>78
全部読むのは難しいんじゃないですか？
アルゴリズムの解析の部分は難しいし、実益が少ない。
アルゴリズムの手順だけ読むくらいでいいのでは？
あと新しいアルゴリズムが書かれていないらしい。

80 ：

クヌース（ブルース風に）

81 ：

クヌースは古典だな
読むか読まないかなら、もちろん読んだ方がいいが
>>79
新しいアルゴリズムは論文読むしか

82 ：

クヌース　ホシーイ　ケレード
ゼパーン　ニナーテ　ルヨーネ
シカータ　ナイカーラ　エイーゴ
デヨンデール　

83 ：

>>79
ところで新しいアルゴリズムてどんなの？
遺伝とかならいらないけど

84 ：

>>83
すみません。よく知りません。
擬似乱数を生成するメルセンヌツイスターが載っていないって、
考案者が文句言っていたのは知っています。

85 ：

クヌースの本は要約版が1冊になって出版される予定だけど、実現しないだろうね。
というかThe Art of Computer Programming自体が完成しないか。
既刊の第4巻はおもしろそう。

86 ：

わざと初等的な証明をつかってるから
無駄にめんどくさいね。
群とか環とか使えば良いのにっておもうよ。

87 ：

self containedになっているのだろう

88 ：

>>84
あの膨大な本の中の、たった一つのテーマだからね。

89 ：

C++のメソッドの呼び方で質問です。
サブクラスからサブクラスを呼ぶときに、スーパークラスを無視した以下の書き方はオブジェクト思考的には違反でしょうか？
void AppDerived::method(){
(static_cast<DetailDerived*>(ptr))->func();
}
スーパークラス(AppBase)のヘッダにmethod()を追加したり、なるべくさわりたくないので上記の方法を思いつきました。

クラスの繋がりは以下の通りです。
class AppBase{
DetailBase* ptr;
}
AppBase ◆− DetailBase
AppBaseとDetailBaseはコンポジット関係です。
class AppDerived : public AppBase{
void method()
}
class DetailDerived : public DetailBase{
void func()
}

90 ：

補足です。
void AppDerived::method(){
ptr->func();
}
class DetailBase{
virtual void func(){ return; }
}
上記の方法を避けたいための方法です。

91 ：

>>89
>オブジェクト思考的
は関係ないね,、C++の実装としてだろう

92 ：

>>89
その派生クラス同士の関係性によってはアリな場合もあるんだけど、 一般的には無しだね。
基底クラスを触りたくないからと言うのは全く理由にならないと思うよ。

93 ：

>>89
AppBaseがコンポジションするDetailBaseはPublicやProtectedってことでしょ？
それなら派生クラスから弄られることを想定しているってことになるから
AppDerivedのMethod()で新しくDetailDerivedを保持し直したらいいんじゃないの？
Privateなら基底クラスでしかDetailBaseを弄らないのだから
AppDerivedのMethod()内でのみ使用するためにDetailDerivedのインスタンス生成すりゃいいんじゃないの？
>>90の方法を避けたいってのは、AppBaseがDetailBaseをコンポジションしてポリモーフィズムするのを
否定しちゃってんじゃないの？コンポジションしている意味が無くならない？

94 ：

ﾌﾟｯw

95 ：

ｸｻｯ

96 ：

すまん

97 ：

おまえかよ

98 ：

このように他人（主に女の子）の汚名を代わって受けるのがイケメンパターン

99 ：

Rゴミ共がw
Rゴミ共がw

100 ：

落ち着け

101 ：

ある順序列Aとそれに含まれる一部の要素からなる順序列Bがあるとき、
Bの順序を満たし、かつAから「変化が少ない」順序列Cを得たい。
A: [ 1 2 3 4 5 ]
B: [ 4 3 ]
C: [ 1 2 4 3 5 ]
「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
移動距離の二乗和が小さい」などが考えられる。
ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
使えそうなアルゴリズムがあったら、ググるキーワードを教えてください。

102 ：

要素の重複とかあるの？

103 ：

>>101
> 「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
> 移動距離の二乗和が小さい」などが考えられる。
これに激しく違和感を感じるけど、
> ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
近似解でいいならGAが楽じゃね？

104 ：

Aを走査していき、Bにも含まれる要素に当たったら、Bの要素順で置き換える
……だと変化が大きいのかもしれないのか

105 ：

>>102
重複はない前提です。
>>103
その基準のところも、なにか使えそうなものがあれば調べてみたいと思いますが。
ところで、どういうところで違和感を感じるでしょう？
>>104
Bの並びによっては団子になってしまいそうですが、確かに計算量は非常に
少なそうですね。

106 ：

>>105
順列と最小二乗って、同じ目的で使って嬉しくなる数学的根拠があるのかな、と思って。
置換の数で距離を測るのが一般的かな？とか。
感覚的な意見で申し訳ないけど。

107 ：

感覚的なものなのでそこはあまり根拠はないですが、移動距離が大きくなるにつれて
ペナルティは増大するほうがいいのかなと。
ただまぁ、ひとつの要素が移動すればその距離に応じて他の要素もずれるわけなんで、
移動距離の総和とかあるいは単純に移動した要素の数でもいいかもしれないですね。
順序の距離とか順列間の距離とかで探したらいくつか距離の定義が見つかりました。

108 ：

Rゴミ共がw

109 ：2013/10/14

落ち着け