我正在尝试使用web工作者制作合并排序算法的并行版本。
并行版本在小阵列上非常慢(我认为这是由于promise和web工作者的开销)，但令人惊讶的是，它在大阵列上也比串行排序慢
并行版本
console.log(navigator.hardwareConcurrency + " threads")
var blob = new Blob([
`onmessage = function(e) {
function merge_sort(arr) {
let length = arr.length;
if (length < 2) {
return arr
}
let middle = Math.floor(length/2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(merge_sort(left), merge_sort(right))
}
function merge(left, right) {
let result = [];
let i=0;
let j=0;
while(i < left.length && j < right.length) {
if(left[i] < right[j]) {
result.push(left[i]) ;
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j))
}
if(e.data.job==='sort'){
postMessage(merge_sort(e.data.arr));
}else{
postMessage(merge(e.data.arr[0],e.data.arr[1]))
}
}`
]);
var blobURL = window.URL.createObjectURL(blob);
var v1 = new Worker(blobURL);
var v2 = new Worker(blobURL);
var v3 = new Worker(blobURL);
var v4 = new Worker(blobURL);
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j))
}
var arr = Array.from({
length: 20000000
}, () => Math.floor(Math.random() * 50000000));
var half1 = []
var half2 = []
var half_1 = []
var half_2 = []
var half_3 = []
var half_4 = []
let middle = Math.floor(arr.length / 2)
half1 = arr.slice(0, middle)
half2 = arr.slice(middle)
let middlehalf1 = Math.floor(half1.length / 2)
half_1 = half1.slice(0, middlehalf1)
half_2 = half1.slice(middlehalf1)
let middlehalf2 = Math.floor(half2.length / 2)
half_3 = half2.slice(0, middlehalf2)
half_4 = half2.slice(middlehalf2)
var t0 = performance.now();
var p1 = new Promise((resolve, reject) => {
v1.postMessage({
job: 'sort',
arr: half_1
});
v1.addEventListener('message', event => resolve(event.data));
v1.addEventListener('error', reject);
})
var p2 = new Promise((resolve, reject) => {
v2.postMessage({
job: 'sort',
arr: half_2
});
v2.addEventListener('message', event => resolve(event.data));
v2.addEventListener('error', reject);
})
var p3 = new Promise((resolve, reject) => {
v3.postMessage({
job: 'sort',
arr: half_3
});
v3.addEventListener('message', event => resolve(event.data));
v3.addEventListener('error', reject);
})
var p4 = new Promise((resolve, reject) => {
v4.postMessage({
job: 'sort',
arr: half_4
});
v4.addEventListener('message', event => resolve(event.data));
v4.addEventListener('error', reject);
})
Promise.all([p1, p2, p3, p4]).then(function(results) {
//console.log( )
var p5 = new Promise((resolve, reject) => {
v1.addEventListener('message', event => resolve(event.data));
v1.addEventListener('error', reject);
})
var p6 = new Promise((resolve, reject) => {
v2.addEventListener('message', event => resolve(event.data));
v2.addEventListener('error', reject);
})
v1.postMessage({
job: 'merge',
arr: [results[0], results[1]]
});
v2.postMessage({
job: 'merge',
arr: [results[2], results[3]]
});
Promise.all([p5, p6]).then(function(arrays) {
merge(arrays[0], arrays[1])
var t1 = performance.now();
console.log(`merge_sort took ${(t1 - t0) / 1000} seconds`)
})
});
串行版本
function merge_sort(arr) {
let length = arr.length;
if (length < 2) {
return arr
}
let middle = Math.floor(length/2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(merge_sort(left), merge_sort(right))
}
function merge(left, right) {
let result = [];
let i=0;
let j=0;
while(i < left.length && j < right.length) {
if(left[i] < right[j]) {
result.push(left[i]) ;
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j))
}
var BigArray =Array.from({ length: 20000000 }, ()=>Math.floor(Math.random() * 50000000));
var t0 = performance.now();
merge_sort(BigArray)
var t1 = performance.now();
console.log(`merge_sort took ${(t1 - t0) / 1000} seconds`)
此外，我正在寻找一个更好的解决方案与平行排序(我使用的承诺看起来很糟糕)
考虑到您正在在线程之间复制数据，并且至少复制一次不必要的数据(通过使用concat)，我对大型数组的速度较慢并不感到惊讶。
如果您真的在对数字进行排序，您可以使用类型数组类型之一，来回传输数组的所有权，而不是复制其内容。这样可以减少复制的数量。如果您的起点是单个数组，那么唯一的复制将是为各个工作程序复制到各个类型的数组，然后从这些单独的数组复制回主数组。
你甚至可以更进一步，这取决于你需要支持什么平台，使用共享内存，这样阵列只有一个副本，每个工作人员只是(最初)在自己的部分上工作。共享内存在Chrome上的平台上启用，其站点隔离功能可以防止Spectre式的漏洞。我最后一次检查它在Firefox中被禁用，在其他浏览器中被禁用或未实现。
但是，如果你排序的不是真正的数字，那么这两个都不起作用，因为它们与类型化数组绑定在一起。