3

所以，我有两个财务数据文件，比如“符号”和“交易量”。在符号中，我有字符串，例如：

FOO
BAR
BAZINGA
...

在卷中，我有整数值，例如：

0001387
0000022
0123374
...

这个想法是股票代码将在文件中重复，我需要找到每只股票的总交易量。因此，我观察 foo 的每一行都会将 foo 的总体积增加在体积中观察到的值。问题是这些文件可能很大：很容易有 5 到 1 亿条记录。典型的一天在文件中可能有大约 1K 不同的符号。

对每个新行使用 strcmp 符号将非常低效。我正在考虑使用关联数组 --- 允许字符串键的哈希表库 --- 例如uthashorGlib的哈希表。

我正在阅读一些非常好的东西Judy arrays？在这种情况下，许可是否有问题？

关于选择有效的哈希表实现有什么想法吗？而且，我是否应该完全使用哈希表或完全使用其他东西。

嗯.. 为之前的遗漏道歉：我需要一个纯 C 解决方案。

谢谢。

4

4 回答 4

0

绝对哈希表听起来不错。你应该看看libiberty 实现。您可以在 GCC 项目Here上找到它。

于 2013-06-20T08:23:00.110 回答
0

我会使用Map. C++ STL伪代码如下所示：

map< string, long int > Mp;
while(eof is not reached)
{
    String stock_name=readline_from_file1();

    long int stock_value=readline_from_file2();

    Mp[stock_name]+=stock_value;
}
for(each stock_name in Mp)
   cout<<stock_name<<" "<<stock_value<<endl;

根据您提供的数据量，它可能效率有点低，但我建议这样做，因为它更容易实现。

如果要严格执行该解决方案C，那么hashing将是最好的解决方案。但是，如果你觉得实现一个哈希表和编写代码来避免collisions很复杂，我还有另一个想法是使用trie. 听起来可能很奇怪，但这也能有所帮助。

我建议你阅读这个。trie它对 a是什么以及如何构建它有一个很好的解释。那里也给出了 C 中的实现。因此，您可能volumes对每个stock. 该值可以存储在末尾，stock string并且可以在需要时轻松更新。

但是正如您所说，您是 C 新手，我建议您尝试使用 using 来实现hash table，然后尝试这个。

于 2013-06-20T08:27:28.943 回答
0

思考为什么不坚持你的关联数组想法。我假设，在执行结束时，您需要一个具有唯一名称及其聚合值的列表。只要您有记忆来保存所有唯一名称，下面就可以使用。当然，这可能不是那么有效，但是，根据您的数据模式可以完成一些技巧。

Consolidate_Index =0;

struct sutruct_Customers
{
name[];
value[];
}

sutruct_Customers Customers[This_Could_be_worse_if_all_names_are_unique]

void consolidate_names(char *name , int value)
{
    for(i=0;i<Consolidate_Index;i++){
        if(Customers[i].name & name)
            {
            Customers[i].value+= Values[index];

            }
    else
    {
    Allocate memory for Name Now!
    Customers[Consolidate_Index].name = name;
    Customers[Consolidate_Index].value = Value;
    Consolidate_Index++;
    }
    }
}

main(){

sutruct_Customers buffer[Size_In_Each_Iteration]

while(unless file is done){

file-data-chunk_names to buffer.name
file-data-chunk_values to buffer.Values

for(; i<Size_In_Each_Iteration;i++)
consolidate_names(buffer.Names , buffer.Values);

}
于 2013-06-20T10:11:47.493 回答
0

我的解决方案：

我最终使用 JudySL 数组来解决这个问题。经过一番阅读，使用 Judy 实现该解决方案非常简单。我在这里完全复制解决方案，以便对其他人有用。

#include <stdio.h>
#include <Judy.h>

const unsigned int BUFSIZE = 10; /* A symbol is only 8 chars wide. */

int main (int argc, char const **argv) {

  FILE *fsymb = fopen(argv[1], "r");
  if (fsymb == NULL) return 1;

  FILE *fvol = fopen(argv[2], "r");
  if (fvol == NULL) return 1;

  FILE *fout = fopen(argv[3], "w");
  if (fout == NULL) return 1;

  unsigned int lnumber = 0;
  uint8_t symbol[BUFSIZE];
  unsigned long volume;

  /* Initialize the associative map as a JudySL array. */
  Pvoid_t assmap = (Pvoid_t) NULL;
  Word_t *value;

  while (1) {

    fscanf(fsymb, "%s", symbol);
    if (feof(fsymb)) break;

    fscanf(fvol, "%lu", &volume);
    if (feof(fvol)) break;

    ++lnumber;

    /* Insert a new symbol or return value if exists. */
    JSLI(value, assmap, symbol);
    if (value == PJERR) {
        fclose(fsymb);
        fclose(fvol);
        fclose(fout);
        return 2;
    }
    *value += volume;

  }

  symbol[0] = '\0'; /* Start from the empty string. */
  JSLF(value, assmap, symbol); /* Find the next string in the array. */
  while (value != NULL) {
    fprintf(fout, "%s: %lu\n", symbol, *value); /* Print to output file. */
    JSLN(value, assmap, symbol); /* Get next string. */
  }

  Word_t tmp;
  JSLFA(tmp, assmap); /* Free the entire array. */

  fclose(fsymb);
  fclose(fvol);
  fclose(fout);
  return 0;

}

我在一个包含 300K 行的“小”样本上测试了该解决方案。输出正确，经过的时间为 0.074 秒。

于 2013-07-14T19:56:43.607 回答