none
两个数据量上20W的集合(LIST<String>),做比较,如何提高效率? RRS feed

  • 问题

  • A 集合与 B 集合都是有上几十W的数据,如果现在要判断 A 集合里面的数据在包含哪些 B 中的数据。

    如果直接做双 FOR 的循环通过 IndexOf 方式查半小时也查不出来。

    有什么别好的集合或者别的方式可供大数据量使用?

    不是比较两个集合的元素有那些是否相等,而是比较是否是否A中的元素有哪些是包含了B中的元素的。

    Sherrys
    • 已移动 Sheng Jiang 蒋晟Moderator 2009年3月25日 20:30 .Net基础类库问题 (从 Visual C# 移动到 .NET Framework 一般性问题讨论区)
    2009年3月25日 3:37

答案

  • 如果都是字符串  或者唯一的key 都是字符串  就比较好比较了

    可以把数据量比较大的一个 生成前缀树 然后进行比较

    http://cnblogs.com/Diryboy/archive/2009/03/18/csharptrie.html



    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 4:33
    版主
  • 建立树的时候   每个节点保存一个 list<int>  保存在初始数组中match的index 就可以了
    list<int>count >1 就是有match

    很多变通的办法


    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 8:00
    版主
  • 因为要在A中查是否包含B,得先给A做索引,然后查起来才快。
    如果是多CPU的话,可以把B分块,多线程查找。

    好好学习,天天向上。
    2009年3月26日 1:52

全部回复

  •  如果是有序的  可以用 array.binarysearch 二分法查找





    最好你能把代码贴出来  我们帮你优化下
    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 3:46
    版主
  •  对了 二分法适用场合   最好还是用 Linklist<T>  或者 sortedlist <T>
    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 3:52
    版主
  • 代码比较简单,就是写的两个 LIST 的双 FOR 循环

    比如 listA 里面存着几十W的中文与英文名称 例如 张三 李四 王二麻子,然后 listB 里面存的是几十W的匹配条件 例如 张 李 黄 andrew 等等。

    然后需要找出 listA 中有哪些人名是包含 listB 里面的条件的。

    因为数据量都比较大,如果做两个 FOR 循环 就是上百亿的搜索了,这样不是很合理,不知道有什么合理的方式,谢谢。

    Sherrys
    2009年3月25日 3:52
  • 如果都是字符串  或者唯一的key 都是字符串  就比较好比较了

    可以把数据量比较大的一个 生成前缀树 然后进行比较

    http://cnblogs.com/Diryboy/archive/2009/03/18/csharptrie.html



    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 4:33
    版主
  • 这种前缀树实现的是 Contain 的比较方式,也就是完全匹配。而我需要的包含 IndexOf 的方式,而且不是同一集合的遍历,是两个集合对笛卡尔乘积似的遍历,寻找A集合中 IndexOf B 集合里面的元素 != -1 的情况。

    这样前缀树的方式好像不太能用到,请教使用方式。

    Sherrys
    2009年3月25日 6:42
  • 建立树的时候   每个节点保存一个 list<int>  保存在初始数组中match的index 就可以了
    list<int>count >1 就是有match

    很多变通的办法


    热烈庆祝进入4星活跃用户队伍
    有原则的回答问题: 不懂的不去装懂,别人回答得很完整的,没有需要补充的不去蹭分。
    2009年3月25日 8:00
    版主
  • 你好,我不是很明白你的意思。。。能否给个简单的例子?
    Sherrys
    2009年3月25日 13:15
  • 数据导入到数据库再比较


    http://feiyun0112.cnblogs.com/
    2009年3月26日 0:49
    版主
  • feiyun0112 说:

    数据导入到数据库再比较


    http://feiyun0112.cnblogs.com/


    若是这样,我就不会来问这个问题了。
    Sherrys
    2009年3月26日 0:50
  • 因为要在A中查是否包含B,得先给A做索引,然后查起来才快。
    如果是多CPU的话,可以把B分块,多线程查找。

    好好学习,天天向上。
    2009年3月26日 1:52
  • Eri.cn 说:

    因为要在A中查是否包含B,得先给A做索引,然后查起来才快。
    如果是多CPU的话,可以把B分块,多线程查找。


    好好学习,天天向上。


    请问在集合里面怎么做索引呢?确实是多CPU。。。说到分块?怎么操作?
    Sherrys
    2009年3月26日 2:05
  • 无人回复。。。
    Sherrys
    2009年3月30日 23:06