同样的算法,不同的数据结构,居然运行差别那么大.

Question

前不久不忙的时候写了一个程序,是对一个我们专业方面的某个空间数据的求解,当初只是为了方便,自己用的.写的乱七八糟,不过用的都是最简单的变量,篇幅也挺长,可读性很差.几乎是想到哪写到哪,哪天想起个什么小算法就加一个.
后来最近想还是把它完善一下吧,这次,从开始就规划了一下,分了几个类,实现了其的一些方法和属性.
数据结构一开始用的Hashtable,后来觉得老装箱拆箱影响效率,用的 dictionary类.key为坐标类,value为数据类.这样就非常方便的把点集写好了.
算法用的还是老算法没变(还精简了一些),程序写完还自己优化了一下.篇幅也小了,自己感觉可读性也强多了. 比较满意.运行时,突然发现问题大了.
原来乱七八糟的程序计算一个空间问题需要0.6-0.8秒,新程序需要3.7-4.5秒.试了好几个例子都几乎如此,新程序要慢的多.
通过跟踪调试,算法部分走的过程是一模一样(新程序优化后还减少了一些判断和无谓的循环),问题肯定出在了 dictionary和一些 复杂的数据结构中.真苦恼,先放放.等月底有兴趣了在说.

Answer 1

dictionary貌似是一个泛型的hashtable,应该比hash的效率要高吧…………

Answer 2

恩··一段好代码·不单单做出效果而已····也要关注它的性能·····
面向对象的三大特征，多态，继承，封装，
多态-提高代码可扩展性
继承-提高代码重用性
封装-提高代码安全性了解数据类型和一些算法。可以提高代码的效率
例如：二分查找法，杂凑查找法，递归，外部排序.....太多东西要写了~~~~~ >.<

Answer 3

也就300多个key-value.key是一个 struct 结构体,里面是 三维坐标.
value 是一个Class, 里面保存的是 点的属性和一些关联方法等.原来老程序是n个3唯数组,把Class中每个属性都开一个3维数组.查询起来直接用index定位.
新程序是把所有点保存在dictionary对照表中,对每个点的属性访问都要先 new point(x,y,z),再通过 字典找到 此 结构实例对应的 Class实例,再读写此 属性.程序好读了,开销大大的增大了

Answer 4

呵呵，是你偏心了啊，原来的程序根本就没那么多struct，你300多的dictionary不算大，但是你大量的查询都要生成struct的话，是很占内存的。单就这个三维坐标而言，我觉得你原来的设计更合理一些。

Answer 5

dictionary应该比hashtable慢吧。
可能分什么样的数据。不同的数据类型，效率应该也不一样。

Answer 6

我认为dictionary不会比HashTable慢，应该是你所说的复杂的数据结构问题

Answer 7

Hashtable与dictionay本身应该是差别不大,差别主要在于你原来的数组操作与后面的结构与类的操作

Answer 8

排除算法上的改变，你的问题应该出在那个hashtable上。用数组的index，一次访问内存就能定位到需要的数据。而用hashtable能否做到一次访存定址，就取决于你的hash的算法了。
.net默认的算法忽略对象类型，把对象当成一个字节流来hash，肯定是做不到的。
建议自己实现hash算法试试

Answer 9

还有一个问题就是这样做可能造成频繁的new/delete对象，可以用内存池来替代

Answer 10

想了一想，小小的改变，效率差别还是不小的。对数组的index，一次访问内存就能定位到需要的数据。对hasttable，
首先，你需要new一个struct，
然后调用查找函数，需要一次函数调用开销，
同时，由于你new的是struct而不是class，需要做一次内存拷贝。
之后，查找函数调用hash算法来定址，由于.net默认的算法忽略对象类型，把对象当成一个字节流来hash，所以这个过程几十次访存。
最后，垃圾收集器启动，来清理你那个struct。 可能的优化：
1、不用struct，class可以传引用
2、避免大量的new/delete，用内存池替代
3、自己实现hash算法，努力做到一次访存定位

Answer 11

最近用面向过程的方法老遭人鄙视.所以老想往OO上再靠一下.
呵呵.现在我也不想了.能高效解决问题就是perfect pragram.
Is not that so ?
呵呵.最近忙于复习英语.满嘴E话.

Answer 12

原来老程序是n个3唯数组,把Class中每个属性都开一个3维数组.查询起来直接用index定位. 
新程序是把所有点保存在dictionary对照表中,对每个点的属性访问都要先 new point(x,y,z),再通过 字典找到 此 结构实例对应的 Class实例… 
=======================================================================================
其实楼主的关键应该不是用了dictionary还是hashtable,效率不会差这么多,何况仅仅是几百个数据而已
问题应该在你的新程序中每个点都要先new point(x,y,z),通过字典找到这个Class肯定比数组中用index定位效率低很多的,其实可读性和效率原本就是一对矛盾,我建议楼主还是采用老方法的好,如果感觉条理不清楚可以调整调整for和if的位置,再加上多多注释一下

Answer 13

hashtable继承 IDictionary接口，
Dictionary也继承 IDictionary接口，而且是泛型的,key的类型相同，value的类型也相同，
如果Dictionary比hash还要慢的话，那微软推出这个类型实现是毫无意义了