ヒッキープログラミングスレ 2 - 1371668281

1：（-＿-）さん：2013/06/20(木) 03:58:01 ID:???: プログラミングの話題のスレ

質問・相談
初心者からプロまで
プログラミングに関することなら何でもＯＫ

ヒッキーのプログラミングするスレ
http://ikura.2ch.net/test/read.cgi/hikky/1362050172/

プログラミングできる奴、一緒にアプリ作ろうぜ！！
http://ikura.2ch.net/test/read.cgi/hikky/1360671157/

ヒキ板情報技術部
http://ikura.2ch.net/test/read.cgi/hikky/1348106094/

前スレ
ヒッキープログラミングスレ
http://jbbs.livedoor.jp/bbs/read.cgi/internet/17286/1361821799/
723：（-＿-）さん：2014/10/09(木) 18:11:11 ID:???: a
724：（-＿-）さん：2014/12/09(火) 00:08:38 ID:???: 今日わかったこと
C#においてクラスと構造体は似て非なるもの
C++の感覚では使えない
725：（-＿-）さん：2014/12/10(水) 05:28:06 ID:???: http://qiita.com/horimislime/items/84fa431460c8d39f37e6
http://qiita.com/awakia/items/5fad0c454ddc7b478ff1
http://qiita.com/FiNGAHOLiC/items/34312c5cbd4989fa192c
http://qiita.com/ririn_yume
メモ
726：（-＿-）さん：2014/12/18(木) 01:18:56 ID:???: 第28回　Perlの構文解析器の作り方と応用例（1）：Perl Hackers Hub｜gihyo.jp … 技術評論社
http://gihyo.jp/dev/serial/01/perl-hackers-hub/002801

おもしろそうなの発見
727：（-＿-）さん：2014/12/18(木) 01:22:18 ID:???: プログラマー向けのQ&Aサイト「Stack Overflow」、日本語版が一般公開 -INTERNET Watch
http://internet.watch.impress.co.jp/docs/news/20141217_680681.html

日本語キター！
728：（-＿-）さん：2015/01/10(土) 04:16:40 ID:???: まだ落ちてるのんか
729：（-＿-）さん：2015/01/12(月) 21:01:00 ID:???: 今夜はトップコーダーに挑戦だ
730：（-＿-）さん：2015/01/12(月) 23:25:27 ID:???: 13日午前1時かららしいSRM？とかいうの
731：（-＿-）さん：2015/01/12(月) 23:29:16 ID:???: 22時からエントリー開始してたみたいだな
今SRM645に参加登録した
732：（-＿-）さん：2015/01/13(火) 02:37:49 ID:???: ダーメだったわ
全然分からんかった
難しすぎだわ
733：（-＿-）さん：2015/01/13(火) 20:17:10 ID:???: ttp://fsm.vip2ch.com/-/hirame/hira062987.png
次のSRMを受けたらどんどんRateが下がって行きそうな予感…
引き際が肝心ということでコレを俺の最高記録とする！
734：（-＿-）さん：2015/01/13(火) 20:22:29 ID:???: 世界中のプログラマでTopCoderをやっている人は何割程度だろうか
その何割で黄色や赤色のとこの人が数千人いるわけだから
TopCoderやってない人も含めればすごいプログラマって世界中に何万といるんだろうなあ…

そして灰色や緑色のあたりがどこにでもいるようなレベルの範囲なんだろうけど
TopCoderに参加してる人だけで数万人になるから
TopCoderに参加してない人も含めたらこのレベル域のプログラマは世界で数百万人以上いるってことだよな…
735：（-＿-）さん：2015/03/13(金) 15:56:45 ID:???: 書き込めるけど見られない
マジでdat取得だけ仕様変更か
736：（-＿-）さん：2015/03/13(金) 19:13:07 ID:???: 専ブラを自作するのはしんどいなあ
737：（-＿-）さん：2015/03/14(土) 23:52:25 ID:???: 仕組み自体は難しいもんじゃないけど
いかんせん組むのが非常に面倒臭いのが難点
738：（-＿-）さん：2015/03/17(火) 14:57:38 ID:???: https://www.jpcert.or.jp/java-rules/vna02-j.html

ふむふむ
739：（-＿-）さん：2015/03/17(火) 18:10:59 ID:???: 専ブラ作ろうと必死らこいてみたが
javaのスレッドの仕組みあたりで苦戦中

