数据记录快速查找算法

        在日常的算法中，查找是一个经常涉及到的话题，而如何提高查找的速度，也是很多程序员、软件研究的话题。

       先看一个例子。

       有这样一个数据类型 S ：

       学生姓名（name），性别(sex)，年龄(age)。。。，

       现在假设有这样一个需求;

       文件A、B中分别存放大量 S 的记录，需要将A、B中重复的记录去掉。

       我们用c代码来演示今天的话题：

typedef struct tagSTUDENT

{

       char *name ;

       bool bSex ;

       int age ;

       …

} S ;

       对于这样一个问题，简单的做法应该是如下：

    A 中读取记录，保存到一个链表（指针链表，数组链表都可以）ListA中，B中读取记录，保存到ListB中，然后用两重循环来实现查找：

int i ,j;

int nCountA = ListA.GetCount() ;

int nCountB = ListB.GetCount() ;

       for (i=0; i < nCountA ;i++)

       {    

              S *pA = (S*)ListA.GetAt(i) ;

              for (j=0; j< nCountB ;j++)

              {

                     S *pB = (S*)ListB.GetAt(j) ;

//比较，匹配

                     if (strcmp(pA->name, pB->name) == 0)

                     {

                            ListA.DeleteAt(i) ;

                            ListB.DeleteAt(j) ;

                            i -- ;

                            nCountB -- ;

                            nCountA-- ;

                            break ;

}

}

}

假设比较匹配使用的是strcmp类似的算法，时间复杂度为O(m)，

这样的算法，时间复杂度为 O(n1*n2*m)，空间复杂度为 O(n1)+O(n2)。

n1为ListA大小，n2为ListB大小，m为姓名长度。

下面，我们来对这个算法优化。

首先我们在这里讨论，使用指针链表好还是数组链表好。

指针链表的优点在于插入，删除快，但定位慢。

数组链表的优点在于定位块，插入，删除，很慢。

第一感觉应该是指针链表会比较好，确实，我们在匹配过程中可以找到一个重复数据就删除，这样确实会比较方便。

其实，在这个地方，使用数组链表优势会更大。

我们分析一下指针链表和数组链表插入的原理。

链表指针每次插入的时候，直接在尾指针处插入一个新数据，时间复杂度为O(1)，不讨论其他细微的开销。

数组插入缓慢的原因，是因为，如果插入的数据不是最后一个，就需要把插入点之后的数据全部向后移动一个位置；删除也是一样的，时间复杂度为O（n）。但是，如果插入的数据是插入到末尾的话，那么这种弊端就不存在。相反，插入，删除，还会变的很快。这就如同链表的尾指针一样，可以达到O（1）时间内完成。

分析了数组的插入原理，我们再对上面查找的过程做修改。在每次查找到重复数据的时候，不要立刻删除，而先做个标记。当查找结束后，再将没有标记的数据复制到另外一个数组中，这样就可以避开数组的缺点，而发挥数组的长处。C代码演示如下

typedef struct tagSTUDENT

{

       char *name ;

       bool bSex ;

       int age ;

       bool bRepeat;// 增加一个标记位

       …

} S ;

int i ,j;

int nCountA = ListA.GetCount() ;

int nCountB = ListB.GetCount() ;

       for (i=0; i < nCountA ;i++)

       {    

              S *pA = (S*)ListA.GetAt(i) ;

              if (!pA-> bRepeat)

{

                     for (j=0; j< nCountB ;j++)

                     {

                            S *pB = (S*)ListB.GetAt(j) ;

                            if (!pB-> bRepeat)

{

//比较，匹配

                                   if (strcmp(pA->name, pB->name) == 0)

                                   {

                                          pA->bRepeat = true ;

                                          pB->bRepeat = true ;

                                          break ;

                                   }

}

}

}

}

有人可能就会说了，使用链表一样也可以做标记，不删除啊，为什么不用链表呢？是的，可以使用链表，但是链表的操作是对指针的操作，定位操作，最快也需要移动一次指针（p = p->next），而对于数组，只需要 i++，这两个操作的速度还是有差别的。（当然，差别不大，但程序员不是经常为一个指令周期而疯狂吗？）

到这里，我们仅是对数据结构的设计，优化的重点就是暂时不删除重复数据，而做标记，等处理完毕后，再统一做处理。这个算法会增加空间复杂度，由O（n）变为O(2*n)。

那么还有没有办法对这样的算法进行更进一步的优化呢？

有的，这也就是我今天要描述的重点。

可以想象，在上面的算法中，有很多重复的步骤。例如，每次ListA中取一个数据，要去B中查找，都需要遍历B中一次，这就导致B中的操作太过频繁。最终算法缓慢。那么现在我们就要优化在B中遍历这一步。

