0

実装を最適化する方法を探しています。基本的に、これは "reduce" のような (Map Reduce フレームワークからの) 関数です。キーとその値を取ります。目標は、すべての値が異なるかどうかをチェックし、それらをリストの形式で出力することです: value1;value2;value3;...valuen; 文字列として。n は非常に大きくなる可能性があります (1000 単位) 

void unique(char *key, int keybytes, char *multivalue, int nvalues,

        int *valuebytes, KeyValue *kv, void *ptr) {

    char * value = NULL;
    char * elem[nvalues];

    int i, j, cx;
    char adj[3858905] = "";

大きな問題は、入力ごとに char adj[] の長さを指定する必要があり、値の数がどれだけ大きいかを事前に知らないことです。（それには膨大な量のメモリが必要です）

    for (i = 0; i < nvalues; i++) {
        if (i == 0) {
            value = multivalue;
        } else {
            value = multivalue + valuebytes[i - 1];
            multivalue = multivalue + valuebytes[i - 1];
        }
        elem[i] = value;
    }

    size_t elem_length = sizeof(elem)/sizeof(char *);
    qsort(elem, elem_length, sizeof(char *), cstring_cmp);

    cx = sprintf(adj, "%s;", elem[0]);

    j = 0;
    for (i = 1; i < nvalues; i++) {
        bool matching = false;
        if (!strcmp(elem[i], elem[j]))
            matching = true;
        j++;
        if (!matching) //{;}
            cx += snprintf(adj + cx, 3858905 - cx - 1, "%s;", elem[i]);                                             
    }

adj は出力文字列 (値のリスト) です。

    kv->add(key, keybytes, adj, strlen(adj) + 1); //this outputs key-value pairs.
}

ただし、C/C++ のみを使用する必要があります。

4

2 に答える 2

0 
struct node {
  int value;
  struct node *next;
};

リンクされたリストを使用してすべての値を保存し、それを文字列に変換することをお勧めします...

リンクされたリストに格納された値の数を保持し、それを使用して文字列の長さを計算し、malloc() を使用して十分なメモリを割り当てることができます.....

そして後で..リストにさらに値が追加されている間、calloc()を使用して割り当てられたメモリを変更できます....

それがあなたがまさに望んでいたものかどうかはわかりません....しかし、それは私には実行可能に見えます

于 2013-03-26T06:08:07.010 に答える
0

ハフマン符号化を使用してみてください。複雑で古いものですが、効率的だと思います。それを行うための新しいアルゴリズムまたは/およびより優れたアルゴリズムがあるかどうかはわかりません。

http://www.cprogramming.com/tutorial/computersciencetheory/huffman.html

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

于 2013-03-24T03:11:21.433 に答える