Java的：赛车Arrays.sortJava、Arrays、sort
2023-09-11 05:54:21
作者：卍我许你三世承诺
我创造了一些改进，快速排序，并决定对Java来测试它 Arrays.sort（）。
结果是迷人的：
在Java 6的：
在我的时间/系统时间=八十三分之七十四= 0.891566265060241 在我的时间/系统时间=七十九分之七十五= 0.9493670886075949 在我的时间/系统时间=八十四分之七十五= 0.8928571428571429在Java 7的：
在我的时间/系统时间=七十零分之一百一十五= 1.6428571428571428 在我的时间/系统时间=七十六分之一百〇一= 1.3289473684210527 在我的时间/系统时间=六十一分之一百〇二= 1.6721311475409837正如你可以看到我的算法执行关于Java 6好，但怎么过对Java 7的女巫，我不明白急剧下降。可能是你能找到什么原因呢？
编辑：请问我的算法如下：
第1步：取3号，对它们进行排序，使用中间数为支点 的步骤2：比枢轴向右大径所有的数字和所有的数字比枢轴到左边，并置于枢轴较小，在它的所述排序后的数组中的最终位置。这为O（N）。实际执行 第三步：递归重复步骤1和2的左侧和右侧。当你富有子阵列小于12元使用网络排序排序。我的源$ C $ C
公共类快速排序{
公共静态无效排序（INT []源）{
INT缓冲区[] =新的INT [source.length]
CONCATENATE（源，缓冲，0，source.length）;
}
私有静态无效串连（INT []来源，INT []缓冲区，诠释低，诠释高）{
诠释计数=高 - 低;
INT lowBuffer =低;
INT highBuffer =高;
如果（计数2）{
返回;
}
如果（计数＆LT; 12）{
networkSort（源，缓冲，低，计数）;
返回;
}
INT pivotIndex = bestOfThree（源，低）;
int值=源[pivotIndex]
的for（int i =低; I＆LT;高;我++）{
如果（我== pivotIndex）{
继续;
}
如果（来源[1] - ;值）{
缓冲区[lowBuffer] =源[I]
来源[lowBuffer] =缓冲[lowBuffer]
lowBuffer ++;
}
其他 {
highBuffer--;
缓冲区[highBuffer] =源[I]
}
}
缓冲区[lowBuffer] =源[lowBuffer] =值;
对于（INT I = lowBuffer; I＆LT;高;我++）{
来源[I] =缓冲区[I]
}
串联（源，缓冲区，lowBuffer + 1，高）;
串联（源，缓冲，低，lowBuffer）;
}
私有静态诠释bestOfThree（INT []来源，诠释低）{
INT A =低;
INT B = A + 1;
INT C = A + 2;
INT中位数= -1;
如果（来源[A]≥=源[B]及放大器;＆放大器;源[A]≥=源[C]）{
如果（来源[B]＆lt;信源[C]）{
中位= C;
}
其他 {
中位= B;
}
}
否则，如果（来源[B]＆GT; =源[A]和放大器;＆放大器;源[B]＆GT; =源[C]）{
如果（来源[A]＆lt;信源[C]）{
中位= C;
}
其他 {
中位= A;
}
}
否则，如果（来源[C]＆GT; =源[A]和放大器;＆放大器;源[C]＆GT; =源[B]）{
如果（来源[A]＆lt;信源[B]）{
中位= B;
}
其他 {
中位= A;
}
}
返回中位;
}
私有静态诠释[] [] networkSort = {
{0,1}，
{1，2，0,2，0，1}，
{0，1，2，3，0,2，1,3，1，2}，
{0，1，3，4，2，4，2，3，1,4，0,3，0,2，1,3，1，2}，
{1，2，4，5，0，2，3，5，0，1，3，4，2，5,0，3，1,4，2，4，1，3，2，3}，
{1，2，3，4，5，6，0，2，3，5，4,6，0,1，4，5，2,6，0，4，1，5,0，3，2 ，5，1，3，2，4，2，3}，
{0，1，2，3，4，5，6，7，0,2，1，3，4，6，5，7，1，2，5，6，0,4，3，7，1 5，2,6，1,4，3，6，2，4，3，5，3，4}，
{0，1，3，4，6，7，1，2，4，5，7，8，0,1，3，4，6，7，2,5，0，3，1，4，5 ，8,3，6,4，7,2，5,0，3，1，4，5，7，2,6，1，3，4，6，2，4，5，6，2,3 }，
{4,9，3,8，2,7，1,6，0，5，1，4，6，9，0，3，5，8，0，2，3，6，7，9，0 ，1，2，4，5，7，8，9，1，2，4，6，7，8，3，5，2，5，6，8，1，3，4，7，2,3 ，6,7，3，4，5，6，4,5}，
{0，1，2，3，4，5，6，7，8，9，1，3，5，7，0，2，4，6，8，10，1，2，5，6，9 ，10，0，4，3，7，1，5，6，10，4,8，5,9，2,6，0,4，3,8，1，5，6，10，2，3 ，8，9，1,4，7，10，3，5，6，8，2，4，7，9，5,6，3，4，7，8}
};
私有静态诠释TMP;
私有静态无效networkSort（INT []来源，INT []缓冲区，诠释低，诠释计数）{
INT [] networkData = networkSort [计数 - 2]。
的for（int i = 0; I＆LT; networkData.length;我+ = 2）{
INT索引1 =低+ networkData [I]
INT索引2 =低+ networkData [I + 1];
如果（来源[索引1]＆GT;源[索引2]）{
TMP =源[索引1];
缓冲区[索引1] =源[索引1] =源[索引2];
缓冲区[索引2] =源[索引2] = TMP;
}
}
}
}
基础测试类
公共抽象类的测试{
保护的INT [] []缓冲液;
私人最终随机随机=新的随机（）;
公众诠释numberOfTests = 100;
公众诠释包括maxValue = 1000;
公众诠释numberOfItems = 100;
保护无效createBuffer（）{
缓冲区=新的INT [numberOfTests] [];
的for（int i = 0; I＆LT; numberOfTests;我++）{
INT []列表=新INT [numberOfItems]
addRandomNumbers（名单）;
缓冲区[i] =清单;
}
}
保护无效createBuffer（INT ...指标的影响）{
缓冲=新INT [1] [];
缓冲器[0] =指标的影响;
}
保护无效addRandomNumbers（INT []列表）{
的for（int i = 0; I＆LT; numberOfItems;我++）{
int值= random.nextInt（包括maxValue）;
名单[I] =值;
}
}
保护的INT [] [] cloneBuffer（）{
INT [] [] clonedBuffer =新INT [numberOfTests] [];
的for（int i = 0; I＆LT; buffer.length;我++）{
INT [] clonedList =新INT [缓冲区[I] .length]。
INT []列表=缓冲区[I]
对于（INT J = 0; J＆LT; list.length; J ++）{
INT元=列表[J]。
clonedList [J] =元;
}
clonedBuffer [我] = clonedList;
}
返回clonedBuffer;
}
公共抽象无效测试（）;
}
性能测试
公共类PerformanceTest扩展测试{
私人最终定时器定时=新的Timer（）;
公共无效测试（）{
createBuffer（）;
timer.reset（）;
testSystem（）;
timeResoult（系统）;
timer.reset（）;
testMy（）;
timeResoult（我的目录）;
}
公共无效测试（INT numberOfTests）{
长myTotalTime = 0;
长systemTotalTime = 0;
的for（int i = 0; I＆LT; numberOfTests;我++）{
createBuffer（）;
timer.reset（）;
testSystem（）;
长SYSTEMTIME = timeResoult（）;
systemTotalTime + = SYSTEMTIME;
timer.reset（）;
testMy（）;
长的数值指明MyTime = timeResoult（）;
myTotalTime + =数值指明MyTime;
的System.out.println（我的时间/系统时间=+数值指明MyTime +/+ SYSTEMTIME += \ T
+（（双）数值指明MyTime / SYSTEMTIME））;
}
的System.out.println（我的时间/系统时间=+（（双）myTotalTime / systemTotalTime））;
}
私人长timeResoult（）{
返回timeResoult（空）;
}
专用长timeResoult（字符串源）{
很长一段时间= timer.check（）;
如果（来源！= NULL）{
的System.out.println（来源+＆GT; \ TTIME：+时间）;
}
返回时间;
}
私人无效testMy（）{
INT [] []缓冲液= cloneBuffer（）;
的for（int i = 0; I＆LT; numberOfTests;我++）{
INT []列表=缓冲区[I]
QuickSort.sort（名单）;
}
}
私人无效testSystem（）{
INT [] []缓冲液= cloneBuffer（）;
的for（int i = 0; I＆LT; numberOfTests;我++）{
INT []列表=缓冲区[I]
Arrays.sort（名单）;
}
}
}
主要
公共静态无效的主要（字串[] args）{
PerformanceTest testBasics =新PerformanceTest（）;
testBasics.numberOfTests = 1000;
testBasics.numberOfItems = 1000;
testBasics.maxValue = 1000000;
testBasics.test（100）;
}
解决方案
他们改变了 Arrays.sort 的排序算法的Java 7，对于分拣对象，Arrays.sort现在使用的算法称为 Timsort 和双支点快速排序的原语。在此更多信息answer.
如果你真的想用旧的，显然你可以设置一个系统属性 java.util.Arrays.useLegacyMergeSort 。
请参阅Java 7的兼容文档。
I created some improvement to QuickSort and decide to test it against Java Arrays.sort().
The results are fascinating:
On Java 6:
My Time / System Time = 74 / 83 = 0.891566265060241 My Time / System Time = 75 / 79 = 0.9493670886075949 My Time / System Time = 75 / 84 = 0.8928571428571429On Java 7:
My Time / System Time = 115 / 70 = 1.6428571428571428 My Time / System Time = 101 / 76 = 1.3289473684210527 My Time / System Time = 102 / 61 = 1.6721311475409837As you can see my algorithm performs better on Java 6, how ever it have a dramatic drop on Java 7 witch I don't understand. May be you can find the reason why?
Edit: How does my algorithm works:
Step 1: Take 3 numbers, sort them, use the middle number as pivot Step 2: Take all the numbers bigger than pivot to the right and all the numbers smaller than pivot to the left, and place pivot in it's final position in the sorted array. This actually implemented in O(N). Step 3: Recursively repeat step 1 and 2 for left and right sides. When you rich sub array smaller than 12 elements use network sort to sort it.My source code
public class QuickSort {
public static void sort(int[] source) {
int buffer[] = new int[source.length];
concatenate(source, buffer, 0, source.length);
}
private static void concatenate(int[] source, int[] buffer, int low, int high) {
int count = high - low;
int lowBuffer = low;
int highBuffer = high;
if (count < 2) {
return;
}
if (count < 12) {
networkSort(source, buffer, low, count);
return;
}
int pivotIndex = bestOfThree(source, low);
int value = source[pivotIndex];
for (int i = low; i < high; i++) {
if (i == pivotIndex) {
continue;
}
if (source[i] < value) {
buffer[lowBuffer] = source[i];
source[lowBuffer] = buffer[lowBuffer];
lowBuffer++;
}
else {
highBuffer--;
buffer[highBuffer] = source[i];
}
}
buffer[lowBuffer] = source[lowBuffer] = value;
for (int i = lowBuffer; i < high; i++) {
source[i] = buffer[i];
}
concatenate(source, buffer, lowBuffer + 1, high);
concatenate(source, buffer, low, lowBuffer);
}
private static int bestOfThree(int[] source, int low) {
int a = low;
int b = a + 1;
int c = a + 2;
int median = -1;
if (source[a] >= source[b] && source[a] >= source[c]) {
if (source[b] < source[c]) {
median = c;
}
else {
median = b;
}
}
else if (source[b] >= source[a] && source[b] >= source[c]) {
if (source[a] < source[c]) {
median = c;
}
else {
median = a;
}
}
else if (source[c] >= source[a] && source[c] >= source[b]) {
if (source[a] < source[b]) {
median = b;
}
else {
median = a;
}
}
return median;
}
private static int[][] networkSort = {
{ 0, 1 },
{ 1, 2, 0, 2, 0, 1 },
{ 0, 1, 2, 3, 0, 2, 1, 3, 1, 2 },
{ 0, 1, 3, 4, 2, 4, 2, 3, 1, 4, 0, 3, 0, 2, 1, 3, 1, 2 },
{ 1, 2, 4, 5, 0, 2, 3, 5, 0, 1, 3, 4, 2, 5, 0, 3, 1, 4, 2, 4, 1, 3, 2, 3 },
{ 1, 2, 3, 4, 5, 6, 0, 2, 3, 5, 4, 6, 0, 1, 4, 5, 2, 6, 0, 4, 1, 5, 0, 3, 2, 5, 1, 3, 2, 4, 2, 3 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 4, 6, 5, 7, 1, 2, 5, 6, 0, 4, 3, 7, 1, 5, 2, 6, 1, 4, 3, 6, 2, 4, 3, 5, 3, 4 },
{ 0, 1, 3, 4, 6, 7, 1, 2, 4, 5, 7, 8, 0, 1, 3, 4, 6, 7, 2, 5, 0, 3, 1, 4, 5, 8, 3, 6, 4, 7, 2, 5, 0, 3, 1, 4, 5, 7, 2, 6, 1, 3, 4, 6, 2, 4, 5, 6, 2, 3 },
{ 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 1, 4, 6, 9, 0, 3, 5, 8, 0, 2, 3, 6, 7, 9, 0, 1, 2, 4, 5, 7, 8, 9, 1, 2, 4, 6, 7, 8, 3, 5, 2, 5, 6, 8, 1, 3, 4, 7, 2, 3, 6, 7, 3, 4, 5, 6, 4, 5 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 0, 2, 4, 6, 8, 10, 1, 2, 5, 6, 9, 10, 0, 4, 3, 7, 1, 5, 6, 10, 4, 8, 5, 9, 2, 6, 0, 4, 3, 8, 1, 5, 6, 10, 2, 3, 8, 9, 1, 4, 7, 10, 3, 5, 6, 8, 2, 4, 7, 9, 5, 6, 3, 4, 7, 8 }
};
private static int tmp;
private static void networkSort(int[] source, int[] buffer, int low, int count) {
int[] networkData = networkSort[count - 2];
for (int i = 0; i < networkData.length; i += 2) {
int index1 = low + networkData[i];
int index2 = low + networkData[i + 1];
if (source[index1] > source[index2]) {
tmp = source[index1];
buffer[index1] = source[index1] = source[index2];
buffer[index2] = source[index2] = tmp;
}
}
}
}
Base testing class
public abstract class Test {
protected int[][] buffer;
private final Random random = new Random();
public int numberOfTests = 100;
public int maxValue = 1000;
public int numberOfItems = 100;
protected void createBuffer() {
buffer = new int[numberOfTests][];
for (int i = 0; i < numberOfTests; i++) {
int[] list = new int[numberOfItems];
addRandomNumbers(list);
buffer[i] = list;
}
}
protected void createBuffer(int...parametes) {
buffer = new int[1][];
buffer[0] = parametes;
}
protected void addRandomNumbers(int[] list) {
for (int i = 0; i < numberOfItems; i++) {
int value = random.nextInt(maxValue);
list[i] = value;
}
}
protected int[][] cloneBuffer() {
int[][] clonedBuffer = new int[numberOfTests][];
for(int i = 0; i < buffer.length; i++){
int[] clonedList = new int[buffer[i].length];
int[] list = buffer[i];
for (int j = 0; j < list.length; j++) {
int element = list[j];
clonedList[j] = element;
}
clonedBuffer[i] = clonedList;
}
return clonedBuffer;
}
public abstract void test();
}
Performance Test
public class PerformanceTest 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() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
QuickSort.sort(list);
}
}
private void testSystem() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
Arrays.sort(list);
}
}
}
Main
public static void main(String[] args) {
PerformanceTest testBasics = new PerformanceTest();
testBasics.numberOfTests = 1000;
testBasics.numberOfItems = 1000;
testBasics.maxValue = 1000000;
testBasics.test(100);
}
解决方案
They changed the sort algorithm of Arrays.sort for Java 7. For sorting objects, Arrays.sort now uses algorithm called Timsort and dual-pivot quicksort for primitives. More info in this answer.
If you really want to use the old one, apparently you can set a system property java.util.Arrays.useLegacyMergeSort.
See Java 7 compatibility documentation.
相关推荐
猜您喜欢
精彩图集
