パソコンなど

パソコンの話をします。

エラトステネスの篩の高速化

 少し前に某会社の採用試験問題(?)の解説みたいな感じでエラトステネスの篩が話題になっていたので書こうと思う。C++を使うよ。

エラトステネスの篩とは

  • ある数以下の素数を比較的高速に求めるアルゴリズム。数の集合から素数の倍数を取り除くことで最後に素数が残る。
  • 以下はlimit以下の素数を格納したstd::vector<int>を返す関数の実装。
std::vector<int> simple_eratosthenes(const long long limit) {
    std::vector<bool> data(limit+1, false);
    data[0] = true;
    data[1] = true;
    for (long long s = 2; s*s <= data.size();) {
        for (long long i = s*s; i < data.size(); i+=s) {
            data[i] = true;
        }
        s++;
        while (data[s] == true) {
            s++;
        }
    }
    std::vector<int> result;
    for (long long i = 0; i < data.size(); i++) {
        if (data[i] == false) {
            result.push_back(i);
        }
    }
    return result;
}

やったこと

  • 最初から偶数を取り除いておくのと同様に、2, 3, 5, 7...など任意の数までの倍数を取り除けるようにした。
  • 2の場合だと、 2x+1のみが残る。
  • 3を含めると、 6x+1, 6x+5のみが残る。
  • 5を含めると、 30x+1, 30x+7, 30x+11, 30x+13, 30x+17, 30x+19, 30x+23, 30x+29 のみが残る。
  • これらのそれぞれを別々の実行スレッドに投げて並列化する。
  • 2の倍数を取り除くと0.5倍、3の倍数まで取り除くと0.33倍、5の倍数まで取り除くと0.267倍というようにメモリの消費量も減る。
  • それぞれに素数は同じ感じで分布しているらしいので並列化のムラはほとんどない。

実装関係の話

  • 上記のsimple_eratosthenesを使って探索範囲の平方根までの素数を求める。
    • simple_eratosthenesはメインの探索を行いながら、動的に篩うための素数を探しているが、マルチスレッド化するためにはこの方法だと別のスレッドからデータを読まなければならない。これはだるい。シングルで事前に計算した方がいい。
  • 各スレッドで、各素数を篩うときに開始位置を算出する必要がある。(例えば、 30x+13=41yを満たすxを求める。(答えは 943=41\times 23=30 \times 31+13\therefore x=31 ))
    • これは二元一次不定方程式なので、拡張互除法などで比較的高速に解ける。
    • 剰余が1となる場合だけ求めておけばあとはそれを何倍かすれば他はもとまるので、スレッドを分割する前に1についてのみを計算しておき、あとはスレッドに任せる。
    • 例えば、 30x_1+1=41y_1を満たす最小の自然数  x_1 は、 451 = 30\times15+1 = 41\times11\therefore x_1=15となる。
    •  30x_2+13=41y_2を満たす自然数  x_2 は、 x_2\equiv x_1\times13\bmod41である。 x_2\equiv195\bmod41なので  x_2=31となる。
  • シングルで求める比較的計算量が大きい部分はこの二つだが計算量は O(\sqrt{n \log n})程度なので、メモリの確保やメインの処理に比べれば雀の涙。(メモリの確保の方が圧倒的に時間がかかる。)

時間計測

  • 私のノートパソコン(MacBook Pro (13-inch, 2018, Four Thunderbolt 3 Ports))で行う。CPUはIntel(R) Core(TM) i5-8259U CPU @ 2.30GHzで、メモリは8GB 2133 MHz LPDDR3
  • コンパイラgcc version 10.2.0 (Homebrew GCC 10.2.0_4)を使い、最適化オプションを盛る。
  • 前述の篩うための素数を探す計算と、開始位置を探す計算は無視する。(1012までやっても14msしかかからない。)
  • メモリの確保にかかる時間は無視する。(今回やりたい評価には無関係なので)
  • 結果の素数をカウントし、その個数を以て正しさを評価する。
  • 素数の個数については、みんなの知識 ちょっと便利帳に掲載されているものを使う。

結果

  • 何個の素数を使って分割するかをbase_sieve_sizeで表す。
  • thread数、圧縮率以外の単位はミリ秒
  • すべて一発取りなので結果はあくまで目安
base_sieve_size 3 4 5 6 7
thread数 8 48 480 5760 92160
圧縮率 3.75 4.375 4.8125 5.21354 5.53939
107 1 1 12 309 44406
108 10 6 13 307 52329
109 684 109 57 325 60774
1010 15246 7033 907 696 62785
1011 208788 177030 68373 8994 58088
  • 結果は全て正しかった。

考察など

  • 問題サイズを大きくした場合、大量のスレッドに分割した方が速くなっている。
    • 問題を細分化したことにより、一つ一つのスレッドがキャシュに乗るようになり、動作が高速になったものと思われる。
    • base_sieve_size = 7の時は基本的に遅いが、問題サイズによる変化が最も小さいので、1012以上の大きさならばより高速に動作する可能性がある。
  • 1011base_sieve_size = 6で計算するために、すでに2.23GBのメモリ領域を使っている。メモリが足りないので1012までを一気に求めることはできない。
    • 計算結果を順次捨てながらメモリ領域を次のスレッドに引き継ぐようにすればメモリ不足は解消できるが、それは別の機会にやると思う。

ソースコード

github.com

巨大なjsonをいい感じに閲覧する

 クソゲーデータマイニングは、gameparams.jsonのデータを見る感じとなっています。しかし、gameparams.jsonはファイル容量にして226MB、615万行、2.26億文字のかなり巨大なファイルです。一般的なテキストエディタ、(atomsublime textなど)では開くことすらままならない上に、開いたとしても最表層だけで13000要素弱あるので、自分の求めるデータに辿り着くのは容易ではありません。

  そこで、それなりに高速でそれなりに機能的なCUIビュワーを作りました。(適当なプログラミング言語が扱える人は、自分でスクリプトを書いた方が楽だとは思います。)読み込みに数秒時間がかかりますが、各命令は基本、瞬間的に動作します。  

