请教高效算法

Sorehead

问题不是很好描述，我用数据库来举例，一个表中有很多条记录，关键字由5个字段组成，分别是A1、A2、A3、A4和A5，假设A1=1，A2=2，A3=3，A4=4，A5=5，通过这些关键字如果定位这条记录？
我需要用C语言做类似的一个东西，A1至A5中的每个元素大概有几万个不同值，请教一个时间和空间要求都比较高的算法。
这些数据都会在内存中保存，别让我看数据库源码，没有时间，我也没有研究过数据库的实现，目前还没有一个好的思路，希望有人提供好的建议。
如果能给我讲一下数据库大致如何实现这个功能也行，先谢了。


后来想想用数据库描述确实有些不对，采用数据库的方式只是一种实现而已，我的目的并不是已有很多记录，然后通过这5个关键字去定位，而是这5个元素才能确定一个唯一值，通过这个唯一值来保存很多其它数据。

[ 本帖最后由 Sorehead 于 2007-8-22 18:40 编辑 ]

zxlzys

一般来说,hash算法比较高效。
可以把这5个关键字连接成一个字符串，然后应用hash算法。
在hash值相同的情况下，遍历比较是不可避免的。

ivhb

嗯。同意楼上说的，给你个例子，来自c programming language

1. 
   
2.    /* hash:  form hash value for string s */
   
3.    unsigned hash(char *s)
   
4.    {
   
5.        unsigned hashval;
   
6. 
   
7.        for (hashval = 0; *s != '\0'; s++)
   
8.            hashval = *s + 31 * hashval;
   
9.        return hashval % HASHSIZE;
   
10.    }
    
11. 
    
12.    /* lookup:  look for s in hashtab */
    
13.    struct nlist *lookup(char *s)
    
14.    {
    
15.        struct nlist *np;
    
16. 
    
17.        for (np = hashtab[hash(s)];  np != NULL; np = np->next)
    
18.            if (strcmp(s, np->name) == 0)
    
19.                return np;     /* found */
    
20.        return NULL;           /* not found */
    
21.    }
    
22. 
    
23.    /* install:  put (name, defn) in hashtab */
    
24.    struct nlist *install(char *name, char *defn)
    
25.    {
    
26.        struct nlist *np;
    
27.        unsigned hashval;
    
28. 
    
29.        if ((np = lookup(name)) == NULL) { /* not found */
    
30.            np = (struct nlist *) malloc(sizeof(*np));
    
31.            if (np == NULL || (np->name = strdup(name)) == NULL)
    
32.                return NULL;
    
33.            hashval = hash(name);                 // 对你而言，这三句话就够了
    
34.            np->next = hashtab[hashval];      // 对你而言，这三句话就够了
    
35.            hashtab[hashval] = np;                // 对你而言，这三句话就够了
    
36.        } else       /* already there */
    
37.            free((void *) np->defn);   /*free previous defn */
    
38.        if ((np->defn = strdup(defn)) == NULL)
    
39.            return NULL;
    
40.        return np;
    
41.    }
    

复制代码

这里我想，你要的就是install这个函数吧。

galaxywar

如果用数据库的思想, 为几个字段建索引

uppet

才几万个记录，小case啦，，，

把五个字段和其它数据项一并放到一个class/struct里面，自定义一个operator<，
再用std::map或者std::set就可以了。。

RB树的时间空间效率完全应该可以满足你的要求了（在4G个数据中查找平均只要32次比较~）

nully

文件中查找，使用b树

Sorehead

2楼的hash方案我也考虑过，不过不大可取，有两个原因：一是不同的输入可能会造成同样的输出，而且是不可逆的；二是查询效率太低，比较次数太多。输出的位数太长或太短都不合适。
数据库的方式后来想想也不合适，数据存储本身就要占用空间，还要花费空间去保存索引。
5楼说的RB树也是我考虑的方案，不过还没有想好该如何组织。

谢谢楼上几位的回复。

[ 本帖最后由 Sorehead 于 2007-8-22 22:51 编辑 ]

Sorehead

　　应该是我没有把问题描述清楚，开始的时候我就想到了数据库的那种方式，有些误入歧途。
　　我需要对大量数据进行处理，每一条数据都会有5个元素，这5个元素组成一个关键字，由这个关键字来保存一些中间数据，这个过程是从读取第一条数据开始，从无到有建立起来的。最终我还需要遍历所有的由这5个元素组成的关键字，得到统计信息。
　　虽然每个元素去重后只有几万个，但5个元素组合后量还是很大的，另外这只是一个关键字，它们后面的数据是一个指针，指向一个树，那个树的数据量也是非常大的，这个树是动态的。
　　
　　目前要处理的数据量我计算过，内存还能容纳下，但是以后数据量再大的话，无法把全部数据都放入内存，计划部分数据存放到硬盘上，不过没有好的方案。由于实时性要求比较高，所以效率要求也比较高。

[ 本帖最后由 Sorehead 于 2007-8-22 22:37 编辑 ]

blackuhlan

先去吃饭,等一下来帮你想想

blackuhlan

自己维持数组A1[MAX]...A5[MAX],A1数组维持A2..5之间的偏移量,A2维持A3...5的偏移量,and so on,A5就是每个具体值的偏移量,类似于段页寻址,只不过这个是5阶的.为了减少内存开销,可以采用链表或树或hashtable或list等等等等都是细节,但这样查询效率下降,具体你自己把握.
不知道这个想法怎么样?