変に凝るから時間がかかってしまう
凝らない仕様にしてれば今頃は半分くらいは完成してたはず
凝ったせいで1ミリも進んでない
740：（-＿-）さん：2015/03/17(火) 18:12:54 ID:???: javaのスレッドの仕組みを理解するための実験的なコード書いては実行してを繰り返してばかりでダメぽ
機能はswingのhtml表示できるというJEditPaneを色々実験してて
実験のコードばかりで
専ブラの実装コードは1ミリも書かれてない・・・
741：（-＿-）さん：2015/03/19(木) 18:13:56 ID:???: やる気が途絶えてしまった
742：（-＿-）さん：2015/03/19(木) 20:20:21 ID:???: redditの仕様の大きさに比べたら2ch用ブラウザはすごく楽に思える
743：（-＿-）さん：2015/03/19(木) 22:02:14 ID:???: 15年くらい前のサイトだからね2chは
そらしょぼいわ
744：（-＿-）さん：2015/03/19(木) 23:35:27 ID:???: Javaのチュートリアルに日本語版があるとは知らなかった

Javaチュートリアル
https://docs.oracle.com/cd/E26537_01/tutorial/
745：（-＿-）さん：2015/03/19(木) 23:37:16 ID:???: うげ・・・日本語版は目次ページだけか・・・
746：（-＿-）さん：2015/03/24(火) 17:16:03 ID:???: 専ブラ開発停滞中
747：（-＿-）さん：2015/03/24(火) 18:39:05 ID:???: 一年以上前から言ってないかそれ
748：（-＿-）さん：2015/03/24(火) 19:56:13 ID:???: 言ってない
これは古い専ブラでスレが見れなくなってから考えだしたから
749：（-＿-）さん：2015/03/24(火) 19:57:03 ID:???: ただ何かしらの停滞と挫折はしょっちゅうやってはいる
750：（-＿-）さん：2015/03/24(火) 21:36:13 ID:???: 最近はしたらばとredditを見てて.netはもう無いものと思ってるわ
専門板もネチネチした荒らしがいるから見ない方が精神衛生上良いし
751：（-＿-）さん：2015/03/24(火) 22:14:12 ID:???: 人の多い板はともかく
それ以外の板は一気に過疎感じがするね
752：（-＿-）さん：2015/04/03(金) 21:27:47 ID:???: 各所の過疎が進みすぎて
専ブラ開発の意欲が失せてきた・・・
753：（-＿-）さん：2015/04/23(木) 04:23:50 ID:???: 構想いていた専ブラの仕様に穴があるの気づいた・・・
まぁ停滞してから１ヶ月経つけどほとんど何も出来てない段階だから
仕様変更は問題ないけど
どう仕様を変えるかのアイデアがまだない・・・
754：（-＿-）さん：2015/04/23(木) 18:30:49 ID:???: スクレイピングとかいうので実装しようと思ってたのに
ダメになる可能性があるらしい・・・

2ch.net専用ブラウザの開発者の皆さまへ ★20 [転載禁止]?2ch.net
http://anago.2ch.net/test/read.cgi/software/1427376861/
755：（-＿-）さん：2015/05/01(金) 20:15:56 ID:???: 980超えると24時間書き込みが無いだけでスレ落ちるとか厳しすぎてワロタ
756：（-＿-）さん：2015/05/02(土) 03:11:33 ID:???: 【スレタイ】ヒッキーのプログラミングするスレ 6
【本文】
前スレ
ヒッキーのプログラミングするスレ 5
http://hello.2ch.net/test/read.cgi/hikky/1404022118/

避難所(2ch鯖落ちや規制などの時)
ヒッキープログラミングスレ 2
http://jbbs.livedoor.jp/bbs/read.cgi/internet/17286/1371668281/

２ちゃんねるヒッキー板プログラミングスレwiki
http://www54.atwiki.jp/projecthikky/

プログラムの公開用アップローダー
http://ux.getuploader.com/hikkyp/
757：（-＿-）さん：2015/05/02(土) 03:43:55 ID:???: うげ、このアップローダのURLは今はRock54対象か
758：（-＿-）さん：2015/05/03(日) 23:00:00 ID:wIrj73.w: ヒッキーのプログラミングするスレ 6 [転載禁止](c)2ch.net
http://hello.2ch.net/test/read.cgi/hikky/1430661582/
759：（-＿-）さん：2015/05/03(日) 23:12:25 ID:???: >>758
乙
760：（-＿-）さん：2015/05/08(金) 00:26:11 ID:???: メモ
http://www.oracle.com/technetwork/jp/java/javase/documentation/api-jsp-316041-ja.html
761：（-＿-）さん：2015/05/24(日) 17:56:28 ID:???: 向こうのスレの専ブラのアイデア
面白いと思うけどプロキシの形で既存2chブラウザに渡せば終わりそうな
それだと専ブラ自体は対応できない細かな問題が出るかな
でもそのために一から作るのもなんか動機が弱くて結局頓挫しそう
762：（-＿-）さん：2015/05/24(日) 18:00:46 ID:???: ツリー型に関してはスラドやredditを見てて思ったけどあまりいい形に思えない
複数の書き込みに対してレス出来ないし見難いしアンカーの連鎖でよさそう
763：（-＿-）さん：2015/05/24(日) 22:20:38 ID:???: 禿同
764：（-＿-）さん：2015/06/06(土) 17:00:46 ID:???: ネット通信覚えるぞ！
メモ

