将棋の局面をただひたすら書きだしたファイル(仮にテキストファイルだとする)があるとして、機械学習をオンライン学習系のアルゴリズムを用いる場合、最後のほうに学習させたデータに引っ張られる傾向があるため、この局面データ(テキストファイルの各行)が事前にランダムシャッフルされていて欲しいというのはあります。
ただ100万が最低値なのは、シャッフルできちんと局面が分散する事を保証するためにそうしてる(´･_･`)10万でも大丈夫かも知れないけれど(´･_･`)
— 平岡 拓也(´･_･`) (@HiraokaTakuya) July 6, 2016
大きなファイルに対する効率的なシャッフルのアルゴリズム自体は、簡単で、私が思うに、例えばファイルを100個ぐらい作って、それぞれの局面をその100個のなかのどれか一つをランダムに選んでappendしていきます。すべての局面が書き出せたら、そのあとファイルをメモリに丸読みしてシャッフルして書き戻すというのをその100個のファイルに対して行なって、最後に100個のファイルを結合して終わり。10分ぐらいあればプログラムは書けます。
なので、私としては平岡さんがなぜ棋譜生成側(ユーザー側)のPCでシャッフルしようとしているのかが今ひとつ理解出来ませんが、ただ、AWSを利用するのでストレージ容量の都合上、サーバー側でシャッフルしたくないというのはあるのかも知れませんね。まあ、だとしたら、もっと小容量のストレージ上でシャッフル出来るアルゴリズムが求められているのかも知れません。
完全にシャッフルされてなくていいなら、局面ファイルを後ろから1GB分ほどメモリに読み込んで、それをシャッフルしてファイルに書き出すと同時に、元のファイルの後ろ1GBをtruncate(切り詰める)していくという方法があるかと思います。これなら元のファイルを格納するためのストレージ＋1GB程度のストレージ容量があれば済みそうです。しかしプログラムがバグっていて、truncateしすぎてせっかくのデーターをロストしてしまうことはよくあるので、バックアップもないようなデーターに対してこういう処理をあまり書きたくはないですね。
もっと攻めるなら、局面ファイルを先頭から1GBほど読み込んで、シャッフルして、それをその先頭から上書きしてしまう、みたいな方法が考えられるかと思います。シャッフルしてもバイト長は変わらないので、上書きしても問題ないはず…です。これなら、元のファイルを格納するためのストレージ容量だけあればシャッフル出来ます。しかし、これも元のファイルでは改行コードが1バイトだったのに書き出すときに改行コードが2バイトになってたりして、上書きしたときに局面ファイルを壊してしまうだとか、ファイル上書きしている最中にPCの電源が落ちて大丈夫なのか？などと考えだすとキリがありませんね。
そんなわけで、私のお勧めは冒頭に書いたアルゴリズムなのですけど、もっといい方法があるのでしたらコメント欄などで教えていただけると幸いです。
ランタイムにシャッフルしたほうがランダム性は増えるような気がします。
ちゃんとstd::random_device使っておかないといけませんが。
100万行のベクター(std::vector<std::string>)をstd::shuffleしたら何秒位かかるんでしょうかねぇ。
最近のPCならあんまり問題にならないような気がします。
それに、粒度的に問題ないレベルって発見されてますでしょうか。
適度に端折っても問題ないレベルというのなら屋根さんの方法はかなり魅力的に思います。
ランタイムとはどこの時点でしょうか？
> 100万行のベクター(std::vector)をstd::shuffleしたら何秒位かかるんでしょうかねぇ。
メモリ上であれば1秒かからないのでは。メモリ上に読み込む時間と、(100万行が1億行ぐらいになったときに)棋譜生成を協力してくれているユーザーのPCでメモリ上に読み込めるのかという問題はあります。
> それに、粒度的に問題ないレベルって発見されてますでしょうか。
100万局面単位ぐらいでシャッフルされていれば、まあ問題ないのではないかとは思っていますが、実験データもないので(そもそもこの方法による強化学習が成功してすらいないので)よくわかりません…。
今回のランタイムとは棋譜生成をユーザー側にやらせるときデス。
random_deviceはそのCPU依存になりやすいのでたくさんのユーザー側の環境に左右されやすくなると思います。
そこらへんがランダムに寄与したりしませんかねぇ・・・。
暇だったのでこんなコードを書いてみました。
シャッフルのシミュレーションです。
http://ideone.com/TAYJvH
結果。
start data generation…Done. time:12424ms.
start data Shuffle…Done. time:69ms.
Thank you!
適当にデータ生成してるのでそれだけが滅茶苦茶重いです・・・。
CPUはi7-6700です。64bitリリースの値です。
シャッフル自体はそんなに重たくない印象です。
100倍位までは耐えられるような感じに見えます。
後はメモリの量次第ですね。
SSDでもスワップしちゃったら結構厳しいのかな？？
あ、書くとこ間違えた・・・。Orz
> そこらへんがランダムに寄与したりしませんかねぇ・・・。
全くしないでしょうね…。1PCでやったとしてもひとたび乱数seedが決まったあとはMersenne twisterでも極めて長い乱数周期を持ってますし、乱数としての質もすこぶる良いですし(623次元で均等分布する)ですし…。
ははワロス。寄与しませんか～。
メルセンヌツイスタ賢い！
下手の横好き的なかんじですね・・・。Orz
ところで、これって屋根さんの求める要件にマッチしてますでしょうか？
違うなら違う部分を指摘してくださると、ほかの方へのヒントになるんじゃないかと思います。
> ところで、これって屋根さんの求める要件にマッチしてますでしょうか？
棋譜全体(80億局面で数百GB)がメモリに読み込めないというのが今回の問題の出発点ですから、メモリ上に丸読みされた棋譜に対してstd::shuffle()するのは論外なのでは。
そうですね。確かに。
やっぱ分割して読むか、よいコンピュータを買ってあらかじめやっておくか位かもですね。
80億読むのにHPC系が必要になるのは結構ハードル高いですね。一台ハイメモリのコンピュータ作ってみるとかどうでしょうか。事務用にでも。
HPCなら384GB位積めたと思うので。ただお値段が自分には手が届きません。屋根さんならできます！（他人事・・・汗）
ともあれ、サル知恵ではちょっと太刀打ちできませんねぇ。Orz
まず、規模がよくわからないですから。もやもやしてて・・・。
メモリ上に丸読みさえしなければ何とでもなると思いますけども。
取り合えず、シャッフルするプールがデカいほどランダム性に寄与するんじゃないかくらいは思いました。
それでもまあ、100万局面単位ぐらいでのshuffleされていれば十分でしょうから、…。(以下、本文冒頭に戻る)
うぅ。自分サル知恵すぎます。Orz
それだと初期ファイルの末尾部分が正しくバラけない感じがします。
しかし目的からして厳密なランダム性は不要でしょうし、
重くて正しいシャッフルを追求するよりは、前後ひっくり返して軽いシャッフルを2回掛ける方が早くて簡単だと思います。
一つ上のコメントへの返信ですかね。
次から、コメント欄のなかの【返信】ボタンを押していただけると幸いでございます。
わかりにくくてすみません。
本文のやねうら方式へのコメントです。
ああ、後段はyakitoriさんの文脈へのコメント混ざってますね。失礼しました。
> 本文のやねうら方式へのコメントです。
本文には3つの方法が書いてありますけども、その一つ目の方法についてでしょうか？
「初期ファイルの末尾部分が正しくバラけない」理由がいまひとつわからないのですが。
最初の方式です。
あ、分配時に100個のファイルサイズは揃えず、分配終わった段階ではファイルサイズがデコボコでもいいってことですか。
先入観が入ってました。
(｀･ω･´)ゞ わかりました。
数GBのファイルを間違えて書き込みモードでfopenしちゃった(ﾃﾍﾍﾟﾛ 事件を思い出したorz
局面に対してstruct { int64 offset; int64 size }みたいインデックス的情報を作って、それを局面数の配列にする。インデックスをシャッフルしてそれを元に新ファイルを作る。みないなのとか
> struct { int64 offset; int64 size }
16バイト×80億(8GB) = 128GB
普通のPCだとメモリに載らないような…。
結局、屋根さんが元締めになって分割ファイルをネットストリームやるのが一番のような。
シャッフルは屋根さんがコントロールするって感じで。
なんか自分おかしなこと言ってるような。
100万局面でファイルに分割してそれを8000ファイル作る感じになるんですかね。
それでも1ファイル数GBですからねぇ。なかなか扱いが難しい。
混血したくなったら2ファイル読んでシャッフルして1ファイル書き出してもう一ファイル読んで・・・。とローテートしてけばいいかな？？
1ファイルのシャッフル自体はMTとstd::shuffleに任せても問題ないと思いますので、そのように。
結局屋根さんが最初に言ったところに帰結してしまいました。
未来行き過ぎです。Orz
ん？800GB！？以上！？？
それをDLっていうのも狂気だなぁ・・・。Orz
> 結局屋根さんが最初に言ったところに帰結してしまいました。
ご理解いただけたようで何より。
なんか荒らす感じなってしまってごめんなさい。
い、、いまさら？
元々荒らそうと思ってやってたのではないので。
ちょっとやりすぎました。Orz
反省してます。
新しいファイルシステムを作るのはどうでしょうか。これなら連続読み出しするプログラムを変更せずに済みます。
ファイルシステムは連続読み出しの時にディスク上の次のデータではなく「ランダムに選んでくる」のであれば要件を満たせそうです。
ただしすでに読み出し済みのものはスキップしないといけません。でも何を読み出し済みなのか保持するとメモリがいっぱい必要です。だからスキップするために何かを覚えておかなければならないシャッフル方法は選べません。これは妥協です。
例えば偶数番目のデータを昇順で読み出した後に奇数番目のデータを昇順で読み出すファイルシステムはスキップ用のフラグは必要ありません。周回数とカウンタがあればいいです。
例えば２５６件ずつのブロックで全データを分割して、読み出すたびにブロックを移動していけば遠くのデータに移動していくことができます。前の例は２件ずつのブロックだと言えます。
スキップ用に保持しなければならないデータ量と選ばれるデータの乱雑さのトレードオフになるはずです。
データと読み出しプログラムの間にアルゴリズムをはさむのは、メモリとソフトウェアの間のMMUや、ディスクキャッシュなんかと同じだと思います。できるだけ違うものを使おうとするのはキャッシュと逆ですけど。
剰余類とかハッシュとかをカッコよく使うと、フラグがほとんど不要でランダムに選んでくるっぽい仕組みが作れるんじゃないかな。
シークのコストが高いから無理と言われると厳しいです。
どんなファイルシステムを採用しようと、最小単位はブロック構造になるでしょうから、そのブロックサイズを下回るサイズで細切れにreadしようとすれば無駄が出るのは必然でしょう。なので、ファイルシステムをどのように変えても解決にはならないかと。
ただ、局面データが固定長レコードであるなら、n個飛ばし、みたいな剰余系をもってシャッフルしたことには出来るでしょうけども、それって周期性の短い、質の悪い乱数でシャッフルしていることに変わりないので、seekのコストが高くつくわりに粗雑なシャッフルしか出来ていないので採用するメリットがないのです。
(物理的な)セクタのサイズが4096バイト(あるいは512バイト)であるとして、そのセクタに入るだけの局面とパッドでセクタサイズになるようにして満たしておいて、シャッフルされた乱数その0でセクタの位置を特定して、さらにその中の局面をシャッフルされた乱数その1の順で拾っていくというのはどうなんでしょ？
シャッフルされた乱数じゃ同じ局面を拾うから違った。
シャッフルされた乱数じゃなくて、シャッフルされた連番で。
その方法だと1局面を読むごとに必ず1セクタを読み込まないといけないのでは。1セクタが4096バイト(1局面32バイト+2バイト=34バイトだとしたら120局面入ります)だとして、普通に1GBほど丸読みしてメモリ上でシャッフルするのに比べて、120倍のreadが必要になります。さすがに効率が悪すぎるのでは。
1局面が必要でreadをすると120局面が出てくるから、もう1局面が必要になったら残っている119局面のうちのどれかを使ってくださいよ。
と思ったけど、それだと粗雑なシャッフルにしか見えないか…orz
はい…(´ω｀)