Топ 10 частот в хэш-таблице со связанными списками

Question

Приведенный ниже код выведет меня наивысшую частоту, которую он может найти в моей хэш-таблице (из которой есть набор связанных списков) 10 раз. Мне нужен мой код для печати 10 лучших частот в моей хэш-таблице. Я не знаю, как это сделать (примеры кода были бы хорошими, простая английская логика / псевдокод такая же замечательная).

1. Я создаю временный список хеширования под названием 'tmp', который указывает на мою хеш-таблицу 'hashtable'
2. Затем цикл while проходит по списку и ищет самую высокую частоту, которая является int 'tmp-> freq'
3. Цикл продолжит этот процесс дублирования самой высокой частоты, которую он находит, с переменной topfreq, пока не достигнет конца связанных списков в хэш-таблице.

Мой 'узел' - это структура, состоящая из переменных 'freq' (int) и 'word' (128 символов). Когда циклу больше нечего искать, эти два значения выводятся на экран.

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

void toptenwords()
{
    int topfreq = 0;
    int minfreq = 0;
    char topword[SIZEOFWORD];

    for(int p = 0; p < 10; p++) // We need the top 10 frequencies... so we do this 10 times
    {
        for(int m = 0; m < HASHTABLESIZE; m++) // Go through the entire hast table
        {
            node* tmp;
            tmp = hashtable[m];

            while(tmp != NULL) // Walk through the entire linked list
            {
                if(tmp->freq > topfreq) // If the freqency on hand is larger that the one found, store...
                {
                    topfreq = tmp->freq;
                    strcpy(topword, tmp->word);
                }
                tmp = tmp->next;
            }
        }
        cout << topfreq << "\t" << topword << endl;
    }
}

Любая помощь будет с благодарностью принята :)

Answer 1

Сохраните массив из 10 указателей на узлы и вставьте каждый узел в массив, поддерживая массив в отсортированном порядке. Одиннадцатый узел в массиве перезаписывается на каждой итерации и содержит мусор.

void toptenwords()
{
        int topfreq = 0;
        int minfreq = 0;
        node *topwords[11];
        int current_topwords = 0;

        for(int m = 0; m < HASHTABLESIZE; m++) // Go through the entire hast table
        {
                node* tmp;
                tmp = hashtable[m];

                while(tmp != NULL) // Walk through the entire linked list
                {
                        topwords[current_topwords] = tmp;
                        current_topwords++;
                        for(int i = current_topwords - 1; i > 0; i--)
                        {
                                if(topwords[i]->freq > topwords[i - 1]->freq)
                                {
                                        node *temp = topwords[i - 1];
                                        topwords[i - 1] = topwords[i];
                                        topwords[i] = temp;
                                }
                                else break;
                        }
                        if(current_topwords > 10) current_topwords = 10;
                        tmp = tmp->next;
                }
        }
}

Answer 2

Абсолютный самый быстрый способ сделать это - использовать SoftHeap. Используя SoftHeap, вы можете найти 10 лучших элементов за время O (n), тогда как для любого другого решения, размещенного здесь, потребуется время O (n lg n).

http://en.wikipedia.org/wiki/Soft_heap

Эта статья в Википедии показывает, как найти медиану за O (n) время, используя мягкую кучу, и топ-10 - это просто подмножество медианной проблемы. Затем вы могли бы отсортировать элементы, которые были в топ-10, если вам нужно было их упорядочить по порядку, и, поскольку вы всегда максимально сортируете 10 элементов, это все равно время O (n).

Answer 3

Предположим, что всего n слов, и нам нужны наиболее часто встречающиеся k слова (здесь k = 10).

Если n намного больше, чем k , самый эффективный способ, который я знаю, - это поддерживать минимальную кучу (т. Е. Верхний элемент имеет минимум частота всех элементов в куче). На каждой итерации вы добавляете следующую частоту в кучу, и если куча теперь содержит k + 1 элементов, вы удаляете наименьший . Таким образом, размер кучи поддерживается равным k элементам, содержащим в любое время элементы k с самой высокой частотой, которые когда-либо наблюдались. В конце обработки, считайте элементы k самой высокой частоты в порядке возрастания.

Сложность времени: Для каждого из n слов мы делаем две вещи: вставляем в кучу размером не более k и удаляем минимальный элемент , Каждая операция стоит O (log k) времени, поэтому весь цикл занимает O (nlog k) времени. Наконец, мы считываем элементы k из кучи размером не более k , принимая время O (klog k), за общее время O ((n + k) log к). Поскольку мы знаем, что k <<em> n , O (klog k) в худшем случае O (nlog k), поэтому это можно упростить до O (nlog k).

Answer 4

Хеш-таблица, содержащая связанные списки слов, выглядит как своеобразная структура данных, которую нужно использовать, если целью является накопление частот слов.

Тем не менее, эффективный способ получить десять узлов наивысшей частоты состоит в том, чтобы вставить каждый из них в приоритетную очередь / кучу, такую ​​как куча Фибоначчи, которая имеет время вставки O (1) и время удаления O (n). Предполагая, что итерация по хеш-таблице выполняется быстро, этот метод имеет время выполнения, которое составляет O (n × O (1) + 10 × O (n)) ≡ O (n).

Answer 5

Шаг 1 (неэффективно):

Переместите вектор в отсортированный контейнер с помощью сортировки вставкой, но вставьте в контейнер (например, связанный список или вектор) размером 10 и удалите все элементы, попадающие в нижнюю часть списка.

Шаг 2 (эффективный):

То же, что и шаг 1, но следите за размером элемента в нижней части списка и полностью пропустите шаг вставки, если текущий элемент слишком мал.

Answer 6

При переборе по хеш-таблице (а затем по каждому содержащемуся в ней связанному списку) сохраняйте самобалансирующееся двоичное дерево (std :: set) в качестве списка «результата». Когда вы сталкиваетесь с каждой частотой, вставьте ее в список, а затем обрежьте список, если в нем более 10 записей. Когда вы закончите, у вас будет набор (отсортированный список) из десяти лучших частот, которыми вы можете манипулировать по своему желанию.

Может быть выигрыш при выполнении при использовании наборов вместо связанных списков в самой хэш-таблице, но вы можете решить это сами.

Answer 7

Я бы сохранил набор уже использованных слов и изменил бы самое внутреннее, если бы условие проверялось на частоте выше, чем предыдущая верхняя частота И tmp-> слово, отсутствующее в списке уже использованных слов.