- 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
- 784 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 22:37:30.79 ID:U/4/CI9X.net]
- >>783
やってみます。ありがとうございます。
- 785 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 08:38:55.46 ID:mo1gDnuH.net]
- 宝くじの攻略とか言ってる段階で確率論でも学んだほうがいいのでは？
- 786 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 08:49:47.26 ID:g55jIHl1.net]
- 確率論学んだからって狂人が正気に戻る訳でもあるまい。
- 787 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 09:12:37.94 ID:h/dwjgiw.net]
- 宝くじが夢を買うってことなら、この人は夢をプログラミングしてるんだよ。
- 788 名前：デフォルトの名無しさん mailto:sage [2015/09/19(土) 09:22:06.02 ID:5cHEEdwc.net]
- 獏は夢を食べます
- 789 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 13:08:11.01 ID:hRep6fdc.net]
- >>786
確率のいい教科書はありませんか測度論までケアしてくれるやつ
- 790 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 13:48:42.32 ID:ZXXgaQ/P.net]
- >>789
・測度と積分 入門から確率論へ
・はじめての確率論 測度から確率へ
この辺りを読まれてはいかがでしょうか。
- 791 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 16:19:22.10 ID:hRep6fdc.net]
- >>790
上の奴って品切れみたい，空手踊りとか肉体系で楽しそうだね
- 792 名前：デフォルトの名無しさん mailto:sage [2015/09/20(日) 17:05:20.53 ID:hheo9oaF.net]
- 測度と確率 小谷
プロ仕様だけど
- 793 名前：デフォルトの名無しさん [2015/10/06(火) 19:59:51.30 ID:uxUTfTFS.net]
- 受ける会社大丈夫？
下記の条件が全て当てはまる会社にご注意下さい。
・IT系 in tokyo
・「社名 労基」でググると過去の2chスレが出てくる
・転職会議で2.5点
- 794 名前：デフォルトの名無しさん mailto:sage [2015/10/08(木) 08:03:53.85 ID:Np+b0DPs.net]
- >>785
ナンバーズ4っぽいから、期待値の高い組み合わせを出したいんだろう。あれ、誕生日で買ったら当たっても安いんだよね。
- 795 名前：デフォルトの名無しさん mailto:sage [2015/10/18(日) 19:20:01.26 ID:mdnTkxCG.net]
- 保守
- 796 名前：デフォルトの名無しさん mailto:sage [2015/10/21(水) 12:58:47.56 ID:ngwDS6AM.net]
- BOOK・OFFで
2200円のこれを200円で買った俺って勝ち組？
i.imgur.com/6zlSiQq.jpg
- 797 名前：デフォルトの名無しさん mailto:sage [2015/10/21(水) 13:08:25.20 ID:Zr5MZtBC.net]
- ゴミにはビタ一文出すな
- 798 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 13:45:30.59 ID:8+WZrGwR.net]
- サッカーや野球のようなゲームがあったとします。
選手は毎年どんどん出現してきて、引退した選手もファイルに残ります。
ファイル名は必ずユニークなIDで、同じファイル名は存在しません。
ここまで仕様確定です。
もし、Aチームの選手はAフォルダに格納される方式を取ったとき、
チームに所属する選手はすぐ出せると思います。
しかし特定の選手を探したいときは難しくなります。
(例えば1990年の得点王選手のIDが記録されていたとして、そのIDにアクセスするのは若干めんどうです)。
そして、引退した選手も保存されるので、ファイルは一方的に増えて行きます。
100万や200万、1000万になるかもしれません。(どのくらいかは知りません)。
確実にアクセスは遅くなり、間違った方法だと検索も大量に取られます。
どのファイルがどこのフォルダに保存されてるのか記載するにしても、もしも仮にDが1億も並んでるとアホの極みと思うわけです。
良さそうな方法考えてください。
- 799 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 13:49:09.94 ID:vcVH8w6b.net]
- データベース使え
- 800 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 15:20:54.63 ID:eH4IcMDe.net]
- チームが買収されたり合併されたらどうすんの
- 801 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 18:50:14.31 ID:yGf9dC8a.net]
- >>798
データベース使え案件だけど無理なら自前で
選手IDをキーにしたB+木のインデックスファイルをつくり
それから検索する
- 802 名前：デフォルトの名無しさん mailto:sage [2015/10/31(土) 22:26:55.40 ID:RIZFllKe.net]
- オンメモリに収まる量ならともかく
外部データ連携するB+木とか自前で用意する方がリスク高いんじゃないの
しかも用途が野球なら実際に必要になる18人と監督+α以外ほぼ無駄データなわけで
そんなもんをまじめに管理するよりゲームの面白さに注力しろって意味でも
DB使え
- 803 名前：デフォルトの名無しさん mailto:sage [2015/11/01(日) 20:12:40.65 ID:MVvuxbKY.net]
- おまえらがいってることがすでにわかんねーよ
- 804 名前：デフォルトの名無しさん mailto:sage [2015/11/01(日) 20:16:08.48 ID:cyCCNHZp.net]
- 登場選手はなんと1000万人！
面白いのかそれ？ｗ
- 805 名前：デフォルトの名無しさん mailto:sage [2015/12/01(火) 15:30:58.86 ID:jz4WAacM.net]
- セジウィック4版が和訳されるのっていつ頃かな？
- 806 名前：デフォルトの名無しさん mailto:sage [2015/12/02(水) 19:19:28.88 ID:A58rIrCf.net]
- 実装したいアルゴリズムの名前がわからないので教えてください
知りたいのは以下の様なものです
---
for (int i = 0; i < 10; i++)
do_something(i);
これをクラスに展開して
int i = -1;
static bool Next() { ++i < 10; }
static int Value { get { return i; } }
static void Main() {
while (Next())
do_something(Value);
}
---
このように変換する方法について調べたいのです
実際に欲しいのはN重ループをフラットに繰り返しで処理する方法です
自力で解こうとしたのですが、どこかで勘違いをしているようで、うまく動いてくれません
名前が分からないと調べようがないので助けてください
- 807 名前：デフォルトの名無しさん mailto:sage [2015/12/02(水) 22:20:37.79 ID:yyIVeakG.net]
- イテレーターで抽象化したいってことかな
- 808 名前：デフォルトの名無しさん mailto:sage [2015/12/03(木) 00:25:03.13 ID:74Kx8KXh.net]
- >>807
そうです
Iteratorパターンというのですか？
このパターンについて調べてみたのですが多重ループを解く方法については記述が見当たりませんでした
- 809 名前：デフォルトの名無しさん [2015/12/03(木) 15:48:13.76 ID:5y9yFaIO.net]
- イタレーターを二つ以上用意する
- 810 名前：uy ◆Qawu9.2l1E mailto:sage [2015/12/03(木) 18:57:59.03 ID:tK7Nyube.net]
- ヒント：ruby
- 811 名前：805 mailto:sage [2015/12/03(木) 20:32:43.77 ID:74Kx8KXh.net]
- 木構造+イテレータでぐぐって解決しました
ありがとうございました
- 812 名前：デフォルトの名無しさん mailto:sage [2015/12/08(火) 20:54:01.39 ID:vWrFkfhW.net]
- デザパタ実践したらファクトリだらけになったんだがこんなもんなのかな
- 813 名前：デフォルトの名無しさん mailto:sage [2015/12/08(火) 23:56:43.50 ID:/pdSfCvK.net]
- >>812
ありがち
デザパタ厨のやつが作ったクラスが
全部createInstanceだらけで使いにくいだけのクソが出来上がってた
まさに早すぎる抽象化
やるならせめてDIとかリフレクションや
アノテーションを使えやって思った
- 814 名前：デフォルトの名無しさん mailto:sage [2015/12/11(金) 12:43:43.71 ID:fYAYo2Es.net]
- 数学っぽい問題なのですが、
n = 100のとき以下の３つの条件を満たす単位分数の組みを考える
1/n1 + 1/n2 + ....+ 1/nk ＝ 1 （１）
n1 + n2 +....+nk = n （２）
n1 < n2 < ....<nk （３）
これをプログラミングを用いて解きたいのですが、いい方法が思い浮かばなくて困っています
何か方法ありましたら、教えてください
- 815 名前：デフォルトの名無しさん mailto:sage [2015/12/14(月) 23:31:43.15 ID:R0gDPv6y.net]
- 簡単な乱数生成のアルゴリズムで、線形合同法と言うのがあります。
数学のループ記述はよく分からないので、プログラム風に書くとこうです。
x = (a * x + b) % mod;
xが上書きされて何度も順番に使用さていると言う意味です。
% mod は割った余りです。
32bit環境なら
mod = 2 ** 32;
となっています。(つまり上記の式は32bitで表現できる最大値未満の乱数がxとして算出され、次の乱数生成にまた使用されます)。
64bit環境なら
mod = 2 * 64;
となっています。
x の初期値は何が入っていても構いません。(例えば式の初回使用時などに適当な値を入れます。例えば今の時間とか)。
a と b は定数で、これを何に設定するかによって乱数が良質であるか悪質であるか、また使える周期の長さが変わります。
周期が長くて良質な物を出すとき、これに何を設定すると良いのか分からないので教えてください。
32bit用と64bit用の両方をお願いします。
ちなみに、それを考えるのがどの程度大変 (または簡単) なことか分からんで質問してます。
- 816 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 18:58:35.99 ID:y7r4C3dc.net]
- https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
例から適当に拾え
てか 線形合同法 定数 あたりでググればソースと解説があるだろ
- 817 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 19:00:49.31 ID:GmzcEDm2.net]
- MT使え
- 818 名前：デフォルトの名無しさん mailto:sage [2015/12/15(火) 21:14:19.01 ID:rY8ZFzdV.net]
- >>816
>>817
ありがとうございます
- 819 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 02:29:13.85 ID:WaYE86JM.net]
- >>814
それ解はあるの？ 無限に続くのでは？
- 820 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 08:55:42.31 ID:2+dP2nJG.net]
- >>819
単位分数って言ってるんだから、各 nk は 1 以上の整数だ。
条件 (2) によって nk は有限個しかないよ。
この条件を満たす解が存在するかどうかは知らん。
アルゴリズム的にはどうなんだろうな。
単純に条件 (2) と (3) に合うものを 1/2 + 1/98 から順に網羅していって、
条件 (1) に合うものをピックアップしていくというのはクソ遅いかな。
もちろん、浮動小数点でやったら誤差が出るから、すべて整数計算だけど。
- 821 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 11:58:26.07 ID:oLnMv084.net]
- その方針だと何れにせよnのdistinct partitionの全体を走る必要がある。
「よい」アルゴリズムのオーダーは知らないけど, 分割数の漸近公式だけ見れば少なくとも準指数時間アルゴリズムになる
- 822 名前：デフォルトの名無しさん mailto:sage [2015/12/23(水) 14:39:33.46 ID:oLnMv084.net]
- やってみた, (2, 6, 7, 8, 21, 56), (3, 5, 6, 8, 9, 24, 45), (3, 4, 7, 8, 12, 24, 42)の3組だけらしい
- 823 名前：デフォルトの名無しさん mailto:sage [2016/01/04(月) 07:49:13.32 ID:quO35K88.net]
- 遺伝的アルゴリズムの無料電子テキスト日本語版が無い
日本の人工知能はクソ
- 824 名前：デフォルトの名無しさん mailto:sage [2016/01/04(月) 12:41:00.87 ID:21yj4oPz.net]
- 北野某に聞けよｗ
- 825 名前：デフォルトの名無しさん mailto:sage [2016/01/05(火) 21:09:57.94 ID:i0IFFoJB.net]
- 人工知能予算は懐の中に消えていきました
- 826 名前：デフォルトの名無しさん [2016/01/20(水) 23:38:29.66 ID:epdaSdlJ.net]
- オライリーの入門データ構造とアルゴリズム、原著のアマゾンレビュー見たら間違いがものすごい多いらしいけど翻訳は直ってるの？
- 827 名前：デフォルトの名無しさん mailto:sage [2016/01/21(木) 22:44:56.10 ID:vB+/Osfo.net]
- いいえたとえ明らかに間違いだ確信しても悪だと感じてもそれを正確に翻訳するのが翻訳家の仕事なのです
翻訳家ごときが主張を勝手にねじまげてはいけないのです
- 828 名前：デフォルトの名無しさん mailto:sage [2016/01/22(金) 00:08:33.24 ID:raZVxvb6.net]
- そりゃそうだな
もしもエラッタが出てるとしてもそれも反映するんじゃなくエラッタとして翻訳して付けるだろうし
- 829 名前：デフォルトの名無しさん mailto:sage [2016/01/23(土) 22:24:00.13 ID:gfbrLyNS.net]
- >>827
昔、「フォトンマッピング」という、
原著の間違い（計算式も含め）が大量に修正されていて、
挿絵まで挿入されて、しかも原著より安いという驚きの翻訳本があった。
まぁ、原著に間違いが多かったのには、それなりの訳があったんたが。
- 830 名前：デフォルトの名無しさん mailto:sage [2016/01/24(日) 04:41:54.83 ID:QDUQ11dL.net]
- 日本の報道は捻じ曲げすぎるよね
海外の出来事のほとんどがまともに入って来ない
- 831 名前：デフォルトの名無しさん mailto:sage [2016/01/24(日) 06:35:32.21 ID:4ZCEMBL4.net]
- ロイターあたりを眺めるのか？
- 832 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 00:49:21.41 ID:DXoTpOvl.net]
- >>827
お前の言ってることは実社会を無視した単なる教条主義
翻訳にしろ何にしろ他人に役立つ仕事をするのに必要なのはpragmatismだよ
ニートして自分の部屋にこもってないで偶には人様の役に立つ仕事をしに外に出ろよ
- 833 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 06:29:16.92 ID:8H4JYu/t.net]
- ずいぶんでかいつりばりだなぁ
- 834 名前：デフォルトの名無しさん mailto:sage [2016/01/25(月) 11:08:55.31 ID:qRGGYULG.net]
- >>827
原著者に問い合わせるだろう普通ｗ
- 835 名前：デフォルトの名無しさん mailto:sage [2016/01/29(金) 04:26:25.65 ID:1+b9HDsX.net]
- 機械翻訳だと中身の検証なんてしないよ
集合知プログラミングという悪しき前例もあるし
- 836 名前：デフォルトの名無しさん [2016/02/07(日) 12:46:18.16 ID:l17BC95H.net]
- 既存のDBがあり顧客都合によりDBレイヤの変更が許されない
要望ではUIレイヤを総入替してAPレイヤをリファクタリングしたいということになっています
しかし現実ではそもそもUIとAPとDBが密結合していてレイヤという概念は存在しません
こういった案件で役立つアーキテクチャスタイルやパターンは何でしょうか
DBの変更が効かないのでドメインモデルパターンは実質不可能です
全てを諦めて貧血モデルとトランザクションスクリプトを使うしかないのでしょうか
リファクタリング案件なのにコードが綺麗になる未来が見えません
- 837 名前：デフォルトの名無しさん mailto:sage [2016/02/07(日) 15:38:18.60 ID:Ah5srJ1t.net]
- >>836
なんとかレイヤってからには基本設計レベルでは元々レイヤはあったんでしょ
それらが実際は密結合しているのが嫌なんでしょ
つまりレイヤを疎結合にするのが目的なわけでしょ
だからUIレイヤを総入替するわけでしょ
将来的なリファクタリングを見据えて疎結合にするのが先なんじゃないの
コードが綺麗とかリファクタリングするとかはその先の話でしょ
- 838 名前：デフォルトの名無しさん mailto:sage [2016/02/07(日) 16:19:13.81 ID:Ah5srJ1t.net]
- あーそれとリファクタリング案件なんて誰が言ってるのか知らんけど
現実にリファクタリングにお金払う会社なんて存在しないからね
たぶん内部事情に詳しい客とか上の人とかが強調して言ってるだけで要件ではないよね
リファクタリングなんて曖昧な言い方は止めて上手いこと見積りに含めないと
現実には行われない可能性が高いね
- 839 名前：デフォルトの名無しさん [2016/02/28(日) 14:04:19.66 ID:kcbLGyy1.net]
- リポジトリパターンなるものを知って使ってみたのですがこれ遅すぎませんか？
テキストファイル用のリポジトリから集約を全件取得
オラクルDB用のリポジトリに対して取得した各集約を保存して最後にコミット
という何気無い処理にもかなり時間がかかっています
リポジトリパターンは業務用システムで実用に耐えうるのでしょうか
- 840 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 21:39:59.71 ID:rqKeW9kJ.net]
- >>839
考え方がおかしい
それってあくまでも層が違うモジュールをぶった切って設計やテストをしやすくするって用途だから
業務の永続化手段として使うものじゃないよ
- 841 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 22:00:28.10 ID:cktW2eh6.net]
- >>840
よくわかりません
一般的な業務用システムでは永続化層を設けないのですか？
- 842 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 23:13:58.36 ID:rqKeW9kJ.net]
- そういうことじゃなく
まあ遅いって判断してるわけだから
何かやり方がおかしいんだよ
- 843 名前：デフォルトの名無しさん mailto:sage [2016/02/28(日) 23:21:17.03 ID:GBJ/TPKE.net]
- >>839
リポジトリパターンが遅いっていう忌みがわからんｗ
じゃあそのまんま同じ処理を他のやり方でやったら普通に早いの？
- 844 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 00:06:09.33 ID:XUzsrygn.net]
- >>843
バルクコピーを使うと高速になります
ですがこれはリポジトリパターンでは使えそうにありません
- 845 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 00:31:30.59 ID:2q2DW/zb.net]
- それパターンなんて関係なくて、バルクコピーなら速くてインサートは遅いってだけじゃん。
- 846 名前：デフォルトの名無しさん mailto:sage [2016/02/29(月) 10:54:35.48 ID:LDxMFaxC.net]
- >>844
そのまんま同じ処理でって言ってるじゃん
バルクコピーしたら処理変わってんだろｗ
リポジトリパターンがその他の設計パターンで実装したものより遅いのかって聞いてんの
- 847 名前：デフォルトの名無しさん [2016/03/14(月) 14:56:36.24 ID:IZ2LWlGv.net]
- 質問です。たとえば以下のようなファイル名のリストがあったときに、ファイル名の類似性によってグルーピングするような一般的なアルゴリズムって何があるでしょうか?
検索キーワードだけでも教えてもらえると助かります!
123-456.zip
書類-1.doc
書類-2.doc
456-789.zip
→グループ化
123-456.zip
456-789.zip
書類-1.doc
書類-2.doc
- 848 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 16:02:15.36 ID:9C/zUDR9.net]
- つベイズ
- 849 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 16:04:35.86 ID:9b9aepwB.net]
- 拡張子で分けてるだけじゃないの？
- 850 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 18:51:10.95 ID:4xYadpbt.net]
- 正規表現である程度のパターンごとに表現する。
- 851 名前：デフォルトの名無しさん mailto:sage [2016/03/14(月) 19:19:25.61 ID:DzDVqAyb.net]
- 男の娘はどちらに分類されるべきかとか考えると趣向による問題だし一般的な分類は無理なんじゃないかな
文字種とかで類似度の高いペアに分けるぐらいでしょ
- 852 名前：デフォルトの名無しさん [2016/03/16(水) 00:01:25.62 ID:MRypUzWZ.net]
- >>847
レーベンシュタイン距離とか
- 853 名前：デフォルトの名無しさん [2016/04/05(火) 16:33:18.67 ID:m6kqb6v+.net]
- ダイクストラのアルゴリズムの正しさの証明がよく分からないのですが、
何かいい本はありますか？
- 854 名前：デフォルトの名無しさん [2016/04/05(火) 16:46:05.13 ID:m6kqb6v+.net]
- imgur.com/MdPoKq5.jpg
imgur.com/PRjr5CT.jpg
imgur.com/41t2x4S.jpg
↑ダイクストラのアルゴリズムの正しさの証明についてですが、
3枚目の赤で囲ったあたりが分かりません。
この証明、分かる人いますか？
- 855 名前：デフォルトの名無しさん [2016/04/05(火) 16:50:41.63 ID:m6kqb6v+.net]
- 3枚目の画像で、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、その後、このことは証明中で使われていないように見えます。
これは何なんでしょうか？
- 856 名前：デフォルトの名無しさん [2016/04/05(火) 16:58:30.51 ID:m6kqb6v+.net]
- 3枚目の画像に、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、
d(x) ≦ d(y) + l(y, x)
ということしか言えないかと思います。
これについてはどうですか？
- 857 名前：デフォルトの名無しさん mailto:sage [2016/04/06(水) 00:31:36.30 ID:pFDX1Wjl.net]
- (b)のyとxについては(a)のwとvと同じかと。最短経路上にあると仮定してるから＜はありえない。
これに別途証明を与える必要があるかどうかは別として。
- 858 名前：デフォルトの名無しさん [2016/04/06(水) 08:08:37.20 ID:QfbBfCGx.net]
- >>857
ありがとうございます。
>>855
の疑問についてはどうでしょうか？
どうも使われていないように思います。
- 859 名前：デフォルトの名無しさん mailto:sage [2016/04/06(水) 09:08:25.64 ID:loGBTR8N.net]
- >>858
「v が先に取り出されたという話ですすめてるのに、d(x) < d(v) となるような x (図にもあるとおり、この x はまだヒープから取り出されてないので、V’ には属さない) があるのはおかしい」
ってことを言いたいんだろうけど、ややこしいね。
y も持ち出さないと d(x) = d(y) + l(y, x) が最短ですってことが言えないんじゃないのかな。
- 860 名前：デフォルトの名無しさん [2016/04/06(水) 23:05:03.06 ID:QfbBfCGx.net]
- >>859
ありがとうございます。
-------------------------------------------------------------------
imgur.com/X6aS3J5.jpg
imgur.com/UyANGwz.jpg
優先度付きキュー（プライオリティーキュー）について質問です。
2枚目の画像に、優先度付きキューへキーを追加する insert(key) の疑似コードが書いてあります。
以下にそれを書きました。
insert(key)
■■H++
■■A[H] = -INFTY
■■heapIncreaseKey(A, H, key)
heapIncreaseKey(A, i, key)
■■if key < A[i]
■■■■エラー：新しいキーは現在のキーより小さい
■■A[i] = key
■■while i > 1 && A[parent(i)] < A[i]
■■■■A[i] と A[parent(i)] を交換
■■■■i = parent(i)
- 861 名前：デフォルトの名無しさん [2016/04/06(水) 23:05:47.70 ID:QfbBfCGx.net]
- さて、質問ですが、なぜ、A[H] = -INFTY などとわざわざ代入しているのでしょうか？
heapIncreaseKey の一番最初の if 文は必ず偽になりますから無意味であるように思います。
なぜこのような無駄なことをしているのでしょうか？
以下のようなコードになぜしないのでしょうか？
insert(key)
■■H++
■■i = H
■■A[i] = key
■■while i > 1 && A[parent(i)] < A[i]
■■■■A[i] と A[parent(i)] を交換
■■■■i = parent(i)
- 862 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 00:15:40.81 ID:pUEgfdfM.net]
- if 変数
else
などと条件分岐すると、速度も遅いし、
ややこしくてバグも増えるから、条件分岐を減らす
配列の番兵なども同じ
- 863 名前：デフォルトの名無しさん [2016/04/07(木) 02:46:40.63 ID:D2Sjbg8N.net]
- >>862
ありがとうございます。
すみませんがよく分かりません。
if 変数
else
などとしているのは、むしろ -INFTY を代入しているコードのほうではないでしょうか？
- 864 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 03:52:09.66 ID:BbGPO0PR.net]
- >>861
優先度ヒープは一度キューに入れたオブジェクトやタスクの優先度を後から変更できた方が実用性が高いんだけど、その2ページだけなら必要ないかも。
その書き直したコードでも大丈夫かもしれない。
アルゴリズムとしてはどの本にも同じようなことが書いてあるのは当然なんだけど、 実は全く同じ擬似コードがコルメン本にある。
バイブル的な本だからそこからパクってきたのかもしれない。
もし大学の情報系の生徒だったりITの仕事で使うなら、コルメン本(アルゴリズムイントロダクション)を進める。
2冊で1万円近くなるし、ページ数も多いものの、解説や証明は丁寧だし版も重ねてるから誤訳や誤字も少ない。証明の解説も詳しい。
他の本でわからないと結局そういった名著を当たることになる。
- 865 名前：デフォルトの名無しさん mailto:sage [2016/04/07(木) 04:55:53.13 ID:pUEgfdfM.net]
- もし変数aに値が入っていないと、一々、nil, undefined のチェックが必要になる。
それが面倒だから、初期値を代入している
if a{
aに値が入っている時だけ、処理する
}
漏れも、JavaScriptで配列を使って、2分ヒープを作ってみたので、参考にして
2分ヒープ(BinaryHeap)
jsdo.it/michihito/bGH5
- 866 名前：デフォルトの名無しさん mailto:sage [2016/04/08(金) 18:59:01.77 ID:QHM1+lud.net]
- カードゲームのaiを実装したいんですが、
行動に対する評価値を２分構文木に入れていくっていうロジックはありですか？
あと、行動すると巻き戻せない、シミュレートできないので、どうしようかなと。
行動に対するロールバックも実装しなければいけないでしょうか？
- 867 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 04:09:29.14 ID:MwGqsbeb.net]
- >>866
どういうルールのゲームで、どういった種類の「行動」があって、どうして2分構文木(2分木じゃないの?)になったの？
- 868 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 13:01:51.57 ID:FoBfIIvs.net]
- >>867
基本的にはカードを出す(呪文を唱える、モンスターを出す)、物理攻撃する、パスするぐらいですかね。
あ、２分探索木じゃ行動が2つじゃないから駄目な気がしてきました。
- 869 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 14:42:40.27 ID:MwGqsbeb.net]
- >>868
AIで探索木的なのを考えてるならA*を勉強してみるといいかも
- 870 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 15:13:16.75 ID:LJnl+JdY.net]
- A* は解領域にマッチしたヒューリスティック関数を決めてあげるのが大変だ‥
- 871 名前：デフォルトの名無しさん [2016/04/09(土) 19:20:31.07 ID:aVoK2gcj.net]
- カードのシャッフルアルゴリズムって
どうしようかと悩みだすと結構悩むなぁ
- 872 名前：デフォルトの名無しさん mailto:sage [2016/04/09(土) 22:57:17.76 ID:O9j9lH5Y.net]
- >>871
一番シンプルなのは
配列からランダムに
取って戻すのを繰り返す
- 873 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 00:15:07.59 ID:8wDwAIGa.net]
- >>871
悩むなぁとか言ってるけど、他の質問も見てると自分で何も考えてないよね？誰かがヒントと方向性示してくれるのを待ってるだけで。
- 874 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 00:17:50.87 ID:tVvAXki7.net]
- おいおい。頭空っぽの奴に自分で考えろとか酷いこと言うなあ
- 875 名前：デフォルトの名無しさん [2016/04/10(日) 08:38:44.69 ID:oXSlNHSo.net]
- >>864-865
あるがとうございました。
- 876 名前：デフォルトの名無しさん mailto:sage [2016/04/10(日) 10:29:49.38 ID:viI7M/4y.net]
- >>871
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC_-_%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB
- 877 名前：デフォルトの名無しさん [2016/04/16(土) 19:09:43.89 ID:RkF64Ds4.net]
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
の「領域探索」が分かりません。
どうして↓のような2分探索木を作り利用するのですか？
imgur.com/uRbPFzt.jpg
imgur.com/TSevr6v.jpg
- 878 名前：デフォルトの名無しさん [2016/04/16(土) 19:11:14.59 ID:RkF64Ds4.net]
- location ではなく x の値をノードに持たせないのはなぜでしょうか？
- 879 名前：デフォルトの名無しさん mailto:sage [2016/04/18(月) 11:03:47.60 ID:Jl/B9TZo.net]
- >>877
2分探索木を使う理由は探索時間を早くするためでしょう。
うまくいけば探索数が半分になるから
>>878
二分探索木をn個の配列で実装しているので、配列の添え字をxにする方法は
xが大きな数だったり整数でなかったりの場合に都合が悪いから
ただこれデータがソートされていることが前提だよね。そのまま二次元に
展開できるのかな
- 880 名前：デフォルトの名無しさん [2016/04/18(月) 20:25:41.28 ID:6VYHQoTT.net]
- >>879
半分どころじゃなくて log n でしょ。
配列の添え字じゃなくて配列の中身をなぜ x にしないのか聞いているんじゃないの？
- 881 名前：デフォルトの名無しさん [2016/04/18(月) 20:30:02.32 ID:6VYHQoTT.net]
- 多分、 location の値を配列に入れているのは、2分探索木の
左右のバランスがよいことが保証されるからじゃないの？
- 882 名前：デフォルトの名無しさん [2016/04/19(火) 10:53:36.63 ID:b4Mb+Ui9.net]
- >>877-878
2次元以上に拡張するためにはそのようにする必要がある。
- 883 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 01:45:04.87 ID:jf1w54Av.net]
- 木のバランス取れて初めて使えるレベルだろ
状況によっては木構造なんか作らず線形に探索した方が速いし
- 884 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 12:27:46.43 ID:9Ocgrhnl.net]
- >>883
状況によっては木構造の方が速くて線形に探索した方が遅い状況も作れるな
|
 |
