2

これはかなり大きな質問だと思いますが、ここに短いバージョンがあります。私のプログラムは、ベクトル全体に散在する多くの要素を削除する必要があります。これらの要素は粒子に関連しており、ベクトル内で移動した粒子がどこに移動したかを伝える必要もあります。メモリ コストを低く抑えることが優先事項であるため、理想的には、データ構造を変更せずに (または可能であれば縮小して)、このプロセスを合理化したいと考えています。

今、長いバージョン：

だから私はできる限り効率的なプログラムを作成しようとしています.多くのビン(ここではカテゴリと呼ばれます)にラベル(特定の粒子に関連する)のリストを格納します.各粒子は1つのカテゴリでしか表現できませんが、何度も表されます (ただし、隣接するサイトである必要はありません)。

カテゴリには、含まれる粒子のリスト (粒子ごとに配列内の 1 つの要素) と、特定のサイトに含まれる粒子のリストがあります。(サイトは、この特定の配列の配列要素に対して私が使用する特定の名前です) したがって、最初は (1,4,5) と読み、粒子 1、4、および 5 がこのカテゴリにあることを示します。2 番目は (4,5,1,1,4,4) と表示されます。

逆ツリー検索を行うために、粒子は、粒子とサイトのカテゴリ リストのどこに位置するかを個別に認識しています。(したがって、粒子のリストの最初であり、サイトのリストの 3 番目と 4 番目であることがわかります)

理想的には、メモリ コストを最小限に抑えることが優先事項であるため、これらのデータ構造に格納された数値をこれ以上追加したくありませんが、必要に応じて追加します。

私の問題は、特定の粒子に対応するすべての要素を削除することは現在非常にコストのかかる操作であることですが、主に特定の粒子に関連するすべてのサイトも見つけなければならないため、プロセスのすべてのステップを実行する必要があります。交換された他の粒子に、サイトが移動したことを伝えます。

私は現在、削除したいすべてのサイトを後ろに送り、それらをポップオフします。これを行うより良い方法がわかりません.

この例では 3 つの粒子しかありませんが、実際のシミュレーションでは数百万の粒子が存在する可能性があることに注意してください。

以下は、私のデータ構造と、カテゴリから粒子を削除するために現在使用している関数です。現時点で最大のコストは、特定の粒子に属するすべてのサイトを並べ替えて、サイトの配列内の場所に配置することです。これを行う唯一の理由は、後ろの近くで見つかった粒子を知るためです。サイトのリストの最後のサイトになります。

助けてくれてどうもありがとう、すみません、これは大きな質問になりました

( whichAtom はすでに選択されているパーティクル ラベルで、 whichCategory はそのカテゴリです)

struct particle
{
    float rate;
    int categorySite;
    vector<int> occupiedSites;
};

struct bin
{
    vector<int> atomsContained;
    vector<int> sites;
};

vector<struct particle> atom (NUMBER_OF_ATOMS);
vector<struct bin> category (10);

void removeAtom()
{
    //tells atom that was last in list of atoms in that category that it has changed position
    atom[category[whichCategory].atomsContained.back()].categorySite = atom[whichAtom].categorySite;

    //removes atom from list of atoms in that category
    category[whichCategory].atomsContained[atom[whichAtom].categorySite] = category[whichCategory].atomsContained.back();
    category[whichCategory].atomsContained.pop_back();

    int numberOfSites = (int) atom[whichAtom].occupiedSites.size();

    //removes sites from that category
    for (int i = 0; i < numberOfSites; i++)
    {
        if (atom[whichAtom].occupiedSites[i] != category[whichCategory].sites.size()-1)
        {
            int categorySize = (int) category[whichCategory].sites.size();
            int distanceFromBack = 1;
            while (category[whichCategory].sites[categorySize-distanceFromBack] == whichAtom && (categorySize-distanceFromBack) != atom[whichAtom].occupiedSites[i])
            {
                distanceFromBack++;
            }


            int originalSite = atom[whichAtom].occupiedSites[i];

            //teling the atom that it has changed site (requires last site listed in the atom to be the one nearest the back)
            int targetAtom = category[whichCategory].sites[categorySize-distanceFromBack];
            std::swap(atom[targetAtom].occupiedSites.back(), atom[whichAtom].occupiedSites[i]);

            // makes sure that the sites are refenced in the order they appear in the array
            if (atom[targetAtom].occupiedSites.size() > 1)
            {
                for (int j = 0; j < atom[targetAtom].occupiedSites.size(); j++)
                {
                    for (int k = (int) atom[targetAtom].occupiedSites.size()-1; k > j; k--)
                    {
                        if (atom[targetAtom].occupiedSites[j] > atom[targetAtom].occupiedSites[k])
                        {
                            std::swap(atom[targetAtom].occupiedSites[j],atom[targetAtom].occupiedSites[k]);
                        }
                    }
                }
            }

            //telling the category that the atoms in the sites have switched
            std::swap(category[whichCategory].sites[originalSite], category[whichCategory].sites[categorySize-distanceFromBack]);
        }
    }

    //removes previously occupied sites from atoms memory (MIGHT BE COMBINEABLE WITH ABOVE)
    for (int i = 0; i < numberOfSites; i++)
    {
        category[whichCategory].sites.pop_back();
        atom[whichAtom].occupiedSites.pop_back();
    }
}
4

