文本快速检索方法，速度敢与 Dictionary 争雄！解决思路

文本快速检索方法，速度敢与 Dictionary 争雄！
我不想发表什么 Bog ..........
权且当成在这儿灌水罢..........


　　发这个贴子，是源于这个贴子 如何使用CopyMemory删除数组中重复的元素



　　首先声明几点：
　　①我的这个代码还很不完善，尤其是对数量非常大的文本创建索引时，效率比较低。主要是创建索引时，移动的数据太多了。当然，我也有解
决办法，用那个方法耗时与数据量成正比关系（现在的几乎是平方关系增长），只是多占用点内存而已。只不过觉得目前没必要去搞它了。
　　②我不是为了贬低 Collection 和 Dictionary ，它们也有各自的优势.........至少，我也觉得 Dictionary 还可以........
　　③用事实证明某些错误的看法，不要误导不明真相的人（虽然我也是算个不明真相的）。
　　④我写的那个 Filter 类，是纯粹的VB代码，完全是按 VB 6.0 的一般功能实现的，没有用什么‘内嵌汇编’等手段来达到XX目的，（只有唯
一的一个API函数：Declare Sub CopyMemory，不算违规吧！）


　　前几天按自己的想法，写了段代码试了一下，确实不尽人意。但也并非一无是处。
　　在字符串数量不算太多，而字符串比较长（或很长）时，我的方法会有很大的优势。

　　在那个帖子中，我没有贴代码（因为自己觉得不太完美，也不知道对楼主是否适用），只简单的发表了点看法而已~~~~~~

　　也许有人会说，‘你的图片是ps的，回贴也只是你的片面之辞。谁知道是不是那么回事呀.......’

　　不错！确实图片是ps的........
　　我在这个论坛贴出的图片都是我自己ps的（只有一张搞笑图片不是，我传在别的地方了，没在CSDN相册中 ^_^），弄图片，除了ps，还有更好的
选择么？我在那个帖子中贴出的结果，是实实在在的运行结果呀~~~~~~~

　　这些就不说了，后面我会给个链接，任何人都可以下载来试试看。
　　你可以在自己的机上了看到相应的代码、运行后看到实实在在的结果！


　　我在那个贴子的 74F 中说了“Dictionary 也不是最快的！”，我可以让你亲眼看到，我的方法也有远远胜过 Dictionary 的时候！


　　有某高人说“……如果是dic.Exists(key)是循环,我觉得key的存在就没意义了...”。
　　对此，我不敢苟同，我认为：即使它不是直接的使用循环，也是某种数据结构的遍历（其实质和循环有多大区别吗？）；Key的存在是必须的，如
果它不用某种方式来使用它的Key，它就不具备速度和效率；但是，它的‘Key’仅仅是个术语而已，只能说明这个具有唯一性的特征，不能说明什么
别的问题，并不因为它称之为“Key”就有无限的优越性！

　　还有某高人在 47F 用那样的代码来证明“dic.Exists(key) 不是用的循环”，我只能说：以这样的依据得出这种结论的人，真是太无知了~~~~~~

　　更有某些世外高人，说什么“dic.Exists(a(i))…………用Hash树，计算出Hash值，直接定位，如果没定位到就说明不存在。”
　　我KAO！要是有直接定位的方法，那速度还不快得惊人，岂不是天下无敌了！谁能够比“直接定位”来得快呀！我就不相信‘Hash值’有那么神奇，
对变化无穷的文本内容还能够进行什么“直接定位”！我的检索方法，在索引表中还有查找、比较过程，还是用了一堆循环，要是它能直接定位了，不
比我的方法快个几十、几百倍啊？可事实并非如此，如果字符串较长、源数据量比较大的话，我的方法的检索速度不知会比 Dictionary 对象快多少倍！
（对于在‘海量’级的数据中进行检索，更会突显我的方法无比优越，当然，得先完成索引的创建）



