这是一个创建于 4347 天前的主题,其中的信息可能已经有所发展或是发生改变。
有个特别大的文件,上千万行,1G多,
格式是这样的,
0,aaaa,1
1,aaaa,2
2,bbbb,1
3,bbbb,2
..
..
..
第一列是不重复的,第二列是字符串,有重复的,第三列是递增的数字,可能不连续,第二列相同的行第三列是不同的,但是第二列不同的数据第三列有可能相同
现在的问题是给出第二列和第三列,找出第一列,
这个数据量比较大,不能用数据库
问有什么比较好的算法?谢谢。
/************************************************************************/
他题目没说清,打如果是需要频繁的增删改查,
我的想法是,先压缩数据,大概是
struct data{
char *str;//字符串
vector<int> pos;//第一列的值
};
于是上面的数据就压缩成两条
struct data data1={"aaaa",{0,1}};
struct data data2={"bbbb",{2,3}};
之后申请指针数组
struct data *ptrs[];
之后建立一个映射f(n)=m,n是第二列字符串,得到的m是偏移量,把上面的数据指针填到ptrs[m]里,如果不能保证f(n)映射一一对应,那就把struct data改成
struct data2{
char *str;//字符串
vector<int> pos;//第一列的值
struct data2 *next;//下一个相同映射值的指针
};
我想问下,
1,如果在实际应用中,我说的这种方法可行不
2,如果有内存限制,这个问题该怎么办(我只能想到遍历。。。)
2 条回复 • 1970-01-01 08:00:00 +08:00
|
|
1
wog 2013-02-02 22:59:22 +08:00
|
|
|
2
best1a 2013-02-02 23:18:37 +08:00
标题不是说了是查么,没必要考虑增删改的情况 这种题目看起来好像面试题。。。一般做法是,根据第二或第三个字段做个hash啥的,分到N个文件中,如果内存限制比较死,那N可以弄大点 然后再各种方法做小范围的查找。。。
|