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