TCP/IPアレルギー撲滅ドリル
http://www.atmarkit.co.jp/ait/articles/0302/01/news001.html
765：（-＿-）さん：2015/06/06(土) 18:36:58 ID:???: さっそくプロキシっぽいの作ってみた

https://paiza.io/projects/fIe-08l1BiBzIqFI9eNriw
766：（-＿-）さん：2015/06/06(土) 18:38:48 ID:???: ほんとうはちゃんとリクエストの内容みてHTTPとかプロトコルチェックしてプロトコルごとに対応しなきゃならんのだろうけど
ひとまず、HTTPリクエストが来ること前提でｗ
767：（-＿-）さん：2015/06/06(土) 19:04:17 ID:???: 単なるWEBサーバーやんけ
768：（-＿-）さん：2015/06/13(土) 06:11:28 ID:???: メモ

Processingで学ぶ実践的プログラミング専門課程
第18回　 UML（1）ユースケース図
http://gihyo.jp/dev/serial/01/practical-programming-with-processing/0018
769：（-＿-）さん：2015/06/18(木) 03:38:26 ID:???: メモ

Perl Hackers Hub
http://gihyo.jp/dev/serial/01/perl-hackers-hub
770：（-＿-）さん：2015/06/23(火) 04:43:54 ID:???: ●餌

初期：
　餌は十数個ランダムに配置される

投下：
　任意のタイミングで任意の位置に餌を発生させることができる

移動：
餌は全く移動しない

●生物

初期：
　生物は経験値ゼロの満腹状態の個体が十数体ランダムに配置される

向き：
生物には向きが存在する

視界：
　　生物は前方に対して左右それぞれ最大45度の計90度の視界を有する
　　真横や後方を認識することはできない
　　視認可能距離は無限大とする

可能行動：
　生物には右腕を左腕が存在しそれを動かすことによって行動する
　右腕前かき　　　前方左斜め(前方左45度)に1単位進む、体の向きが移動前の左斜め前方向を前方とする向きに変わる
　左腕前かき　　　前方右斜め(前方右45度)に1単位進む、体の向きが移動前の右斜め前方向を前方とする向きに変わる
　右前＋左前　　　1単位前進

感情：
　快不快

快：
　空腹時以外
　
不快：
　空腹時
　
状況：
　視界にある最寄の餌との距離

経験：
　状況に対して行った可能行動をキーとしてそれによっての最寄の餌との距離変化を値とする情報群
　行動するたびに値が更新されていく

快時：
　可能行動を一切行わない

不快時：
　経験皆無・・・可能行動のいずれかをランダムに行う
　経験多少・・・未経験の可能行動のいずれかをランダムに行う
　経験十分・・・最寄の餌との距離がもっとも減少する可能行動を行う、同程度のものが複数ある場合はいずれかをランダムに行う

摂食：
　空腹時に餌を接触することによって瞬時に餌を完食する
　同一の餌に2匹以上の空腹の生物が同時に接触した場合はいずれか１つの個体のみが摂食を行える
　その場合、摂食を行える個体は空腹時からの経過時間が最も短い個体に決定される、経過時間が同じ個体が2匹以上いる場合はそのうちからランダムに決定される

満腹：
　空腹時に餌１個を摂食することで満腹になる
　満腹になると感情が快になる
　
空腹：
　満腹時から一定時間が経過すると空腹状態になる
　空腹になると感情が不快になる

死亡：
　空腹時から一定時間が経過すると生物は死亡する
　死亡以降、死体は餌として扱われる
771：（-＿-）さん：2015/06/23(火) 04:44:59 ID:???: 訂正

状況：
　視界にある最寄の餌との方向と距離
772：（-＿-）さん：2015/06/23(火) 05:15:31 ID:???: 発展

寿命と交配を設ける

残り寿命が閾値を超えたら交配行動を求め行動する
最寄の個体に接近し強制交配を行う、交配した両個体はそこで死亡（ただし餌とはならず消滅する）
交配により子個体が2個体発生する。親の両個体から経験を半分ずつ受け継ぐ。経験はランダムに選出される。
受け継ぐ経験はランダムに選出されるため子個体はそれぞれ異なる経験を持つ個体となる
773：（-＿-）さん：2015/06/23(火) 05:41:06 ID:???: メモ

