import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
public class CollectionTest<T extends Comparable> {
public Collection<T> mergeSortedCollection(Collection<T> a, Collection<T> b) {
Collection<T> result = new LinkedList<T>();
Iterator<T> iA = a.iterator();
Iterator<T> iB = b.iterator();
T oA = null;
if (iA.hasNext()) {
oA = iA.next();
}
T oB = null;
if (iB.hasNext()) {
oB = iB.next();
}
while (oA != null && oB != null) {
// System.out.println(oA+" "+oB);
if (oA.compareTo(oB) <= 0) {
result.add(oA);
if (iA.hasNext()) {
oA = iA.next();
} else {
oA = null;
}
} else {
result.add(oB);
if (iB.hasNext()) {
oB = iB.next();
} else {
oB = null;
}
}
}
if (oA == null) {
result.add(oB);
while (iB.hasNext()) {
oB = iB.next();
result.add(oB);
}
} else if (oB == null) {
result.add(oA);
while (iA.hasNext()) {
oA = iA.next();
result.add(oA);
}
}
return result;
}
static ExecutorService pools = Executors.newFixedThreadPool(64);
static List getDataList = new LinkedList();
static List insertDataList = new LinkedList();
public static void main(String[] args) throws Throwable {
blockAlgorithm();
}
static void blockAlgorithm() throws Throwable{
long start = System.currentTimeMillis();
List<Item> datas = getData();
while(getDataList.size()<100000){
final CountDownLatch finishSignal = new CountDownLatch(datas.size());
for (final Item item : datas) {
pools.execute(new Runnable() {
@Override
public void run() {
try {
item.done = true;
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}finally{
finishSignal.countDown();
}
}
});
}
finishSignal.await();
insertDB(datas);
datas.clear();
datas = getData();
}
System.out.println("finish "+(System.currentTimeMillis() - start));
pools.shutdown();
}
static void nonblockAlgorithm() throws Throwable{
final long start = System.currentTimeMillis();
final ConcurrentLinkedQueue result = new ConcurrentLinkedQueue();
Runnable dataFetch = new Runnable() {
@Override
public void run() {
try {
List<Item> datas = getData();
while(getDataList.size()<=100000){
for (final Item item : datas) {
pools.execute(new Runnable() {
@Override
public void run() {
try {
Thread.sleep(500);
item.done = true;
result.add(item);
// System.out.println(item.seNum+" "+insertDataList.size());
} catch (Exception e) {
e.printStackTrace();
}
}
});
}
datas.clear();
datas = getData();
}
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("dataFetch end");
}
};
Runnable inserter = new Runnable() {
@Override
public void run() {
List a = new LinkedList();
while (insertDataList.size()<100000) {
// System.out.println(a.size());
Object o = result.poll();
if (o!=null) {
a.add(o);
if (a.size()==1000) {
try {
insertDB(a);
a.clear();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
System.out.println("finish "+(System.currentTimeMillis() - start));
System.out.println("inserter end");
pools.shutdown();
}
};
pools.execute(dataFetch);
pools.execute(inserter);
}
private static void insertDB(List<Item> datas) throws InterruptedException {
Thread.sleep(1000);
insertDataList.addAll(datas);
System.out.println("insertDB size="+insertDataList.size());
}
private static List getData() throws InterruptedException {
List datas = new LinkedList();
for (int i = 0; i < 1000; i++) {
datas.add(new Item());
}
getDataList.addAll(datas);
Thread.sleep(1000);
System.out.println("getData size="+getDataList.size());
return datas;
}
}
class Item {
boolean done;
int seNum;
static AtomicInteger ai= new AtomicInteger(0);
public Item() {
seNum = ai.getAndIncrement();
}
}
分享到:
相关推荐
通过merge-sort算法的实现,掌握外存算法所基于的I/O模型与内存算法基于的RAM模型的区别;理解不同的磁盘访问优化方法是如何提高数据访问性能的。
Merge Sort算法c++的实现。用的是VS2008
runoob-algorithm-merge-sort.zip
c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")
merge sort 排序 C++ merge sort 算法的C++实现
Merge Sort 算法的C语言实现 linux 下编译;windows下没试过,也许需要改头文件
斯坦福公开课算法1 merge sort 第一节
void merge_sort(int A[],int p,int r) { int q; if(p) { q=(p+r)/2;//计算q的值,即将问题拆分成两个子问题; merge_sort(A,p,q); //左半边递归调用merge_sort,缩小问题规模 printf("\n"); //print_A(A...
归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并算法采用非常经典的分治策略,每次把序列分成n/2的长度,将问题分解成小问题,由复杂变简单。因为使用了递归算法,不能用于大数据的排序。归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用...
排序——归并排序(Merge sort)
void merge(int A[],int p,int q,int r);//合并排序算法 /************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入...
Algorithm-cpp-drop-merge-sort.zip,HTTPS://GITHUB/COM/EMILK/DROP MIGGE排序的C 实现,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
基于python的排序算法-归并排序Merge Sort
归并排序(Merge Sort)源码及运行示例
merge-sort code
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
算法分析与设计教学课件:Chapter 4 Merge Sort and Recursion.pptx