【Java 集合与队列的插入、删除在并发下的性能比较】_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 【Java 集合与队列的插入、删除在并发下的性能比较】

【Java 集合与队列的插入、删除在并发下的性能比较】

 2015/4/28 18:15:40  melorogee  程序员俱乐部  我要评论(0)
  • 摘要:这两天在写一个java多线程的爬虫,以广度优先爬取网页,设置两个缓存:一个保存已经访问过的URL:vistedUrls一个保存没有访问过的URL:unVistedUrls需要爬取的数据量不大,对URL压缩后,可以把这两个数据结构都放入内存,vistedUrls很显然用HashSet<String>实现,因为已经访问的URL只会添加,不会删除和修改,使用HashSet可以高效判断一个URL是否已经访问。纠结unVistedUrls该用什么数据结构,如果用队列的话,并发情况下
  • 标签:Java 队列

这两天在写一个java多线程的爬虫,以广度优先爬取网页,设置两个缓存:

  •   一个保存已经访问过的URL:vistedUrls
  •   一个保存没有访问过的URL:unVistedUrls

  需要爬取的数据量不大,对URL压缩后,可以把这两个数据结构都放入内存,vistedUrls很显然用HashSet<String>实现,因为已经访问的URL只会添加,不会删除和修改,使用HashSet可以高效判断一个URL是否已经访问。

  纠结unVistedUrls该用什么数据结构,如果用队列的话,并发情况下,队列中可能会用重复的URL,比如一个线程A爬了CSDN的一个URL1,另一个线程B爬了博客园的一个URL2,URL1和URL2的页面都有一个相同的出链URL3,线程A把URL3加入到unVistedUrls的队尾,等待下次爬取,但在URL3被爬取之前,线程B也把URL3加到队尾,这样队列中就有两个相同的URL,可能会导致重复爬取网页,当然可以通过其他方法来保证不会重复爬取。

  然后就想能否也用Set来保存未访问的URL,这样在添加新的URL时,自动去重处理了,能够有效保证不爬取重复网页。但是unVistedUrls会有大量的插入和caozuo.html" target="_blank">删除操作,我认为对集合进行大量的插入删除性能会比较低,为了测试集合的插入删除性能对比队列低多少,我写了一个简单的并发测试:

  1. package com.xwtech.uomp.base.action.handler.admin;
  2. public class asdsd {
  3. ? ? ? ???/**
  4. ? ? ? ???测试集合与队列的插入与读写性能? ?**/
  5. ? ? ? ?? ?public class SetQueueTest {? ?? ?// 随即数构造器
  6. ? ? ? ?? ??
  7. ? ? ? ? ? ? ? ?? ?private static Random r = new Random(10);? ? // 控制测试线程停止的原子变量
  8. ? ? ? ?? ??
  9. ? ? ? ? ? ? ? ?? ?private static AtomicBoolean stop = new AtomicBoolean(false);??12?
  10. ? ??
  11. ? ? ? ? ? ? ? ?? ?static abstract class Service {? ??
  12. ? ? ? ? ? ? ? ? ? ? ? ?? ?
  13. ? ? ? ? ? ? ? ? ? ? ? ?? ?// 操作的计数器
  14. ? ? ? ?? ?? ???protected long count = 0;?
  15. ? ? ? ?? ?? ?? ? // 添加一堆元素,并去一个元素
  16. ? ? ? ?? ?? ?? ? public abstract String addAndPick(List<String> elements);??
  17. ? ? ? ?? ?? ?? ? // 取一个元素
  18. ? ? ? ?? ?? ?? ?public abstract String pickOne();??
  19. ? ? ? ?? ?? ??
  20. ? ? ? ?? ?? ?? ?public void tell() {? ?? ??
  21. ? ? ? ?? ?? ?? ?? ? ? ? System.out.println(this + " :t" + count);? ?? ???
  22. ? ? ? ?? ?? ?? ?? ? ? ? }? ??
  23. ? ? ? ?? ?? ?? ?}??
  24. ? ? ? ?? ?}
  25. ? ? ? ?? ???static class SetService extends Service {?
  26. ? ? ? ?? ???? ? ? ? private TreeSet<String> set = new TreeSet<String>();? ?
  27. ? ? ? ?? ?? ?? ? @Override? ?? ???
  28. ? ? ? ?? ?? ?? ? public synchronized String addAndPick(List<String> elements)?
  29. ? ? ? ?? ?? ?? ? {? ?? ?? ???
  30. ? ? ? ?? ?? ?? ?? ? ? ???count++;? ??
  31. ? ? ? ?? ?? ?? ?? ? ? ???set.addAll(elements);? ?? ?
  32. ? ? ? ?? ?? ?? ?? ? ? ???return set.pollFirst();? ??
  33. ? ? ? ?? ?? ?? ?? ? ? ???}? ?
  34. ? ? ? ?? ?? ?? ?@Override? ?? ?? ??
  35. ? ? ? ?? ?? ?? ?public synchronized String pickOne()
  36. ? ? ? ?? ?? ?? ?{? ?? ?? ??
  37. ? ? ? ?? ?? ?? ?? ? ? ? count++;? ???
  38. ? ? ? ?? ?? ?? ?? ? ? ? return set.pollFirst();??
  39. ? ? ? ?? ?? ?? ?? ? ? ? }??
  40. ? ? ? ?? ???}??
  41. ? ? static class QueueService extends Service {? ??
  42. ? ? ? ? ? ? private Queue<String> queue = new LinkedList<String>();?
  43. ? ? ? ? ? ??
  44. ? ? ? ?? ?? ?? ?@Override? ?? ?? ??
  45. ? ? ? ?? ?? ?? ?public synchronized String addAndPick(List<String> elements)
  46. ? ? ? ?? ?? ?? ?{? ?? ?? ?? ? count++;? ?? ?
  47. ? ? ? ?? ?? ?? ?queue.addAll(elements);? ?? ?
  48. ? ? ? ?? ?? ?? ?return queue.poll();? ?? ??
  49. ? ? ? ?? ?? ?? ?}? ?
  50. ? ? ? ?? ?? ?? ? @Override? ???
  51. ? ? ? ?? ?? ?? ? public synchronized String pickOne() {??
  52. ? ? ? ?? ?? ?? ?? ? ? ???count++;? ?? ?? ?
  53. ? ? ? ?? ?? ?? ?? ? ? ???return queue.poll();? ?? ?? ?
  54. ? ? ? ?? ?? ?? ?? ? ? ???}? ?
  55. ? ? ? ?? ?? ?? ? }??
  56. ? ???static class Tester implements Runnable {? ??
  57. ? ? ? ? ? ???// 绑定要测试的工具对象
  58. ? ? ? ?? ?? ?? ? private Service service;??
  59. ? ? ? ?? ?? ?? ??
  60. ? ? ? ?? ?? ?Tester(Service s) {? ?? ?? ???
  61. ? ? ? ?? ???? ? ? ???this.service = s;? ???
  62. ? ? ? ?? ???? ? ? ???}??
  63. ? ? ? ?? ?? ?? ???@Override? ?? ?? ?
  64. ? ? ? ?? ?? ?? ???public void run() {? ?
  65. ? ? ? ?? ?? ?? ?? ? ? ?? ?while (stop.get() == false) {? ???
  66. ? ? ? ?? ?? ?? ?List<String> elements = new ArrayList<String>();??
  67. ? ? ? ?? ?? ?? ?int len = r.nextInt(200) + 8;? ?? ?? ?? ?
  68. ? ? ? ?? ?? ?? ?for (int i = 0; i < len; i++) {? ?? ??
  69. ? ? ? ?? ?? ?? ?? ? ? ? elements.add(String.valueOf(r.nextInt()));??
  70. ? ? ? ?? ?? ?? ?? ? ? ? }? ?? ?? ?? ?? ??
  71. ? ? ? ?? ?? ?? ?service.addAndPick(elements);? ?? ???
  72. ? ? ? ?? ?? ?? ?for (int i = 0; i < 104; i++)? ???
  73. ? ? ? ?? ?? ?? ?? ? ? ? service.pickOne();? ?? ?
  74. ? ? ? ?? ?? ?? ?}? ?? ??
  75. ? ? ? ?? ?? ?? ?? ? ? ?? ?}? ??
  76. ? ? ? ?? ?? ?? ???}??
  77. ? ? ? ?? ?? ?private static void test(Service service, int time, TimeUnit unit)
  78. ? ? ? ?? ???? ? ? ? ? ? ? ???throws InterruptedException?
  79. ? ? ? ?? ???? ? ? ? ? ? ? ???{? ?? ??
  80. ? ? ? ?? ???? ? ? ???ExecutorService execs = Executors.newCachedThreadPool();?
  81. ? ? ? ?? ???? ? ? ???for (int i = 0; i < 20; i++) {? ??
  82. ? ? ? ?? ???? ? ? ? ? ? ? ???execs.execute(new Tester(service));?
  83. ? ? ? ?? ???? ? ? ? ? ? ? ???}? ?? ???
  84. ? ? ? ?? ???? ? ? ???execs.shutdown();? ??
  85. ? ? ? ?? ???? ? ? ???unit.sleep(time);? ?? ?
  86. ? ? ? ?? ???? ? ? ???stop.compareAndSet(false, true);? ??
  87. ? ? ? ?? ???? ? ? ???service.tell();? ??
  88. ? ? ? ?? ???? ? ? ???}??
  89. ? ? ? ?? ???public static void main(String[] args) throws InterruptedException?
  90. ? ? ? ?? ???{? ?? ??
  91. ? ? ? ?? ???? ? ? ? Service setService = new SetService();? ??
  92. ? ? ? ?? ???? ? ? ? test(setService, 5, TimeUnit.SECONDS);??
  93. ? ? ? ?? ???? ? ? ? stop.compareAndSet(true, false);// 重置终止条件
  94. ? ? ? ?? ?? ???Service queueService = new QueueService();?
  95. ? ? ? ?? ?? ???test(queueService, 5, TimeUnit.SECONDS);? ??
  96. ? ? ? ?? ?? ???}?
  97. ? ? ? ?? ???}
复制代码

输出的结果如下:

  1. SetQueueTest$SetService@5e9de959 :? ?? ?7149859 SetQueueTest$QueueService@11b343e0 :? ? 24303408
复制代码
  1. 测试结果让我感到吃惊,TreeSet的插入删除效率确实比LinkedList低,20个线程跑了10秒,使用队列,插入删除24303408次,使用集合,插入删除7149859次。它们之间差距并不大,队列只比集合快2~3倍。属于同一个数量级。于是我这个小型的爬虫应该放心的选择用Set作为unVistedUrls的实现。
复制代码
发表评论
用户名: 匿名