「HTTP/2」がついに登場！開発者が知っておきたい通信の仕組み・新機能・導入方法
http://codezine.jp/article/detail/8663
774：（-＿-）さん：2015/06/23(火) 05:47:20 ID:???: SPDYにしろHTTP/2にしろ
そんな糞重いサイトなんか消えてなくなれってしか思わんわ
無駄に動的コンテンツとか動的読み込みとか要らんちゅうの
軽量ページの遷移だけでなんとかしてほしいわ
775：（-＿-）さん：2015/08/27(木) 04:29:03 ID:???: Java

Pattern.quote(String)

https://paiza.io/projects/1wPSZNGBSwZ8c1w2QfQnLw
776：（-＿-）さん：2015/09/01(火) 04:43:28 ID:???: メモ

注目高まる人工知能--押さえておきたい用語21選
http://japan.zdnet.com/article/35068871/
777：（-＿-）さん：2015/09/22(火) 06:07:41 ID:???: https://paiza.jp/poh/joshibato/matsue-ruby

コードゴルフ難しい
778：（-＿-）さん：2015/10/12(月) 04:31:59 ID:???: 覚悟決めたgzipのdeflate圧縮アルゴリズム実装をするぞ
779：（-＿-）さん：2015/10/12(月) 05:22:16 ID:???: うう、gzipのdeflat圧縮の解除の処理を実装したの2年前だし
そのコードを眺めてたが、昔の俺は出来る奴だったんだな・・・
コード何を書いてるのかよくわからんし・・・deflateの知識を完全にド忘れしてて理解不能に近いわ・・・
780：（-＿-）さん：2015/10/12(月) 05:38:20 ID:???: やべえわ、deflate圧縮の再勉強が必要なレベルだわ・・・それはダルすぎ・・・覚悟消滅
781：（-＿-）さん：2015/10/12(月) 05:52:52 ID:???: DEFLATE
https://tools.ietf.org/html/rfc1951

ZLIB
https://tools.ietf.org/html/rfc1950

GZIP
https://tools.ietf.org/html/rfc1952
782：（-＿-）さん：2015/10/12(月) 05:55:42 ID:???: 翻訳版

DEFLATE
http://www.futomi.com/lecture/japanese/rfc1951.html

ZLIB
http://www.futomi.com/lecture/japanese/rfc1950.html

GZIP
http://www.futomi.com/lecture/japanese/rfc1952.html
783：（-＿-）さん：2015/10/12(月) 05:56:54 ID:???: 色々な翻訳載せてるこの人は神だわ

英語技術文書日本語訳
http://www.futomi.com/lecture/japanese/index.html
784：（-＿-）さん：2015/10/12(月) 06:11:29 ID:???: うん、前回もこの日本語訳で学習したような気がする
原文のほうはちょろっと眺めてみたが見た覚えが全くない
2年前の俺は英語文章を読む気概は無かったようだ
785：（-＿-）さん：2015/10/12(月) 06:21:53 ID:???: カスタムハフマンで圧縮はしんどそう
ハフマン符号表を独自に生成（あるいは事前用意）でやるんだろうけど
ある程度のサイズ（ブロックというやつか）読み込んだデータのヒストグラム取って大きな偏りがある場合は
カスタムハフマンで超圧縮できたりしたらすごいんだろうけど
事前用意ならある程度データの偏りがあることが分かってるデータ形式を取り扱うときとかかな
どのみち面倒や
786：（-＿-）さん：2015/10/12(月) 06:25:39 ID:???: ただ固定ハフマンだとほとんど圧縮できなさそう
同じ連続データが頻出するようなデータ形式じゃないと固定ハフマンより非圧縮ブロック使うほうがいいし
本気で圧縮を考えるならカスタムハフマン使わざるをえないのか・・・
787：（-＿-）さん：2015/10/12(月) 06:28:14 ID:???: ハフマン符号の生成法自体は書いてあるけど
カスタムハフマンだと符号表の圧縮もしなきゃならんし、何よりブロックフォーマットが面倒
788：（-＿-）さん：2015/10/12(月) 06:31:24 ID:???: 前回は伸張処理だったから固定ハフマンの内容について深く考えなかったけど
やたらめったら同じ連続データが頻出しない限り固定ハフマンを使う価値ねえわ
普通のテキスト文書を圧縮なら単純に頻出文字のビット数抑える目的のカスタムハフマン作るほうが断然いいな
789：（-＿-）さん：2015/10/12(月) 06:39:36 ID:???: 固定ハフマンは3バイト(24bit)以上一致すると半分以下のに減らせる感じではあるが
html文書の圧縮とかなら2文字以上タグやパラメータ名が頻出したとしても
タグやパラメータ名なんて文書全体の大した割合じゃないし、固定ハフマンだとちょろっとしか圧縮できないな
俺がいまこのスレで連投してるレスだって連続データ多くないだろうし
ただヒストグラムで頻出検査しても微妙そうではあるが
790：（-＿-）さん：2015/10/12(月) 06:52:14 ID:???: だいたい半分に圧縮か
http://ideone.com/4kiJcR
791：（-＿-）さん：2015/10/12(月) 06:59:50 ID:???: Javaでもだいたい半分か・・・
http://ideone.com/PXzrny

