1

現在、データ構造の実行時間に応じて、頻度を計算するためにハッシュ テーブルの作成に取り組んでいます。O(1)の挿入、O(n)の悪いルックアップ時間など。

std::mapとハッシュテーブルの違いを数人に尋ねたところ、次のような回答がありました。

"std::map要素を二分木として追加するとO(log n)が発生しますが、実装するハッシュ テーブルではO(n)になります。"

したがって、リンクされたリストの配列 (個別の連鎖用)構造を使用してハッシュ テーブルを実装することにしました。以下のコードでは、ノードに 2 つの値を割り当てています。1 つはキー (単語)で、もう 1 つは値 (頻度)です。それは次のように機能します。インデックスが空の場合に最初のノードが追加されると、リンクされたリストの最初の要素として頻度0で直接挿入されます。すでにリストにある場合 (残念ながら検索にO(n)時間がかかります)、頻度を 1 増やします。見つからない場合は、単純にリストの先頭に追加します。

実装には多くのフローがあることを知っているので、周波数を効率的に計算するために、ここの経験豊富な人々に尋ねたいのですが、この実装をどのように改善できますか?

これまでに書いたコード。

#include <iostream>
#include <stdio.h>

using namespace std;

struct Node {
    string word;
    int frequency;
    Node *next;
};

class linkedList
{
private:
    friend class hashTable;
    Node *firstPtr;
    Node *lastPtr;
    int size;
public:
    linkedList()
    {
        firstPtr=lastPtr=NULL;
        size=0;
    }
    void insert(string word,int frequency)
    {
        Node* newNode=new Node;
        newNode->word=word;
        newNode->frequency=frequency;

        if(firstPtr==NULL)
            firstPtr=lastPtr=newNode;
        else {
            newNode->next=firstPtr;
            firstPtr=newNode;
        }

        size++;
    }
    int sizeOfList()
    {
        return size;
    }
    void print()
    {
        if(firstPtr!=NULL)
        {
            Node *temp=firstPtr;
            while(temp!=NULL)
            {
                cout<<temp->word<<" "<<temp->frequency<<endl;
                temp=temp->next;
            }
        }
        else
            printf("%s","List is empty");
    }
};

class hashTable
{
private:
    linkedList* arr;
    int index,sizeOfTable;
public:
    hashTable(int size) //Forced initalizer
    {
        sizeOfTable=size;
        arr=new linkedList[sizeOfTable];
    }
    int hash(string key)
    {
        int hashVal=0;

        for(int i=0;i<key.length();i++)
            hashVal=37*hashVal+key[i];

        hashVal=hashVal%sizeOfTable;
        if(hashVal<0)
            hashVal+=sizeOfTable;

        return hashVal;
    }
    void insert(string key)
    {
        index=hash(key);
        if(arr[index].sizeOfList()<1)
            arr[index].insert(key, 0);
        else {
            //Search for the index throughout the linked list.
            //If found, increment its value +1
            //else if not found, add the node to the beginning
        }
    }



};
4

2 に答える 2

0

最悪の場合を気にしますか？いいえの場合は、std::unordered_map（衝突を処理し、不要なmultimap）または trie/critbit ツリーを使用します（キーによっては、ハッシュよりもコンパクトな場合があり、キャッシュ動作が改善される場合があります）。はいの場合は、std::setまたはトライを使用します。

たとえば、オンラインの上位 k 統計が必要な場合は、辞書に加えて優先キューを保持します。各ディクショナリ値には、出現回数と、単語がキューに属しているかどうかが含まれています。キューは上位 k の頻度/単語のペアを複製しますが、頻度によってキーが付けられます。別の単語をスキャンするときはいつでも、それが (1) まだキューにないかどうか、および (2) キュー内の最小要素よりも頻度が高いかどうかを確認してください。その場合、最小のキュー要素を抽出し、スキャンした要素を挿入します。

必要に応じて独自のデータ構造を実装することもできますが、STL 実装に携わるプログラマーはかなり鋭い傾向があります。それが最初のボトルネックであることを確認します。

于 2012-04-21T22:42:14.150 に答える
0

1- std::map および std::set での検索の複雑な時間は O(log(n)) です。また、std::unordered_map と std::unordered_set の償却時間の複雑さは O(n) です。ただし、ハッシュの一定時間は非常に長くなる可能性があり、小さい数値の場合は log(n) より長くなります。私はいつもこの顔を考えています。

2- std::unordered_map を使用する場合は、タイプに対して std::hash が定義されていることを確認する必要があります。それ以外の場合は、それを定義する必要があります。

于 2012-04-26T07:48:55.243 に答える