Несколько хеш-таблиц для проекта Word Count - PullRequest
Новая
       23

Несколько хеш-таблиц для проекта Word Count

0 голосов
/ 21 декабря 2018

Я уже написал рабочий проект, но моя проблема в том, что он намного медленнее, чем я планировал, поэтому у меня есть некоторые идеи о том, как его улучшить, но я не знаю, как реализовать эти идеи.или я должен на самом деле реализовать эти идеи в первую очередь?

Тема моего проекта - чтение файла CSV (Excel), заполненного твитами, и подсчет каждого его слова, а затем отображение наиболее используемыхслова.
(в каждой строке Excel есть информация о твите и самом твите, я должен заботиться только о твите)

Вместо того, чтобы делиться всем кодом, я просто напишу то, что сделалпока и спрашиваю только о той части, с которой я борюсь.
Прежде всего, я хочу извиниться, потому что это будет длинный вопрос.

Важное примечание: единственное, на что я должен обратить внимание, это не проблема, скорость или объем памяти.

Все шаги:

  • Прочитать новую строку из файла Excel.
  • Найдите часть "твит" из всей строки и сохраните ее в виде строки.
  • Разделите строку твита на слова и сохраните ее в массиве.
  • Для каждого слова, хранящегося в массиве, вычислить значение ASCII слова.

(Для нахождения значения слова ascii я просто суммирую значение ascii каждогоимеет буквенное обозначение)

  • Поместите слово в хэш-таблицу с ключом значения ASCII.

(Пример: слово "hello" имеет asciiзначение 104 + 101 + 108 + 108 + 111 = 532, поэтому он хранится с ключом 532 в таблице хаста)

  • В хэш-таблице только слово "как строка" изначение ключа «as int» сохраняется, а количество слов (сколько используется одно и то же слово) сохраняется в отдельном массиве.

Я поделюсь функцией Вставка (для вставки чего-либо в Hashtable), потому что я думаю, что это будет сбивать с толку, если я попытаюсь объяснить эту часть без кода. 

void Insert(int key, string value) //Key (where we want to add), Value (what we want to add)
{

    if (key < 0) key = 0; //If key is somehow less than 0, for not taking any error key become 0.

    if (table[key] != NULL) //If there is already something in hast table 
    {       

        if (table[key]->value == value) //If existing value is same as the value we want to add
        {               
            countArray[key][0]++;
        }
        else //If value is different,
        {           
            Insert(key + 100, value);  //Call this function again with the key 100 more than before.
        }
    }
    else //There is nothing saved in this place so save this value
    {           
        table[key] = new HashEntry(key, value); 
        countArray[key][1] = key;
        countArray[key][0]++;           
    }

}

Так что функция «Вставка» состоит из трех частей.

  • Добавить значение в хеш-таблицу, если хаст-таблица с данным ключом пуста.
  • Если таблица хаста с данным ключом не пуста, это означает, что мы уже поместили слово с этим значением ascii.

Поскольку разные слова могут иметь одинаковое значение ascii .

  • Программа сначала проверяет, совпадает ли это слово.
  • Если это так, увеличить счет (в массиве счетчиков).
  • Если нет, функция вставки снова вызывается со значением ключа (то же значение ключа + 100), пока не будет найдено пустое место или такое же значение.

После целых строкчитаются и каждое слово сохраняется в Hashtable ->

Сортировка массива Count
Печать первых 10 элементов

Этоконец программы, так в чем же проблема?

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

Моя вторая проблема - много значений с одинаковым значением ASCII, мой метод проверки на сто больше, чем обычные методы значения ascii, но?чтобы найти пустое место или одно и то же слово, вставьте сам вызов функции сотни раз за слово.
(что вызвало наибольшую проблему).

Поэтому я подумал об использовании нескольких хеш-таблиц.
Например,Я могу проверить первую букву слова, и если она
Между A и E, сохранить в первой хеш-таблице
Между F и J, сохранить во второй хеш-таблице
...
Между V и Z сохраните в последней хэш-таблице.

Важное замечание еще раз: единственное, на что я должен обратить внимание - это скорость, объем памяти или размер, это не проблема.

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

Если можно использовать несколько хеш-таблиц, вместо создания хеш-таблиц, одну за другой, возможно ли создать массив, в котором хранится Hashtable в каждом месте?(То же самое, что и Array of Arrays, но на этот раз в массиве хранятся Hashtables) Если это возможно и логично, может кто-нибудь показать, как это сделать?

Это моя хеш-таблица: 

class HashEntry
{
public:
    int key;
    string value;
    HashEntry(int key, string value)
    {
        this->key = key;
        this->value = value;
    }
};

class HashMap
{
private:
    HashEntry * *table;
public:
    HashMap()
    {
        table = new HashEntry *[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            table[i] = NULL;
        }
    }

//Functions

}

Мне очень жаль за такой длинный вопрос, который я задал, и мне снова очень жаль, если я не смог объяснить каждую часть достаточно ясно, английский не является моим родным языком.

Еще одно последнее замечание, которое я делаюэто для школьного проекта, поэтому я не должен использовать какое-либо стороннее программное обеспечение или включать какие-либо другие библиотеки, потому что это запрещено.

1 Ответ

0 голосов
/ 22 декабря 2018

Вы используете очень плохую хеш-функцию (добавление всех символов), поэтому вы получаете так много коллизий, и ваш Insert метод вызывает себя так много раз.

Для подробного обзораразличные хеш-функции см. в ответе на этот вопрос.Я предлагаю вам попробовать DJB2 или FNV-1a (который используется в некоторых реализациях std::unordered_map).

Вам также следует использовать более локализованные "пробники" для пустого места, чтобы улучшить локальность кэша и используйте цикл вместо рекурсии в вашем Insert методе.

Но сначала я предлагаю вам немного подправить HashEntry: 

class HashEntry
{
public:
    string key; // the word is actually a key, no need to store hash value
    size_t value; // the word count is the value.
    HashEntry(string key)
        : key(std::move(key)), value(1) // move the string to avoid unnecessary copying
    { }
};

Затем давайте попробуем использоватьЛучшая хеш-функция: 

// DJB2 hash-function
size_t Hash(const string &key)
{
    size_t hash = 5381;
    for (auto &&c : key)
        hash = ((hash << 5) + hash) + c;
    return hash;
}

Затем переписать Insert функцию: 

void Insert(string key)
{
    size_t index = Hash(key) % TABLE_SIZE;

    while (table[index] != nullptr) {       
        if (table[index]->key == key) {               
            ++table[index]->value;
            return;
        }
        ++index;
        if (index == TABLE_SIZE) // "wrap around" if we've reached the end of the hash table
            index = 0;
    }           

    table[index] = new HashEntry(std::move(key));
}

Чтобы найти запись в хеш-таблице по ключу, вы можете использовать аналогичный подход: 

HashEntry *Find(const string &key)
{
    size_t index = Hash(key) % TABLE_SIZE;

    while (table[index] != nullptr) {       
        if (table[index]->key == key) {               
            return table[index];
        }
        ++index;
        if (index == TABLE_SIZE)
            index = 0;
    }           

    return nullptr;
}
...