Использование функции Map для сопоставления ключей со значениями

Question

Рассматривая классический пример функций Map () и Reduce (), я пишу программу, которая принимает в качестве входного файла файл .txt, а затем подсчитывает частоту каждого слова в документе.Я провел много исследований обеих функций и нашел много примеров с использованием Java или общего псевдокода, но есть одна часть, которую я не могу понять.Это то, что у меня сейчас есть:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void map(char *name, char *content){
        char *str = (char*)malloc((9999)*sizeof(char));
        str = content;
        char* token;
        token = strtok(str, " ,.");

        while(token)
        {
                token = strtok(NULL, " ,.");
        }
}

int main(int argc, char *argv[]){
        int i =0;
        char line[9999]; //= (char*)malloc((argc)*sizeof(char));
        FILE *fp = fopen(argv[1], "r");

        while (fgets(line, 150, fp) != NULL)
        {
                map(argv[1], line);
        }
        fclose(fp);

return 0;        
}

Функция map способна построчно разбивать каждое слово в документе, но часть, которую я не понимаю, состоит в том, как отобразить значения.Как типичный "emit (token, 1)" будет переведен в C?

Answer 1

Обычно это решается с помощью какого-то словаря (так же, как вероятнее всего использовались примеры с java и псевдокодом).Например, вы можете использовать двоичное дерево поиска (скорее всего, самобалансирующееся красно-черное дерево), где каждый узел содержит слово и счет.Несбалансированный BST очень прост в создании, не так эффективен для поиска.Другое решение (более простое в реализации, но, вероятно, гораздо более медленное в работе) состояло бы в том, чтобы иметь простую структуру, содержащую указатель на строку и счетчик, и иметь массив таких структур.Это может потребовать большого копирования и, вероятно, большого перераспределения (и, следовательно, плохого времени выполнения), независимо от того, сохраните ли вы массив отсортированным или нет.