数据量大的情况下,找出一个list集合中多于另一个list集合的元素? 需要考虑性能 时间复杂度

streamlong 发布于 2017/02/21 16:19
阅读 1K+
收藏 1

语言:java

数据量大的情况下,找出一个list集合中多于另一个list集合的元素?  

需要考虑性能  时间复杂度

已被pass的:

1.直接使用集合自带操作       listA.removeAll(listB);  或者集合工具里面的求差集方法except()

2.换种set集合来操作,set集合能确保数据唯一

3.有人说:开多线程,用硬件损耗来提升软件性能?感觉采用这种方式是土豪级别的。

请问各为看管,有啥高见,说一说么?

 

加载中
2
公孙二狗
公孙二狗

数据量大,多大?

数据量大,为啥都要把它们放到 list 里?在出题时就不考虑内存问题吗?

而且就算用 HashSet 来存储,这个时候 HashSet 本身存储的是引用,数据量那么大都放内存了,会在乎它们的引用占用的那么点内存吗?

其实还可以看看数据的特征,根据特征来考虑解决方案有时很重要。

如果是面试,我觉得可以和面试官探讨一下,而不是有问只能答,你也可以问。

0
Charkey
Charkey

可以看看其他的集合类库比如 Guava

0
如比如比
如比如比

自己扩展集合类,在add,remove等方法执行Callback来维护元素类的父信息。

class E implements xxinterface {
    private List parentA;
    private List parentB;
    
    public void setParentA(List list) {
        this.parentA = list;
    }
    public boolean isOnlyA() {
        return parentB == null;
    }
}

遍历一边listA就能找出不在listB中存在的元素了。

0
D
DataPudge

可以尝试使用Redis 做两个集合的差集

0
尚浩宇
尚浩宇

用java8的lambda表达式

0
zigzagroad
zigzagroad
没说数据从哪来的。如果是数据库中的数据,直接就过滤出来了。
0
Kit_lee
Kit_lee

对对象排序后,放入LinkedList,遍历速度最快

0
雨翔河
雨翔河

分而治之行不行:

a拆分为a1,a2,a3。。。

b进行排序,大数据量可以拆开来归并排序。

取a1,a2,a3。。。的数据开n线程去b里面查找数据,速度极快,如果没找到则放入一个set中,每个线程去找之前看一下这个set里面有没有它,有的话就不用找了,结果就在set中。这样set里面的数据就是a里面有的,b没有的数据。

0
唱不完的离歌
唱不完的离歌

提个个人建议,先对少的那个ListA先排序,然后依次拿另一个ListB的里面的元素。在ListA中做二分查询,单词查询时间复杂度为lgn,所以假设listb有N个元素,整个查找过程的时间复杂度为nlgn,就算再加上lista的排序时间,如果你用的是归并排序等高效排序算法则排序时间复杂度为nlgn,就算你用的是最差的冒泡排序,时间复杂度为n2,整个查找过程时间复杂度为2nlgn(排序用归并)或n(lgn+n)排序用冒泡

0
streamlong
streamlong

谢谢大家的发言,这个是一道面试题啦,当时因为后面还有问题,这个问题就一笔带过了。现在总结下:数据量大,最常用的做法是直接从根源去过滤数据,比如从数据库提取的时候就过滤,还有一种是因为业务场景的不同,没办法从数据库直接过滤,到程序逻辑层面,应该考虑的就是算法问题吧,虽然集合类及集合工具类蛮多,但是这个也是对集合常用操作做的一些封装,还是要考虑各集合特征及具体业务场景的,不能两全时,还是需要做些牺牲的,比如用时间换空间等策略......

返回顶部
顶部