迭代排序列表并计算不同的数字

Question

我想迭代一个排序列表以获得不同数字的数量。

请在下方找到我的尝试。列表的大小为 k*k。当列表排序时，我比较连续的项目以识别重复项。

int count_distinct(list<int> v)
{
    int num = k*k;
    std::list<int>::iterator it;
    it = v.begin();
    for (int a=0; a<k*k-1; a++)
    {
        if(*it == *it+1)
            num--;
        it++;
    }

    return num;
}

我不能更改列表，所以 std::list::unique() 不是一个选项。制作列表或独特项目的副本对我来说太慢了。

Answer 1

如何使用 std::set 获取唯一元素计数？

size_t count_distinct(const list<int>& v)
{    
    std::set<int> temp (v.begin(), v.end());

    return temp.size(); 
}

Answer 2

假设您要查找该列表中唯一整数的数量，并且该列表未排序，您可以使用临时集或 unordered_set，如下所示：

size_t count_distinct(list<int> v)
{
    std::unordered_set<int> distinct;
    for(auto &x : v)
    {
        distinct.insert(x);
    }
    return distinct.size();
}

Answer 3

这是一个提取所有唯一值的容器的解决方案（因为你说你想在之后使用它们）：

计算个唯一值的方法：

template < typename T >
size_t count_unique(const std::list<T> & input)
{
    std::set<T> unique(input.begin(), input.end());
    return unique.size();
}

提取唯一值列表的方法：

template < typename T >
void unique(const std::list<T> & input, std::list<T> & output)
{
    std::set<T> unique(input.begin(), input.end());   
    std::copy(unique.begin(), unique.end(), std::back_inserter(output));
}

示例程序：

int main(int argc, char** argv)
{
    std::list<int> list = { 1, 3, 4, 10, 3, 1, 6, 7 };
    std::list<int> out;

    std::cout << count_unique(list) << std::endl;

    unique(list, out);
    for (auto & x : out)
        std::cout << x << std::endl;
}

Answer 4

您可以使用 std::list<int>::unique() 获取 v 中的所有不同元素，并使用 size() 计算它们。 v 必须排序。检查 v 是否使用函数 std::is_sorted() 排序。如果不是 - 对其进行排序。这也意味着 count_distinct 不适用于常量列表对象。

size_t count_distinct(list<int>& v)
{
    if (!is_sorted(v.begin(), v.end()))
    {
        v.sort();
    }
    v.unique();
    return v.size();
}

Answer 5

您的代码存在以下问题：

您按值将容器传递给函数。您应该通过 const 引用传递它，以最大限度地减少速度和内存损失。
您的条件 *it == *it+1 始终为假（您比较 n 和 n+1）。可能你想写 *it == *(it+1) 但 std::list 有 bidirectional iterators 而你不能 +1 它们。

代码应该是这样的：

size_t count_distinct(const std::list<int>& l) {
    if (l.empty()) return 0;

    size_t distinct = l.size();
    auto prev = l.begin();

    for (auto cur = std::next(prev); cur != l.end(); ++cur, ++prev) {
        if (*cur == *prev)
            --distinct;
    }

    return distinct;
}

或者您可以编写 std::unique 算法的修改版本：

template<class ForwardIt>
size_t unique_cnt(ForwardIt first, ForwardIt last) {
    if (first == last)
        return 0;

    size_t distinct = 1;    
    ForwardIt prev = first;

    while (++first != last) {
        if (!(*prev == *first)) {
            ++distinct;
        }
        prev = first;
    }
    return distinct;
}

然后简单地使用它

size_t distinct = unique_cnt(l.begin(), l.end());

还有一个 std::unique_copy + 自定义迭代器的方法，但是看起来不够优雅。

Answer 6

对于排序数据，您可能不会比您尝试实施的直接方法更有效率。

我更喜欢这样的东西，因为我发现向上计数比向下计数更直观：

std::size_t count_unique_sorted(std::list<int> const& l) {
    if (l.empty()) return 0;
    std::size_t count = 1;
    auto previous_value = l.front();
    // TODO: hope that the compiler fixes that redundant first comparison...
    for (auto next_value : l) {
        if (next_value != previous_value) {
            // the value changed! increment count and update previous_value
            ++count;
            previous_value = next_value;
        }
    }
    return count;
}

您还可以使来自 C++17 的算法 std::unique_copy() algorithm to count instead of copy, by providing a custom OutputIterator. But this will have little benefit performance-wise versus the approach presented above. Maybe it will be worth revisiting, when the parallel implementations 变得可用。

这是一个例子：

template <typename T>
struct counter : public std::iterator<std::output_iterator_tag, T> {
    explicit counter(std::size_t& count) : count(count) {}
    counter& operator*() { return *this; }
    counter& operator++() { return *this; }
    void operator=(T const&) { ++count; }
private:
    std::size_t& count;
};

std::size_t count_unique_sorted2(std::list<int> const& l) {
    std::size_t count = 0;
    std::unique_copy(l.begin(), l.end(), counter<int>(count));
    return count;
}

请注意，在这两种情况下，您都希望将列表作为 const 引用而不是作为函数的副本传递。

如果您觉得这仍然很慢，请随时探索并行化的乐趣。这样做的好处可能取决于数据量和分布。所以你应该在那时开始一些系统的分析。

除非您需要对值进行大量重新排序，否则首先考虑将数据转储到 std::vector<int> 中。拥有随机访问迭代器可以简化事情，拥有更好的局部性也可以加快速度...

迭代排序列表并计算不同的数字

Iterate sorted list and count distinct numbers

c++

list

unique

counting