БЛОГ НА HUSL


Оптимизация алгоритма подсчета слов

Автор вопроса: Sonic Myst

Программа читает обычный текстовый файл подсчитывает слова и сохраняет в другом текстовом файле в виде словаря.

Вопрос: как ускорить программу? Сейчас подсчет в 50-60 Мб-ом файле занимает 3-4 сек., как сделать чтобы занимало менее 2 сек.?

Вот пример файла на выходе:

Слово1 1246
Слово2 65161
Слово3 156
...... ....

Вот код программы:

#include "pch.h"
#include <fstream>
#include <istream>
#include <iostream>
#include <string>
#include <map>

using namespace std;

bool is_delimeter(char* letter);

map<string, int> get_dict(ifstream* in);

void clear_dublicate(map<string, int>* dict);
void write_data(string output, map<string, int>* dict);


int main(int argc, char* argv[]) {

    if (argc < 2) return 1;

    string filepath = argv[1];
    std::ifstream is(filepath, std::ifstream::binary);

    if (is) {
        std::map <std::string, int> dict = get_dict(&is);
        clear_dublicate(&dict);

        write_data("C:\\test\\output.txt", &dict);
    }
    else
    {
        std::cout << "file path error" << endl;
    }
    is.close();

    return 0;
}

bool is_delimeter(char* letter)
{
    if (*letter < -64 || - 1 < *letter)
        return true;
    return false;
}

map<string, int> get_dict(ifstream * in)
{
    setlocale(LC_ALL, "rus");
    std::string line;
    std::string word;
    std::map<string, int> dict;
    std::map<string, int>::iterator it;

    // get length of file:
    in->seekg(0, in->end);
    int length = in->tellg();
    in->seekg(0, in->beg);

    char * buffer = new char[length];

    in->read(buffer, length);

    for (int i = 0; i < length; i++)
    {
        char letter = buffer[i];

        if (is_delimeter(&letter))
        {
            // check empty word
            if (word.length() > 0)
            {
                it = dict.find(word);

                if (it != dict.end())
                {
                    dict[word] += 1;
                }
                else
                {
                    dict[word] = 1;
                }
            }
            word = {};
        }
        else
        {
            word += letter;
        }
    }
    delete[] buffer;
    return dict;
}

void clear_dublicate(map<string, int>* dict)
{
    string word;
    std::map<string, int>::iterator it;

    for (auto item : *dict) {
        if (-64 <= item.first[0] && item.first[0] <= -32)
        {
            //cout << item.first << endl;
            word = item.first;
            word[0] = tolower(word[0]);

            it = dict->find(word);

            if (it != dict->end())
            {
                it->second += item.second;
            }
            dict->erase(item.first);
        }
    }
}

void write_data(string output, map<string, int>* dict)
{
    ofstream fout;

    fout.open("C:\\test\\output.txt");

    for (auto item : *dict) {
        fout << item.first << " " << item.second << endl;
    }

    fout.close();

    cout << "file is recorded";
}

Источник

Ответы (2 шт):

Автор решения: avp

Поскольку вы читаете весь файл в память, не нужны никакие map<>, string и т.п. контейнеры.

Вам нужно поместить указатели на все слова (завершая каждое 0-м в памяти) в vector<char *>.

Далее вы сортируете его и при выводе подсчитываете, сколько раз встретилось слово (одинаковые слова после сортровки будут рядом).

При смене слова в отсортрованном векторе проводите вывод в файл.

Я провел некоторое исследование проблемы и выяснил, что оптимальный метод решения зависит от характера данных (как, собственно, и почти всегда -)).

Краткое резюме состоит в следующем. Если слова почти не повторяются, то метод с сортировкой дает лучший результат. При росте числа повторов слов в файле побеждает метод, основанный на map. Использование unordered_map (хэширование) показывает значительно лучшие результаты, чем map (дерево).

Однако, если окончательный результат (словарь с частотами) должен быть упорядочен, то требуется дополнительная сортировка (утилита sort на моем компе затрачивает ~1.5 sec. для 65 мегабайтного файла).

Ниже приводятся краткие результаты моделирования

avp@avp-desktop:~/avp/hashcode$ g++ -O3 sort-vs-map.cpp
avp@avp-desktop:~/avp/hashcode$ ./a.out -h
Usage: ./a.out [-h] | [n-measure-loops [n-initial-words] [repeate-ini] [max-word-length]]
avp@avp-desktop:~/avp/hashcode$ ./a.out 1 10000000 1 10
measure 1 loops,  initial 10000000 words max length 10, repeate 1 times
Generate text: 65009462 bytes 10000000 words (repeate 1 times)
make_sort_dict:
5905886 clocks (6380921 unique words)
make_map_dict:
15472055 clocks (6380921 unique words)
make_unordered_map_dict:
7329761 clocks (6380921 unique words)
avp@avp-desktop:~/avp/hashcode$ ./a.out 1 1000000 10 10
measure 1 loops,  initial 1000000 words max length 10, repeate 10 times
Generate text: 64994340 bytes 10000000 words (repeate 10 times)
make_sort_dict:
4848500 clocks (707433 unique words)
make_map_dict:
8352081 clocks (707433 unique words)
make_unordered_map_dict:
2962171 clocks (707433 unique words)
avp@avp-desktop:~/avp/hashcode$ ./a.out 1 10000 1000 10
measure 1 loops,  initial 10000 words max length 10, repeate 1000 times
Generate text: 65273000 bytes 10000000 words (repeate 1000 times)
make_sort_dict:
4185644 clocks (8535 unique words)
make_map_dict:
2495361 clocks (8535 unique words)
make_unordered_map_dict:
891762 clocks (8535 unique words)
avp@avp-desktop:~/avp/hashcode$

