主页 / 问题 / 573330
Accepted
Malov Vladimir
Asked:2020-10-04 03:09:25 +0000 UTC2020-10-04 03:09:25 +0000 UTC

计算唯一值取模个数的算法优化

  • 772

乍一看，这个任务似乎并不难：从源容器中获取唯一整数值​​的模数。首先想到的是将绝对值的所有内容转储到一个集合中并查看其大小：

#include <iostream>
#include <vector>
#include <set>

size_t getUniqueByModuleItemCount(const std::vector<int>& input)
{
    std::set<unsigned> unique;

    for(int item : input) {
        unique.insert(abs(item));
    }

    return unique.size();
}

int main() {

    std::vector<int> srcVec = {1, -4, 3, 2, -12, 0, 4, 17, -2, -2, -3, 13, 7};
    size_t uniqueItemCount = getUniqueByModuleItemCount(srcVec);
    std::cout << "Unique items count by absolute value is " << uniqueItemCount << std::endl;
}

它有效，但显然，这种算法的复杂性O(N*lnN)（通过原始容器的所有元素插入到树中，每次插入 lnN）。因此，问题是 - 是否有任何想法如何优化该算法的复杂性O(N)？

c++

1 个回答

  1. Best Answer

    我做了一个小实验...

    使用不同容器随机生成的N具有正值和负值的数字向量：

    size_t usingSet(const std::vector<int>& input)
{
    std::set<unsigned> unique;
    for(int item : input) {
        unique.insert(abs(item));
    }
    return unique.size();
}

size_t usingHash(const std::vector<int>& input)
{
    std::unordered_set<unsigned> unique;
    unique.reserve(input.size());
    for(int item : input) {
        unique.insert(abs(item));
    }
    return unique.size();
}

size_t usingVec(const std::vector<int>& input)
{
    std::vector<unsigned> uniq;
    uniq.reserve(input.size());
    for(int item : input) {
        uniq.push_back(abs(item));
    }
    sort(uniq.begin(),uniq.end());
    return unique(uniq.begin(),uniq.end()) - uniq.begin();
}

    我们找出唯一元素的数量 1000 次。时间以微秒为单位，明明是正负……但还是挺适合评价的。我没有四舍五入，我觉得很容易在我的脑海里在几秒钟或几毫秒内算出来。

                                Set          Hash        Vector
-----------------------------------------------------------
N =         10:             790          1256           253
N =        100:            8304          8243          1192
N =       1000:          130070         78354         27573
N =      10000:         1543452        757059        498093
N =     100000:        14545110       4232742       6182957
N =    1000000:       127603400      27039847      61045621

    因此，向量开始丢失 10 到 10 万个哈希值。对于小值，散列甚至丢失set'y，在 100 个元素的级别进行比较。然后set它无可救药地输给了所有人-据我了解，不仅是因为O(N*ln N)，而且还因为大量的内存重新分配（reserve()它没有成员，不像散列和向量）。

    如何检查消耗的内存更简单，我没有想出什么，但很明显，这里 vector 会给大家一个良好的开端:)

    一句话，最可悲的选择就是set，根本就没有用的意思。对于小尺寸 - 高达数万 - 最好采用矢量，然后看看更重要的是什么 - 速度或内存。

    所有这些都在 Visual C++ 2015，32 位中。对于 Visual C++ 2010，32 位，vector 的优势就更加明显了 :) 而 hash 在这里丢失了：

                                Set          Hash        Vector
-----------------------------------------------------------
N =         10:             813          1459           223
N =        100:            8688         10795          1448
N =       1000:          135905        102716         29086
N =      10000:         1623786       1068878        519483
N =     100000:        18334735       8822607       6316194
N =    1000000:       179540082      83667899      61899536

    谁想为其他编译器重复 - 不客气......

    顺便说一下，您仍然可以使用向量进行优化——因为我们只需要唯一元素的数量——您不能unique在内存中使用它进行混洗，而只是简单地遍历并重新计算那些邻居不相同的元素。

    更新。我假设匹配的数量很少；我在评论中被纠正了。我仍然没有使唯一元素的数量很少——手不会说谎——而是像这样填充数组：

    for(int i = 0; i < N; ++i)
    src.push_back((rand()%(N/5))*(i%2 ? 1 : -1));

    那些。有很多巧合，但仍然是独特的元素——O(N)

    2015年的成绩，没等到百万：

                                Set          Hash        Vector
-----------------------------------------------------------
N =         10:             279           760           229
N =        100:            2693          2785          1185
N =       1000:           53087         24940         26121
N =      10000:          806965        273205        472123
N =     100000:        12350458       3440321       6006227

    边界向下移动了一点，但原则仍然存在：set飞过，但击败数组上的哈希值直到 100；hash 从 1000 开始领先，而不是从 10000 开始。

    在所有N元素都是单位的极限下，结果几乎是自相矛盾的：

                                Set          Hash        Vector
-----------------------------------------------------------
N =         10:             200           895           219
N =        100:             888          1840           493
N =       1000:            7676         10020          2778
N =      10000:           73524        102685         25881
N =     100000:          733058       1167238        259100
N =    1000000:         7396809      11645557       3561249

    矢量，而且只有矢量！这种情况下的散列甚至会丢失set'y。

    一切，根本就没有时间做实验；谁想继续:)

    Update2 - 在他的“优化的 C++”中，Günteroth 有充分的理由写道，unordered_set虽然它产生了效果，但在阅读如何称赞它时，它根本不是人们所期望的 :) 书中的引述：哈希表std::unordered_map比 快std::map，但是不是由其声誉所暗示的数量级差异。

    • 8

相关问题