[c++(?)][google] mapのvalueを基準にした枝刈り

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
purin52002
記事: 235
登録日時: 2年前
連絡を取る:

[c++(?)][google] mapのvalueを基準にした枝刈り

#1

投稿記事 by purin52002 » 2年前

こんにちは
今回はc++のmap(最終的にはgoogleのライブラリであるsparse_dense_map)について質問があります

私は現在強化学習のプログラムを作成しています.
強化学習についての説明は割愛しますが,学習値を格納するためのコンテナとしてmapを使っております.(インデックスではなくキーでアクセスしたいため)

学習を重ねるごとにmapの値は更新,もしくは追加されていくのですが,
学習回数を増やすとメモリが足りなくなってしまいます.

そこで,一定回数学習を行ったら学習値(mapのvalue)が低いデータを削除しようと考えました.
しかし,mapをvalueでsortする方法がわかりません.こまりました^p^

そこで今回の質問です.
  • map(google::sparse_dense_map)のvalueが小さい任意のn個を消去する方法 <-最終的に知りたいこと
  • mapをvalueでソートする方法 <-これができれば任意のn個を削除できる
なお,書きやすさのためにmapとしていますが,実際に使っているのはgoogleのライブラリであるsparse_dense_mapです.

よろしくお願いします<(_ _)>
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

アバター
purin52002
記事: 235
登録日時: 2年前
連絡を取る:

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#2

投稿記事 by purin52002 » 2年前

おそらくですが、priority_queueを使えばいいかもしれません。

priority_queueは順序付きのスタックです。
priority_queueのプレディケートでmapのvalueを比較しましょう。

コード:

using namespace std;
int main()
{
    using MyMap=map<int,double>;
    using DataType=pair<int,double>;

    MyMap x;//値は適当に代入
    priority_queue<DataType> y(begin(x),end(x));//プレディケートはデフォルトでstd::less

    while(!y.empty())
    {
        cout<<y.top()<<endl;//降順で表示
        y.pop();
    }
}
これでどうでしょうか?

[hr]

という茶番はさておき、
priority_queueと組み合わせることによりsortができるということがわかりました。
お騒がせいたしました<(_ _)>
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

かずま

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#3

投稿記事 by かずま » 2年前

vector を使うんだったら、それをソートすればよいのでは?

コード:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>  // sort

using namespace std;

int main()
{
    using MyMap = map<int, double>;
    using DataType = pair<int, double>;
    struct comp {
        bool operator()(const DataType& a, const DataType& b) const {
            return a.second > b.second;  // value で降順
        }
    };
    MyMap x = { {1, 3.3}, {2, 1.1}, {3, 4.4}, {4, 2.2} };
    vector<DataType> y(begin(x), end(x));
    sort(begin(y), end(y), comp());
    for (auto& z : y)
        cout << z.first << " " << z.second << endl;
}

アバター
purin52002
記事: 235
登録日時: 2年前
連絡を取る:

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#4

投稿記事 by purin52002 » 2年前

かずまさん
http://d.hatena.ne.jp/ponkotuy/20111216/1324027752
こちらのページによるとvectorをソートするよりpriority_queueに未ソートのvectorを渡してソートしてもらうほうが早いらしいです。(ほんとかどうかはしらない^^;)
今回はこちらのサイトを信用して先のようなコードにしました。

解決済みにするのを忘れていたので追加で質問をしたいと思います。

現在の私のプログラムでは学習を一回するごとに(mapの値を一回更新するごとに)先のコードを用いて枝刈しています。
しかし、それでは頭が悪そうです。(大量のコピーが学習回数分行われるため)

そこで枝刈の頻度を少なくしようと思いました。
最初は学習回数を指標に枝刈を行おうと思いましたが、極端な話、mapのサイズが1Byteだった場合はたとえ1000回学習したとしても1kB(1kじゃないだろ、とかいう突込みはなしで^^;)のメモリ消費で済みますし、1kBのmapを扱う場合は1000回学習すると1MBもメモリを消費してしまいます。

