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

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 772 名前：デフォルトの名無しさん mailto:sage [2015/09/12(土) 21:06:00.39 ID:Yzh+CkQk.net] ci.nii.ac.jp/naid/170000087534 ci.nii.ac.jp/naid/170000087558 どっちも内容同じ？ 773 名前：デフォルトの名無しさん mailto:sage [2015/09/13(日) 09:11:22.28 ID:n3zvmQA3.net] ハロー "Hello, World" OSと標準ライブラリのシゴトとしくみ 単行本 – 2015/9/12 www.amazon.co.jp/dp/4798044784/ こんなのでた。 面白そう。 774 名前：スモモンガー mailto:sage [2015/09/16(水) 21:09:13.76 ID:k300cqkh.net] とりあえずソース直しました。 >>772 私は二つ投稿してないんですが（汗）一回修正入れたんでそのせいかもしれないです。新しいほう が間違えがないんじゃないかと思います。 775 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 01:36:24.28 ID:h/C+p+kS.net] 毎日変わる文字列がどのパターンに当たるか判定するソフトを作りたいんですが、 どの言語を使えばいいですか？ 宝くじの攻略に使いたいんですが htmlとVBを10年前にやったことがある程度の能力しかありません 0 7 �A 3 �D 6 8 �H �@ 4 と毎回不規則に並んでいる数字から毎回不規則に4つ選び、 該当の2591の形がどのパターンなのかを判断するというソフトです さらにこのとき選ばれた2591を別の不規則の数列に当てはめたときも判定するようにしたいです 0 �A 4 6 8 �@ 3 �D 7 �H この数列のときはどの形なのか・・・という具合にです これを平日の間手動でやるのは限界があったので 776 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 09:31:31.86 ID:8C/CtMhx.net] アルゴリズムだろ、馬鹿には無理だが 777 名前：デフォルトの名無しさん [2015/09/17(木) 15:49:14.71 ID:jeXjMZOh.net] アルゴリズムの勉強って何をすればいいの？ 何も見ずに書けるようになるとか？ 778 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 16:56:57.71 ID:RFJKEvXv.net] とりあえずwiki行ってリンク辿れば？ 779 名前：デフォルトの名無しさん mailto:sage [2015/09/17(木) 17:07:55.21 ID:ylAQcAdL.net] >>775 どういう処理がしたいかよくわからんけど データがすくないならスクリプト言語，多いんならC++でも使えば？ 780 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 00:53:57.52 ID:kZ1aVgi2.net] >>777 セジウィックや、オライリーのインド人の本など、 アルゴリズムの本は、一杯出ている >>775 丸で囲んだ数字などの、 MS-CP932の機種依存文字を使うな。 これらは、Shift-Jisにも属さない文字 781 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 02:38:17.41 ID:YgOe18Uv.net] 囲み数字はShift_JISX0213に入ってるんだよなあ Shift-Jisとかいう独自規格のことは知らないけど 782 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 17:33:44.18 ID:uevEmGa3.net] >>780 オライリーの本調べてみたら問題がたくさんのってるようですね。 解いて勉強すればいいということですか 783 名前：デフォルトの名無しさん mailto:sage [2015/09/18(金) 20:20:23.43 ID:7AiId5VK.net] >>782 とりあえず解いていけばよい まずは既存のアルゴリズムを知ること そして問題に対して適切なアルゴリズムを適用して解決できるようになること 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 状況によっては木構造の方が速くて線形に探索した方が遅い状況も作れるな 885 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 13:48:32.88 ID:6r15gyc9.net] >>883 では、どういう状況の場合に線形探索を利用するのか先生から説明をどうぞ 886 名前：デフォルトの名無しさん [2016/04/21(木) 14:08:39.31 ID:0vzabbti.net] MIT系の『Introduction to Algorithms』 と Princeton系の『Algorithms』 どっちがおすすめ？ 887 名前：デフォルトの名無しさん mailto:sage [2016/04/21(木) 14:19:32.38 ID:TG5MxLgd.net] >>886 頭がいいなら前者、バカなら後者 888 名前：デフォルトの名無しさん [2016/04/22(金) 08:39:42.12 ID:pemVeZaH.net] Introduction to Algorithms って当たり前のことをループ不変とかを使って説明しているよね。 はっきりいってくどい。 889 名前：デフォルトの名無しさん [2016/04/22(金) 20:17:37.76 ID:pemVeZaH.net] AlgorithmsはJavaのソースコードが載っていて具体的。 890 名前： ◆QZaw55cn4c mailto:sage [2016/04/22(金) 23:06:44.42 ID:DMiaofP1.net] >>883 バランスを常にとるように作ることはできる 891 名前：デフォルトの名無しさん [2016/04/23(土) 10:50:53.22 ID:M5Qy0F9U.net] >>888 Introduction to Algorithmsは確かにくどくて読みにくい。 別に難しい本でもない。 892 名前：デフォルトの名無しさん [2016/04/23(土) 10:51:34.32 ID:M5Qy0F9U.net] 結論は、 Donald E. Knuthの本が一番。 893 名前：デフォルトの名無しさん mailto:sage [2016/04/23(土) 16:24:35.42 ID:jNieRcbT.net] 終了 894 名前：デフォルトの名無しさん [2016/04/24(日) 09:33:35.68 ID:jhscNiw7.net] 日本人著者によるアルゴリズムの本で一番いい本って浅野孝夫の情報の構造っていう本。 石畑清の本ってAVL木の説明が出鱈目だってAmazonのレビューに書いてあった。 895 名前：デフォルトの名無しさん [2016/04/24(日) 09:37:13.46 ID:jhscNiw7.net] ところでPascalで書かれている本が多いのはなぜ？ Cのほうが分かりやすくない？ 896 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 09:42:22.03 ID:HSA/nLEW.net] pascal は学術系なんだよ。 897 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 11:11:12.52 ID:Z/fpIQVL.net] 処理のフローが書いてあるだけだろ 898 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 13:30:26.41 ID:n5HZWl0r.net] >>892 あれは回答とかあっさりしすぎなとこあるだろ。。 899 名前：デフォルトの名無しさん [2016/04/24(日) 18:45:27.10 ID:jhscNiw7.net] エイホホップクロフトウルマンのデータ構造とアルゴリズムを図書館から借りてきて 読んでいるけど、説明がいい加減すぎる。 900 名前：デフォルトの名無しさん mailto:sage [2016/04/24(日) 23:44:13.95 ID:pid8Qk86.net] 入門 データ構造とアルゴリズム、2013、オライリー Narasimha Karumanchi(インド人) 著 セジウィック・石畑清が定番 川中真耶も、赤黒木の説明だったかな？ わかりやすかった 901 名前：デフォルトの名無しさん [2016/04/25(月) 08:06:15.68 ID:rnP5hl5x.net] Karumanchiの本はこうすればいいということしか書いていない。 なぜそうすればいいかが全く書かれていない欠陥本。 902 名前：デフォルトの名無しさん [2016/04/26(火) 10:56:55.51 ID:JtHly74d.net] 石畑清の本は説明が面倒なところは容易に分かるとかいって逃げている。 903 名前：デフォルトの名無しさん [2016/04/27(水) 09:48:32.30 ID:Sdx3kEFz.net] >>894 浅野孝夫のその本、最高だな。 超詳しく省略なく書いてある。 書きすぎとかいう批判が出そうなくらいだな。 904 名前：デフォルトの名無しさん [2016/04/30(土) 11:02:54.99 ID:jYDzAJS5.net] アルゴリズムイントロダクションを買おうと思うんだけど、 総合版にするか第1巻第2巻のみにするかで迷っている。 後半の特殊なアルゴリズムはいらないような気もするし。 なんで総合版って割高なの？ 905 名前：デフォルトの名無しさん mailto:sage [2016/04/30(土) 18:06:23.76 ID:YBbs5n7s.net] 総合版ってあの鈍器だっけ。 906 名前：デフォルトの名無しさん [2016/04/30(土) 19:17:12.58 ID:jYDzAJS5.net] 総合版を買うことにしました。 907 名前：デフォルトの名無しさん [2016/05/01(日) 13:40:03.98 ID:tKi6j9CT.net] 匿名通信（Tor、i2p等）ができるファイル共有ソフトBitComet（ビットコメット）みたいな、 BitTorrentがオープンソースで開発されています 言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？ Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします https://twitter.com/Lyrise_al ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできないアスペルガーｗ The Covenant Project 概要 Covenantは、純粋P2Pのファイル共有ソフトです 目的 インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します 特徴 Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW) 接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です DHTにはKademlia + コネクションプールを使用します UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります) 検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません ｑ 908 名前：デフォルトの名無しさん [2016/05/01(日) 20:44:59.79 ID:u3cieUqF.net] >>903 ポインタを使っていないのはなぜなんだろうか？ Pascalってポインタを使えるよね。 909 名前：デフォルトの名無しさん mailto:sage [2016/05/01(日) 21:24:53.98 ID:JP6hgmB0.net] >>908 可能な限り参照で済ませる文化だったかと 910 名前：デフォルトの名無しさん [2016/05/02(月) 03:02:21.21 ID:/Hk1TQTD.net] 古いからと否定する気はないけど今なら良い書籍が沢山有る気がするぜ どれがそうなんだって言われたら困るけど２０年前よりはいい本が出てる気がする 911 名前：デフォルトの名無しさん [2016/05/02(月) 09:17:48.88 ID:F0I20g+z.net] >>910 そうか？ 日本語の本では、アルゴリズムイントロダクションくらいしか思い浮かばない。 ほかに新しくていい本なんてあるか？ 912 名前：デフォルトの名無しさん [2016/05/02(月) 13:17:36.23 ID:F0I20g+z.net] 比較的新しい本でいい本っていうと、翻訳系以外だと全く思い浮かばないんだが。 913 名前：デフォルトの名無しさん [2016/05/02(月) 18:10:09.56 ID:F0I20g+z.net] 浅野孝夫の本はクイックソートとか載っていないのがいいね。 914 名前：デフォルトの名無しさん mailto:sage [2016/05/03(火) 10:25:55.27 ID:xwMa7zwR.net] アルゴリズムイントロダクションって具体的にどれくらい難しいですか？（予備知識の多さではなく理解の難しさ） 数学科向けの数学書ぐらい？ 915 名前：デフォルトの名無しさん [2016/05/03(火) 14:57:28.35 ID:bxMOJzqX.net] 簡単。 916 名前： ◆tAo.kQ2STk mailto:sage [2016/05/03(火) 15:46:52.15 ID:CPxVolRD.net] ちょっとOS書いてるんだけど 可変長かつ連続したメモリ領域が本当に必要になるケースはOSレベルではそんなに無いって事を仮定して ・メモリ全体を1つ16バイトのチャンクに分ける ・各チャンクのアドレスの下4ビットが常に0になるので、普段はアドレスを4ビット右シフトした値を識別子として保持する としてアロケータを組んでみてます。 32ビットの識別子で36ビット(64GiB)の空間を扱えるって利点の他に x86_64のglibc mallocが1確保に対し管理領域として追加で8 Bytes消費するのと比較して、 こちらは16バイトの確保に対して管理領域として1ビット必要なので glibc mallocで1024バイトの連続した領域を確保するのと同じ利用効率になり、かつ 「ポインタ」の保存に必要な領域が半減するという利点があります。 アドレスの算出にシフト演算が必要な点と、 基本的なデータ構造(list, set, map, hash, ...)を 1個16バイトのチャンクの組み合わせとして表現するのがちょっと手間である事 連続したメモリ領域の確保に別なアロケータが必要である事が主な欠点です。 実際には、4KiB単位の連続したメモリ領域をアロケータが面白みもない方法で確保して、 その中身をチャンクとして分割し、先頭2チャンクを管理領域にして確保/開放を行うという実装にしています。 連続したメモリ領域が本当に必要でも、4KiBあれば十分と今は仮定しています。 こういう方法ってこのスレ的には既出？ 917 名前：デフォルトの名無しさん [2016/05/03(火) 18:42:53.59 ID:bxMOJzqX.net] >>914 日本人の書いた薄っぺらい教科書よりも簡単。 918 名前：デフォルトの名無しさん mailto:sage [2016/05/03(火) 18:52:57.38 ID:k0lWibxS.net] >>914 ページ数は多いものの、説明は丁寧だから難しいということはない。大学の1,2年向け。 一冊の小さくまとまった教科書と違って説明を端折ったりしてないから、途中でわからなくなって結局別の本を買い足したりする必要がない 919 名前：デフォルトの名無しさん [2016/05/03(火) 19:03:24.76 ID:bxMOJzqX.net] ただ、直観的に明らかな事実もわざわざご丁寧に説明していてうざい。 920 名前：デフォルトの名無しさん [2016/05/03(火) 20:50:04.37 ID:bxMOJzqX.net] 浅野孝夫の『情報の構造』に載っているプログラム例がエレガントで感心した。 921 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 08:24:35.18 ID:PCMiFBXM.net] >>917-919 ありがとうございます 922 名前：デフォルトの名無しさん [2016/05/04(水) 12:49:25.38 ID:A2cfTnr6.net] >>920 浅野孝夫のその本は説明が粗雑なところを詳細なプログラムを読むことで補完しなければならないところが難点。 923 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 15:23:50.62 ID:OcRpngHJ.net] .>>916 さっぱりわかんね 要するにビットマップで管理するってことか？ 勝手にやれとしか 924 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 16:00:56.01 ID:p+LvbHBp.net] >>923 要するに、32ビットのポインタで64GiBの領域を使えるって事 普通は64ビット版のプログラムはポインタを64ビットに拡張するんだけど、 木構造のようなポインタを多用するデータ構造の場合は 32ビット版と比較してメモリの効率が半減するデメリットがある。 この方法だと、メモリ効率を落とさずに4GiBを超えるメモリ領域を同時に使える。 既出かどうか(或いはもっと良い方法があるか)知りたかった 925 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 16:38:51.07 ID:WruTeJWf.net] アロケータが確保する分にはいいとして、任意のポインタをどう表現するのかねぇ 926 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 17:24:52.95 ID:p+LvbHBp.net] 任意のポインタを、アドレスを4ビット右シフトした値として表現する。 ポインタが指す先は常にチャンク境界(16バイト)にアラインメントされてて、 ポインタを使うときは4ビット左シフトしてアドレスに変換してから使う。 「ポインタを変数とかに代入してとっておくこと」と「ポインタをデリファレンスして他所から値を持ってくること」を分けて考えてる。 1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。 https://github.com/pixie-grasper/operating-system/blob/master/kernel/objects.asm 927 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 17:35:44.12 ID:ypA5W//n.net] >>916 よくわかんねーけどやめたら 928 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 17:37:59.32 ID:WruTeJWf.net] >1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。 やっぱりそうなるんだ。 ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。 929 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 17:56:42.05 ID:p+LvbHBp.net] > ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。 OS内に何らかの言語のインタプリタを実装して、 所謂ユーザーモードで動くプログラムは全てその言語で走る、というのを考えてる。 全てがシェルスクリプト、みたいな感じ。 で、そのインタプリタは数と文字列とハッシュを扱えれば良いと思っていて ハッシュをAVL、文字列をrope構造なんかの木構造で実装するとすれば 16バイトってサイズは各ノードに情報を格納するのに丁度いいサイズではあるのよ。 ropeってのはこれな。 https://en.wikipedia.org/wiki/Rope_(data_structure) その考えで行くと、あんまり無駄は出ないんじゃないかなとは思う。 勿論実行速度は多少犠牲になるけどね。 930 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 18:36:41.93 ID:VTHyhTWb.net] >>916 FATの考え方だね。 メモリ管理でも応用できる気はするけど。 931 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 19:24:52.99 ID:WruTeJWf.net] OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。 確かにLISPのConsCellの持ち方に似てはいるが。 932 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 20:55:58.55 ID:I71ZCmWZ.net] 16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。 WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと 同じような気がするのだが。 933 名前： ◆tAo.kQ2STk mailto:sage [2016/05/04(水) 22:32:04.59 ID:p+LvbHBp.net] >>931 > OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。 正確には、OSが内部で使うアロケータの話。 malloc/freeとは仕様が違うっていうか前提からして噛み合わない。関数が返す領域のサイズが固定だから。 とここまで書いて、「常に1チャンクだけ確保して返す」とは明確には言ってなかったことに気付いた。ごめんよ。 incしてorするコードが根底にあるから忘れてたわ。 >>932 > 16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。 16バイト境界でしか返さないって条件だと、16バイトの確保の為に追加で8バイトとか必要になる。 malloc/freeの仕様上、どうしても何バイト確保してあるかって情報をヒープ側に保持する必要があるからね。 開放する時点で何バイト確保されているかが自明で、かつ固定長ならば1ビットで済む。 > WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと 操作の意味はそれと同じかも。中身は全然違うだろうけど。 934 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 23:32:14.08 ID:I71ZCmWZ.net] なんか似たような話を最近見た気がしたがこれだった。 codezine.jp/article/detail/9325 935 名前：デフォルトの名無しさん mailto:sage [2016/05/04(水) 23:54:19.41 ID:NIqCX6OH.net] ホント最近の記事だな。 936 名前：デフォルトの名無しさん [2016/05/05(木) 20:14:53.64 ID:Rts6L3H5.net] 浅野孝夫の『情報の構造』の赤黒木のプログラムがすごすぎる。 名人芸の域に達している。 937 名前：デフォルトの名無しさん mailto:sage [2016/05/06(金) 02:45:47.47 ID:iu7snuDE.net] >>916 ObjectIDに、32bitメモリアドレスを使っている言語では、 使わない下位4bitを、nil, undefined, true/false などに使っている 938 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 00:38:26.53 ID:fVgrqlwf.net] gof本の「オブジェクトのクラス」、「パラメータ化」という表現がよくわからん 939 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 09:44:21.83 ID:vQZ70y3E.net] >>938 よくわからん、じゃねえよ 教えてくださいってちゃんと言えよカス 940 名前：デフォルトの名無しさん mailto:sage [2016/05/10(火) 14:50:16.86 ID:bh4nZJj2.net] クラスのインスタンスを引数として渡すってことじゃねーの。 つまりポリモーフィズムよ。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef