2

恐怕这是一个相当大的问题，但这是简短的版本。我的程序需要删除散布在向量中的大量元素。这些元素与粒子有关，它还需要告诉任何粒子在它们移动到的向量中移动。保持低内存成本是当务之急，所以理想情况下，我希望简化这个过程，同时不改变我的数据结构（或者如果可以的话，缩小它们）。

现在是长版：

因此，我正在尝试制作一个尽可能高效的程序，该程序在多个箱（此处称为类别）中存储标签列表（与特定粒子相关），其中每个粒子只能在一个类别中表示，但可能多次出现（尽管不一定在相邻站点中）

这些类别有一个它们包含哪些粒子的列表（每个粒子在数组中的一个元素）以及一个特定站点中包含哪些粒子的列表。（站点是我在这个特定数组中的数组元素始终使用的特定名称）所以第一个可能是 (1,4,5)，显示粒子 1、4 和 5 属于此类。然后第二个可能会读取 (4,5,1,1,4,4)。

为了进行反向树搜索，粒子分别知道它们在粒子和站点的类别列表中的位置。（所以 1 会知道它在粒子列表中排名第一，在站点列表中排名第三和第四）

理想情况下，我不想再添加这些数据结构存储的数字，因为最小化内存成本是我的首要任务，但如果必须的话，我会这样做。

我的问题是删除与某个粒子相对应的所有元素目前是一项非常昂贵的操作，但我必须完成该过程的每一步，主要是因为必须找到与特定粒子相关的所有站点就像告诉其他交换的粒子他们的站点已经移动了一样。

我目前将所有要删除的网站都发送到后面并将它们弹出，我看不到更好的方法。

请记住，虽然示例中只有 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

我倾向于建议不要使用这种反向引用（粒子记住它们的成员资格），正是因为它往往会使结构僵化并使删除更加乏味。粒子只记住它们的类别并在必要时手动扫描这些阵列可能比同时记住（并保持准确的数据）它们在这些类别中的位置更快。

于 2013-10-01T09:14:26.103 回答
0

好的，我发现了一个简单的重新排列，可以在不增加内存成本的情况下大大改善它。

在我订购与我想在矢量末尾删除的粒子相关的所有站点之前，然后一次将它们全部删除。

这基本上是愚蠢的。从最后一个开始（for循环现在倒计时而不是倒计时）我可以一个一个地删除它们，与最后一个交换，查看它的站点列表以找到我正在处理的特定站点（而不是每次都重新排序）然后交换所有内容并一个一个删除站点。

现在我的问题似乎是从向量中删除站点的行为（最后的 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();
    }
}

还要感谢 Ben，他建议使用哈希表而不是向量/数组，这可能会很好地解决这里提出的问题，不幸的是在程序的其他地方我必须从这个站点向量中随机选择一个粒子，这样就有机会选择它由站点数量加权，这很容易使用数组，但我看不到如何使用哈希表来做到这一点？

于 2013-10-01T14:59:45.590 回答