0

1,000 万を超える単語のリストから固有の単語を選別するための最適なアルゴリズムは何ですか? 実行時間の点で最高のテクニックが必要です。

4

3 に答える 3

3

私が覚えている 2 つの簡単な方法があります。

  1. 重複を折りたたむデータ構造にすべての項目を追加します (通常はハッシュですが、バランス ツリーまたはトライを試すこともできます)。
  2. リストを並べ替えてから、前の要素と等しくないすべての要素をコピーして実行します。

大まかに言えば、通常のごちゃごちゃを条件として、ハッシュ テーブルとトライは expected を返し、O(n)バランス ツリーとソートは expected を返しますO(n log n)。解が特定のデータO(n)の解よりも高速であるとは限りません。O(n log n)

(1) のすべてのオプションには、データ構造内のノードに対して多くの小さなメモリ割り当てを行うという欠点があり、専用のアロケータを使用しない限り遅くなる可能性があります。したがって、私の経験では、重要なコードを記述する必要のある作業に着手する前に、実際に関心のあるデータのサイズで並べ替えをテストする価値があります。

使用している言語によっては、これらのアプローチのいくつかは他のアプローチよりもテストしやすい場合があります。たとえば、Python で文字列のリストがある場合、ハッシュテーブルのアプローチはset(my_strings). C には標準のハッシュテーブルがないため、ハッシュテーブルを作成するか、ライブラリを探しています。

もちろん、書きやすさが実行時間に直接影響するわけではないので、(あなたが主張するように) プログラマーの時間が重要ではなく、実行速度だけが問題である場合、数週間かけて入手可能な最良の文献に慣れるのに問題はないはずです。ソートとハッシュテーブルについて。あなたは私よりもはるかによくその質問に答えることができるでしょう。

于 2012-07-19T10:01:31.390 に答える
1

それらをハッシュに追加するだけです。一定時間挿入。オーダー n よりもうまくできるとは思えません。レッド ブラック ツリーは、小さなデータ セットでは高速になる可能性があります (ハッシュを計算するよりもツリーをトラバースする方が高速です) が、データ セットは大きくなります。

于 2012-07-19T09:36:51.630 に答える
0

ネタバレ：

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

struct somehash {
        struct somehash *next;
        unsigned hash;
        char *mem;
        };

#define THE_SIZE (10*1000*1000)
struct somehash *table[THE_SIZE] = { NULL,};

struct somehash **some_find(char *str, unsigned len);
static unsigned some_hash(char *str, unsigned len);

int main (void)
{
char buffer[100];
struct somehash **pp;
size_t len;

while (fgets(buffer, sizeof buffer, stdin)) {
        len = strlen(buffer);
        pp = some_find(buffer, len);
        if (*pp) { /* found */
                fprintf(stderr, "Duplicate:%s", buffer);
                }
        else    {       /* not found: create one */
                fprintf(stdout, "%s", buffer);
                *pp = malloc(sizeof **pp);
                (*pp)->next = NULL;
                (*pp)->hash = some_hash(buffer,len);
                (*pp)->mem = malloc(1+len);
                memcpy((*pp)->mem , buffer,  1+len);
                }
        }
return 0;
}struct somehash **some_find(char *str, unsigned len)
{
unsigned hash;
unsigned short slot;
struct somehash **hnd;

hash = some_hash(str,len);
slot = hash % THE_SIZE;
for (hnd = &table[slot]; *hnd ; hnd = &(*hnd)->next ) {
        if ( (*hnd)->hash != hash) continue;
        if ( strcmp((*hnd)->mem , str) ) continue;
        break;
        }
return hnd;
}

static unsigned some_hash(char *str, unsigned len)
{
unsigned val;
unsigned idx;

if (!len) len = strlen(str);

val = 0;
for(idx=0; idx < len; idx++ )   {
        val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801;
        }
return val;
}
于 2012-07-19T09:41:15.003 に答える