Поскольку вы читаете весь файл в память, не нужны никакие 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;
}
find
вget_dict
, можно сразу делатьdict[word]++;
оператор[]
уmap
вставляет элемент, если его нет, с дефолтным значением (0 дляint
). Также нужно вообще удалитьclear_dublicate
, а вget_dict
приводить слово к нужному виду перед вставкой (я так понимаю, это просто приведения первой буквы к нижнему регистру).