- プログラミングのお題スレ Part3
416 ：デフォルトの名無しさん[sage]：2014/03/28(金) 01:12:42.80 ID:SMJgLyGD - す う が く な ん て ・ ・ ・ Orz
導関数とかマッタク理屈がわからん・・・。＼(^o^)／ｵﾜﾀ
|
- プログラミングのお題スレ Part3
417 ：174[sage]：2014/03/28(金) 11:25:40.60 ID:SMJgLyGD - >>368 いず みー
ttp://ideone.com/stwHzp
ベンチマーク作ったよ。
これぞ究極の圧縮展開アルゴリズム！しかも可逆！！！ただし、o(N!)だ。
現在のC++では20バイト程度しか圧縮できない。
それでもかなりかかる。
軽いなーと思ったら、MakeData()の数字を上げてみましょう。
多倍長はいっても、何メガバイトまで圧縮できるのやら・・・。
＊順列圧縮＊
バイナリをとあるソート済みの配列の順列の途中経過であると仮定する。
ならば、バイナリを順列にかければ1週の間に最低一回はソート済みの数列になるのではないか。
という理論を思いつきまして、書いてみたんですよ。
採算分岐点は3kb程度、o(3000!)とかふざけてるが、それ以上になるとなんでも概ね3kb程度に収まる。
とにかく順列が馬鹿みたいに重いのでこれを高速化できればストレージ問題はほぼ解消する。
ランレングスこそ過去にして未来だったのだ。
と、いう感じです。
|
- プログラミングのお題スレ Part3
424 ：デフォルトの名無しさん[sage]：2014/03/28(金) 19:54:51.56 ID:SMJgLyGD - >>422
yes!20バイトしか圧縮できないのはじぶんの手落ちでございます。
多倍長演算できないと自分には扱えない。
そして、O（N!）で死ぬ。
>>417になんで名前欄はいってるんだ。
間違ってないけど、入れる気はなかった。
|
- プログラミングのお題スレ Part3
425 ：デフォルトの名無しさん[sage]：2014/03/28(金) 20:02:05.65 ID:SMJgLyGD - >>418
名前は聞いたこと有るんだけど、理論がどういうものかはサッパリ。
数学なんてぇ〜。
|
- プログラミングのお題スレ Part3
427 ：デフォルトの名無しさん[sage]：2014/03/28(金) 23:35:57.42 ID:SMJgLyGD - >>426
なんとなく理解した。
配列を右か左に一回ずつシフトしていった履歴一列をXに展開するようにY方向へ並べていって、
まじめにソートされた列をX方向へY方向に観測しながら見つける。
これすごい発想だけど、メモリがN*N必要じゃん。
順列するより早いけど、ランレングスで1ブロックに1KBかかるな。
オンメモリの場合メモリ4Gで64kしか圧縮できなくないか？でも1/64なら相当か。
むむむ・・・・。
|
- プログラミングのお題スレ Part3
428 ：デフォルトの名無しさん[sage]：2014/03/28(金) 23:37:30.66 ID:SMJgLyGD - あぁ、頑張れば1/128いけるな。
|