3

以下のコードは、ハッシュ テーブル (リンクされたリストの束) で見つけられる最高頻度を 10 回出力します。ハッシュ テーブルに上位 10 個の頻度を出力するコードが必要です。これを行う方法がわかりません（コード例は素晴らしいでしょう、プレーンな英語のロジック/疑似コードも同様に素晴らしいです）。

  1. ハッシュテーブル「hashtable」を指す「tmp」という一時的なハッシュリストを作成します
  2. その後、while ループがリストを調べて、int 'tmp->freq' である最高周波数を探します。
  3. ループは、ハッシュ テーブルのリンク リストの最後に到達するまで、変数 'topfreq' を使用して検出した最高頻度を複製するこのプロセスを続行します。

私の「ノード」は、変数「freq」(int) と「word」(128 文字) で構成される構造体です。ループで他に検索するものがなくなると、これら 2 つの値が画面に表示されます。

問題は、私が見つけたばかりの数から次に低い数を見つける方法を考え出すことに頭を悩ませることができないことです (そして、これには同じ 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;
    }
}

ありとあらゆる助けをいただければ幸いです:)

4

7 に答える 7

2

10個のノードポインタの配列を保持し、配列をソートされた順序で維持しながら、各ノードを配列に挿入します。配列の11番目のノードは、反復ごとに上書きされ、ジャンクが含まれます。

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;
                }
        }
}
于 2009-05-10T06:26:52.577 に答える
0

ステップ1（非効率的）：

挿入ソートを使用してベクトルをソートされたコンテナーに移動しますが、サイズ10のコンテナー（リンクリストやベクトルなど）に挿入し、リストの一番下にある要素をすべて削除します。

ステップ2（効率的）：

手順1と同じですが、リストの一番下にあるアイテムのサイズを追跡し、現在のアイテムが小さすぎる場合は挿入手順を完全にスキップします。

于 2009-05-10T08:35:35.747 に答える
0

ハッシュテーブル（およびそこに含まれる各リンクリスト）を反復処理するときは、自己平衡二分木（std :: set）を「結果」リストとして保持します。各頻度に出くわしたら、それをリストに挿入し、10を超えるエントリがある場合はリストを切り捨てます。終了すると、上位10個の周波数のセット（ソート済みリスト）が表示され、必要に応じて操作できます。

ハッシュテーブル自体のリンクリストの代わりにセットを使用することでパフォーマンスが向上する可能性がありますが、それは自分で解決できます。

于 2009-05-10T05:41:44.417 に答える
0

リンクされた単語のリストを含むハッシュ テーブルは、単語の頻度を蓄積することが目標である場合に使用する独特のデータ構造のように思えます。

それにもかかわらず、最も頻度の高い 10 個のノードを取得する効率的な方法は、O(1) の挿入時間と O(n) の削除時間を持つフィボナッチ ヒープなどの優先キュー/ヒープにそれぞれを挿入することです。ハッシュ テーブル テーブルの反復が高速であると仮定すると、このメソッドの実行時間は O(n×O(1) + 10×O(n)) ≡ O(n) になります。

于 2009-05-10T09:37:19.607 に答える
0

すでに使用されている単語のセットを維持し、最も内側の if 条件を変更して、以前のトップ頻度よりも高い頻度をテストし、かつ tmp-> 既に使用されている単語のリストにない単語をテストします。

于 2009-05-10T05:33:41.020 に答える
0

合計でn 個の単語があり、最も頻繁に使用されるk 個の単語が必要であるとします (ここでは、k = 10)。

nがkよりもはるかに大きい場合、私が知っている最も効率的な方法は最小ヒープを維持することです (つまり、一番上の要素はヒープ内のすべての要素の最小頻度を持ちます)。各反復で次の周波数をヒープに挿入し、ヒープにk +1 個の要素が含まれている場合は、最小の を削除します。このようにして、ヒープは常に k 個の要素のサイズで維持され、これまでに見られたk 個の最高頻度の要素が常に含まれます。処理の最後に、k 個の最も頻度の高い要素を昇順で読み取ります。

時間の複雑さ: n 個の単語のそれぞれについて、2 つのことを行います: 最大でkのサイズのヒープに挿入し、最小要素を削除します。各操作には O(log k) の時間がかかるため、ループ全体に O(nlog k) の時間がかかります。最後に、最大kのサイズのヒープからk 個の要素を読み取り、O(klog k) 時間、合計時間 O((n+k)log k) かかります。k < nであることがわかっているため、O(klog k) は最悪でも O(nlog k) になるため、これは単純に O(nlog k) に単純化できます。

于 2009-05-10T10:08:14.870 に答える
0

これを行う絶対的な最速の方法は、SoftHeap を使用することです。SoftHeap を使用すると、O(n) 時間で上位 10 項目を見つけることができますが、ここに投稿された他のすべてのソリューションは O(n lg n) 時間かかります。

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

このウィキペディアの記事は、ソフトヒープを使用して O(n) 時間で中央値を見つける方法を示しており、トップ 10 は単に中央値問題のサブセットです。次に、必要に応じて上位 10 位のアイテムを並べ替えることができます。常に最大 10 個のアイテムを並べ替えるので、それでも O(n) 時間です。

于 2009-06-15T20:17:41.997 に答える