アッカーン
792：（-＿-）さん：2015/10/12(月) 07:02:17 ID:???: 半分というのは素晴らしい成績なのか微妙なのか判断つかんな・・・
793：（-＿-）さん：2015/10/12(月) 07:10:10 ID:???: PHPは他の圧縮形式もサポートしてるから
後で比較してみるかな
794：（-＿-）さん：2015/10/13(火) 07:32:04 ID:???: ふむ
https://paiza.io/projects/-D3AYAjkYK36g5yiYpEG_g
795：（-＿-）さん：2015/10/14(水) 06:24:15 ID:???: Deflateは固定ハフマンを使うのなら

最大で258バイトを13ビット（2バイト弱、距離1バイトの1バイトを258バイト分繰り返し）～26ビット(4バイト弱、距離32Kバイトから258バイト分のコピー)に圧縮できる

3バイト(24ビット)を参照で圧縮する場合は
最小12ビット(2バイト弱、距離1の1バイトを3バイト分繰り返し)～24ビット以上は圧縮の意味がないので23ビットまでで
23ビットは距離約8Kバイトまでの参照
796：（-＿-）さん：2015/10/14(水) 06:45:25 ID:???: ZLIBで使われるAdler32

下位バイト、s1 はバイトデータの総和に1を足したもの
上位バイト、s2 はバイトデータの先頭からの部分和に1を足した物の総和

RFCで紹介されてるコードはループ毎に素数65521で割って効率が悪いので（どんなCPUでも剰余算は効率が悪い）
ある程度足し合わせた状態を素数65521 で割って計算していくほうが効率がよい
ある程度足し合わせた状態がs1とs2のオーバーフローしないギリギリまで求めたい
既にあるadler32の値をupdateで更新するときに
s1とs2にが最も早くギリギリの値になるのはs1とs2の初期値が最大でバイトデータ全部が0xFF(255)のとき
s1とs2は最終的に素数65521 の余りとして算出されるため最大値は双方ともに65520
s1の最大値は簡単に 65520 + n * 255
s2は初項65520の交差255の等差数列の和の総和として表現できる

等差数列の和は
初項 a[0] 交差 d 、a[i+1] = a[i] + d
a[0]からa[n]までの和S[n] = (n+1)*a[0] + d*(n+1)*n/2

その総和なのでs2 = S[0] + S[1] + ... + S[n]
= (1+2+..+(n+1))*a[0] + d*(2*1 + 3*2 + 4*3 + ... + (n+1)*n)/2
=(n+1)*(n+2)*a[0]/2 + d*(2*1 + 3*2 + 4*3 + ... + (n+1)*n)/2

なんかs2はすさまじい桁になりそう
797：（-＿-）さん：2015/10/14(水) 06:51:13 ID:???: adler32の下位s1上位s2ともに2バイト
符号有int型(4バイト)で計算するとなると31ビットまで使える
32ビットが4Gだから31ビットはその半分の2G、20億？
6万ちょっとから20億までは随分と離れてる気がするけど
s2はすぐに到達してしまうようだ、(いくつかのAdler32の実装を見るとそんな感じ)
ライセンス回避のためかみんなちょろっとずつ実装の仕方や数値を変えているようではあった
Adler32の効率いいコードを実装しようとすると面倒そうだな
798：（-＿-）さん：2015/10/14(水) 22:43:49 ID:???: yukicoderなんかで無駄時間使ってしまった
799：（-＿-）さん：2015/10/14(水) 22:44:43 ID:???: yukicoderで★１の問題を解くのが適度に時間潰しに向いててついついハマってしまう
800：（-＿-）さん：2015/10/14(水) 22:45:17 ID:???: ★２以上だと難しくて解けないけど
★１くらいだと俺の脳みそだと適度に悩んで答えが出せるから楽しい
801：（-＿-）さん：2015/10/14(水) 22:46:29 ID:???: さっさとdeflateの圧縮アルゴリズムを実現するロジックを考えねば
802：（-＿-）さん：2015/10/14(水) 23:00:59 ID:???: まず
転送用バッファ（処理済みデータ)
保留バッファ(圧縮するかしないか、圧縮するなら固定ハフマンかカスタムハフマンかを考察中・解析中のデータ)
入力バッファ(まだ解析対象になってないデータ)