2 に答える 2

0

わかりました、メモリ コストを追加せずに大幅に改善する簡単な再配置を見つけました。

ベクトルの最後で削除したい粒子に関連するすべてのサイトを注文する前に、それらを一度にすべて削除しました。

これは、基本的に、愚かでした。最後の 1 つから開始することにより (for ループはカウントアップではなくカウントダウンするようになりました)、それらを 1 つずつ削除し、最後の 1 つと交換し、サイトのリストを調べて、扱っている特定のサイトを見つけます (毎回並べ替えます）、すべてを入れ替えて、サイトを 1 つずつ削除します。

今、私の問題は、ベクターからサイトを削除するという行為そのもの（最後の pop_back ）が高価であるようです。誰かがこれについてアドバイスを持っているなら、私は知りたいですか？while ループは依然として最も時間のかかる部分ですが、構造体を変更するだけで改善できるかどうかはわかりません。

とにかく、これが私のコードです（データ構造は上記と同じです）

void removeAtom()
{
    //tells atom that was last in list of atoms in that category that it has changed position
    atom[category[whichCategory].atomsContained.back()].categorySite = atom[whichAtom].categorySite;

    //removes atom from list of atoms in that category
    category[whichCategory].atomsContained[atom[whichAtom].categorySite] = category[whichCategory].atomsContained.back();
    category[whichCategory].atomsContained.pop_back();

    //works out number of sites to remove
    int numberOfSites = (int) atom[whichAtom].occupiedSites.size();

    //removes sites from that category, starting with the last one
    for (int i = numberOfSites; i > 0; i--)
    {
        //finds where the site we want to remove is, and where it will go (i.e. the end of the vector)
        int startingSite = atom[whichAtom].occupiedSites[i-1];
        int swappingSite = (int) (category[whichCategory].sites.size() - 1);

        //finds which atom is at the end, tells starting site that it's changed to this type
        int targetAtom = category[whichCategory].sites.back();
        category[whichCategory].sites[startingSite] = targetAtom;


        //finds where this site is in the list of sites that the target atom maintains
        int whichOccupiedSite = 0;
        int foundOccupiedSite = 0;

        while (foundOccupiedSite==0)
        {
            if (atom[targetAtom].occupiedSites[whichOccupiedSite] == swappingSite)
            {
                foundOccupiedSite = 1;
            }
            whichOccupiedSite++;
        }
        whichOccupiedSite--;

        //tells the atom it's moved site
        atom[targetAtom].occupiedSites[whichOccupiedSite] = startingSite;

        //removes this site
        category[whichCategory].sites.pop_back();
        atom[whichAtom].occupiedSites.pop_back();
    }
}

また、ベクトル/配列ではなくハッシュテーブルを使用することを提案したベンに感謝します。おそらく、ここで尋ねられた問題にはうまくいくでしょう。残念ながら、プログラムの他の場所では、サイトのこのベクトルからランダムに粒子を選択する必要があります。サイトの数によって重み付けされます。これは配列では簡単ですが、ハッシュ テーブルでそれを行う方法がわかりません。

于 2013-10-01T14:59:45.590 に答える