データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 二分木じゃなくて三分木なら2^d以下ではないわけだけど、>>669の証明を二分木から三分木に変えても
論理展開に違いが出ないから明らかにおかしいだろう。 三分木では、
「もしそうでないと仮定すると、 T のすべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまう」
が成り立ちません。 三分木の場合の証明は以下のようになりますね。
三分木において、深さ d までの葉の総数が 3^d + 1 個以上である三分木が存在すると仮定する。
深さ d までの葉の総数が最多である三分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 3^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い三分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 3^d 個以下である。 >が成り立ちません。
成り立たないことがわかっているなら証明いらんだろうｗ
逆に言うと、それが成り立たないことが証明されていない。
>>673
3^dってどこから出てきたわけ？ 2分ヒープは完全二分木を使ったデータ構造ですが。
この完全二分木のことを半順序のついた木というのはなぜでしょうか？ %%%%1000%%%%
000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end バッチ処理, ジョブ制御に有効なデザインパターンって何? >>675
再帰的に、親は両方の子以下の数値をもつ。
左右の子の大小関係は考慮しない
ここでは説明しやすいように、配列の[0]は使わない。
[1]から始めると計算が楽。
親1, 左右の子は2, 3で、法則は、親n, 子2n, 2n+1
もし[0]から始めると、
親0, 左右の子は1, 2で、親1, 左右の子は3, 4で、
法則は、親n, 子2n+1, 2n+2、となり複雑
親[1] → 子[2, 3]
[1]3, [2]10, [3]30
[2] → [4, 5]
[4]100, [5]20
[3] → [6, 7]
[6]70, [7]200
JavaScript で、漏れが作った、2分ヒープ
http://jsdo.it/michihito/bGH5 シングルトンがいけないとかたまに聞くんだけど
シングルトンなしでどうやるのか誰か教えて
シングルトン使わないで済むならシングルトン辞めることには吝かではないんだが
どうやるのかが分からない
HolderとかRepository作るとどうしてもシングルトンになっちゃう
誰か助けて シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？
と思うんだが 内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。
2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1
よって、 h = O(log(n))
とある本に書いてあります。
これっておかしいですよね？
h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。
もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？ メッセージキューイングって
Commandパターンで実装するで合ってる？ >>686
>>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1)
>>よって、 h = O(log(n)) ・・・(2)
一見すると正しそうに見えるけど、どっちがどうおかしいと？ h が n の関数ではないにもかかわらず
h ∈ O(log(n))
と書いているのがナンセンスです。 >>689
nとhの関係は(1)で示されているんじゃね？
不等式を変形すれば良いのでは？ n から h は一意的に決まりません。
よって、
h は n の関数ではありません。 >>691
(1)より一意に決まらなくても計算量は同じでしょ？ ＞もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ここの時点でおかしい 抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「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行位の既存コード */
} ■ このスレッドは過去ログ倉庫に格納されています
