我这里首先尝试了 ReentrantLock, 用它我本以为可以精确控制锁的粒度, 这里省去了一些非必要代码, 思路是创建一大堆线程然后全部等锁, 线程就绪之后再放开锁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
public class SleepSort {
final static ReentrantLock lock = new ReentrantLock();
final static Condition condition = lock.newCondition();
static volatile boolean locked = true;
static volatile AtomicInteger index = new AtomicInteger(0);
static int[] sleepInts;
static Runnable getRunnable(int time) {
return () -> {
lock.lock();
while (locked) condition.await();
lock.unlock();
Thread.sleep(time);
sleepInts[index.getAndIncrement()] = time;
};
}
static void sleepSort() {
System.out.println("start sleep sort");
long start = System.currentTimeMillis();
ExecutorService executor = Executors.newFixedThreadPool(1000);
for (int i = 0; i < 1000; i++) sleepInts[i] *= 21L;
for (int i = 0; i < 1000; i++) executor.execute(getRunnable(sleepInts[i]));
lock.lock();
locked = false;
condition.signalAll();
lock.unlock();
executor.shutdown();
executor.awaitTermination(100000L, TimeUnit.DAYS);
long time = System.currentTimeMillis() - start;
System.out.println("end sleep sort: " + time);
System.out.println("sleep sort examine: " + examine());
}
static boolean examine() {
for (int i = 0; i < sleepInts.length - 1; i++)
if (sleepInts[i] > sleepInts[i + 1]) return false;
return true;
}
public static void main(String[] args) {
final int[] ints = new int[1000];
Random random = new Random();
for (int i = 0; i < 1000; i++)
ints[i] = random.nextInt(10);
final int[] ints1 = new int[1000];
for (int i = 0; i < 1000; i++)
ints1[i] = random.nextInt(10);
sleepInts = ints1;
sleepSort();
System.out.println("start Arrays sort");
long start = System.currentTimeMillis();
Arrays.sort(ints);
long time = System.currentTimeMillis() - start;
System.out.println("end Arrays sort: " + time);
}
}
|
结果: 其中经过测试, 时间放大 21 倍才能确保排序结果正确(我的电脑上)….
1
2
3
4
5
|
start sleep sort
end sleep sort: 295
sleep sort examine: true
start Arrays sort
end Arrays sort: 0
|
我尝试换成了 synchronized:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
static Runnable getRunnable(int time) {
return () -> {
synchronized (o) {
while (locked) {
o.wait();
}
}
Thread.sleep(time);
sleepInts[index.getAndIncrement()] = time;
};
}
static void sleepSort() {
System.out.println("start sleep sort");
long start = System.currentTimeMillis();
ExecutorService executor = Executors.newFixedThreadPool(1000);
for (int i = 0; i < 1000; i++) {
sleepInts[i] *= 11L;
}
for (int i = 0; i < 1000; i++)
executor.execute(getRunnable(sleepInts[i]));
synchronized (o) {
locked = false;
o.notifyAll();
}
executor.shutdown();
executor.awaitTermination(100000L, TimeUnit.DAYS);
long time = System.currentTimeMillis() - start;
System.out.println("end sleep sort: " + time);
System.out.println("sleep sort examine: " + examine());
}
|
最低可以到放大 11 倍, 至于和 Arrays.sort 比, 那没事了
1
2
3
4
5
|
start sleep sort
end sleep sort: 192
sleep sort examine: true
start Arrays sort
end Arrays sort: 0
|