- 1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net]
- 【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
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
- 29 名前：デフォルトの名無しさん [2013/04/19(金) 21:42:39.55 .net]
- Wordとかのエディタの「元に戻す」「Undo」機能ってどうやって実装されてるんですか？
Mementoパターンなるものをwikiで調べたんですが、Wordとかの大きな文書だと、
一つのstateのデータ量が多すぎて、すぐにメモリが足りなくなって破綻しそうな気がするんですが・・・
ja.wikipedia.org/wiki/Memento_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3
- 30 名前：デフォルトの名無しさん mailto:sage [2013/04/19(金) 21:48:42.39 .net]
- 全体のコピーじゃなくて差分と操作内容
- 31 名前：デフォルトの名無しさん mailto:sage [2013/04/19(金) 21:58:43.00 .net]
- >>29
そこいらは腕の見せ所だから色々な実装がある。と言うのが
普通の答えだと思いまする。
結果データではなく、verbとパラメーターをリング状に記憶
させるという実装はしたことがある
- 32 名前：デフォルトの名無しさん mailto:sage [2013/04/19(金) 23:38:59.62 .net]
- A→Bへの変化が起きるとき、B→Aへと戻る動作Δを登録していく。
Undo時に動作Δを呼び出す。
- 33 名前：デフォルトの名無しさん [2013/04/20(土) 01:34:18.08 .net]
- wordの文書って画像いれなきゃ
数十キロしかないだろ？
- 34 名前：デフォルトの名無しさん [2013/04/20(土) 07:13:11.67 .net]
- バカスレw
バカ共がまた知識ぶって騒いでやがるw
死ねゴミクズw
- 35 名前：デフォルトの名無しさん mailto:sage [2013/04/20(土) 10:00:25.18 .net]
- リロケータブル形式で記憶しておけばメモリだけでなくファイル等も利用することが可能。
作業途中の状態保存にも使えて便利。
- 36 名前：デフォルトの名無しさん mailto:sage [2013/04/20(土) 10:54:34.60 .net]
- stack.push(deflate(操作前のデータ xor 操作後のデータ))
とか思い付いたけどどうよ？
- 37 名前：デフォルトの名無しさん mailto:sage [2013/04/20(土) 12:19:10.51 .net]
- 簡単にジャーナルを取れるのに差分計算するとか
アホの極み
- 38 名前：デフォルトの名無しさん mailto:sage [2013/04/30(火) 22:53:00.60 .net]
- C++でstateパターンを実装していたんだが、実はCライクに関数ポインタを使った実装のほうが短くて簡潔書けることがわかった。でも他人が見たら何をやっているのかわかりづらいかもしれないから、多少手間になっても決まったデザインパターンでやるほうがいいのかもしれない。
- 39 名前：デフォルトの名無しさん mailto:sage [2013/05/21(火) 00:35:42.34 .net]
- >>29
UndoでMementoってのは、実は多くの場面で使いにくいんじゃないかなーって思ってる
Adobeのアンドゥは無限回じゃないけど、あれはこのパターン使ってるのかな
- 40 名前：デフォルトの名無しさん [2013/06/09(日) 19:06:14.70 .net]
- 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 名前：桃白白 ◆9Jro6YFwm650 [2013/06/09(日) 19:26:26.73 .net]
- >>40
i++; j--;がないと仮定すると
a[i]がpivotと同じ値だったらiが進まない。
a[j]がpivotと同じ値だったらjが進まない。
効率が悪い、無限ループになる恐れがある。
なので、i++; j--;は無限ループを回避するために必要であるか、
または、効率を良くするために必要なのである。桃白白はそう思うのである。
- 42 名前：デフォルトの名無しさん mailto:sage [2013/06/09(日) 19:48:02.69 .net]
- なくても問題ないが
- 43 名前：デフォルトの名無しさん [2013/06/10(月) 09:15:30.73 .net]
- まだやってるw
さっさと死ねw
- 44 名前：デフォルトの名無しさん [2013/09/18(水) 13:39:49.18 .net]
- 入門 データ構造とアルゴリズム [大型本]
Narasimha Karumanchi (著), 黒川 利明 (翻訳), 木下 哲也 (翻訳)
この本はおすすめですか？
www.amazon.co.jp/dp/4873116341
- 45 名前：デフォルトの名無しさん mailto:sage [2013/09/18(水) 14:11:03.23 .net]
- >>44 が何者かによる。学生さんならいいんじゃない？プロならう〜ん…個人的にはいらないかな(買わなかった)
- 46 名前：デフォルトの名無しさん mailto:sage [2013/09/18(水) 19:27:36.43 .net]
- >600弱の練習問題とその解
・・・ｗ
- 47 名前：デフォルトの名無しさん [2013/09/18(水) 23:07:49.85 .net]
- プログラミングの宝箱っていう本、誤りが多すぎる。
なんで売れているの？
- 48 名前：デフォルトの名無しさん mailto:sage [2013/09/21(土) 16:31:47.20 .net]
- 真の宝の周りにはたくさんの偽りの情報が紛れているものさ
- 49 名前：デフォルトの名無しさん mailto:sage [2013/09/21(土) 16:58:27.85 .net]
- 世の中、見た目で判断する人が多いから
- 50 名前：デフォルトの名無しさん mailto:sage [2013/09/22(日) 10:28:15.10 .net]
- 見た目は大事
- 51 名前：デフォルトの名無しさん [2013/09/22(日) 20:22:12.39 .net]
- プログラミングの宝箱っていう本、見た目がいいの？
見た目がいいってどういうこと？
- 52 名前：デフォルトの名無しさん [2013/09/22(日) 20:24:16.43 .net]
- 杉原厚吉のデータ構造とアルゴリズムの本ってソートのプログラムも
載っていないんだね。だめだめ。
- 53 名前：デフォルトの名無しさん [2013/09/22(日) 20:25:25.63 .net]
- セジウィックの本もどこがいいのか分からない。
プログラムが読みにくいし。
やっぱりクヌースの本が一番いいのかな。
- 54 名前：デフォルトの名無しさん [2013/09/22(日) 20:27:01.59 .net]
- >>47
その本、クイックソートのプログラムが間違っているよね。
- 55 名前：デフォルトの名無しさん mailto:sage [2013/09/22(日) 21:23:03.07 .net]
- >>47
そもそも売れてるの？
- 56 名前：デフォルトの名無しさん [2013/09/22(日) 22:06:44.18 .net]
- ソフトバンククリエイティブの本っていい加減な本が多いような気がする。
- 57 名前：デフォルトの名無しさん [2013/09/22(日) 22:11:29.25 .net]
- ところでアマゾンのランキングって何のランキングなの？
たとえば、アルゴリズムの本のランキングを見るとどう見ても売れていない
ような絶版の中古本がランクインしていたりする。
- 58 名前：デフォルトの名無しさん [2013/09/22(日) 22:14:08.27 .net]
- ところで、MITのOpen Coursewareで勉強している人はいない？
- 59 名前：デフォルトの名無しさん [2013/09/22(日) 22:16:07.27 .net]
- 柴田望洋のアルゴリズムとデータ構造の本、レベル低すぎ。
なんなの望洋ってｗ
- 60 名前：デフォルトの名無しさん mailto:sage [2013/09/22(日) 22:17:15.56 .net]
- >>58
どのコース？
- 61 名前：デフォルトの名無しさん mailto:sage [2013/09/22(日) 22:17:59.43 .net]
- 見慣れない本質不必要な単語が頻出するから
講義系のテキストは却下だな
- 62 名前：デフォルトの名無しさん [2013/09/22(日) 22:29:45.56 .net]
- まだ下の上二つを見始めたところです。英語はよく分かりませんが、板書を見て大体
分かります。見ている（見た）人がいたら質問とか今後すると思うのでお願いします。
Pythonによるプログラミングの入門の講義。レベルが低い。
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/
コンピューターサイエンスのための数学。レイトン教授が最高に面白い。
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/
まだ見てないけど、和田英一が訳した有名な教科書の著者の講義。まだ見ていない。
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/
アルゴリズム入門2005年。まだ見ていない。リベストらの有名なアルゴリズムの教科書の著者が講義。
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
アルゴリズム入門2011年
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/
- 63 名前：デフォルトの名無しさん mailto:sage [2013/09/22(日) 22:49:56.98 .net]
- >>62
アルゴリズムの講義なら Coursera や Udacity あたりに新しいのがいっぱいあるぞ。セジウィックが講義してるのもあるし。
https://www.coursera.org/courses?orderby=upcoming&search=algorithms
そういう自分も Coursera の前は>>62の最後のコースでアルゴリズム勉強したわ。
古いからちょっと画面が小さいんだよねー。
- 64 名前：デフォルトの名無しさん [2013/09/22(日) 22:54:12.17 .net]
- >>63
情報ありがとうございます。そっちも視野に入れたいと思います。
- 65 名前：デフォルトの名無しさん [2013/09/26(木) 13:01:06.57 .net]
- 死ねゴミ共がw
死ねゴミ共がw
- 66 名前：デフォルトの名無しさん [2013/09/28(土) 06:46:14.59 .net]
- オライリーから出たインド人のアルゴリズムとデータ構造の本、最悪。
説明もほとんどなしにコードと問題が載っているだけ。
買ってはいけない。
- 67 名前：デフォルトの名無しさん mailto:sage [2013/09/28(土) 16:59:53.64 .net]
- >>66
コードと問題が説明になっているのだろう。
- 68 名前：デフォルトの名無しさん mailto:sage [2013/09/28(土) 17:57:20.08 .net]
- あれは演習問題集だから…
- 69 名前：デフォルトの名無しさん mailto:sage [2013/09/28(土) 18:16:31.35 .net]
- 資格勉強に役立つ？
- 70 名前：デフォルトの名無しさん mailto:sage [2013/09/28(土) 18:28:54.24 .net]
- 就職や昇級に反映されるなら役立つ
そうでなければ趣味
- 71 名前：デフォルトの名無しさん mailto:sage [2013/09/29(日) 12:57:58.61 .net]
- アルゴリズムやデザインパターンって公式的に覚えてしまったら、
中身がどうなっているかどうか知っていようといまいと生産性は変わらない。
ただ中身を知っていると、何かトラブルが起きたり、
それらを組み合わせて新しいことを覚えなくてはいけないときに差が出てくる。
が、今時はそういうことはかなり稀なので、機械的に覚えてしまって、
さっさと人を使う立場になってしまう方が悩まなくていいかも。
- 72 名前：デフォルトの名無しさん mailto:sage [2013/09/29(日) 15:55:56.14 .net]
- >>71
トンチンカンなこと言ってるぞ？ ライブラリレベルまで落とし込まれているような
アルゴリズムならともかく、デザインパターンは公式的に覚えて使えるもんじゃ
ないぞ。中身の実装方法はともかく、GoFのデザインパターンですら、複数
組み合わせて使うのが普通なのに。
- 73 名前：デフォルトの名無しさん mailto:sage [2013/09/29(日) 15:59:49.30 .net]
- effective javaのいってんじゃねーの
俺ってやさしい
- 74 名前：デフォルトの名無しさん [2013/10/02(水) 01:48:18.78 .net]
- >>66
君、アマゾンのレビューを書いた人？
星一つしかついてなかったｗ
- 75 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 06:46:43.90 .net]
- 率直に言って、C++という言語はデータ構造を分からせるのには向かない。
内容は時間的/空間的計算量という評価に徹してデータ構造とその読み出し方を
解説したもので、むしろ優れた本だと思う。
- 76 名前：デフォルトの名無しさん [2013/10/02(水) 08:06:05.95 .net]
- >>75
普通の大学で使うような教科書のほうがいいと思う。
エイホ・ホップクロフト・ウルマンのアルゴリズムとデータ構造とか
MITの教科書とか。
- 77 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 08:33:04.43 .net]
- Ahoの本は良いな
はずれがない
- 78 名前：デフォルトの名無しさん [2013/10/02(水) 09:11:06.55 .net]
- クヌースの本も読んだほうがいい？
クヌースの本はプログラマ必読の書らしいけど
- 79 名前：デフォルトの名無しさん [2013/10/02(水) 11:01:55.61 .net]
- >>78
全部読むのは難しいんじゃないですか？
アルゴリズムの解析の部分は難しいし、実益が少ない。
アルゴリズムの手順だけ読むくらいでいいのでは？
あと新しいアルゴリズムが書かれていないらしい。
- 80 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 11:55:09.13 .net]
- クヌース（ブルース風に）
- 81 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 19:03:31.81 .net]
- クヌースは古典だな
読むか読まないかなら、もちろん読んだ方がいいが
>>79
新しいアルゴリズムは論文読むしか
- 82 名前：デフォルトの名無しさん mailto:sage [2013/10/03(木) 10:30:06.56 .net]
- クヌース ホシーイ ケレード
ゼパーン ニナーテ ルヨーネ
シカータ ナイカーラ エイーゴ
デヨンデール
- 83 名前：デフォルトの名無しさん mailto:sage [2013/10/03(木) 14:33:48.67 .net]
- >>79
ところで新しいアルゴリズムてどんなの？
遺伝とかならいらないけど
- 84 名前：デフォルトの名無しさん [2013/10/03(木) 19:57:54.46 .net]
- >>83
すみません。よく知りません。
擬似乱数を生成するメルセンヌツイスターが載っていないって、
考案者が文句言っていたのは知っています。
- 85 名前：デフォルトの名無しさん [2013/10/03(木) 20:17:33.09 .net]
- クヌースの本は要約版が1冊になって出版される予定だけど、実現しないだろうね。
というかThe Art of Computer Programming自体が完成しないか。
既刊の第4巻はおもしろそう。
- 86 名前：デフォルトの名無しさん mailto:sage [2013/10/04(金) 09:08:51.46 .net]
- わざと初等的な証明をつかってるから
無駄にめんどくさいね。
群とか環とか使えば良いのにっておもうよ。
- 87 名前：デフォルトの名無しさん mailto:sage [2013/10/04(金) 09:12:18.81 .net]
- self containedになっているのだろう
- 88 名前：デフォルトの名無しさん mailto:sage [2013/10/07(月) 09:07:45.97 .net]
- >>84
あの膨大な本の中の、たった一つのテーマだからね。
- 89 名前：デフォルトの名無しさん [2013/10/07(月) 20:33:21.18 .net]
- 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 名前：89 [2013/10/07(月) 23:01:02.14 .net]
- 補足です。
void AppDerived::method(){
ptr->func();
}
class DetailBase{
virtual void func(){ return; }
}
上記の方法を避けたいための方法です。
- 91 名前：デフォルトの名無しさん mailto:sage [2013/10/07(月) 23:12:12.86 .net]
- >>89
>オブジェクト思考的
は関係ないね,、C++の実装としてだろう
- 92 名前：デフォルトの名無しさん mailto:sage [2013/10/08(火) 00:52:45.41 .net]
- >>89
その派生クラス同士の関係性によってはアリな場合もあるんだけど、 一般的には無しだね。
基底クラスを触りたくないからと言うのは全く理由にならないと思うよ。
- 93 名前：デフォルトの名無しさん mailto:sage [2013/10/08(火) 10:05:07.76 .net]
- >>89
AppBaseがコンポジションするDetailBaseはPublicやProtectedってことでしょ？
それなら派生クラスから弄られることを想定しているってことになるから
AppDerivedのMethod()で新しくDetailDerivedを保持し直したらいいんじゃないの？
Privateなら基底クラスでしかDetailBaseを弄らないのだから
AppDerivedのMethod()内でのみ使用するためにDetailDerivedのインスタンス生成すりゃいいんじゃないの？
>>90の方法を避けたいってのは、AppBaseがDetailBaseをコンポジションしてポリモーフィズムするのを
否定しちゃってんじゃないの？コンポジションしている意味が無くならない？
- 94 名前：デフォルトの名無しさん [2013/10/09(水) 18:19:09.59 .net]
- ﾌﾟｯw
- 95 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 07:27:16.17 .net]
- ｸｻｯ
- 96 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 07:54:38.65 .net]
- すまん
- 97 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 08:38:38.27 .net]
- おまえかよ
- 98 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 18:02:10.65 .net]
- このように他人（主に女の子）の汚名を代わって受けるのがイケメンパターン
- 99 名前：デフォルトの名無しさん [2013/10/12(土) 18:05:18.38 .net]
- 死ねゴミ共がw
死ねゴミ共がw
- 100 名前：デフォルトの名無しさん mailto:sage [2013/10/12(土) 21:43:22.30 .net]
- 落ち着け
- 101 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 14:04:12.97 .net]
- ある順序列Aとそれに含まれる一部の要素からなる順序列Bがあるとき、
Bの順序を満たし、かつAから「変化が少ない」順序列Cを得たい。
A: [ 1 2 3 4 5 ]
B: [ 4 3 ]
C: [ 1 2 4 3 5 ]
「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
移動距離の二乗和が小さい」などが考えられる。
ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
使えそうなアルゴリズムがあったら、ググるキーワードを教えてください。
- 102 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 14:24:30.97 .net]
- 要素の重複とかあるの？
- 103 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 14:29:12.64 .net]
- >>101
> 「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
> 移動距離の二乗和が小さい」などが考えられる。
これに激しく違和感を感じるけど、
> ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
近似解でいいならGAが楽じゃね？
- 104 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 15:28:06.54 .net]
- Aを走査していき、Bにも含まれる要素に当たったら、Bの要素順で置き換える
……だと変化が大きいのかもしれないのか
- 105 名前：101 mailto:sage [2013/10/13(日) 16:04:56.10 .net]
- >>102
重複はない前提です。
>>103
その基準のところも、なにか使えそうなものがあれば調べてみたいと思いますが。
ところで、どういうところで違和感を感じるでしょう？
>>104
Bの並びによっては団子になってしまいそうですが、確かに計算量は非常に
少なそうですね。
- 106 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 16:45:07.14 .net]
- >>105
順列と最小二乗って、同じ目的で使って嬉しくなる数学的根拠があるのかな、と思って。
置換の数で距離を測るのが一般的かな？とか。
感覚的な意見で申し訳ないけど。
- 107 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 17:11:59.64 .net]
- 感覚的なものなのでそこはあまり根拠はないですが、移動距離が大きくなるにつれて
ペナルティは増大するほうがいいのかなと。
ただまぁ、ひとつの要素が移動すればその距離に応じて他の要素もずれるわけなんで、
移動距離の総和とかあるいは単純に移動した要素の数でもいいかもしれないですね。
順序の距離とか順列間の距離とかで探したらいくつか距離の定義が見つかりました。
- 108 名前：デフォルトの名無しさん [2013/10/14(月) 09:57:46.64 .net]
- 死ねゴミ共がw
- 109 名前：デフォルトの名無しさん mailto:sage [2013/10/14(月) 10:21:17.60 .net]
- 落ち着け
- 110 名前：デフォルトの名無しさん [2013/11/03(日) 22:41:37.52 .net]
- グーグルのアルゴリズムコンテストとか受けてるやついる？
- 111 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:09:19.22 .net]
- 全要素の値を0で初期化した要素数nの一次元配列にたいして、
ランダムに選んだm (< n) 個の要素のみ値を1にした配列を作りたいです。
次の方法を考えました。
1. 先頭からm個の要素の値を1に、残りの要素の値を0にした配列を用意する。
2. その配列に対して Fisher-Yates shuffle を施す。
これよりも実行速度において効率的な方法はあるでしょうか。
（並列化を利用して効率よくする方法もアリです）
ただ、できるだけ偏りは無くしたいです。
- 112 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:13:31.20 .net]
- nとmをどれくらいに想定してるのさ
- 113 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:56:55.33 .net]
- >>112
n は 1000000 くらい
m は 1000 log 1000 くらいなので、だいたい 7000 弱程度です
- 114 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:59:21.68 .net]
- （その程度だと、どんな馬鹿なアルゴリズムでも一瞬で終わる処理だと思うが、何らかの効率的アルゴリズムが欲しい理由でもあるのかも……）
- 115 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 21:24:13.39 .net]
- >>114
もっと巨大な配列なら、より効率的な方法があるのでしょうか。
どんな方法か知りたいです。
- 116 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 22:58:36.70 .net]
- >>115
くじ引きと同じ論法でO(N)で作れるだろ
- 117 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 07:10:30.69 .net]
- >>116
それって、1000000個の重複のない数列から7000個を取り出すんだろ？
重複のないくじを作るのに結局シャッフルがいるんじゃないのか？
だったら、やってることは>>111と同じだと思うが
というか、>>111だってシャッフルはO(N)なんだから、
そもそも質問の意図もよう分からんが
- 118 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 07:44:36.62 .net]
- >>117
シャッフルは要らない。n本のくじの中にm本の当たりがある場合と同じ。
それを配列番号1からn番まで引く。くじ引きは何番目に引こうが当たりが出る確率は等確率。
>>111も確かにO(N)だな。ソートと勘違いしてた。
だけどくじ方式の場合は逐一頭から取り出す場合は配列を用意する必要はないし、
必要な分だけ計算すればいい。
int array[n];
for (size_t i=0; i<n; ++i) {
bool hit = m/(n-i)の確率のrand;
if (hit) {
--m;
array[i] = 1;
} else {
array[i] = 0;
}
}
- 119 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 13:06:53.22 .net]
- 偏りをなくしたいということは低周波成分をなくしたいということかな？
すなわち、1が連続したり、なかなか出なかったりするのを無くすということ。
だったら乱数を使うのは誤り。
- 120 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 20:29:44.62 .net]
- >>118
すごいですね、その発想は出てこなかったです。
簡単な例で図を描いて確かめてみましたが、みんな当たる確率は同じになりました。
Fisher-Yates shuffle でやるより断然スジがいいです。
採用させてもらいます。
>>119
たしかに、1 や 0 があまりに連続しているの好ましくないです。
その場合、乱数を使わずにどうやるのでしょうか。
1 か o かを選ぶのに乱数を使うのではなく、もっと別のところで使うという意味でしょうか。
それとも、全くどこにも使わないのでしょうか。
- 121 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:16:46.95 .net]
- >>120
乱数から低周波成分を除去した数列を使います。別名ブルーノイズ。
配列を参照するだけなので超高速で偏りの無いパターンを作ることができる。
100万個から7000個を選んでも１が連続する確率は0。規則性もなし。
ブルーノイズ数列の一部をとってもブルーノイズ数列。使い回しができる。
欠点として１回はブルーノイズ数列を作る必要があるが時間がかかる。100万個
の数列だと1時間くらいかかる。一回作ってファイルに保存しておけばOK。
- 122 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:23:07.46 .net]
- >>120
不思議に思ったんだがひょっとして
配列の全要素の初期値って不定扱いなのか？
なら>>118を採用する理由もわかるが
- 123 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:01:24.83 .net]
- 言語にもよるけど、int 型なら多くの場合0じゃない？
で気づいたけど、1 か 0 しか入らないなら bool 型でいいんじゃないか？メモリもグッと節約できる。
- 124 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:12:20.58 .net]
- >>122
いえ、今回は、必ず何らかの値で初期化される、という種類のデータ構造（配列）を使っています。
（言語的は初期値として未定を表す値を指定できる配列も簡単に作れますが、
今回は意味ないので、そのような配列は使っていません）
>>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。
要するに、データ構造そのものをどんどん大きくしながら作っていけます。
シャッフルも Fisher-Yates shuffle でしたら順にトラバースしますが、
その要素と、別のランダムに選んだ要素を参照しなければならず、
シャッフル処理をする前にデータ構造が完全に出来上がっていなければなりません。
その上で要素をスワップしていきます。
じつはプログラミング言語はCではなくHaskellを使っており、Haskellでは後者より前者のように、
値を入れた要素を次々と繋げながらデータ構造を（目的の規模まで）大きくしていく方が
プログラムしやすいんです。
>>123
すいません、0 と 1 を使ったのは単に質問をシンプルにするためでした。
本当は、質問で 1 を入れるところでは min < x < max のランダムな浮動小数点を入れます。
そもそもの目的をぶっちゃけますと、ランダムな重み付き有向グラフの隣接行列を作ることです。
- 125 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:14:23.54 .net]
- >>124
> >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
> その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。
すいません、ちょっと言い方がおかしいですね。
配列の頭から順に要素をトラバースしながら、ではなくて、順に配列を大きくしながら、
とか、配列を組み上げながらと言うべきでした。
- 126 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:23:35.67 .net]
- >>121
申し訳ないです、そこまで強力なものは今回は求めていないです。
あまりに偏りすぎていると使えないな、という程度のことでした。
しかし、これはこれで大変興味深いです。
ホワイトノイズやピンクノイズなどは聞いたことがありますが、ブルーは初耳です。
調べてみます。
- 127 名前：122 mailto:sage [2013/11/19(火) 22:35:24.77 .net]
- なるほど納得
非零要素を一次元上（あるいは二次元とか）に並べて
それを仮想電子のようにみなし仮想クーロン斥力みたいなの計算して
要素番号補正したらとか考えてたんだが
それだと逆に傾向出ちゃうか
値を入れた同じ行、同じ列に対して再度選択を阻害するパラメーターを入れて
云々かんぬん…いかん、わけがわからくなってきた
逃走っ（しゅたたた…）
- 128 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:54:30.96 .net]
- やってみましたら、たとえ Haskell であっても、
>113 程度の規模ではシャッフルでもくじ引きでも、あっという間でした。
>>114 の指摘通りで、かなり恥ずかしいです。
憶測で遅いと決めつけず、質問する前に試すべきでした。
プログラムの見やすさが抜群に良いという点で、くじ引きの方法でやることにします。
みなさん、ありがとうございました。
- 129 名前：デフォルトの名無しさん mailto:sage [2013/11/27(水) 04:14:03.66 .net]
- Edmonds's Blossom Algorithmを詳しく説明していただけないでしょうか
|
 |