転送用バッファは処理済みデータの要求があったときにコピーするデータ
未処理データがまだ残っており転送用バッファが空になったとき保留バッファの解析・考察をして圧縮処理を施し転送用バッファにコピーする
保留バッファが一定サイズ未満になったとき入力バッファからデータをコピーしてくる

圧縮は最大258バイトの長さを縮められるから保留バッファはそれ以上のデータは保持しておいたほうがいい
非圧縮ブロックは64KiBまでの長さにできるから、保留バッファを64KiBにするって手もあるのかもしれんけど
非圧縮ブロックは長さ情報を頭に挿入しなきゃならんし
所謂アスキー文字の値127以下の文字ばかりなら固定ハフマンでも8bitで格納だから
バイト境界を意識しなきゃならん非圧縮ブロックを使うなら値128～255が多いデータのときでほどよく分布してる場合か
偏りがあるなら距離長さの対象になるかもしれんし
そうでなくても同じデータが頻出するならカスタムハフマンで頻出値を8bit未満に符号化できるかもしれんし
803：（-＿-）さん：2015/10/14(水) 23:11:29 ID:???: カスタムハフマンを使うときは符号表も圧縮して挿入しなきゃならんから
符号表分のバイト数を加えても超圧縮できるときじゃないとメリットないよなあ
たぶん数十バイトから百数十バイトくらい余分に使うのかな
頻出データが5biｔくらいになったとしても相当な頻度での量がないと圧縮効果は薄そう
804：（-＿-）さん：2015/10/14(水) 23:35:08 ID:???: 2chのスレとかだとあっという間に数百キロバイト超えるのな
１レスごとの書き込み量の多いスレだと100レス行く前に32Kに達するし
１レスごとの書き込み量の少ないスレだと200～300レスくらいで32Kに達する

32KiBで参照して圧縮するわけだけど
2chのスレみたいなテキストベースは32KiBも調べる必要なさそう
2KiBくらいでも十分かも

バイナリデータだと32KiBという短い距離だと早々同一のバイト列は出てこなさそう
ビットマップの単色が頻繁に続くってことならやはり32KiBも参照する必要はないし
TrueColorだと１マス4バイトくらいか？32KiBだと大雑把に8000マスくらいか？
横1024の画像データならたった8ラインにも満たない・・・
もっと遠いとこに似たような色の並びがあったとしても参照できないし
deflateが圧縮業界で雑魚な感じなのか
805：（-＿-）さん：2015/10/14(水) 23:41:29 ID:???: うん？テキストベースを2KiBだとちょっと少ないか
アスキー文字なら１バイト文字だけどunicodeとかマルチバイト文字は
1000文字で2000バイト超えたりするわけだから
2chの1レスは2000文字くらい書けたりするわけだ、大半は全角文字だから2バイト文字で4000バイトは超える
荒らしとかの　ああああああああああああああああああ　みたいな連続文字は簡単に圧縮対象だけど
例えば名無しデフォルトが多くメ欄はsageが多く、日付は同じ日のレスもそれなりあることを考えると
10KiBくらいは参照したほうがよさげか
806：（-＿-）さん：2015/10/14(水) 23:55:49 ID:???: RFCにある圧縮処理の実装の仕方の参考情報を元に
頭悪い俺がロジックを考える（ひとまず自力だけで考える）

まず32KiBの参照
RFCにあるのは3文字(バイト)分のキーで距離マップを作るといいとある

保留バッファ中のX番目のデータの評価を終えて次のバイトに行くときに
X-2、X-1、Xの３バイトをキーとして処理を終えたデータ分も含めた総バイト位置の配列を値としてマップしていく
この場合はX-2番目のデータの総バイト位置を値の配列の最後尾に加える
んで
次のX+1番目のデータの評価のときX+1、X+2、X+3をキーとしてマップから探し出して
一致するものがあれば距離の近い順（最後尾)のほうからデータ列の一致をチェックしていく
繰り返しデータが発生するのはその参照したデータを走査していく際にX+1番目の手前であるX番目に到達してしまったとき
そのときに参照距離の最初に戻って繰り返し一致していくか判定するわけだ
807：（-＿-）さん：2015/10/15(木) 00:02:10 ID:???: 距離マップにひたすらマッピングしてくと、とんでもないデータ量になりかねない(キーは最大2の24乗にもなるし)
つまり32KiB超えた分は適宜削除しなきゃならない
そこでキューを使う、キューにマップするキーと配列に追加する値のセットを挿入していき、
キューのサイズが32KiBを超えたら先頭のキューのものをマップから削除する

