各位兄弟啊,本人在编的程序碰到了个麻烦,请大家讨论一下。
问题:
有1000万个无序带重复node,每个node占据100B,需要逐个加入到某结构中,要求加入时能去掉重复结点,并且运行时间尽量要在10分钟左右完成。
怎么解决呢?
我采用了以下方法
1:采用无序队列存放,每次加入一结点时与前面以有结点比较是否存在,不存在则加入队列。
(!!!需要比较的次数太多了,可能会计算1小时都得不到结果!!!)
2:采用二叉搜索树,刚开始时速度是快多了,但结点多了后1000万*100B=1000M,内存不够用了,机器瘫痪了。
3:
4:
请各位大虾帮忙提个意见吧!谢谢了!
问题:
有1000万个无序带重复node,每个node占据100B,需要逐个加入到某结构中,要求加入时能去掉重复结点,并且运行时间尽量要在10分钟左右完成。
怎么解决呢?
我采用了以下方法
1:采用无序队列存放,每次加入一结点时与前面以有结点比较是否存在,不存在则加入队列。
(!!!需要比较的次数太多了,可能会计算1小时都得不到结果!!!)
2:采用二叉搜索树,刚开始时速度是快多了,但结点多了后1000万*100B=1000M,内存不够用了,机器瘫痪了。
3:
4:
请各位大虾帮忙提个意见吧!谢谢了!
解决方案 »
- 关于resource.h无法使用的问题
- OCX定义参数,用什么类型可以在JS调用的时候看到?
- 请问如何按位比较
- 如何得到当前控件窗口的指针
- 改变对话框的背景色(变为白色)后, 使用 Static Text控件(Radio Button这类控件也一样 )时 文字的背景为那种灰色 该怎么该 ?(例如
- 如何做一个窗体,固定占据屏幕顶端一行,其它窗体在最大化时也不能进入这个区域?
- 有几种"窗口子类化"的创建方式?(看过<<Window程序设计>>的一定进来看看);
- 关于在VC++中PivotTable的应用
- 绘制数据曲线
- display(),memset(),这是库函数吗?
- vc里怎么得到手形光标?
- 设置静态文本框时出的一点小的问题
原来以前学过啊~~
都忘光光了
为什么要用无序的呢
这样比较会慢很多啊
______________________________________________________________________________
我这问题中结点是逐个产生并无序的,这是条件无法改变。
如果每次加入一个点后就排成有序队列的话,在查找时是可以快多(譬如可采用二分查找或快速查找法),但是每插入一个结点时都需要调整,时间上肯定得不偿失。
肯定是不能全放到内存里了
又学到了
看看
B-树 是麻玩意~~~
——————————————————————————————————
找本计算机本科的《数据结构》,一般都有介绍
_______________________________________________________________________
A Gread Idea!
根据你的提示,我想可以采用以下方法进行处理会比较快速并容易实现。
1:将1~1000万个node按大小分成10000段,每段放在一个相应的文件里。
2:需新加入一个node时先计算出该node应存放的文件,再在该文件的node里比较是否存在,不存在则插入;因为每个文件最多只放置10000个node,所以速度应该会大大提高!