同步和异步是表示这种 API 的接口风格。比如常见的 Linux 的 BIO 接口、Go 的 IO 接口、Rust 里的 async 函数,这些都是同步风格的接口,先后调用这样的两个接口,它们默认是同步执行的,你要异步执行,需要另外开线程或者协程;Node.js、Vert.X 的绝大部分接口,都是异步风格的接口,先后调用这样的两个接口,它们默认是异步执行的,你要同步执行,需要把第二个接口写到前一个接口的回调函数里。
阻塞和非阻塞是表示这种 API 需要调用者配合使用的线程模型。比如 Linux 的 BIO 接口会阻塞调用者的线程,它就是阻塞的,而 Go 的 IO 接口、Rust 的 async 函数、Node.js 和 Vert.X 里的异步接口,都不会阻塞调用者的线程,它们就是非阻塞的。
在没有协程的年代,同步风格的 BIO 接口就是会导致线程阻塞,它意味着心智负担小,开发方便,但是吃资源;而不会阻塞线程的 NIO/AIO 接口往往是异步风格(或者封装为异步风格),代码写起来心智负担重,性能好,比如 Node.js 和 Vert.X。所以经常有人拿同步代指阻塞,拿异步代指非阻塞,它们成为了同义词两两绑定在一起,即“同步阻塞”和“异步非阻塞”。
而 Go 、Rust 等语言提供的协程,相当于是对“异步非阻塞”的一种高级封装,可以像写同步代码那样写不阻塞线程的代码,让你即拥有高性能,又没有很高的心智负担。但是也很少见他们讨论自己是同步还是异步,阻塞还是非阻塞,因为风格上确实是同步的,封装的实际上是异步常用的非阻塞接口,确实不会阻塞线程,但是协程是可能被阻塞。所以不要套概念,理解原理,理解同步具体指的是谁和谁,异步具体指的是谁和谁,阻塞和非阻塞指的具体是谁,搞清楚对象,套定义就可以了。
privatevoidswap(int i, int j){ if (i != j) { this.data[i] = this.data[i] ^ this.data[j]; this.data[j] = this.data[i] ^ this.data[j]; this.data[i] = this.data[i] ^ this.data[j]; } }
privatevoidheapify(int index){ int leftIndex = 2 * index + 1;
while (leftIndex < heapSize) { int rightIndex = leftIndex + 1; int greatestIndex = rightIndex < heapSize && this.data[rightIndex] > this.data[leftIndex] ? rightIndex : leftIndex;
if (this.data[greatestIndex] <= this.data[index]) { break; }
swap(index, greatestIndex); index = greatestIndex; leftIndex = 2 * index + 1; } }
@Override public String toString(){ StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; i<heapSize; i++) { b.append(data[i]); if (i != heapSize - 1) b.append(", "); } b.append(']');
staticintdoMergeSmallSum(int[] array, int[] help, int start, int end){ if (end - start < 2) { return0; }
int mid = start + ((end - start) >> 1); int left = doMergeSmallSum(array, help, start, mid); int right = doMergeSmallSum(array, help, mid, end); return left + right + doMerge(array, help, start, mid, end); }
staticintdoMerge(int[] array, int[] help, int start, int mid, int end){ int i = start; int j = mid; int k = start; int sum = 0;
while (i < mid && j < end) { if (array[i] < array[j]) { int t = array[i++]; help[k++] = t; sum += t * (end - j); } else { help[k++] = array[j++]; } }
while (i < mid) { help[k++] = array[i++]; }
while (j < end) { help[k++] = array[j++]; }
for (k = start; k < end; k++) { array[k] = help[k]; }