(メモ) 本日の目標
2008年07月25日00:44
17:00 起床。 表参道に行って3ヶ月ぶりに髪の毛をカット。 21:00頃 帰宅した。
仕事を開始する。
本日の目標(クエスト) :
1.バイナリファイル上で実装された Linked List を merge sort アルゴリズムを利用した並べ替えによって処理する。 処理中の内部リストが一定以上短くなったら、メモリ上でのクイックソートに切り替えて、効率化を図ること。
2.バイナリファイル上で B-TREE を実装する。 B-TREEに対する追加処理は理解できたが、削除処理が理解できていない。 これを調査し、まずはサンプルプログラムの作成を行うこと。
3.ファイルシステムの理解 ... inode とは何か。
http://en.wikipedia.org/wiki/Inode
http://en.wikipedia.org/wiki/List_of_file_systems
http://en.wikipedia.org/wiki/XFS
4.ファイル格納システムを作成する。
現時点で僕が思いつく限界は、File Allocation Table 式だ。 Windowsの FAT32は 基本的に一方向リンクトリストだが、僕は今、これを双方向リンクトリストで実装すれば stateless な defragmentation 処理が出来るはずじゃないかと考えている。 これは ひょっとしたら amiga の SFSと同じ方式なのではないかと考えているが、未確認だ。
http://en.wikipedia.org/wiki/Smart_File_System
今僕が持っている考えがもっともよい方法とは考えがたいので、もう少し調査する。
5.ISAM とは何か。
ISAMというのは、業務でアプリを作っていると非常によく聞く言葉の一つだ。 これはどうやらデータベースのデータ格納方式のひとつらしい。 非常に重要なアルゴリズムであるらしい。 調査すること。
◇
こうやって書いてみると、到底今日一日=朝までには終わらなさそうな気がしてきた。
フリープログラマーの道は険しい。
仕事を開始する。
本日の目標(クエスト) :
1.バイナリファイル上で実装された Linked List を merge sort アルゴリズムを利用した並べ替えによって処理する。 処理中の内部リストが一定以上短くなったら、メモリ上でのクイックソートに切り替えて、効率化を図ること。
2.バイナリファイル上で B-TREE を実装する。 B-TREEに対する追加処理は理解できたが、削除処理が理解できていない。 これを調査し、まずはサンプルプログラムの作成を行うこと。
3.ファイルシステムの理解 ... inode とは何か。
http://en.wikipedia.org/wiki/Inode
http://en.wikipedia.org/wiki/List_of_file_systems
http://en.wikipedia.org/wiki/XFS
4.ファイル格納システムを作成する。
現時点で僕が思いつく限界は、File Allocation Table 式だ。 Windowsの FAT32は 基本的に一方向リンクトリストだが、僕は今、これを双方向リンクトリストで実装すれば stateless な defragmentation 処理が出来るはずじゃないかと考えている。 これは ひょっとしたら amiga の SFSと同じ方式なのではないかと考えているが、未確認だ。
http://en.wikipedia.org/wiki/Smart_File_System
今僕が持っている考えがもっともよい方法とは考えがたいので、もう少し調査する。
5.ISAM とは何か。
ISAMというのは、業務でアプリを作っていると非常によく聞く言葉の一つだ。 これはどうやらデータベースのデータ格納方式のひとつらしい。 非常に重要なアルゴリズムであるらしい。 調査すること。
◇
こうやって書いてみると、到底今日一日=朝までには終わらなさそうな気がしてきた。
フリープログラマーの道は険しい。
コメント一覧
おかあつ 2008年07月25日 00:57
http://www.oreillynet.com/windows/blog/2003/01/data_is.html
http://johnaugust.com/archives/2004/data-is-singular
関係ないけど、data をもう単数形(というか不加算名詞?)とみなしてもいいじゃないか、という話が出てる。
http://johnaugust.com/archives/2004/data-is-singular
関係ないけど、data をもう単数形(というか不加算名詞?)とみなしてもいいじゃないか、という話が出てる。
ねこ☆ミ。 2008年07月25日 01:01
おかあつ 2008年07月25日 01:06
これ授業の教材みたいだけど、マニアックなまでに、いいね。
http://www.rku.ac.jp/~ikawa/twcuy2005/
http://www.rku.ac.jp/~ikawa/twcuy2005/y2005-db-1.html
東京女子大学
http://ja.wikipedia.org/wiki/%E6%9D%B1%E4%BA%AC%E5%A5%B3%E5%AD%90%E5%A4%A7%E5%AD%A6
だけど、結構お嬢様学校なんだなぁ...
http://www.rku.ac.jp/~ikawa/twcuy2005/
http://www.rku.ac.jp/~ikawa/twcuy2005/y2005-db-1.html
東京女子大学
http://ja.wikipedia.org/wiki/%E6%9D%B1%E4%BA%AC%E5%A5%B3%E5%AD%90%E5%A4%A7%E5%AD%A6
だけど、結構お嬢様学校なんだなぁ...
おかあつ 2008年07月25日 01:08
シリコンバレーがあるロサンゼルスの新聞 : LATimes
http://www.latimes.com/
すごい面白そうだ。
でも、なんかこうやっていつも横道にそれて更に時間がかかるんだよな ... 。
これは後回しにしないと。
http://www.latimes.com/
すごい面白そうだ。
でも、なんかこうやっていつも横道にそれて更に時間がかかるんだよな ... 。
これは後回しにしないと。
ねこ☆ミ。 2008年07月25日 01:09
RDBのINDEXはB TREEを改良したやつ(B*TREE?)を
利用することが多いけど、何回も追加、更新、削除をしていると、
物理ディスク上で断片化が起きるので、たまに再構成が
必要なんだよなぁ。。。。
利用することが多いけど、何回も追加、更新、削除をしていると、
物理ディスク上で断片化が起きるので、たまに再構成が
必要なんだよなぁ。。。。
おかあつ 2008年07月25日 01:12
http://johnaugust.com/archives/2004/data-is-singular
この件で、data が複数形か単数形かについては、喧々諤々の討論があったみたいだ。 でも、思うんだけど、英語って、深いところまでつきつめると、案外、あいまいな言葉なんだよな、と思う。 色々な言語の寄せ集めで、色々な文法的な要素が退化してなくなってしまっているんだよね... 。
この件で、data が複数形か単数形かについては、喧々諤々の討論があったみたいだ。 でも、思うんだけど、英語って、深いところまでつきつめると、案外、あいまいな言葉なんだよな、と思う。 色々な言語の寄せ集めで、色々な文法的な要素が退化してなくなってしまっているんだよね... 。
ねこ☆ミ。 2008年07月25日 01:12
東京女子大学でこれを教えてるのか、、、一般教養っぽいなぁw
おかあつ 2008年07月25日 01:15
間違い見っけた
>B 木はBalanced Tree(バランス木)
B-TREE の語源が、Balancedだとは 、B-TREEの考案者も含めて、誰も言及していないらしい。
... ま、あまり関係ないところだけど。
>B 木はBalanced Tree(バランス木)
B-TREE の語源が、Balancedだとは 、B-TREEの考案者も含めて、誰も言及していないらしい。
... ま、あまり関係ないところだけど。
おかあつ 2008年07月25日 01:16
>物理ディスク上で断片化が起きるので、たまに再構成が必要なんだよなぁ。。。。
あぁ、確かにそういうことって、ある。 頭の片隅においておこう... 。
あぁ、確かにそういうことって、ある。 頭の片隅においておこう... 。
おかあつ 2008年07月25日 01:22
http://www.rku.ac.jp/~ikawa/twcuy2005/twcu-db-n09.pdf
僕、こういう課題が出ると、きちんと最後まで理解できるようにならないと、気持ちが悪いクチで、結局時間切れになって課題を出せなくて単位がもらえないタイプなんだよな...。 損な性格。
だけど、何でみんな、こういう課題が出ると、きちんと期日内に終わらせて提出できるのが、僕は結構不思議。 だって、まともにやったらムチャムチャ時間かかるよ?
夜間大でとったロシア語の授業も、そんな感じで点数低かったなぁ。 だけど、あの授業出たやつで、本当にロシア人と話したり、ロシアに行ったりしたヤツが何人居るかって、問いたい。 子一時間問い詰めたい。
僕は最後まで理解したいんだ!
僕、こういう課題が出ると、きちんと最後まで理解できるようにならないと、気持ちが悪いクチで、結局時間切れになって課題を出せなくて単位がもらえないタイプなんだよな...。 損な性格。
だけど、何でみんな、こういう課題が出ると、きちんと期日内に終わらせて提出できるのが、僕は結構不思議。 だって、まともにやったらムチャムチャ時間かかるよ?
夜間大でとったロシア語の授業も、そんな感じで点数低かったなぁ。 だけど、あの授業出たやつで、本当にロシア人と話したり、ロシアに行ったりしたヤツが何人居るかって、問いたい。 子一時間問い詰めたい。
僕は最後まで理解したいんだ!
おかあつ 2008年07月25日 01:32
Smart File System は 物凄くドキュメントが少ないみたいだ...。
ねこ☆ミ。 2008年07月25日 01:32
http://www1.bbiq.jp/memo/hash.html
最初に別の検索方法から説明してるけど、
Hash(ISAM)はこれでわかるかも(?_?
Hash関数をどうつくるか考える必要がありますが、、、
最初に別の検索方法から説明してるけど、
Hash(ISAM)はこれでわかるかも(?_?
Hash関数をどうつくるか考える必要がありますが、、、
おかあつ 2008年07月25日 01:43
> http://www1.bbiq.jp/memo/hash.html
これは僕にはちょっとツッコミがたんなさ過ぎるかも...。
Hash関数っていうのは、もともと「鳩ノ巣問題」っていう数学的な問題というか、考えてみると当たり前な問題というかがあって、絶対に完璧なHash関数って作れない。
また Hash関数って、すんごい定番の関数がたくさんある。 与えられた バイトごとに 2乗して引き算するとか、そういう感じのヤツで、そこそこの性能は出る。 もっと厳密な衝突耐性が必要な場合は、SHAとかMD5を使う。
そのことを理解するには、
暗号技術入門-秘密の国のアリス (単行本(ソフトカバー))
http://www.amazon.co.jp/dp/4797322977
これを読むのが一番いいと思う。 この本は、英語の文献・日本語の文献全部ひっくるめても、間違いなく 最高の入門書だと思う。 たぐい稀な良書。
これは僕にはちょっとツッコミがたんなさ過ぎるかも...。
Hash関数っていうのは、もともと「鳩ノ巣問題」っていう数学的な問題というか、考えてみると当たり前な問題というかがあって、絶対に完璧なHash関数って作れない。
また Hash関数って、すんごい定番の関数がたくさんある。 与えられた バイトごとに 2乗して引き算するとか、そういう感じのヤツで、そこそこの性能は出る。 もっと厳密な衝突耐性が必要な場合は、SHAとかMD5を使う。
そのことを理解するには、
暗号技術入門-秘密の国のアリス (単行本(ソフトカバー))
http://www.amazon.co.jp/dp/4797322977
これを読むのが一番いいと思う。 この本は、英語の文献・日本語の文献全部ひっくるめても、間違いなく 最高の入門書だと思う。 たぐい稀な良書。
ねこ☆ミ。 2008年07月25日 01:44
>だけど、何でみんな、こういう課題が出ると、きちんと期日内に終わらせて提出できるのが、僕は結構不思議。 だって、まともにやったらムチャムチャ時間かかるよ?
2割の人。 徹夜をして毎回頑張る。
6割の人。 上の人の回答を写す
2割の人。 あきらめる。
って感じかもw
2割の人。 徹夜をして毎回頑張る。
6割の人。 上の人の回答を写す
2割の人。 あきらめる。
って感じかもw
ねこ☆ミ。 2008年07月25日 01:46
結城浩さんは、わかりやすく、技術を説明してくれますね。
素晴らしい
素晴らしい
ねこ☆ミ。 2008年07月25日 01:47
暗号技術入門-秘密の国のアリス (単行本(ソフトカバー))
は、会社にあるけど、手元にないなぁ。。。
は、会社にあるけど、手元にないなぁ。。。
おかあつ 2008年07月25日 01:54
>会社にあるけど、手元にないなぁ。。。
この際、家に置く用に一冊、会社に置くように一冊、電車で読むように一冊、無くした時用に一冊全部で4冊買ってしまってもいいかもしれない。
(実は僕、2冊持ってる。 ちなみに暗号大全も2冊持ってる。更に、暗号大全は原書も持ってたりする。)
暗号大全
http://www.amazon.co.jp/dp/4797319119
この際、家に置く用に一冊、会社に置くように一冊、電車で読むように一冊、無くした時用に一冊全部で4冊買ってしまってもいいかもしれない。
(実は僕、2冊持ってる。 ちなみに暗号大全も2冊持ってる。更に、暗号大全は原書も持ってたりする。)
暗号大全
http://www.amazon.co.jp/dp/4797319119
おかあつ 2008年07月25日 01:56
よく読んだら、ISAMってただ単に一般的なインデックスのことなんだね。
テープを使っていたような昔はISAMって呼んでたんだね...。
http://ja.wikipedia.org/wiki/Indexed_Sequential_Access_Method
テープを使っていたような昔はISAMって呼んでたんだね...。
http://ja.wikipedia.org/wiki/Indexed_Sequential_Access_Method
おかあつ 2008年07月25日 01:57
日本のWIKIのこういうホスト系の記述って、異様にマニアックなまでに細かくて、英語より判り易いことって多いと感じる。
恐るべし日本のホスト屋。
恐るべし日本のホスト屋。
ねこ☆ミ。 2008年07月25日 02:05
ハッシュって、
http://ja.wikipedia.org/wiki/Indexed_Sequential_Access_Method
>テーブルの内容へのポインタを格納したハッシュテーブルを索引と
>して用いることで、全データを検索することなく目的のデータを
>取り出すことを可能とした。
が、ポイントかな?
ハッシュは、キー項目の値が決まれば、レコードにすばやくアクセスできる。
でも、順序をもっていないので、ソートには時間がかかる。
RDBのB treeだと、小さいものから順番に検索する(手繰(たぐ)る)ことができるけど、ハッシュだと、時間がかかる。。。
http://ja.wikipedia.org/wiki/Indexed_Sequential_Access_Method
>テーブルの内容へのポインタを格納したハッシュテーブルを索引と
>して用いることで、全データを検索することなく目的のデータを
>取り出すことを可能とした。
が、ポイントかな?
ハッシュは、キー項目の値が決まれば、レコードにすばやくアクセスできる。
でも、順序をもっていないので、ソートには時間がかかる。
RDBのB treeだと、小さいものから順番に検索する(手繰(たぐ)る)ことができるけど、ハッシュだと、時間がかかる。。。
ねこ☆ミ。 2008年07月25日 02:09
ホストの記述って結構少ないかもしれない。。。
ググってもホストのプログラムは作れないと思う。
多分、情報処理の試験に出てくるようなものとしてとか、
また、RDBの仕組みとして、ひかかってきてるような気がします(推測)
ググってもホストのプログラムは作れないと思う。
多分、情報処理の試験に出てくるようなものとしてとか、
また、RDBの仕組みとして、ひかかってきてるような気がします(推測)
おかあつ 2008年07月25日 02:10
多分、ざっくりした理解ではそれで正しいと思う。
インデックスっていうのは、MSX で言えば、ジャンプテーブルみたいなものだよね。 0000からFFFFまで全部スキャンしなくても、ジャンプテーブルの何番っていう感じで指定することで、目的のルーチンのアドレスを知ることができるって言う意味で。
(ってこういう説明で「あぁ!」っていう人は今はあまり居ないと思うけど(^-^;) )
インデックスっていうのは、MSX で言えば、ジャンプテーブルみたいなものだよね。 0000からFFFFまで全部スキャンしなくても、ジャンプテーブルの何番っていう感じで指定することで、目的のルーチンのアドレスを知ることができるって言う意味で。
(ってこういう説明で「あぁ!」っていう人は今はあまり居ないと思うけど(^-^;) )
ねこ☆ミ。 2008年07月25日 02:11
あぁ!(とか書いてみるw)
ですね。
ですね。
おかあつ 2008年07月25日 02:12
>ホストの記述って結構少ないかもしれない。。。
僕は「多い」って感じるのは、僕がホストの仕事を結構やっていたからなのかなぁ...。
JCLの仕事を暫らくやらされてたんだよね...嫌だったけど、今思えばいい経験だったのかも...。
僕は「多い」って感じるのは、僕がホストの仕事を結構やっていたからなのかなぁ...。
JCLの仕事を暫らくやらされてたんだよね...嫌だったけど、今思えばいい経験だったのかも...。
ねこ☆ミ。 2008年07月25日 02:16
おかあつ 2008年07月25日 02:20
Hashっていうのは、一般的に Hash値を求める処理のことだけを指すんだよね。
例えば、
田中→大田区
佐藤→江東区
鈴木→杉並区
っていうデータを保存したいとしても、キーが「田中」とか「鈴木」とかじゃ、扱いが悪い。
だから、これらのデータを「ほぼ一意」な数値に置き換えて処理する必要がある。
じゃないと、B-TREEにせよ、ブルートフォース検索にせよ、なんにせよ、扱いが悪い。
この「ほぼ一意」な数値に置き換える処理のことをハッシュ値を求めるって呼ぶ。
このとき、java だと、 hashValue() っていう標準のメソッドがあるので、これをオーバーライドすることで好きなハッシュ値を算出して出力することができるようになってる。 で、マップやディクショナリ処理を行うときは、この hashValue() を元に、内部的なデータ構造を構築して処理するようになってる。
転じて、 キー(鍵)→バリュー(値) っていうデータの結びつきを保存することを ハッシュする、みたいな言い方をするようになったみたい。 特に Perl とか JavaScript とかのユーザーにおいて、その傾向が顕著だと思う。
例えば、
田中→大田区
佐藤→江東区
鈴木→杉並区
っていうデータを保存したいとしても、キーが「田中」とか「鈴木」とかじゃ、扱いが悪い。
だから、これらのデータを「ほぼ一意」な数値に置き換えて処理する必要がある。
じゃないと、B-TREEにせよ、ブルートフォース検索にせよ、なんにせよ、扱いが悪い。
この「ほぼ一意」な数値に置き換える処理のことをハッシュ値を求めるって呼ぶ。
このとき、java だと、 hashValue() っていう標準のメソッドがあるので、これをオーバーライドすることで好きなハッシュ値を算出して出力することができるようになってる。 で、マップやディクショナリ処理を行うときは、この hashValue() を元に、内部的なデータ構造を構築して処理するようになってる。
転じて、 キー(鍵)→バリュー(値) っていうデータの結びつきを保存することを ハッシュする、みたいな言い方をするようになったみたい。 特に Perl とか JavaScript とかのユーザーにおいて、その傾向が顕著だと思う。
ねこ☆ミ。 2008年07月25日 02:21
JCLは苦手です。はい。
>1.バイナリファイル上で実装された Linked List を merge sort
>アルゴリズムを利用した並べ替えによって処理する。
> 処理中の内部リストが一定以上短くなったら、メモリ上での
>クイックソートに切り替えて、効率化を図ること。
これって、どの程度メモリを利用できるかによって、一定以上短いかが
決まるような気がするのですが、 利用できるメモリ量から、
判定するのでしょうか?
それとも、アプリの設定値として何か固定値等を利用するのかな(?_?
>1.バイナリファイル上で実装された Linked List を merge sort
>アルゴリズムを利用した並べ替えによって処理する。
> 処理中の内部リストが一定以上短くなったら、メモリ上での
>クイックソートに切り替えて、効率化を図ること。
これって、どの程度メモリを利用できるかによって、一定以上短いかが
決まるような気がするのですが、 利用できるメモリ量から、
判定するのでしょうか?
それとも、アプリの設定値として何か固定値等を利用するのかな(?_?
おかあつ 2008年07月25日 02:23
あと、ダスドとか検索すると、そのテの人のマニアックな談義がたくさん聞ける。
なんか、そういう、化石の様なキーワードがたくさんあるんだよね...。
シスアウトとか。 電文とか。
なんか、そういう、化石の様なキーワードがたくさんあるんだよね...。
シスアウトとか。 電文とか。
おかあつ 2008年07月25日 02:25
>これって、どの程度メモリを利用できるかによって、一定以上短いかが
>決まるような気がするのですが、 利用できるメモリ量から、
>判定するのでしょうか?
>それとも、アプリの設定値として何か固定値等を利用するのかな(?_?
それは、結構難しい問題かも...。 スループットだけを考えたら、できるだけ大きいに越したことはないだろうけど...。
>決まるような気がするのですが、 利用できるメモリ量から、
>判定するのでしょうか?
>それとも、アプリの設定値として何か固定値等を利用するのかな(?_?
それは、結構難しい問題かも...。 スループットだけを考えたら、できるだけ大きいに越したことはないだろうけど...。
ねこ☆ミ。 2008年07月25日 02:25
上のHash記述ですが、なるほど。
おかあつ 2008年07月25日 02:30
鳩ノ巣問題(ピジョンホール)っていうのがあって、これって、どんなに高性能なハッシュ関数を使っても必ず衝突は起こるっていう数学の証明のことなんだよね。
なんか難しく感じるけど、これって「鳩が5羽居て、鳩の巣が4個あったら、必ず、その中の最低1個の鳩の巣には2羽の鳩がいるだろう」っていう話で、考えてみると、実に当たり前なことなんだよね。
文字列は無限種類あるけど、それを int なりの値に圧縮してしまうわけだから、どんなに高性能なハッシュ関数を使っても、無限の鳩に40億チョイの鳩の巣しかないわけで、必ずぶつかるんだよね。
なんか難しく感じるけど、これって「鳩が5羽居て、鳩の巣が4個あったら、必ず、その中の最低1個の鳩の巣には2羽の鳩がいるだろう」っていう話で、考えてみると、実に当たり前なことなんだよね。
文字列は無限種類あるけど、それを int なりの値に圧縮してしまうわけだから、どんなに高性能なハッシュ関数を使っても、無限の鳩に40億チョイの鳩の巣しかないわけで、必ずぶつかるんだよね。
ねこ☆ミ。 2008年07月25日 02:36
証明はしらないのですが、圧縮がかかるので、ぶつかってしまうのは、
感覚的にわかります。
それでは、お先におやすみなさい。
感覚的にわかります。
それでは、お先におやすみなさい。
おかあつ 2008年07月25日 02:43
おやすみなさい!
おかあつ 2008年07月25日 02:47
inode っていうのは、ファイルの属性を記憶している領域で、一意のIDで管理されているらしい。
ハードリンクという機能があるUNIXではあるひとつのファイルの存在に対して複数のパスが存在しえる。 そういう状況のなかで、このinode番号は、要は、あるファイルの存在を一意に表す役割を果たすらしい。
疑問:
ところで、Windows にも ジャンクションという機能が追加されたので、1つのファイルに2つ以上のパスが存在することになった。 すると、Windowsにも inode番号の様なものがあるんだろうか。
ハードリンクという機能があるUNIXではあるひとつのファイルの存在に対して複数のパスが存在しえる。 そういう状況のなかで、このinode番号は、要は、あるファイルの存在を一意に表す役割を果たすらしい。
疑問:
ところで、Windows にも ジャンクションという機能が追加されたので、1つのファイルに2つ以上のパスが存在することになった。 すると、Windowsにも inode番号の様なものがあるんだろうか。
おかあつ 2008年07月25日 03:07
気がつけば、3 4 5 は 目処がついてしまった...。 あとは1と2か ...。
ねこ☆ミ。 2008年07月25日 11:12
>気がつけば、3 4 5 は 目処がついてしまった...。 あとは1と2か ...。
おお、速いですねぇ^^
>っていうデータを保存したいとしても、キーが「田中」とか「鈴木」とかじゃ、扱いが悪い。
>だから、これらのデータを「ほぼ一意」な数値に置き換えて処理する必要がある。
>じゃないと、B-TREEにせよ、ブルートフォース検索にせよ、なんにせよ、扱いが悪い。
>この「ほぼ一意」な数値に置き換える処理のことをハッシュ値を求めるって呼ぶ。
ブルートフォース検索はわからないのだけど、B-TREEは順序が問題になるのでハッシュ値では、だめで、値そのものを格納してると推測してます。(ごめん、調べてない。)
おお、速いですねぇ^^
>っていうデータを保存したいとしても、キーが「田中」とか「鈴木」とかじゃ、扱いが悪い。
>だから、これらのデータを「ほぼ一意」な数値に置き換えて処理する必要がある。
>じゃないと、B-TREEにせよ、ブルートフォース検索にせよ、なんにせよ、扱いが悪い。
>この「ほぼ一意」な数値に置き換える処理のことをハッシュ値を求めるって呼ぶ。
ブルートフォース検索はわからないのだけど、B-TREEは順序が問題になるのでハッシュ値では、だめで、値そのものを格納してると推測してます。(ごめん、調べてない。)