1

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

Вопрос: как ускорить программу? Сейчас подсчет в 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";
}
7
  • профайлером надо смотреть, где время теряется 15 фев 2020 в 12:34
  • 1
    попробуйте map заменить на unordered_map. может поможет.
    – pavel
    15 фев 2020 в 12:50
  • просто не нужно взять палочку, ложить его на стол, кивнуть головой, поднять правую руку, делать шаг направо под углом 45 градусов, делать шаг налево под таким же углом, все для того, чтобы сделать шаг вперед... 15 фев 2020 в 12:51
  • @PavelGridin профайлей показывает, что it = dict->find(word); - 52%, dict[word] += 1; - 33% занимает от времени выполнения. 15 фев 2020 в 13:00
  • 1
    вообще тут не нужен никакой find в get_dict, можно сразу делать dict[word]++; оператор [] у map вставляет элемент, если его нет, с дефолтным значением (0 для int). Также нужно вообще удалить clear_dublicate, а в get_dict приводить слово к нужному виду перед вставкой (я так понимаю, это просто приведения первой буквы к нижнему регистру).
    – IR42
    15 фев 2020 в 13:10

2 ответа 2

3

Поскольку вы читаете весь файл в память, не нужны никакие 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;
}
13
  • Спасибо, что-то подобное и хотелось увидеть в ответе. Пока не буду ставить отметку, как ответ, надо написать код и проверить) 15 фев 2020 в 13:31
  • а почему вы считаете, что лучше записывать в вектор символов, затем сортировать и считать, чем просто записать в map? 15 фев 2020 в 13:45
  • @ARHovsepyan, сортировка всегда быстрее, чем вставка в дерево или скачки по памяти для хэшированной организации map (из-за локализации данных в кэше) (в принципе, для 64-бит архитектуры можно еще улучшить, если вместо указателей хранить в векторе 4-х байтные смещения)
    – avp
    15 фев 2020 в 14:20
  • @avp, в каком то частном случаи вы могли оказаться правы, но тут действий с вектором( добавление в конец, сортировка, подсчет всех одинаковых элементов) слышком много, Часто( зависит от количества элементов) даже только одна сортировка стоит дороже чем вставка в дерево. Но вы так уверенно утверждаете обратное того, что проверялось и изучалось не один раз, что мне остается лишь предложить вам проверить это на примере данной задачи( и так и сяк). Это конечно не стоит дальше обсуждать, только далеко не всегда вектора эффективнее и удобнее других всех контейнеров... 15 фев 2020 в 15:16
  • 1
    @ARHovsepyan, откровенно говоря, измерение времени выполнения одна из самых сложных задач. На пустом компе в одних и тех же условиях разброс во времени между последовательными запусками в 10% это совершенно обычная вещь. Причем, такое ощущение, что время меняется не скачками, а скорее волнообразно, но эти волны не слишком стабильны, иногда можно заметить значительные выбросы в обе стороны. Подозреваю, что "виновником" является политика энергосбережения
    – avp
    20 фев 2020 в 20:50
1

Зачем эти лишные телодвижения, когда можно просто читать в 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';
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.