Как избежать или улучшить метод грубой силы: подсчет повторений символов для всех слов в текстовом файле словаря

Question

Я написал эту служебную функцию, которая будет брать содержимое файла альфа-словаря и складывать количество повторений каждой буквы или символа алфавита.

Это то, что я имею до сих пор:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <vector>

// this function just generates a map of each of the alphabet's
// character position within the alphabet. 
void initCharIndexMap( std::map<unsigned, char>& index ) {
    char c = 'a';
    for ( unsigned i = 1; i < 27; i++ ) {
        index[i] = c;
        c++;
    }
} 

void countCharacterRepetition( std::vector<std::string>& words, const std::map<unsigned, char> index, std::map<char, unsigned>& weights ) {
    unsigned count = 0;

    for ( auto& s : words ) {
        std::transform(s.begin(), s.end(), s.begin(), ::tolower );

        for ( std::size_t i = 0; i < s.length(); i++ ) {
            using It = std::map<unsigned, char>::const_iterator;
            for ( It it = index.cbegin(); it != index.cend(); ++it ) {
                if ( s[i] == it->second ) {
                    count++;
                    weights[it->second] += count;
                }
                count = 0;
            }
        }
    }
}

int main() {
    std::vector<std::string> words;
    std::string line;

    std::ifstream file;
    file.open( "words_alpha.txt" );

    while( std::getline( file, line )
        words.push_back(line);

    std::map<unsigned, char> index;
    initCharIndexMap(index);

    std::map<char, unsigned> weights;
    countCharRepetition(words, index, weights);

    for (auto& w : weights)
        std::cout << w.first << ' ' << w.second << '\n';

     return EXIT_SUCCESS;
 }

Это дает мне вывод, который на первый взгляд кажется верным:

a 295794
b 63940
c 152980
d 113190
e 376455
f 39238
g 82627
h 92369
i 313008
j 5456
k 26814
l 194915
m 105208
n 251435
o 251596
p 113662
q 5883
r 246141
s 250284
t 230895
u 131495
v 33075
w 22407
x 10493
y 70578
z 14757

Текстовый файл словаря, который я использую, можно найти на этой github странице.

Кажется, это работает. Обработка на моей нынешней машине заняла около 3 минут, что не так уж и ужасно, однако это похоже на brute force подход. Есть ли более эффективный способ выполнения такой задачи?

Answer 1

Если вы просто подсчитываете, сколько раз появляется каждый символ, то все, что вам нужно, это:

int frequency[26] = {};
for (auto const& str : words) {
  for (int i=0; i<str.size(); i++) {
    frequency[tolower(str[i]) - 'a']++;
  }
}

for (int i=0; i<26; i++) {
  cout << char(i + 'a') << " " << frequency[i] << endl;
}

Если вы хотите включить символы верхнего и нижнего регистра, измените размер массива на 90, удалите вызов tolower и измените цикл таким образом, чтобы он печатался, только если i находится между a и z или A и Z.

Answer 2

Все вышеупомянутые ответы предполагают преемственность между a и z, а история скажет вам , то есть , а не всегда. Решение не должно предполагать это, и все еще может быть эффективным.

#include <iostream>
#include <fstream>
#include <iterator>
#include <climits>
#include <cctype>

int main(int argc, char *argv[])
{
    if (argc < 2)
        return EXIT_FAILURE;

    unsigned int count[1U << CHAR_BIT] {};

    std::ifstream inp(argv[1]);
    for (std::istream_iterator<char> it(inp), it_eof; it != it_eof; ++it)
        ++count[ std::tolower(static_cast<unsigned char>(*it)) ];

    for (unsigned i=0; i<(1U << CHAR_BIT); ++i)
    {
        if (std::isalpha(i) && count[i])
            std::cout << static_cast<char>(i) << ' ' << count[i] << '\n';
    }
}

выход

[~ user]$ clang++ --std=c++14 -O2 -o main main.cpp
[~ user] time ./main /usr/share/dict/words 
a 199554
b 40433
c 103440
d 68191
e 235331
f 24165
g 47094
h 64356
i 201032
j 3167
k 16158
l 130463
m 70680
n 158743
o 170692
p 78163
q 3734
r 160985
s 139542
t 152831
u 87353
v 20177
w 13864
x 6932
y 51681
z 8460

real    0m0.085s
user    0m0.073s
sys     0m0.005s

Это, вероятно, было бы достаточно быстро для вашего приложения, каким бы оно ни было.

Answer 3

Если вы просто хотите повысить производительность, я бы сказал, что вам все равно придется читать в файле char за char - но я думаю, что весь поиск - это обработка, которая может быть оптимизирована.

Я бы сказал, что следующий псевдокод должен быть быстрее (я попробую привести пример позже):

void read_dictionary(char *fileName)
{
    // Pre-sized array (faster access)
    std::array<int, 26> alphabet_count = {0};

    // Open the file
    FILE *file = fopen(fileName, "r");
    if (file == NULL)
        return; //could not open file

    // Read through the file
    char c;
    while ((c = fgetc(file)) != EOF)
    {
        // If it is a letter a-z
        if ( ((c >= 'a') && (c <= 'z')) ||
        {
             // Increment the array value for that letter
             ++alphabet_count[c - 'a'];
        }
        // else if letter A-Z
        else if ( ((c >= 'A') && (c <= 'Z')) ||
        {
             // Increment the array value for that letter
             ++alphabet_count[c - 'A'];
        }
    }
}

Дело в том, что мы не ищем совпадений, мы используем значение char для индексации в массиве для увеличения буквы алфавита

Answer 4

Ваша версия отслеживает слова без необходимости: вы просто считаете символы в файле. Разделение на слова и строки не имеет значения. Также нет необходимости хранить слова.

Вы могли бы стремиться к читаемому высокоуровневому коду и написать что-то вроде этого:

// https://github.com/KubaO/stackoverflown/tree/master/questions/letter-count-56498637
#include <cctype>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
//*

int main() {
   Histogram<char, 'a', 'z'> counts;

   std::ifstream file;
   file.open("words_alpha.txt");

   for (auto ch : make_range<char>(file)) counts.count(tolower(ch));

   for (auto c : std::as_const(counts)) std::cout << c.value << ' ' << c.count << '\n';
}

Это необходимый минимум для того, как должен выглядеть современный код C ++

Для этого требуется класс Histogram и адаптер make_range для входных потоков. Вы не можете просто реализовать std::begin и std::end для std::ifstream, потому что функция члена end() имеет приоритет и мешает (см. этот ответ ). Код ниже - фрагмент, помеченный // * выше.

template <typename T>
void saturating_inc(T &val) {
   if (val < std::numeric_limits<T>::max()) val++;
}

template <typename T, T min, T max>
class Histogram {
   using counter_type = unsigned;
   using storage_type = std::vector<counter_type>;
   storage_type counts;

  public:
   template <typename U>
   void count(U val) {
      if (val >= min && val <= max) saturating_inc(counts[size_t(val - min)]);
   }
   Histogram() : counts(1 + max - min) {}
   struct element {
      T value;
      counter_type count;
   };

   class const_iterator {
      T val;
      storage_type::const_iterator it;

     public:
      const_iterator(T val, storage_type::const_iterator it) : val(val), it(it) {}
      const_iterator &operator++() {
         ++val;
         ++it;
         return *this;
      }
      bool operator!=(const const_iterator &o) const { return it != o.it; }
      element operator*() const { return {val, *it}; }
   };
   const_iterator begin() const { return {min, counts.begin()}; }
   const_iterator end() const { return {0, counts.end()}; }
};

template <class C, class T>
class istream_range {
   C &ref;

  public:
   istream_range(C &ref) : ref(ref) {}
   std::istream_iterator<T> begin() { return {ref}; }
   std::istream_iterator<T> end() { return {}; }
};

template <class T, class C>
istream_range<C, T> make_range(C &ref) {
   return {ref};
}

На этом пример заканчивается.

Answer 5

#include <array>
#include <fstream>
#include <iostream>

int main()
{
    std::ifstream file;
    file.open( "words_alpha.txt" );

    char c;
    std::array<std::size_t, 26> counts {};

    while( file >> c)
        ++counts[c-'a'];

    for(char c = 0; c<26;++c)
        std::cout<<'('<<c+'a'<<','<<counts[c]<<")\n";
}