我发现了一种更有效的排序算法，平均和最佳性能为 O(N)，最差性能为 O(N Log(N))。关于均匀分布的数据。
我需要你的帮助来告诉我我的测试是否正确，而我最大的问题是：如何在真实世界的数据上进行测试？
这个问题将有五个部分：
- 关于 java.util.Collections.sort 的简短介绍
- 关于我的算法的解释
- 测试输出
- 我的算法的源代码
- 我的测试程序的源代码
关于 java.util.Collections.sort 的简短介绍
Java在Collections.sort实现中使用改进的合并排序算法。从 jdk 7 开始，它被替换为timsort。在我的测试中，我一直在使用 jdk 6。与 Android 中使用的相同。
关于我的算法的解释
我发现了一种有趣的排序方法。我使用统计排序。或者更准确地说是线性统计排序。我假设所有变量都有“好的”线性回归。因此，我正在根据变量的值计算变量的近似索引。如果多个变量具有相同的索引，我将它放在缓冲区数组中。比我使用 Collections.sort() 对缓冲区进行排序。这个想法是缓冲区将非常小，因此对其进行排序将是〜O（1）。这是 O(N) 和 O(N Log(N)) 性能之间的差异，在最坏的情况下它的大小是 N。之后我在我的近似排序数组和缓冲区之间进行合并。结果是排序数组。
测试输出
- 我的时间/系统时间 = 511 / 859 = 0.5948777648428405
- 我的时间/系统时间 = 417 / 467 = 0.892933618843683
- 我的时间/系统时间 = 309 / 403 = 0.7667493796526055
- 我的时间/系统时间 = 308 / 344 = 0.8953488372093024
- 我的时间/系统时间 = 204 / 483 = 0.422360248447205
- 我的时间/系统时间 = 204 / 368 = 0.5543478260869565
- 我的时间/系统时间 = 279 / 291 = 0.9587628865979382
- 我的时间/系统时间 = 206 / 288 = 0.7152777777777778
我的算法的源代码
public class StatisticSort {
private static long minemum;
private static long sum;
public static void sort(List<Integer> source) {
findMinMaxAndSum(source);
int size = source.size();
ArrayList<Integer> buffer = new ArrayList<Integer>();
Vector<Integer> sourceVector = new Vector<Integer>(size);
sourceVector.setSize(size);
for (int i = 0; i < size; i++) {
Integer ai = source.get(i);
int index = calculateIndex(ai, source);
if (index != i && sourceVector.get(index) == null) {
sourceVector.set(index, ai);
}
else {
buffer.add(ai); // value
}
}
Collections.sort(buffer);
int bufferSize = buffer.size();
for (int i = 0, j = 0, counter = 0; i < size || j < bufferSize;) {
if (i < size && j < bufferSize) {
Integer ai = sourceVector.get(i);
while (ai == null && i < size) {
i++;
if (i < size) {
ai = sourceVector.get(i);
}
}
if (i == size) {
continue;
}
Integer aj = buffer.get(j);
if (aj < ai) {
source.set(counter, aj);
j++;
}
else {
source.set(counter, ai);
i++;
}
counter++;
}
else {
if (i < size) {
Integer ai = sourceVector.get(i);
if (ai != null) {
source.set(counter, ai);
counter++;
}
i++;
}
else if (j < bufferSize) {
Integer aj = buffer.get(j);
source.set(counter, aj);
j++;
counter++;
}
}
}
}
private static int calculateIndex(Integer ai, List<Integer> source) {
int size = source.size();
return Math.min(size - 1, (int) (((ai - minemum) * size * (size - 1)) / (2 * (sum - size * minemum))));
}
private static void findMinMaxAndSum(List<Integer> source) {
long minemum = Long.MAX_VALUE;
long maximum = -Long.MAX_VALUE;
long sum = 0;
for (int value : source) {
sum += value;
if (value < minemum) {
minemum = value;
}
if (value > maximum) {
maximum = value;
}
}
StatisticSort.minemum = minemum;
StatisticSort.sum = sum;
}
}
我的测试程序的源代码
public abstract class Test {
protected ArrayList<ArrayList<Integer>> buffer;
private final Random random = new Random();
public int numberOfTests = 100;
public int maxValue = 1000;
public int numberOfItems = 100;
protected void createBuffer() {
buffer = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < numberOfTests; i++) {
ArrayList<Integer> list = new ArrayList<Integer>();
addRandomNumbers(list);
buffer.add(list);
}
}
protected void createBuffer(int...parametes) {
buffer = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < parametes.length; i++){
list.add(parametes[i]);
}
buffer.add(list);
}
protected void addRandomNumbers(ArrayList<Integer> list) {
for (int i = 0; i < numberOfItems; i++) {
int value = random.nextInt(maxValue);
list.add(value);
}
}
protected ArrayList<ArrayList<Integer>> cloneBuffer() {
ArrayList<ArrayList<Integer>> clonedBuffer = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < buffer.size(); i++){
ArrayList<Integer> clonedList = new ArrayList<Integer>();
ArrayList<Integer> list = buffer.get(i);
for(int element : list){
clonedList.add(element);
}
clonedBuffer.add(clonedList);
}
return clonedBuffer;
}
public abstract void test();
}
性能测试
public class TestPerformance extends Test{
private final Timer timer = new Timer();
public void test() {
createBuffer();
timer.reset();
testSystem();
timeResoult("System");
timer.reset();
testMy();
timeResoult("My List");
}
public void test(int numberOfTests) {
long myTotalTime = 0;
long systemTotalTime = 0;
for(int i = 0; i < numberOfTests; i++){
createBuffer();
timer.reset();
testSystem();
long systemTime = timeResoult();
systemTotalTime += systemTime;
timer.reset();
testMy();
long myTime = timeResoult();
myTotalTime += myTime;
System.out.println("My Time / System Time = " + myTime + " / " + systemTime + " = \t" + ((double) myTime / systemTime));
}
System.out.println("My Time / System Time = " + ((double) myTotalTime / systemTotalTime));
}
private long timeResoult() {
return timeResoult(null);
}
private long timeResoult(String source) {
long time = timer.check();
if (source != null) {
System.out.println(source + ">\tTime: " + time);
}
return time;
}
private void testMy() {
ArrayList<ArrayList<Integer>> buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
ArrayList<Integer> list = buffer.get(i);
StatisticSort.sort(list);
}
}
private void testSystem() {
ArrayList<ArrayList<Integer>> buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
ArrayList<Integer> list = buffer.get(i);
Collections.sort(list);
}
}
}
主要的
public static void main(String[] args) {
TestPerformance testBasics = new TestPerformance();
testBasics.numberOfTests = 1000;
testBasics.numberOfItems = 1000;
testBasics.maxValue = 1000000;
testBasics.test(1000);
}