　　不说了，说多了没意思，有兴趣的下载来看看............
　　这个代码与我在那个帖子中的没多大的区别，只是为了便于对比，把 57F 中 Tiger_Zhao（VB老鸟）的代码搬过来用了， Collection 和 Dictionary
的使用方法，说白了就是照抄的。然后，我把原来生成源数据的方法修改了一下，生成速度快了几倍。


　　我一直没有试过‘巨量’数据的，5W数据的只试过四、五次，一般都是2000至15000的。有兴趣的、机子配置好的朋友，可以试一下10W甚至100W数据
量的结果，试了后贴出来让大家看一下 ^_^
　　我那个“检索速度比较”是最后加上去的，就是想和 Dictionary 比划比划，究竟谁的检索速度快~~~~~~~
　　为了节约点生成数据的时间，我用了生成少量数据，增加循环来达到检索多次的效果。可以很负责任的说：你用一条 String 让 objFilt 检索 10万
次，和用 10万 条不同的 String 让 objFilt 各检索一次，是没有本质区别的，我的检索方法不会说“哟，这个字符串刚让我检索过嘛，不是找到了吗，
我可以即刻返回它的下标是xxxxx”。至于 Dictionary ，由它吧，我无所谓............

　　注意一下运行时，先要“生成数据”，然后呢，要进行“检索速度比较”，必须要先把“Dictionary”和“我的方法”各点一次，让我的创建好索引，
Dictionary 弄好它的“Key”.............. 至于 Collection ，随你的便吧~~~~~~~~



[解决办法]
嘿,支持代码PK.
[解决办法]
顶 ~~~
[解决办法]
顶！顶！顶！
[解决办法]

有点火气。

是否能说说你算法的思路？

多一句嘴，绝不是PK。
如果仅仅谈理论可能性（例如内存空间无限大），字符串也是可以用稀疏表直接寻址的。别忘了，在计算机中，任何信息都是数字。其实，无非是问题复杂度高的场合，是否有实际可能来实现，例如是否有足够的内存空间，以及引发磁盘交换之后，寻址的优势是否存在等等。

数据快速检索算法，也是计算机科学的一门学问。不妨查查文献，大概至少可以检索到几十万篇论文。能找到综述性的著作就更好了。直接 PK 代码，未必说明算法优劣，也可能是代码编写技巧的问题。而且，任何算法都有适用的场合。要找到任何情况下都最有的算法，似乎不大可能。

没有深入研究过这类问题，瞎说的。

[解决办法]
“我不想发表什么 Bog .......... ”

BOG是啥东东啊？
[解决办法]
支持讨论，欢迎代码PK！
[解决办法]
OK!
[解决办法]
哎~~~~，，，观战！
[解决办法]

探讨

引用:

有点火气。

是否能说说你算法的思路？

多一句嘴，绝不是PK。
如果仅仅谈理论可能性（例如内存空间无限大），字符串也是可以用稀疏表直接寻址的。别忘了，在计算机中，任何信息都是数字。其实，无非是问题复杂度高的场合，是否有实际可能来实现，例如是否有足够的内存空间，以及引发磁盘交换之后，寻址的优势是否存在等等。

数据快速检索算法，也是计算机科学的一门学问。不妨查查文献，大概至少可以检索到几十万…


内存空间总是有限的，具体的实现不能作假设，要基于客观事实。

我的方法只是把源字符串转换成了个索引表，并记录对应的下标。
检索某字符串是否存在于这个数组中，按索引与对应位置的源串比较，相同存在，不同就不存在。

我的索引表大小只跟源数据的项目数有关，跟源数据的复杂度无关。
比如10000条源数据：
可能要只占用60K左右（VB中，每个字符串只有1个字符时，加上数组本身的）；
也可能要占用20M左右（每个字符串有1000个左右字符时），我的表始终占用不到100K。

至于你说的‘稀疏表’，字符串的组合是无穷的，你的“稀疏表”准备用多大的空间来贮存？

[解决办法]
不错
[解决办法]
我晕，要注意用语文明
[解决办法]

这里是csdn啊........误人子弟真不好,
你大概是学生吧对计算机还是保持谦卑

