超难，如何用最快的速度查出15项相同的数据记录！

imkeke

{:soso_e106:}看着觉着很神奇，我想学。。。

szcougar

yangyangzhifeng 发表于 2013-4-25 12:34
略微提速

这不错 谢谢！！！！！

hezongzhong

做科研论文好像不需要这样干娄

香川群子

lee1892 发表于 2013-4-25 22:02
我很期待～

速度果然进入了秒级别……

Data Compare Check.rar (368.41 KB, 下载次数: 65)

2013-5-2 00:18 上传

点击文件名下载附件

附件已有更新……增加了任意检查个数的选项。请已经下载的同学注意。


算法要点：
1. 读取原始数据后，用字典法整理为长整形序号： Dic to Long：  大约0.8秒
2. 按字典项个数计算循环比对次数以后，从小到大排序找到比对次数最少的前几列： Sort：  0秒
    （循环比对次数=k*(K+1)/2  → 貌似Lee1892直接用了平方计算虽然没有产生实际差别但有点不讲理）
3. 对前几列用数组法归并具有相同项的行序号，以便缩小检查范围： Filter: 0.2秒
4. 遍历2 to m -1 进行检查，仅检查前几列中有相同字典项的行数……（这个就是我前面忽然想起来的算法精髓）
    For...Next...Compare Check： 仅需2-3秒  
   （实际检查716,145行）而全循环检查需要比对=Σ（1-9585）=45,940,905行次，相差64倍。
    但因为预先决定比对行位置也需要大量计算，所以计算效率也损失很大的，实际速度差就没有几十倍那么大了。
5. 输出结果： Output： 大约0.02秒

因此在我的计算机上合计耗时 2-3秒左右，如果机器好，或许可以进入2秒。



补充：
Lee1892的结构算法代码构造稍复杂一些，一下子是看不懂的。
但当我自己的算法代码实现以后，再去看一下，发现原理几乎是相同的。

但显然Lee1892的算法速度更快。
有趣的是，我的检查比对次数明显比Lee1892的算法少，相差大约10倍。
但我的过程耗时要大很多，所以最后还是他的代码速度更快一些。

陈国华

香川群子 发表于 2013-4-27 14:12
速度果然进入了秒级别……

佩服，测试时间基本在2秒出头，Lee1892的为3秒出头，都很厉害！

lee1892

香川群子 发表于 2013-4-27 14:12
速度果然进入了秒级别……

在我之前的代码上进行了如下改进，附件： 水样监测_使用数据结构加速(130502) by Lee1892.rar (355.02 KB, 下载次数: 67)

2013-5-2 10:25 上传

点击文件名下载附件

：
1、增加了一个arrCompared布尔型数组，二维，直接用数据行行号表达二者是否进行过比对
2、在对第5个项目（按所需对比次数升序）检查时，如果是未对比过的两行（说明前4个项目不同），则检查第6个项目是否相同，否、则直接排除

这样改进后，进行19项对比的次数仅余22万+次，运行时间由2秒+加速至1秒+

原采用树形数据结构的方法	此贴改进后
读取原始数据用时：0.05秒 初始化及整理数据用时：0.78秒 查找对比用时：1.24秒 结果排序用时：0.00秒 清空缓存用时：0.02秒 输出至表格用时：0.03秒 合计用时：2.1秒 复制代码	读取原始数据用时：0.05秒 初始化及整理数据用时：0.89秒 查找对比用时：0.39秒 结果排序用时：0.00秒 清空缓存用时：0.02秒 输出至表格用时：0.03秒 合计用时：1.4秒 复制代码

可以看到查找对比用时大幅降低，而初始化时间由于要申请9586*9586个布尔元素的数组空间增加的较多。

至于香川的方法，由于其逻辑上并未解释清楚，而代码的变量名起得实在是看得我云山雾罩，根本没法弄明白是干什么的，所以也没法通过代码弄明白。但基于其之前的说明，我很怀疑其在真实数据情况下（或言不同的数据特点，数据十分分散-重复度低，数据相对集中-重复度高），其执行速度的期待值是什么样的情况。

楼上的机器大概结构和我用的不一样啊~~

我实在是蛮期待有比我的方法更快的方式出现的，呵呵~
话说楼主也没见给些花呀~~~嗯，这行要加红加粗加下划线 {:soso_e144:}

香川群子

重新整理了一下，与【标准全循环比较算法代码】做了相互比较。

分别比较相同个数= 19、18、17、16、15、14、13、12、11 时3种算法的速度。

当检查相同个数=11时，显然直接全循环比较更快。因为所谓结构算法也将沦为全数遍历比对检查而失去优势。


……
进一步，如果检查相同个数比11更小时，比对方法要做180度改变，因此没必要检查比较速度了。

香川群子

lee1892 发表于 2013-5-2 10:36
在我之前的代码上进行了如下改进，附件：：
1、增加了一个arrCompared布尔型数组，二维，直接用数据行行 ...

楼主提供的9586行数据，应该是比较符合实际的数据了。

不管怎么说，我的代码，比全循环比对还是快了不少。

至于你说代码看不懂……如果不进行注释或具体的说明，看不懂这很正常。
你的代码我也不是一下子就能看懂的。
即使水平比我高的，在没有详细注释的情况下估计也不可能一下子看懂。


由于我的代码算法上并不比你的代码更有优势，所以我也不准备详细说明了（估计你也没有兴趣吧）





换了水平

香川群子

lee1892 发表于 2013-5-2 10:36
在我之前的代码上进行了如下改进，附件：：
1、增加了一个arrCompared布尔型数组，二维，直接用数据行行 ...

另外，我的代码虽然比不上你，但和你改进之前的版本比较，差异并非很显著。

大致在5%-20%之间，甚至在检查相同个数= 16、17、18、19 时，还比你改进之前的版本稍快。

…………
实际上，原因如下：
由于算法思路差异，当数据结构为：
所要检查的前n列差异明显时，我的代码速度会比你的更快一些。

而当所要检查的前n列，或者所有数据的分布都是相同项目更多时，我的代码速度比你的要慢。

这个情况确实存在。



…………
比如举一个极端的例子：
把第1列的序号值（每一行的值都不相同）复制后覆盖粘贴到19列中的任意其中1列，比如就覆盖第2列（数据的第1列）好了。
然后运行代码，则我的算法速度就已经超过你的代码了。

从这一点上看。我的算法确实和你的不是一样的。

仅仅当19列中的第5-19列甚至全部19列的值都完全相同时，我的算法才会变得很慢……直接相当于全部需要遍历了。

除了这样的极端情况，我的代码比起全循环遍历来说，肯定要好很多。

suwenkai

中午没有时间看，晚上再下载来看一下学习。。。