したがって、学習回数ではなくmapのメモリサイズを指標に枝刈を行おうと思いました。
しかし、ここでも問題が出てきてしまいました。
メモリをどれぐらい消費したら枝刈を行うか、プログラム上でmapのメモリサイズをどのように取得するか、という問題です。

今回の質問はこれらの解決策についてです。()の中はやりたいことです。
  • PCの動作が遅くならない程度のメモリの確保の方法(mapのサイズが確保したメモリ以上になりそうだったら枝刈)
  • マシンが扱える最大メモリを取得する方法(最大メモリのうち何割をmapに割くか、ユーザに入力させる)
  • mapのメモリサイズを取得する方法(mapのメモリサイズを指標とするため)
さらにおおもとの質問として
  • 枝刈は何を指標にして行うべきか?
というものも追加しておきます。

あと、しつこいようですが使用しているmapはgoogleのdense_hash_mapになります。

よろしくお願いします<(_ _)>
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

hoge

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#5

投稿記事 by hoge » 2年前

purin52002さん
http://d.hatena.ne.jp/ponkotuy/20111216/1324027752
このページで行なっているのはpriority_queueを構築するまでの測度
popの処理を含めるとpriority_queueはソート済みvectorより遅い。
小さい値をn個取り出したいならvectorをpartial_sort()した方がいい。


アバター
purin52002
記事: 235
登録日時: 2年前
連絡を取る:

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#7

投稿記事 by purin52002 » 2年前

なるほど、言われてみれば毎回popするのってすごい遅そうですもんね^^;
vectorとsortに置き換えようと思います。

もともと任意のn個を削除する、という質問でしたが現在は全体のx%以下の要素を削除しようと考えています。

コード:

using MyMap=map<int,double>;
using DataType=pair<int,double>;

MyMap x;//適当に初期化

auto sum_func=[](const double &left,const DataType &right){return left+right.second;};
auto sum=accumulate(begin(x),end(x),0.,sum_func);//valueの総和

vector<DataType> y(begin(x),end(x));
sort(begin(y),end(y),greater<DataType>());//昇順でソート

const double thresholod=0.1;//閾値
auto find_func=[&threshold,&sum](const DataType &x){return x/sum > threshold;};
auto itr=find_if(begin(y),end(y),find_func);//割合がthreshold超過になる要素の検索

x=MyMap(itr,end(y));//再構築
というコードを考えているためnth_elementではなくsortを用いようと思います。

引き続き枝刈の指標について回答をお待ちしております<(_ _)>
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

かずま

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#8

投稿記事 by かずま » 2年前

purin52002 さんが書きました:

コード:

sort(begin(y),end(y),greater<DataType>());//昇順でソート
DataType は pair ですから、greater は、まず first で比較し、
それが同じ場合は second で比較するので、map の key で降順になりますよ。
map の value でソートしたいのではないのですか?

アバター
purin52002
記事: 235
登録日時: 2年前
連絡を取る:

Re: [c++(?)][google] mapのvalueを基準にした枝刈り

#9

投稿記事 by purin52002 » 2年前

すみません、書き忘れていました。

コード:

template<>
struct std::greater<DataType>
{
    bool operator()(const DataType &left,const DataType &right){return left.second>right.second;}
};
というようにgreaterを特殊化するコードがあると思ってください。


[hr]

元の定義を上書きしてまで特殊化する必要はないですね。

コード:

auto pred=[](const DataType &left,const DataType &right){return left.second>right.second;};
sort(begin(y),end(y),pred);
とします。
c++初心者を自負しています。
質問者さんには今後私にプログラミングを教えてくれるようにやさしく丁寧に教えるつもりです。ぎぶあんどていく^p^
回答者さんには精一杯感謝します。ぎぶおんりー^p^

返信

“C言語何でも質問掲示板” へ戻る