1 将希尔排序改为并发运行
//串行希尔排序
public static void shellSort(int[] arr){
int h=0;
while( h <=arr.length/3){
h = h*3+1;
}
while(h>0){
for(int i=h;i<arr.length;i++)
if(arr[i]<arr[i-h]){
int tmp = arr[i];
int j = i-h;
while(j>=0&&arr[j]>tmp){
arr[j+h] = arr[j];
j-=h;
}
arr[j+h] =tmp;
}
h =(h-1)/3;
}
}
static int[] arr = {1,3 ,20,15,28,14,13};
并行程序
static ExecutorService es = Executors.newCachedThreadPool();
public static class ShellTask implements Runnable{
int i;
int h;
CountDownLatch count;
public ShellTask(int i, int h, CountDownLatch count) {
super();
this.i = i;
this.h = h;
this.count = count;
}
@Override
public void run() {
if(arr[i]<arr[i-h]){
int tmp = arr[i];
int j = i-h;
while(j>=0&&arr[j]>tmp){
arr[j+h] = arr[j];
j-=h;
}
arr[j+h] =tmp;
}
count.countDown();
}
}
public static void ShellTaskSort(int[] arr) throws InterruptedException{
//计算h的值
int h=1;
while(h<=arr.length/3){
h = h*3+1;
}
CountDownLatch count = null;
while(h>0){
System.out.println("h= "+h);
if(h>=4){
count = new CountDownLatch(arr.length-h);
}
for(int i=h;i<arr.length;i++) {
if(h>=4){
es.execute(new ShellTask(i, h, count));
}else {
if(arr[i]<arr[i-h]){
int tmp = arr[i];
int j = i-h;
while(j>=0&&arr[j]>tmp){
arr[j+h] = arr[j];
j-=h;
}
arr[j+h] =tmp;
}
}
}
count.await();
h =(h-1)/3;
}
}
2 Semaphore 信号量的使用
//现成程序中的在不断的产生数据，然后交到TestDo.dosome() 方法去处理。请将程序改造成
//有10个线程来消费生产者产生的数据，这些消费者都调用了TestDo.dosome方法进行处理
// 故每个消费者都需要一秒才能处理完，程序应保证这些消费者线程依次有序的消费数据、
// 只有上一个消费者消费完后，下一个消费者才能消费数据。下一个消费者是谁都可以，但要
// 保证这些消费者线程拿到的数据是有顺序的。
public static void main(String[] args) {
final SynchronousQueue<String> queue = new SynchronousQueue<>();
//信号量
final Semaphore sp = new Semaphore(1);
for(int i=0;i<10;i++){
new Thread(new Runnable(){
@Override
public void run() {
try {
sp.acquire();
String input = queue.take();
String output = TestDo.doSome(input);
System.out.println(Thread.currentThread().getName()+":"+output);
sp.release();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}).start();
}
System.out.println("begin:"+System.currentTimeMillis()/1000);
for(int i=0;i<10;i++){ //不要改动
String input = i+" "; //不要改动
try {
queue.put(input);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//String output = TestDo.doSome(input);
//System.out.println(Thread.currentThread().getName()+":"+output);
}
}
static class TestDo{
public static String doSome(String input){
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
String output = input+":"+System.currentTimeMillis()/1000;
return output;
}
}
3 多线程去获取头一把锁，变为串行执行
/**
* 现有程序同时启动了4个线程去调用TestDo.doSome(key,value)方法，由于先暂停1秒，然后再输出以秒为单位的
* 当前时间值，所以，会打印四个相同的时间值，如下所示
* 4：4 ：1258199615
* 1: 1 ：1258199615
* 3：3 ：1258199615
* 1：2 ：1258199615
* 请修改代码，传入key相同时，则这几个线程应互斥排队输出结果，即当有两个线程的key都是"1"时，它们中的一个要比
* 另外其他线程晚一秒输出结果
* 4：4 ：1258199615
* 1: 1 ：1258199615
* 3：3 ：1258199615
* 1：2 ：1258199616
*/
private TestDo testDo;
private String key;
private String value;
public Test2(String key,String key2,String value){
this.testDo = TestDo.getInstance();
// 通过这种操作，使值相同，但不是同一个对象
this.key = key+key2;
// a = "1"+"";
// b = "1" + "";
// a和b是同一个对象
this.value = value;
}
@Override
public void run() {
testDo.doSome(key, value);
}
public static void main(String[] args) {
Test2 a = new Test2("1", "", "1");
Test2 b = new Test2("1", "", "1");
Test2 c = new Test2("3", "", "1");
Test2 d = new Test2("4", "", "1");
System.out.println("begin:"+System.currentTimeMillis()/1000);
a.start();
b.start();
c.start();
d.start();
}
public static class TestDo{
private TestDo(){
}
private static TestDo instance = new TestDo();
public static TestDo getInstance(){
return instance;
}
//private ArrayList<Object> list = new ArrayList<Object>() ;
//使用CopyOnWriteArrayList
CopyOnWriteArrayList<Object> list = new CopyOnWriteArrayList<>();
public void doSome(Object key,String value){
Object o = key;
if(!list.contains(o)){
list.add(o);
}else{
for (Object object : list) {
if(o.equals(object)){
o =object;
}
}
}
synchronized (o) { //需同步的代码块
try {
Thread.sleep(1000);
System.out.println(key+":"+value+":"+System.currentTimeMillis()/1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
