3

get_number()返回一个整数。我将调用它 30 次并计算返回的不同整数的数量。我的计划是将这些数字放入一个std::array<int,30>，排序然后使用std::unique。

这是一个好的解决方案吗？有更好的吗？这段代码将成为我程序的瓶颈。

我在想应该有一个基于哈希的解决方案，但是当我只有 30 个元素时，它的开销可能会太大？

编辑我将unique更改为distinct。例子：

{1,1,1,1} => 1
{1,2,3,4} => 4
{1,3,3,1} => 2
4

6 回答 6

7

我会使用std::set<int>它更简单：

std::set<int> s;
for(/*loop 30 times*/)
{
   s.insert(get_number());
}
std::cout << s.size() << std::endl; // You get count of unique numbers

如果你想计算每个唯一号码的返回次数，我建议map

std::map<int, int> s;
for(int i=0; i<30; i++)
{
  s[get_number()]++;
}

cout << s.size() << std::endl;  // total count of distinct numbers returned

for (auto it : s)
{
  cout << it.first << " " << it.second<< std::endl;  // each number and return counts
}
于 2013-10-03T09:22:53.710 回答
4

最简单的解决方案是使用std::map：

std::map<int, size_t> counters;

for (size_t i = 0; i != 30; ++i) {
    counters[getNumber()] += 1;
}

std::vector<int> uniques;
for (auto const& pair: counters) {
    if (pair.second == 1) { uniques.push_back(pair.first); }
}

// uniques now contains the items that only appeared once.
于 2013-10-03T09:31:35.207 回答
3

使用std::map,std::set或std::sort算法会给您带来O(n*log(n))复杂性。对于少量到大量的元素，它是完全正确的。但是你使用一个已知的整数范围，这就为许多优化打开了大门。

正如您所说（在评论中）您的整数范围是已知且短的：[0..99]. 我建议实施修改后的计数排序。见：http ://en.wikipedia.org/wiki/Counting_sort

您可以在进行排序时计算不同项目的数量，从而无需std::unique调用。整个复杂性将是O(n). 另一个优点是所需的内存与输入项的数量无关。如果您有 30.000.000.000 个整数要排序，则不需要单个补充字节来计算不同的项目。

即使允许的整数值的范围很大，表示[0..10.000.000]消耗的内存也会很低。实际上，优化的版本可以消耗低至每个允许的整数值 1 位。这不到 2 MB 内存或笔记本电脑内存的 1/1000。

这是一个简短的示例程序：

#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>

// A function returning an integer between [0..99]
int get_number()
{
    return rand() % 100;
}


int main(int argc, char* argv[])
{
    // reserves one bucket for each possible integer
    // and initialize to 0
    std::vector<int> cnt_buckets(100, 0);
    int nb_distincts = 0;

    // Get 30 numbers and count distincts
    for(int i=0; i<30; ++i)
    {
        int number = get_number();
        std::cout << number << std::endl;
        if(0 == cnt_buckets[number])
            ++ nb_distincts;

        // We could optimize by doing this only the first time
        ++ cnt_buckets[number];
    }

    std::cerr << "Total distincts numbers: " << nb_distincts << std::endl;
}

你可以看到它工作：

$ ./main | sort | uniq | wc -l
Total distincts numbers: 26
26
于 2013-10-03T11:48:58.273 回答
0

最简单的方法就是使用std::set.

std::set<int> s;
int uniqueCount = 0;

for( int i = 0; i < 30; ++i )
{
    int n = get_number();

    if( s.find(n) != s.end() ) {
        --uniqueCount;
        continue;
    }

    s.insert( n );
}

// now s contains unique numbers
// and uniqueCount contains the number of unique integers returned
于 2013-10-03T09:22:43.143 回答
0

使用arrayandsort看起来不错，但unique如果您只需要计算不同的值，则可能有点矫枉过正。以下函数应返回排序范围内不同值的数量。

template<typename ForwardIterator>
size_t distinct(ForwardIterator begin, ForwardIterator end) {
  if (begin == end) return 0;

  size_t count = 1;
  ForwardIterator prior = begin;
  while (++begin != end)
  {
    if (*prior != *begin)
      ++count;

    prior = begin;
  }
  return count;
}

与基于set- 或 -map的方法相比，这种方法不需要任何堆分配，并且元素连续存储在内存中，因此它应该快得多。渐近时间复杂度O(N log N)与使用关联容器时相同。我敢打赌，即使是您最初使用 using 的解决方案，std::sort也会std::unique比 using 快得多std::set。

于 2013-10-03T10:23:07.330 回答
0

尝试一个集合，尝试一个无序集合，尝试排序和独特，尝试其他看起来有趣的东西。

然后测量每一个。如果您想要最快的实现，没有什么可以替代尝试真实代码并查看它的实际作用。

您的特定平台和编译器以及其他细节肯定很重要，因此请在尽可能接近生产环境的环境中进行测试。

于 2013-10-03T11:43:23.157 回答