- 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
- 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]
- クラスのインスタンスを引数として渡すってことじゃねーの。
つまりポリモーフィズムよ。
|
 |