これは効率悪そう

問題は、評価対象は保留バッファであり、32KiBの参照は転送用バッファに入れられた処理済データの分も含むわけだ
しかも保留バッファを順に走査していくと32KiBの参照は保留バッファ内にも持つ必要が出てくる

つまり、処理済データ32KiB分を保持するマップとキュー、
そして保留バッファの情報を保持するマップとキューが必要となる

うん、効率悪そう
808：（-＿-）さん：2015/10/15(木) 00:07:04 ID:???: カスタムハフマンによるリテラル値の符号化による圧縮を考える場合は
評価対象である保留バッファの0～255の値のヒストグラムを作り、
頻出順に並び替えてハフマン符号表を生成し、ヒストグラムの個数と符号化後のビット数を掛けて和すると圧縮サイズになるって感じか
それとは別に符号表のサイズも考慮せにゃならんが
809：（-＿-）さん：2015/10/15(木) 00:13:59 ID:???: ブロック区切りは保留バッファごとじゃなく
直近の処理済データでブロックを終わらせなくていいのなら継続と言う感じかな
ブロックのサイズ制限があるのは非圧縮ブロックのみだが
非圧縮ブロックは先頭にブロックサイズを入れなきゃならんから
直近の処理済データが非圧縮ブロックならそこでブロックは終わってなければならない

保留バッファにあるデータを評価した結果
最後の処理済の継続ブロック（すなわち固定ハフマンかカスタムハフマン）と同じブロックでよいのなら
そのまま符号化データを転送用データにぶっこんでいけばいいし
違うブロックのほうがいいのならブロック終端の256の符号をぶっこんでから
新しいブロックを作る必要があると
810：（-＿-）さん：2015/10/15(木) 00:23:39 ID:???: ここで１つ問題がある
ブロックは最後のブロックにはそれを示すフラグを入れる必要があるわけだ
複数のブロックで構成することを事前に想定しているのならいいが
全体を１ブロックだけ（１つの処理方法だけ）で構成するとなると
ブロックの先頭にあるフラグビットに最終ブロックのフラグを立てなければならない

入力データの全てが保留バッファに完全に収まるというのなら、あるいは入力データの全サイズが一定サイズ以下なら
単一ブロックと決め付けて処理するのもアリかもしれんが

