作为排序依据的索引/索引的独立阵列中的最快的方法 [英] Fastest way to sort an array by a separate array of indices/indexes
问题描述
假设我有以下设置：
int[] vectorUsedForSorting = new int[] { 1,0,2,6,3,4,5 }
int[] vectorToBeSorted = new int[] {1,2,3,4,5,6,7}
什么是排序 vectorToBeSorted 通过最有效的/快速的方式 vectorUsedForSorting ？例如，我想 vectorToBeSorted [0] 成为 vectorToBeSorted [1] ，因为第一个元素 vectorUsedForSorting 是 1 （即 vectorToBeSorted [0] 应成为`vectorToBeSorted [vectorUsedForSorting [0] 等）。
What is the most efficient/fast way to sort vectorToBeSorted by using vectorUsedForSorting? For example, I would want vectorToBeSorted[0] to become vectorToBeSorted[1], since the first element of vectorUsedForSorting is 1 (i.e., vectorToBeSorted[0] should become `vectorToBeSorted[vectorUsedForSorting[0]], etc).
我的目标为 vectorToBeSorted 是 [2,1,3,5,6,7,4] 后排序算法就完成了。
I am aiming for vectorToBeSorted to be [2,1,3,5,6,7,4] after the sorting algorithm is complete.
我希望能实现的东西非常快。需要注意的是计算复杂性应该是主要的焦点，因为我将整理尺寸1,000,000，更数组。
I am hoping to achieve something very fast. Note that computational complexity should be the main focus, since I will be sorting arrays of size 1,000,000 and more.
我的目标为子线性时间复杂度，如果这是可能的。
I am aiming for sub-linear time complexity if this is possible.
推荐答案
当性能是一个问题，而阵列都很大，你至少得的认为的并行实现（特别是因为这个问题是embarassingly并行：这不是很大的努力，应该得到一个不错的，接近线性的加速与越来越多的内核）：
When performance is an issue, and the arrays are large, you at least have to consider a parallel implementation (especially since this problem is embarassingly parallel: It's not much effort and should yield a nice, near-linear speedup with an increasing number of cores) :
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class ArrayReordering
{
public static void main(String[] args)
{
basicTest();
performanceTest();
}
private static void basicTest()
{
int[] vectorUsedForSorting = new int[] { 1,0,2,6,3,4,5 };
int[] vectorToBeSorted = new int[] {1,2,3,4,5,6,7};
int[] sortedVectorLinear = new int[vectorToBeSorted.length];
int[] sortedVectorParallel = new int[vectorToBeSorted.length];
sortLinear(vectorUsedForSorting, vectorToBeSorted, sortedVectorLinear);
sortParallel(vectorUsedForSorting, vectorToBeSorted, sortedVectorParallel);
System.out.println("Result Linear "+Arrays.toString(sortedVectorLinear));
System.out.println("Result Parallel "+Arrays.toString(sortedVectorParallel));
}
private static void performanceTest()
{
for (int n=1000000; n<=50000000; n*=2)
{
System.out.println("Run with "+n+" elements");
System.out.println("Creating input data");
int vectorUsedForSorting[] = createVectorUsedForSorting(n);
int vectorToBeSorted[] = new int[n];
for (int i=0; i<n; i++)
{
vectorToBeSorted[i] = i;
}
int[] sortedVectorLinear = new int[vectorToBeSorted.length];
int[] sortedVectorParallel = new int[vectorToBeSorted.length];
long before = 0;
long after = 0;
System.out.println("Running linear");
before = System.nanoTime();
sortLinear(vectorUsedForSorting, vectorToBeSorted, sortedVectorLinear);
after = System.nanoTime();
System.out.println("Duration linear "+(after-before)/1e6+" ms");
System.out.println("Running parallel");
before = System.nanoTime();
sortParallel(vectorUsedForSorting, vectorToBeSorted, sortedVectorParallel);
after = System.nanoTime();
System.out.println("Duration parallel "+(after-before)/1e6+" ms");
//System.out.println("Result Linear "+Arrays.toString(sortedVectorLinear));
//System.out.println("Result Parallel "+Arrays.toString(sortedVectorParallel));
System.out.println("Passed linear? "+
Arrays.equals(vectorUsedForSorting, sortedVectorLinear));
System.out.println("Passed parallel? "+
Arrays.equals(vectorUsedForSorting, sortedVectorParallel));
}
}
private static int[] createVectorUsedForSorting(int n)
{
// Not very elegant, just for a quick test...
List<Integer> indices = new ArrayList<Integer>();
for (int i=0; i<n; i++)
{
indices.add(i);
}
Collections.shuffle(indices);
int vectorUsedForSorting[] = new int[n];
for (int i=0; i<n; i++)
{
vectorUsedForSorting[i] = indices.get(i);
}
return vectorUsedForSorting;
}
private static void sortLinear(
int vectorUsedForSorting[], int vectorToBeSorted[],
int sortedVector[])
{
sortLinear(vectorUsedForSorting, vectorToBeSorted,
sortedVector, 0, vectorToBeSorted.length);
}
static void sortParallel(
final int vectorUsedForSorting[], final int vectorToBeSorted[],
final int sortedVector[])
{
int numProcessors = Runtime.getRuntime().availableProcessors();
int chunkSize = (int)Math.ceil((double)vectorToBeSorted.length / numProcessors);
List<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
ExecutorService executor = Executors.newFixedThreadPool(numProcessors);
for (int i=0; i<numProcessors; i++)
{
final int min = i * chunkSize;
final int max = Math.min(vectorToBeSorted.length, min + chunkSize);
Runnable task = new Runnable()
{
@Override
public void run()
{
sortLinear(vectorUsedForSorting, vectorToBeSorted,
sortedVector, min, max);
}
};
tasks.add(Executors.callable(task));
}
try
{
executor.invokeAll(tasks);
}
catch (InterruptedException e)
{
Thread.currentThread().interrupt();
}
executor.shutdown();
}
private static void sortLinear(
int vectorUsedForSorting[], int vectorToBeSorted[],
int sortedVector[], int min, int max)
{
for (int i = min; i < max; i++)
{
sortedVector[i] = vectorToBeSorted[vectorUsedForSorting[i]];
}
}
}
这篇关于作为排序依据的索引/索引的独立阵列中的最快的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
