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

尝试使用霍夫曼编码。这是一件复杂而古老的事情，但我认为这是有效的。我不知道是否有新的或/和更好的算法可以做到这一点。

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

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

于 2013-03-24T03:11:21.433 回答
0 
struct node {
  int value;
  struct node *next;
};

我建议使用链表来存储所有值，然后将其转换为字符串...

您可以计算链表中存储值的数量并使用它计算字符串长度......然后使用 malloc() 分配足够的内存......

稍后......虽然更多的值被添加到列表中，您可以修改使用 calloc() 分配的内存......

我不知道它是不是你真正想要的……但对我来说它看起来是可行的

于 2013-03-26T06:08:07.010 回答