Thanks & References

  • TTaro_

 gameparams.jsonは以下の記事の内容を使って取得しています。さまざまな都合により、私のGithubにgameparams.jsonは存在しないので以下の記事を参考に自分で取ってきてください。

kawaii-14.hatenablog.com

C++によるjsonファイルの読み込みにはnlohmann jsonを使っています。非常に高機能で高速で書きやすいです。

github.com

 

Download

Installation

  • このプロジェクトのレポジトリにはjson_splitとjson_viewerが入っています。json_splitは関係ないのでjson_viewerに入ってください。
  • makefileがあるのでmakeしてください。
  • ビルドには、C++11以上に対応したコンパイラとnlohmann jsonが必要です。各々の環境に合わせてインストールしてください。

使い方

開き方、閉じ方

  • ./jsonviewer.out fiilename.jsonのように開きます。
  • (gameparams.jsonの場合)数秒の待ち時間の後、>のマークが表示されます。この状態の時に命令を入力することでいろいろできます。
  • ctrl+c, ctrl+d, 空の命令(改行のみ)を入力すると終了できます。

命令一覧

  • list option

    • optionと部分一致した子要素を表示する。
    • 何も指定しない場合は全部表示する。
    • 標準出力
  • find condition | condition & condition...

    • 条件指定リスト
    • 条件が指定できる以外の動作はlistと同じ
      条件
      • 条件はディレクトリ/ディレクトリ/要素名 = 値のように記述する。
      • 現在のディレクトリの子要素に、ディレクトリ/ディレクトリ/子要素があるかどうか検証され、ある場合は値と一致すればlistのように表示される。
      • 対応しているのは数値(整数、実数)、真偽値(true, false)、文字列(""で囲まれた範囲、エスケープシーケンスには未対応)、null
      • 配列はディレクトリや要素側で、要素[0]のように指定できる。
      • 数値は大小関係(以上以下、より大きいと未満)が比較できる。
      • 要素とリテラルの比較は実装しているが、要素同士の比較は実装していない。
      条件の接続
      • | 論理和
      • & 論理積
      • ^ 排他的論理和
      • 条件は常に左優先で評価される。
      • a|b&c^dと書くと((a|b)&c)^dと評価される。
      • 括弧で囲んで順序を規制したりするような機能は実装していない。すまねぇ
  • select option

    • optionは番号
    • 直近のlist、findで表示した番号の子要素に移動する。
    • move, backを実行するたびに番号は消える。
    • エラーなどは標準エラー出力
  • move option

  • back

    • 親の階層に移動する。
    • 普段は何も表示しない。
    • エラーなどは標準エラー出力
  • dump option

    • optionと完全一致した要素以下を展開して表示する。
    • 4文字のソフトタブにのみ対応している。
    • 何も指定しないと、直近のlist, findで表示した要素を全て展開して表示する。
    • 標準出力(エラー以外)
  • output filename command

    • filenameというファイルを作成し、commandの内容(標準エラー出力以外)をそのファイルに書き出す。
    • listとdumpにしか効果はないが、commandにそれ以外のコマンドを指定しても動く。

実行例

1.全ての要素のリストを得る

  • listコマンドで得られます。

2.Ohioのデータに移動する

  • list Ohioで"Ohio"という文字列に部分一致する最表層の要素を一覧します。
  • リストの0番がその要素なので、select 0で選べます。

3.Ohioの全長を調べる

  • 全長は、A_Hull/sizeの配列の0番目の要素に格納されています。
  • 先程の状態から、move A_Hulldump sizeで表示されます。
  • 全長は280.77mらしいです。

4.rootに戻る

  • backコマンドをを2回実行すると戻れます。
  • moveコマンドをオプションなしで実行するとrootに戻れます。

5.全ての空母のリストを得る

  • 空母はtypeinfoのspeciesが"AirCarrier"になっています。
  • そのため、find typeinfo/species = "AirCarrier"で表示できます。

6.Σ値が1.7である艦艇のリストを得る

  • sigma値はA_Artillery/sigmaCountか、A1_Artillery/sigmaCountに書いてあります。
  • find A_Artillery/sigmaCount = 1.7 | A1_Artillery/sigmaCount = 1.7で表示できます。

7.全長が250mより長い巡洋艦の全要素を、longCruiser.jsonに保存する

  • 全長はA_Hull/sizeの0番目の要素に格納されており、巡洋艦はtypeinfo/speciesが"Cruiser"になっています。
  • よって、これを満たす要素のリストは、find A_Hull/size[0] > 250 & typeinfo/species = "Cruiser"で得ることができます。
  • その状態でdump命令を実行すると、表示されている全要素を出力するので、その中身をoutputコマンドでlongCruier.jsonに書き込みます。
  • コマンドは、output longCruiser.json dumpとなります。

終わりに

  • 命令は全て標準入力から読んでいるので、適当なテキストファイルにクエリを書いておいて、./jsonviewer hoge.json < query.txtのような感じで自動化できます。
  • 命令のパーサー(特に文字列周り)がゲボカスなのはわかってます。気が向いた時に直すかもしれませんが、クソゲーのマイニングに使う分には問題ないので直さないかもしれません。
  • バグ等あれば、Twitterかissueで優しく(再現できる条件を)教えてください。

update note 2021/4/19

  • 配列は値ではなく無名要素で構成されたオブジェクトとして扱うようにした。