首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 关于两个表比较并找出不同项的算法？？ [已结帖,结帖人:songcheng]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • songcheng
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 结帖率：
    发表于：2008-08-08 02:04:50 楼主
    其实这个问题是Excel VBA编程遇见的问题，不过为了寻求更加高效的算法，我来请教各位高手了。
    [size=4][color=blue]问题背景：
    1、我有两张表，表A中有113个整型数据，表B中有178个整型数据。已知表A的113个数据是表B的子集，即178个数据中完全包含了113个数据。我要找出A表和B表中不同的数据项。

    2、还是表A和表B，A有113个数据，B有178个数据。A表和B表中的数据有交集，但不完全相同。现要筛选出A表和B表中不同的数据。请问如何做？

    关于问题1，我的想法是将B中的178个数据，每个在A表中进行完全的对比，需要的对比次数为：178*113 = 20114次。
    关于问题2，我的想法是对A表中的每个数据都依次在B表中对比，查看是否有相同的，相同即输出，B表重复A表的操作。这样的话，需要对比的次数为：2*113*178 = 40228次。

    关于以上两种情况，请问大家有更好的改进算法吗？谢谢了！

    [/color][/size]
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhaolinger2
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-08 08:55:291楼 得分:0
    第二个题，要是把A\B的数据都读出来，拿A与B比较，如果有相同的就把A\B中的相同项删掉，剩下的就是各自不同的数据了。这样只需要比较一遍20114次
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      2

      2
    发表于：2008-08-08 09:40:582楼 得分:0
    除非你是大量的调用,或者你是想借用做研究,不然就没任何优化的必要;

    这么小的规模,才几万次的整数比较操作,也太小看计算机了;

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • youxia000
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-08 10:24:013楼 得分:10
    哈希散列数少的那组，然后遍历B去散列表找有没有相等的数

    第二个问题可以给A，B都加上标志位，找到过就为1，最后统计为0的数
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • eric_0206
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-08 13:21:264楼 得分:10
    如果两张表都只是作为数的集合，也就是在表中数据无序的情况下，这样的查找几乎就等于是遍历搜索了。作为数据库中的表，我们通常会为它建立索引来提高查找效率，也就相当于是等于排序。所以，按照这样的思想，我们可以将两个表都先按照升序或者降序排序，然后将一个表中的元素逐个在另一个表中查找，如果找到或者当前元素比自己大，就可确认是存在相同或者不存在，如此一来，下一个元素可接着此处的断点向下查找。这样一来，时间复杂度可降到线性阶，加上排序的时间复杂度，算法时间复杂度应该为nlog（n）的。

    似乎两个问题都适用，不知道有没有问题。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 5

      2
    发表于：2008-08-08 13:24:205楼 得分:0
    将A和B中的数据排序之后，用类似归并的方式进行处理：
    初始化两个指针分别指向A和B的头部，然后比较两个指针位置的数据：
        如果a=b，那么说明该元素属于A和B的交集，二个指针同时后移；
        如果a <b，说明a元素只在A中有，A指针后移；
        如果a>b，说明b元素只在B中有，B指针后移。

    如果象你说的两个表中都只有一百多数据，那确实没有什么优化的必要。

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • songcheng
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-08 15:13:476楼 得分:0
    我这个只是一个示例，针对这一类情况的提问，所以，数据量将会很大的。远远超过100多个
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jiju8484
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-08 16:25:207楼 得分:0
    引用楼主 songcheng 的帖子:
    其实这个问题是Excel VBA编程遇见的问题，不过为了寻求更加高效的算法，我来请教各位高手了。
    [size=4][color=blue]问题背景：
    1、我有两张表，表A中有113个整型数据，表B中有178个整型数据。已知表A的113个数据是表B的子集，即178个数据中完全包含了113个数据。我要找出A表和B表中不同的数据项。

    2、还是表A和表B，A有113个数据，B有178个数据。A表和B表中的数据有交集，但不完全相同。现要筛选出A表和B表中不同的数据。请…


    对AB表分别hash；

    如果AB表内部数据互译，可以放在一起，排序可以找出来
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhulinpptor
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-19 16:04:118楼 得分:0
    2 种方法 ：
    第一种方法 ；
    1 先排序表A  ,
    2 表B中的元素去排序好的表A中进行折半查找
    第二种方法；
    对AB表分别hash
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved