c++ - 确定向量中频率最高的 char 元素?

Question

我正在尝试确定以字符为元素的向量中最常见的字符。

我正在考虑这样做：

• 循环遍历向量并创建一个映射，其中键是向量中的唯一字符。相应的值将是该字符频率的整数计数。
• 在我浏览完向量中的所有元素后，地图将包含所有字符频率。因此，我必须找到哪个键具有最高值，从而确定向量中最常见的字符。

不过，这似乎很令人费解，因此我想知道是否有人可以建议这种方法在性能/良好编码方面是否被认为是“可接受的”

这可以以更好的方式完成吗？

Answer 1

如果您只使用常规的 ascii 字符，则可以使解决方案更快一些 - 使用大小为 256 的数组，而不是使用映射，并计算数组单元格中具有给定代码 'x' 的字符的出现次数count[x]。这将从您的解决方案中删除一个对数（256），从而使其更快一些。我不认为在优化这个算法方面可以做更多的事情。

Answer 2

对一个字符向量进行排序，然后对其进行迭代以寻找最大运行长度似乎比使用 map 方法快 5 倍（使用下面相当不科学的测试代码作用于 16M 字符）。从表面上看，这两个函数的执行应该彼此接近，因为它们的执行时间为 O(N log N)。然而，排序方法可能受益于就地向量排序的分支预测和移动语义。

结果输出为：

Most freq char is '\334', appears 66288 times.
usingSort() took 938 milliseconds
Most freq char is '\334', appears 66288 times.
usingMap() took 5124 milliseconds

代码是：

#include <iostream>
#include <map>
#include <vector>
#include <chrono>

void usingMap(std::vector<char> v)
{
    std::map<char, int> m;
    for ( auto c : v )
    {
        auto it= m.find(c);
        if( it != m.end() )
            m[c]++;
        else
            m[c] = 1;
    }

    char mostFreq;
    int count = 0;
    for ( auto mi : m )
        if ( mi.second > count )
        {
            mostFreq = mi.first;
            count = mi.second;
        }

    std::cout << "Most freq char is '" << mostFreq << "', appears " << count << " times.\n";
}

void usingSort(std::vector<char> v)
{
    std::sort( v.begin(), v.end() );
    char currentChar = v[0];
    char mostChar = v[0];
    int currentCount = 0;
    int mostCount = 0;
    for ( auto c : v )
    {
        if ( c == currentChar )
            currentCount++;
        else
        {
            if ( currentCount > mostCount)
            {
                mostChar = currentChar;
                mostCount = currentCount;
            }
            currentChar = c;
            currentCount = 1;
        }
    }

    std::cout << "Most freq char is '" << mostChar << "', appears " << mostCount << " times.\n";
}

int main(int argc, const char * argv[])
{
    size_t size = 1024*1024*16;
    std::vector<char> v(size);
    for ( int i = 0; i < size; i++)
    {
        v[i] = random() % 256;
    }

    auto t1 = std::chrono::high_resolution_clock::now();
    usingSort(v);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout
        << "usingSort() took "
        << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
        << " milliseconds\n";
    auto t3 = std::chrono::high_resolution_clock::now();
    usingMap(v);
    auto t4 = std::chrono::high_resolution_clock::now();
    std::cout
        << "usingMap() took "
        << std::chrono::duration_cast<std::chrono::milliseconds>(t4-t3).count()
        << " milliseconds\n";
    return 0;
}