跟随,学习,进步

Yisaer

Yisa's Blog

https://yisaer.github.io

上海大学14级计算机学院,酷家乐黄埔研究院 研发工程师

转到作者网站

并发下的搜索与排序

概论在传统的串行运行下,在数组内查找特定元素和将数组排序都有一套成熟的方法。对于数组内查找,如果是有序数组在可以在查找的话可以运用二分查找法,而对于无序数组则应该将数组遍历一遍。而对于数组排序,则是有类似快排,归并排序等等复杂度控制在O(nlogn)的算法。 从算法的角度来说,似乎并没有往下继续优化的空间了。但是如果运行在并行环境下,虽然理论上的算法复杂度并没有变小,但是我们可以用并行的方式来将时间缩短。为何可以使用并行考虑这么一件事情,如果我们将一堆苹果放在一个篮子里,那么我们唯一能做的做法就是将苹果一个个的依次放入篮子,这没什么好说的。那么如果我们要加快速度的话,我们会多派一个人手,比如将苹果堆一分为二,然后两个人分别将两堆苹果同时放到一个篮子里。但是如果我们考虑到我们希望放入苹果时,希望是一个红苹果一个青苹果间隔,那么在两个人毫无配合的情况下,这种方式反而不如一个人依次放入来的效果好。也就是说,运用并行的场景下,要求我们所处理的数据互相不干扰,那么你就可以使用并行来充分的利用起时间。数组并行搜索对于一个数组,我们想在里面找到元素a的下标,在串行模式中我们只能运用遍历的方式来搜索指定元素。但是如果我们将数组一分为二,然后将分配两个线程并行的单独搜索,那么CPU也就被更多的利用了。以Java为例子,首先我们准备好线程池,并发数,原子性的Int与数组static ExecutorService pool = Executors.newCachedThreadPool();static final int Thread_Num = 2;static AtomicInteger res = new AtomicInteger(-1);static int[] arr;然后我们在再编写每个线程所应该执行的搜索函数,规定了搜索值与搜索区间12345678910111213141516public static int search(int searchValue,int beginPos,int endPos){ for(int i = beginPos;i=0){ return res.get(); } if(arr[i] == searchValue){ System.out.println("Found"); if( !res.compareAndSet(-1,i)){ return res.get(); } return i; } } return -1;}然后我们创建每个线程完成的任务,以Future模式声明,实现了Callable接口12345678910111213141516public static class SearchTask implements Callable{ int begin,end,searchValue; public SearchTask(int begin, int end, int searchValue) { this.begin = begin; this.end = end; this.searchValue = searchValue; } @Override public Integer call() throws Exception { int re = search(searchValue,begin,end); return re; }}最好我们将搜索封装成一个函数即可,当中由于一个数组被切割成N份来并行搜索,我们可以用Arraylist来包装每个线程,从而遍历每个线程是否得到结果。123456789101112131415161718192021public static int pSearch(int searchValue) throws ExecutionException, InterruptedException { int subArrSize = arr.length/Thread_Num+1; List re = new ArrayList(); for(int i = 0;i=arr.length){ end = arr.length; } re.add(pool.submit(new SearchTask(i,end,searchValue))); } try { for (Future fu : re) { if (fu.get() = 0) { return fu.get(); } } return -1; }finally { pool.shutdown(); }}最后许多串行情境下的算法,只要当中数据不相互影响,大部分都可以用并发的情境来充分利用CPU,下次我会分析下如何使用并发来数组排序


寒假的总结与新学期的计划

前言寒假结束了,感觉这个寒假又像之前的假期一样,没有完全利用起来呀。 诶这也是没办法。总结一下这个寒假所做的事情并想一下接下来的安排吧。异步编程这个寒假首先做的事情应该就是接触异步编程,学习使用了Netty框架,并用Netty框架写了一个服务端用在了爬虫作业中。 看了一遍O’Reilly的JavaNio,现在想想感觉自己对选择器和信道还是感觉懵懵懂懂的。虽然写过一遍Demo,不过这个东西就像当初刚接触JDBC一样,希望自己以后能对异步编程的理解越来越深吧。爬虫大二的时候一直希望能学会写爬虫。这个寒假学了python的requests库与bs4库以后,写了两个爬虫来练手。一个是自己用于爬取OJ题目代码的爬虫,一个是爬取豆瓣上书的信息的爬虫。豆瓣爬虫也结合了线程池的技术来加快速度。 虽然感觉在爬虫上这不算什么,但是这种从不会到会的感觉还是很棒的。Unix编程这个寒假大部分的时候应该都放在了Unix编程上面。用C语言来调用系统函数来完成一个个功能非常有意思,而且也对于理解Unix类的操作系统有着非常大的帮助。虽然这本书在寒假大致已经看完了,但是感觉只看了一遍以后并没有完全吸收,而且我觉得这本书真的值得再去学习一遍,将代码再去完成一遍。之前有很多命令函数完成的比较囫囵吞枣,感觉这个学期还要抽时间一天来学习一章的速度重温一遍。以后想去刷apue与unp,希望自己有一天能发展成系统、网络的工程师。话说还一直赖着HTTPD的实现没有写,准备抽空用C语言将HTTP服务器实现。Java高并发程序设计一本国人写的非常棒的书,个人觉得比Java并发实战那本书写的更加直白易懂。这本书大概是在寒假的最后一礼拜开始看的,今天连看带写Demo的完成了前四章吧。总的来说是熟悉了大部分概念与JDK里面的Concurrent并发包。 虽然这是以JAVA对语言的多线程教材,但是感觉提出并解决了许多在并发状况下会出现的错误与如何解决。Loic为了给计算思维交差写的一个Syn泛洪攻击,类似于一个加农炮,服务端从操作大量客户端来向某一台主机发起Syn泛洪攻击。 感觉安全这方面还是很有趣的,我也只是试着写了一个工具测试。 不过如果以后接触安全的话我想我会去了解Web安全吧,毕竟在Web方面有点了解。计划安排接下来会去先将设计模式了解一下以后再将Java高并发刷完,当中会去熟悉学习springboot与mybatis框架,准备为下一次实习做起准备。如果能抽得出时间会二刷Unix系统编程。这应该就是短期内打算在冬季学期内完成的目标了吧。 长期的打算以后再看吧, 感觉自己有很多事情要去做就等以后再说吧。然后每天的锻炼也要坚持不能停,尽快将生物钟恢复到在学校的早睡早起吧。当然Github的活跃更新也不能断. 嗯就这样吧先..