そうでない場合は問題だな
入力データの終端まで来て、あ、やっぱ単一ブロックでよかったわってなっても今更ブロックのフラグの変更は無理だし
苦肉策を要するならデータの無い終了フラグのためだけのブロックを作るというのも一つの手か
非圧縮ブロックならLEN=0にして3bit+4byteで35bitか
固定ハフマンブロックなら、3bit+7bitで10bitでこれが一番妥当だな
カスタムハフマンは・・・3bit+色々byteあってこれはダメなパティーン
固定ハフマンの10bitの終了ブロック作りゃいいだけだから、まぁいいのか
811：（-＿-）さん：2015/10/16(金) 18:23:36 ID:???: 脱線してVirtualBoxに入れてたUbuntu14ちゃんをアプデしたらぶっ壊れた件ｗ
aptitude update　でパッケージリスト更新して、かなり久しぶりだからかすごい量のアプデがあったけど
気にせず aptitude upgrade ぽーん！とやったらぶっ壊れたｗ
途中でinitramfsが失敗してるようで一時領域が不足してポポポーン！
cpやmkdirが失敗しまくリングなメッセージ多発してショッキングだったは
同じく久方ぶりにアプデしたdebian6ちゃんは平然とやってのけたのに！（ヤバそうなメッセージはチラホラあったような感じではあったけど！）
どちらも常に上書き保存設定にしてたから前の状態に復元できないという！（せっかく仮想環境使っている意味がないことをしている俺！！）
そもそもこんな低スペックPCでVirtualBoxを動かすってのが無理があるんだ！
812：（-＿-）さん：2015/10/16(金) 18:28:52 ID:???: うーん、どうしようか
大昔にDLったUbuntu14ちゃんのインストールディスクイメージちゃんでUbuntuちゃんを再インストールするか
でもそれだと結局大量のアプデ地獄が
だからといってヘボ回線だから更新されてるかもしれないインストールディスクイメージのDLはしんどいしな
え？失敗を調査して手動で修復？無理無理、なんか6万件近いアプデが入ったみたいだしそんなん無理や！
813：（-＿-）さん：2015/10/16(金) 18:31:32 ID:???: そもそも何でubuntuちゃんをVirtualBoxに入れたのか記憶にすらない・・・
あ、思い出したわ、Mono VisualBasicを試すためだったな
814：（-＿-）さん：2015/10/17(土) 03:08:28 ID:???: 今日も今日とて脱線してCygwinの更新とyukicoderやってたは
ダメぽ
815：（-＿-）さん：2015/10/17(土) 03:09:30 ID:???: 昨日のyukicoderのコンテストの★2の問題が解けなかったわ…
やはり★1の問題を解くのがいいわ
816：（-＿-）さん：2015/10/18(日) 06:23:04 ID:???: 今日もyukicoderに没頭してしまった
とうとう通常問題の★1は全部解き終わってしまった
★2の問題に取り組むか、gzip処理を作る続きをするか（続きも何もガワしか作ってないがな)
817：（-＿-）さん：2015/10/19(月) 04:38:45 ID:???: 方針
ひとまず固定ハフマンを使って圧縮して一時バッファに突っ込む
ある一定サイズの入力データを読み終えた時点で
そこまでのデータを非圧縮ブロックとして扱ったときの８割（？）程度以下に圧縮できていれば一時バッファを確定出力データとして送る
そうで無いときはその部分のヒストグラムを調べ使用されてない値が一定数（５割くらい？）以上あればカスタムハフマンの符号表を作り
カスタムハフマンで符号表含めて８割程度以下になるならカスタムハフマン採用
そうで無い場合は３つのケースで最もデータサイズが小さくなるものを採用
818：（-＿-）さん：2015/10/19(月) 04:46:17 ID:???: うーむ、一時的な圧縮データである一時バッファを作らず
変換パターン（アルファベット値と距離長さの値）を保存しておけば
カスタムハフマンの符号表での圧縮サイズ測りやすいか？
カスタムハフマンを使う場合は２通りの圧縮手法が考えられる
単純にビット数の小さい連続リテラル値としての圧縮と
固定ハフマンと距離長さをメインにする同じ変換パターンでの圧縮と
後者の場合はデータ値(0-255)のヒストグラムじゃなく変換アルファベット値(0-287)のヒストグラムにする必要があるな
前者の場合は0-255のヒストグラムが必要になるな
819：（-＿-）さん：2015/10/19(月) 04:55:54 ID:???: カスタムハフマンはもう１つパターンがあったか
確定データの最後がカスタムハフマンブロックならそのカスタムハフマンの符号表を使えるというパターン

前からのカスタムハフマンの符号表を使うか、今回解析したデータ列から生成できるカスタムハフマン符号表を使うか

前の符号表使う問題点としてはヒストグラムが異なるデータ群のものになるってことか
ハフマン符号表の生成法の復習をまだしてないからよく分からんが
前のデータ群になかったデータ値・アルファベット値が出てきたらちょっとややこしそう
出現する値の種類は変わらなくても分布が変われば圧縮効率が極端に落ちるだろうし
確定済みのデータ群のカスタムハフマン符号表を使うメリットが出てくるケースはすごく限定されそう
820：（-＿-）さん：2015/10/19(月) 04:58:34 ID:???: 前のカスタムハフマンを使うメリットは符号表データを新たに埋め込む必要がないってところくらいか
あくまで前のデータ群とヒストグラムの類似性が高いときだけの限定的用途にしかならんか
821：（-＿-）さん：2015/10/19(月) 04:59:33 ID:???: ひとまずハフマン符号表の生成ロジックの復習をしないと
カスタムハフマンを適用する基準すら設けられない
822：（-＿-）さん：2015/10/19(月) 05:07:52 ID:???: まぁでも一応圧縮ロジックの概要は掴めた気がする

対象データの一定サイズ分を距離長さ圧縮のアルファベット値に変換したパターンを生成
（パターン生成時についでに固定ハフマンでの圧縮サイズ(ビット数)も計算していく）
非圧縮時、および前回確定データがカスタムハフマンならそれ使用時のサイズも算出
この時点で非圧縮の８割以下が生成できるならそれでいいんじゃね？的な判定
ダメぽそうなら
この解析中データ限定のカスタムハフマン符号表を生成を考える
ヒストグラムの分布的に具合が悪そうならカスタムハフマン符号表の生成はなしに現時点での最小サイズになるものを採用
分布の偏りに見込みを感じたらカスタムハフマン符号表を生成して圧縮後サイズを算出
ここまでの中で一番最小のサイズに収まるものを採用