考えたことがあたってるとちょっとうれしくなるよね

    PAYDAY2 Blacklist Assist

    最近更新中のPAYDAY2のBlacklist MODの補助ツール
    ※特に理由が無い場合は最新バージョンを使用してください。


    ━━━━━━━━━━━━━━━━━━━━━━━━━━━

    ちょうど一年前くらいにとある理由でプログラムを書くことになった。

    ・読み込むデータは用意されている
    ・解析手法も用意されている
    ・結果の見せ方も大体既存の参考資料がある

    ・使用言語は自由
    ・とりあえず動けばいいらしい

    というゆるい開発だったので、これまでの趣味の延長で作り始めた。

    やはりGUIはあったほうが便利だろうということ、グラフや表で結果を示したかったこともあり、言語はC#を選んだ。
    (というより割とまともに扱えるものがC#以外にな・・・)

    読み込むデータは大体以下のようになっていた

    data.csv
    #ヘッダー開始(ない場合もあり、ない場合はヘッダー終わりもなし)
    #ヘッダー終わり
    日時,データ1-1,データ2-1,...(複数列)
    日時,データ1-2,データ2-2,...
    日時,データ1-3,データ2-3,...
    以下数千から数百万行

    ・解析手法でのちにデータを消すことが分かっている
    ・とりあえず動けばいいらしい

    ということから、今までの経験から得た技術のListを用いてデータを格納していることにした。

    Step0
    List1-1(データ1-1を格納)
    List1-2(データ1-2)
    List1-3(データ1-3)
    List1-4(データ1-4)
    List1-5(データ1-5)

    と順番に格納していくわけである。(データ2-は表記省略)

    解析する間に

    Step1
    List1-1(データ1-1)
    List1-2(データ1-2)
    List1-3(データ1-3)

    List1-4(データ1-5)

    Step1
    List1-1(データ1-1)

    List1-2(データ1-3)

    List1-3(データ1-5)

    と歯抜けになっていく。

    Forで回していたと思うので、ここはList.RemoveAt(Int32)でデータを抜いていった。

    しかし、遅い、遅い、待てども待てども終わらない。何が悪い?

    既存技術の組み合わせということがあって、同様の処理をするプログラムがフリーで公開されている。
    それらを用いると時間がかかるものでも1分程度、自作のものは1時間以上かかる。

    明らかにおかしい!
    いろいろな場所にブレークポイントを設置した結果、上記の箇所が原因であると特定された。
    (ここまでに一通り作ろうと思っていた機能をすべて盛り込み済みで、自分の開発した中では最大規模のプログラムになっており、特定作業も大変であった)

    どうやら、要素を削除するたびに、要素を前に詰めているようだった。
    言葉にすると伝わりづらいだろうか、昔作った画像が出てきたので参考に

    270407_prog.png

    数百万*数列あるデータに対して、列ごとにデータを一つ消すたびに後ろからデータを詰めていたらしく、計算量は莫大な量になっていたということである。

    今までは扱うデータ量が多くとも数千程度だったので、詰め詰めしても大して気にならなかったようだが、今回は数百万*十数と今までとは全く違う規模のデータ量なので問題が浮き彫りになった。

    消すとダメ・・・ダメ・・・なら飛ばせばいいじゃない!とひらめいた。
    お風呂に入っていた時だったような気がする。ぽけーっとしてるとひらめくことあるよね。

    270407_prog2.png

    要素を作成する際に、前後関係と要素データを合わせて持つようにする。

    Step0
    List1-1(データ1-1を格納、前なし、後1-2)
    List1-2(データ1-2、前1-1、後1-3)
    List1-3(データ1-3、前1-2、後1-4)
    List1-4(データ1-4、前1-3、後1-5)
    List1-5(データ1-5、前1-4、後なし)

    といった具合である。
    すると

    Step1
    List1-1(データ1-1を格納、前なし、後1-2)
    List1-2(データ1-1、前1-1、後1-3)
    List1-3(データ1-2、前1-1、後1-5)
    List1-4(データ1-4、前なし、後なし)
    List1-5(データ1-5、前1-3、後なし)

    といった具合になり、詰め詰めしなくともすむ。
    これは!すごいのでは!

    と、独自でクラスを作り始めたのだが、途中で「もしかして、自分が思いつくのなら既にあるのでは?」と考え、検索してみると

    「連結リスト(片方向リスト、双方向リスト)」

    というものが、これにあたるようで、C#にももちろん標準で実装されていると分かった。

    こちらを利用したところ、ほかのフリーソフト並みの爆速で処理が終わるようになった。
    今度のボトルネックはストレージからの読み込み速度だが、ここはいまだに難儀している。

    何はともあれ、

    「何が悪い?」

    から

    「消すとダメ・・・ダメ・・・なら飛ばせばいいじゃない!とひらめいた。」

    「もしかして、自分が思いつくのなら既にあるのでは?」


    やっとタイトルである、「考えたことがあたってるとちょっとうれしくなるよね」

    先人たちも同じところで躓いて、同じことを考えていたと分かるとうれしい!

    もちろん、そんなところで時間を(完全ではないにせよ)無駄にしないためにも基礎知識をきちんとつけておくべきではある。

    でも、うれしいよね。

    と、なぜ今更こういうことを書いたかというと、先ほども同じ経験をしたからである。

    ・ユーザ登録型
    ・ユーザごとに個人ページを持ち、ブログのようなことができる

    といったものをRailsの勉強で作ろうとしてるのだが、何分データベースもまともに触ったことがないので、データベースをどう作ればいいのかとここ数日悩んでいた。

    初期の想像

    Table ユーザ情報
    ID Name Password など
    1 Taro ababa
    2 Hana gegeg

    Table Taroさんのブログ
    記事ID Title Text など
    1 te fefef
    2 fdf fefe

    Table Hanaさんのブログ
    記事ID Title Text など
    1 te fefef
    2 fdf fefe

    これではユーザが増えるごとにテーブルが増える・・・テーブルが増えるとパフォーマンスが悪いと、ではどうすれば・・・。

    と先ほど思いついたのが

    Table ユーザ情報
    ID Name Password など
    1 Taro ababa
    2 Hana gegeg

    Table ブログ情報
    記事ID 投稿者ID Title Text など
    1 1 fefe cdcd
    2 2 df cece

    ブログ記事情報を一つのテーブルにまとめ、中に投稿者IDを作ればいいのだ!なるほど。

    これが正解らしい。

    と、いうことで、ふと前の経験を思い出したわけである。
    スポンサーサイト