用不同的键对std :: map进行排序？

Question

我正在尝试使用STL来解决以下问题(如果我不需要,我不想实现自己的数据结构).我想出了一个有效的实现,但是我希望有更快的东西...或者我有哪些代码可以做到最好？

我有一个大型数据集,其中每个条目包含两个项目:一个键和一个大小.数据集中有多个条目具有相同的密钥.我需要知道的是:对于每个密钥,数据集中有多少个密钥,每个密钥的总大小是多少.例如,给定此数据集(键,大小):

(1, 3)
(3, 27)
(7, 7)
(3, 2)
(1, 1)

我想生成此输出,按大小升序排序:

Key 1:  Size 4, Count 2
Key 7:  Size 7, Count 1
Key 3:  Size 29, Count 2

由于数据集完全未排序,我首先需要聚合键来计算它们并总结大小.然后我需要通过总大小来求助该数据结构以产生最终输出.这是我用std :: map和std :: vector完成任务的代码:

struct Node
{
    int Size;
    int Count;

    Node()
        : Size(0), Count(0)
    {
    }

    Node(int size)
        : Size(size), Count(1)
    {
    }
};

void map_insert(std::map<int, Node> &map, int key, int size)
{
    std::map<int, Node>::iterator itr = map.find(key);

    if (itr != map.end())
    {
        itr->second.Count++;
        itr->second.Size += size;
    }
    else
    {
        map[key] = Node(size);
    }
}

bool compare(const std::pair<int, Node> &a1, const std::pair<int, Node> &a2)
{
    return a1.second.Size < a2.second.Size;
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::map<int, Node> _map;

    map_insert(_map, 1, 3);
    map_insert(_map, 3, 27);
    map_insert(_map, 7, 7);
    map_insert(_map, 3, 2);
    map_insert(_map, 1, 1);

    std::vector<std::pair<int, Node>> v(_map.begin(), _map.end());
    std::sort(v.begin(), v.end(), compare);

    return 0;
}

减去输出代码,这会产生正确的排序.我讨厌使用两个独立的数据结构,但似乎没有办法根据不同的密钥"求助"树.这里是否存在严重的低效率,我可以避免？谁能想到更好的方法来做到这一点？

请注意,我假设使用Node实例(而不是Node指针)将比new'ing更快并删除在此处使用的每个节点.这是一个合理的假设还是你认为new/delete会比复制这些小结构更快？

编辑:有趣的是,我从来不知道multimap,但使用下面提供的实现(感谢Naveen),看起来Multimap表现更差.(注意我的意图是快速实现,内存不是问题,我应该指出这一点.)使用此实现:

class Timer
{
public:
    Timer()
        : mStart(0)
    {
    }

    void Start()
    {
        mStart = std::clock();
    }

    double Mark()
    {
        std::clock_t curr = std::clock();
        double f = (curr - mStart)/((double)CLOCKS_PER_SEC);
        mStart = curr;
        return f;
    }

private:
    std::clock_t mStart;
};

struct Node
{
    int Size;
    int Count;

    Node()
        : Size(0), Count(0)
    {
    }

    Node(int size)
        : Size(size), Count(1)
    {
    }


};

void map_insert(std::map<int, Node> &map, int key, int size)
{
    std::map<int, Node>::iterator itr = map.find(key);

    if (itr != map.end())
    {
        itr->second.Count++;
        itr->second.Size += size;
    }
    else
    {
        map[key] = Node(size);
    }
}

bool compare(const std::pair<int, Node> &a1, const std::pair<int, Node> &a2)
{
    return a1.second.Size < a2.second.Size;
}

int make_size(int i, int size_max)
{
    return (7 * i) % size_max;
}

int make_key(int i, int key_max)
{
    return (11 * i) % key_max;
}

void first_impl(int max, int size_max, int key_max)
{
    std::cout << "first_impl:" << std::endl;
    double total = 0;
    double curr = 0;
    Timer t;
    t.Start();

    {
        std::map<int, Node> _map;

        for (int i = 0; i < max; ++i)
            map_insert(_map, make_key(i, key_max), make_size(i, size_max));

        total += curr = t.Mark();
        std::cout << "\tinsert: " << curr << std::endl;

        std::vector<std::pair<int, Node>> v(_map.begin(), _map.end());

        total += curr = t.Mark();
        std::cout << "\tcreate: " << curr << std::endl;

        std::sort(v.begin(), v.end(), compare);

        total += curr = t.Mark();
        std::cout << "\tsort: " << curr << std::endl;
    }

    total += curr = t.Mark();
    std::cout << "\tcleanup: " << curr << std::endl;

    std::cout << "\ttotal: " << total << std::endl;
}

void second_impl(int max, int size_max, int key_max)
{
    std::cout << "second_impl:" << std::endl;
    double total = 0;
    double curr = 0;
    Timer t;
    t.Start();

    {
        std::map<int, Node> res;
        typedef std::multimap<int, int> MultiMap;
        MultiMap mMap;

        for (int i = 0; i < max; ++i)
            mMap.insert(std::make_pair(make_key(i, key_max), make_size(i, size_max)));

        total += curr = t.Mark();
        std::cout << "\tinsert: " << curr << std::endl;

        std::multimap<int, int>::iterator iter = mMap.begin();
        std::multimap<int, int>::iterator endIter = mMap.end();
        for(; iter != endIter; ++iter)
        {
            int val = iter->first;
            if(res.find(val) != res.end())
            {
                    continue;
            }

            std::pair<MultiMap::iterator, MultiMap::iterator> iterPair = mMap.equal_range(val);
            Node n;
            n.Size = val;
            n.Count = mMap.count(val);

            int size = 0;
            for(; iterPair.first != iterPair.second; ++iterPair.first)
            {
                    size += iterPair.first->second;                 
            }

            res[size] = n;
        }
        total += curr = t.Mark();
        std::cout << "\tsort: " << curr << std::endl;
    }

    total += curr = t.Mark();
    std::cout << "\tcleanup: " << curr << std::endl;

    std::cout << "\ttotal: " << total << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    const int size_max = 31;
    const int key_max = 1019;
    const int max = 1000000;
    first_impl(max, size_max, key_max);
    second_impl(max, size_max, key_max);

    return 0;
}

结果看起来像这样:

first_impl:
        insert: 0.094
        create: 0
        sort: 0
        cleanup: 0
        total: 0.094
second_impl:
        insert: 1.653
        sort: 46.894
        cleanup: 66.081
        total: 114.628

第二个实现显然较慢.事实上,键的总数远远低于总项数(大约1000的唯一键的总数代表我的数据集)使std :: map成为赢家,因为它很快就达到稳定状态不需要更多节点的地方.在我进行二次调查之前,我完全错过了这个事实.

看起来我的原始实现比multimap更好,因为我不愿意依赖Boost,我想我有答案.谢谢大家!

Answer 1

A multimap<>可以帮到你.

数据集中有多个条目具有相同的密钥.
multimap<>可以处理重复的键,地图不能.

数据集中每个键
multimap<>::count()的数量占用一个键并返回匹配元素的数量.

对于每个关键的是他们的总规模
multimap<>::equal_range()需要一个键和返回std::pair< multimap<>::iterator, multimap<>::iterator >,其中第一个迭代器匹配关键的第一要素,第二个是最后一次.他们可以按照他们开始和结束的想法进行迭代.因此,使用它们将是一个简单的循环来计算每个键的总大小.

显然,它并不完全适合您的需求,如果您要在大型数据集上运行,也许您将获得实现自定义容器的一些有价值的性能.祝好运!