我们这里是以学生姓名做为匹配关键字，为简单起见，假设数据A中的所有学生姓名不重复，数据B也满足这个条件，后面我们再考虑复杂一点的情况。

对于每个学生姓名，既然唯一，那么就可以使用一个数值来代表，例如，1代表“张三”，2代表“李四”，那么如果A中有“张三”，要在B中查找有无“张三”，就只需要看B中有没有1。有人会说，这样做有什么意义？意义有两点：

1）  使用数值（DWORD）查找，会比字符串查找速度快。因为字符串查找时间复杂度是O(n)，而数值匹配，时间复杂度为O(1)

2）  理解这个思路，对于后面的优化方法才能更加容易接受。

那么如何将“张三”，“李四”对应到数值1，2呢？

使用CRC(循环冗余校验)来实现这种对应关系。假设“张三”的Hex值为“d5 c5 c8 fd”，那么就可以定义数值DWORD dwIndex = d5 + c5 + c8 + fd，这就是CRC值。当然了，这个值如何计算，完全可以根据需要来，比如你觉得加法算出的CRC值重复性大，那么可以使用乘法，移位等算法，来使数值比较分散，降低重复的几率。但这样还是没有办法避免重复，所以，每次找到匹配数值后，还应该继续检查学生姓名是否匹配。算法描述就是：

typedef struct tagSTUDENT

{

       unsigned long ulIndex ;// 在数据A、B中读取的时候填充

       char *name ;

       bool bSex ;

       int age ;

       bool bRepeat;// 增加一个标记位

       …

} S ;

int i ,j;

int nCountA = ListA.GetCount() ;

int nCountB = ListB.GetCount() ;

       for (i=0; i < nCountA ;i++)

       {    

              S *pA = (S*)ListA.GetAt(i) ;

              if (!pA-> bRepeat)

{

                     for (j=0; j< nCountB ;j++)

                     {

                            S *pB = (S*)ListB.GetAt(j) ;

                            if (!pB-> bRepeat)

{

//比较，匹配

                                   if (pA->ulIndex == pB->ulIndex)

                                   {

                                          pA->bRepeat = true ;

                                          pB->bRepeat = true ;

                                          break ;

                                   }

}

}

}

}

这样一来，算法就可以优化到O(n1*n2)了。

到这一步，估计不少人已经看出端倪了。不错，接下来，我们就要使用散列表（HashTable）来优化数据存储。

我们在上面说过，读取数据的时候保存到链表或者数组中，而现在，我们要保存到散列表中，而散列表的索引（index）就是我们上面说过的，根据学生姓名算出来的数值。散列表的大小可以根据情况定义。散列表的数据结构可以设计成散列链表，散列链表的优势在于：

1）  支持的数据可以无线扩大（链表可以存储无线大的）。

2）  对于碰撞的算法简单快速。

typedef struct tagSTUDENT

{

       unsigned long ulIndex ;// 在数据A、B中读取的时候填充

       char *name ;

       bool bSex ;

       int age ;

       bool bRepeat;// 增加一个标记位

       …

} S ;

iterator itA = HashA.begin() ;

for (; itA != itA.end(); ++itA)

{

S *pA = (S *)itA ;

S *pB = HashB.find(pA->ulIndex) ;

if (pB)

{

                     pA->bRepeat = true ;

                     pB->bRepeat = true ;

}

}

我们来看看现在的时间复杂度。假设散列表大小为M，每次匹配的算法复杂度为

O( n/M),完成整个操作的算法复杂度为 O(n1*n2/M)。

回头再看一下我们遗留的一个问题，如果学生姓名有重复，如何解决？

我们可以定义散列链表，如果有重复的数据，就放到链表中，所以匹配的时候，需要

在找到index数值后，然后再进一步使用字符串匹配找到符合的学生记录。

        但是，需要知道的是，如果要支持模糊匹配，这种算法就没有办法进行优化。

但是，如果数据本身可以提取特征值，那么模糊匹配也可以支持。具体情况要根据实际的情况去看了。

        针对链表，散列表的数据结构，可以自己设计，也可以使用STL，但我觉得，自己设计的数据结构，使用起来更加方便。速度慢？呵呵，STL的也没有使用特殊的算法，也没有使用汇编，自己设计的为什么就会慢呢？如果慢，那只能说明你设计的数据结构有问题了，呵呵。

（本文为原创，转载请注明出处，作者。）

最后

以上就是幸福铃铛为你收集整理的数据记录快速查找算法的全部内容，希望文章能够帮你解决数据记录快速查找算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。