c#写的装有vs2005的可以试试，100W个GUID做key存文本里要40M，hash Dictionary
using System;
using System.Collections.Generic;
using System.IO;
using System.Diagnostics;

class Program
{
static void Main(string[] args)
{
int num = 100 * 10000;
Dictionary<string, int> dict = new Dictionary<string, int>(100 * 10000);

FileStream fs = new FileStream("dict.txt", FileMode.Create);
StreamWriter sw = new StreamWriter(fs);
for (int i = 0; i < num; i++)
{
string s = System.Guid.NewGuid().ToString();
dict.Add(s, i);
sw.WriteLine(s);
}
sw.Close();
fs.Close();

while (true)
{
Console.Write("输入查找的key：");
string ke = Console.ReadLine();
watchStart();
if (dict.ContainsKey(ke))
Console.WriteLine("找到");
else
Console.WriteLine("不存在该key");
Console.WriteLine("用时:" + ((float)watchStop() / 10000.0).ToString() + "毫秒");
}

}

/// <summary>
/// .net刻度为单位,1毫秒=10000刻度
/// </summary>
private static Stopwatch _stopwatch = new Stopwatch();

public static void watchStart()
{
_stopwatch.Start();
}

public static long watchStop()
{
_stopwatch.Stop();
long temp = _stopwatch.ElapsedTicks;
_stopwatch.Reset();
return temp;
}

}
[解决办法]
周末无事，写了一个用哈希函数的

VB code

'类模块 class1Private Const BUFFERSIZE As Long = 100000Private mIndex(0 To BUFFERSIZE - 1) As LongPrivate nCurIndex As LongPrivate Type DATA    sKey As String    nNext As LongEnd TypePrivate mStrData() As DATAPrivate Sub Class_Initialize()    Dim i As Long    ReDim mStrData(1 To BUFFERSIZE) As DATA    For i = 0 To BUFFERSIZE - 1        mIndex(i) = -1        mStrData(i + 1).nNext = 0    Next    nCurIndex = 1End SubPublic Sub ClearAll()    Call Class_InitializeEnd SubPublic Function Add(key As String) As Boolean    Dim hash As Long    Dim n As Long, m As Long        hash = CalcHash(key)    If mIndex(hash) = -1 Then        mIndex(hash) = nCurIndex        mStrData(nCurIndex).sKey = key        mStrData(nCurIndex).nNext = 0    Else        n = mIndex(hash)        Do            m = n            If StrComp(mStrData(n).sKey, key) = 0 Then                Add = False                Exit Function            End If            n = mStrData(n).nNext        Loop While n <> 0        mStrData(m).nNext = nCurIndex        mStrData(nCurIndex).sKey = key        mStrData(nCurIndex).nNext = 0    End If    nCurIndex = nCurIndex + 1    Add = TrueEnd FunctionPublic Function Exists(key As String) As Boolean    Dim hash As Long    Dim n As Long         hash = CalcHash(key)    If mIndex(hash) <> -1 Then        n = mIndex(hash)        Do            If StrComp(mStrData(n).sKey, key) = 0 Then                Exists = True                Exit Function            End If            n = mStrData(n).nNext        Loop While n <> 0    End If    Exists = FalseEnd FunctionPrivate Function CalcHash(sData As String) As Long    Dim byt() As Byte    Dim hash As Long, x As Long    Dim i As Long, nLen As Long        nLen = Len(sData)    If nLen > 15 Then        nLen = 15    End If        byt = Left(sData, nLen)        nLen = nLen * 2    For i = 0 To nLen - 1 Step 2        hash = hash And &H7FFFFFF        hash = hash * 16 + byt(i)        x = hash And &HF0000000        If x <> 0 Then            hash = hash Xor (x \ &HFFFFFF)            hash = hash Xor x        End If    Next        CalcHash = hash And &HFFFFFFF    CalcHash = CalcHash Mod BUFFERSIZEEnd Function 
 
[解决办法]
探讨

To 70F:
　　还有，你看一下蚜虫提供的用 Hash 原理的实现，循环是乎是不可少的。
 

 

查看更多 下一篇