и сама программа (метод построения словаря через map взят из ответа @AR Hovsepyan).

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

using namespace std;

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>



// do N random words in txt[], copy them to file R times
void build_text_file (int n, int wl, int rep, const char *fname)
{
  char *txt =(char *) malloc((wl + 1) * n);
  char *t = txt;

  for (int i = 0; i < n; i++) {
    int l = random() % wl + 1;
    for (int j = 0; j < l; j++)
      *t++ = random() % ('z' - 'a' + 1) + 'a';
    *t++ = ' ';
  }
  *t++ = ' ';

  int sz = (int)(t - txt);
  printf("Generate text: %d bytes %d words (repeate %d times)\n",
         sz * rep, n * rep, rep);

  int fd = open(fname, O_WRONLY | O_CREAT | O_TRUNC, 0666);
  for (int i = 0; i < rep; i++)
    if (write(fd, txt, sz) != sz)
      perror("write");
  close(fd);
  free(txt);
}

// returns number of unique words
template <typename T>
int
make_map_dict (const char *ifn)
{
  //  std::unordered_map<std::string, int> dict;
  T dict;
  std::ifstream is(ifn);
  std::ofstream fout("outfile");
  std::string word;
  if (is.is_open()) {
    while (is >> word) {
      if (word[0]) {
        //      cout << "w: [" << word << "]\n";
        ++dict[word];
      }
    }
  }

  int n = 0;
  if (fout.is_open()) {
    for (auto p : dict) {
      n++;
      fout << p.first << ' ' << p.second << '\n';
    }
  }

  return n;
}

int cmp (const void *a, const void *b, void *txt)
{
  return strcmp((char *)txt + *(int *)a, (char *)txt + *(int *)b);
}

// returns number of unique words
int
make_sort_dict (const char *ifn)
{
  int fi = open(ifn, O_RDONLY);
  if (fi < 0) {
    perror(ifn);
    return 0;
  }
  off_t sz = lseek(fi, 0, SEEK_END);
  lseek(fi, 0, SEEK_SET);

  // printf("fsize = %d\n", (int)sz);
  char *txt = (char *)malloc(sz + 1);
  int lrd = read(fi, txt, sz);
  close(fi);
  //  printf("lrd = %d\n", lrd);
  if (lrd != sz)
    perror("read");
  txt[sz - 1] = 0;

  vector<int> v;
  int n = 0;

  int in_word = 0;
  for (int i = 0; txt[i]; i++) {
    if (txt[i] > ' ') {
      if (!in_word) {
        v.push_back(i);
        in_word = 1;
      }
    } else {
      if (in_word) {
        in_word = 0;
        txt[i] = 0;
      }
    }
  }

  n = v.size();
  //printf("nwords = %d\n", n);
  qsort_r(&v[0], n, sizeof(v[0]), cmp, txt);

  FILE *fo = fopen("outfile2", "w");
  int cnt = 1, nu = 0;
  for (int i = 1; i < n; i++) {
    if (strcmp(txt + v[i], txt + v[i - 1])) {
      fprintf(fo, "%s %d\n", txt + v[i - 1], cnt);
      cnt = 1;
      nu++;
    } else
      cnt++;
  }
  fprintf(fo, "%s %d\n", txt + v[n - 1], cnt);

  fclose(fo);
  free(txt);

  return nu + 1;
}


int main (int ac, char *av[])
{
  if (av[1] && strcmp(av[1], "-h") == 0) {
    puts("Usage: ./a.out [-h] | [n-measure-loops [n-initial-words] [repeate-ini] [max-word-length]]");
    exit(1);
  }

#define GET_ARG(x, v) ({ x = atoi(av[1] ? av[1] : #v); if (x < 1) x = v; if (av[1]) av++;})

  int nm = 0,  // n-measure-loops
    nw = 0,    // n-initial-words
    nr = 0,    // repeate-ini
    lw = 0;    // max-word-length

  GET_ARG(nm, 100);
  GET_ARG(nw, 10000);
  GET_ARG(nr, 1);
  GET_ARG(lw, 10);


  printf("measure %d loops,  initial %d words max length %d, repeate %d times\n",
         nm, nw, lw, nr);
  const char *ifn = "tstfile";
  build_text_file(nw, lw, nr, ifn);

  puts("make_sort_dict:");
  int nu = 0;
  clock_t t0 = clock();
  for (int i = 0; i < nm; i++)
    nu = make_sort_dict(ifn);
  clock_t t1 = clock();
  printf("%ld clocks (%d unique words)\n", (long)(t1 - t0), nu);

  puts("make_map_dict:");
  t0 = clock();
  for (int i = 0; i < nm; i++)
    nu = make_map_dict<std::map<std::string, int>>(ifn);
  t1 = clock();
  printf("%ld clocks (%d unique words)\n", (long)(t1 - t0), nu);

  puts("make_unordered_map_dict:");
  t0 = clock();
  for (int i = 0; i < nm; i++)
    nu = make_map_dict<std::unordered_map<std::string, int>>(ifn);
  t1 = clock();
  printf("%ld clocks (%d unique words)\n", (long)(t1 - t0), nu);


  return 0;
}
→ Ссылка
Автор решения: AR Hovsepyan

Зачем эти лишные телодвижения, когда можно просто читать в map и записать в файл? 

std::map<std::string, int> dict;
std::ifstream is(argv[1]);
std::ofstream fout(" ваш файл ");
std::string word;
if (is.is_open()) {
    while (is >> word)
        ++dict[word];
}
if (fout.is_open()) {
    for (auto p : dict)
        fout << std::setw(20) << std::left << p.first << ' ' << p.second << '\n';
}
→ Ссылка

licensed under cc by-sa 3.0 with attribution.