[JAVA] Aiming for a practical radix sort
Aiming for a practical radix sort
As a fast sort algorithm, [Count Sort](https://qiita.com/drken/items/44c60118ab3703f7727f#8-%E8%A8%88%E6%95%B0%E3%82%BD%E3%83%BC % E3% 83% 88-% E3% 83% 90% E3% 82% B1% E3% 83% 83% E3% 83% 88% E3% 81% AF% E9% 87% 8D% E8% A6% 81% I think many people know E3% 81% AA% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0). Count sorting involves scrutinizing the contents of an array, counting into an index array (bucket) for the value of the contents, and then writing back the contents of that bucket to the array. Assuming a size of $ n $, the amount of calculation of $ O (n) $ will complete the sort. The average complexity of a Quicksort named Fast is $ O (n \ log {n}) $, so it's a faster sort. However, there is a bottleneck that if the value that appears in the array is large, you will need a bucket for that maximum value. If the maximum value in the array is 100,000, the size of the bucket will also be 100,000.
Radix sort (https://qiita.com) to solve the problem of radix sort bucket size and the lack of versatility of having to change the size of the bucket created by the maximum value. / drken / items / 44c60118ab3703f7727f # 8-3-% E5% 9F% BA% E6% 95% B0% E3% 82% BD% E3% 83% BC% E3% 83% 88-radix-sort) Has been done. In radix sort, pay attention to the fact that the value is made up of multiple "digits", and repeat the counting sort for each digit. At this time, the trick is to sort in order from the last digit. The number of buckets is OK as long as it appears in the digits.
A commonly used int is 32 bits, so if you divide it into 8 bits, you can think of an int as a 4-digit 256-ary number. For this reason, when programming radix sort, it is often 8 bits at a time.
Since the amount of radix sort is $ O (n * number of digits)
Another problem with radix sort is that it uses a separate memory that is the same size as the original array. If you code the radix sort obediently, you will use a one-way list such as Vector or ArrayList in the bucket, but since this one-way list will have all the contents of the original array. , It consumes memory that much. Also, the method of counting only in the bucket, finding the output position of the array from the count, and relocating the value in another array also consumes memory. Using the same amount of memory as the original array is a little hesitant when the array size is hundreds of thousands. So, first of all, do not use another memory (this is the In-place algorithm % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)) Let's consider a radix sort algorithm.
Prerequisites
--The program uses Java. --The values that can be sorted are positive ints (not considering negative numbers). The number of digits can be any number as long as it is in the range of int. --Sort in ascending order.
In-place radix sort concept
Not using another memory means destroying the original array and using it as it is as the sort result. In count sort and radix sort, once you get one array from the beginning, you will not use that array index anymore, so let's delete it. And instead, add a value to the bucket. This way, the total amount of memory will not change. Also, when the scrutiny is over, simply connect the buckets and that will be the sort result.
To achieve this idea, the original array must be a one-way list, such as a Vector or ArrayList. I looked at the API documentation for Vector and ArrayList when trying to write a program in Java, but it seems that there is no function to simply connect one-way links (?) So I decided to write a one-way link myself.
data structure
First, define the original data structure. Here, I chose the class name TestGoods and tried to have the product name and price as fields. Sorting will be done by price value. Add the field next for one-way links to this original data structure.
TestGoods.java
/**Product Class(test) */
public class TestGoods {
public int price; ///price
public String name; ///product name
public TestGoods next; ///One-way link to the next TestGoods
/**constructor*/
public TestGoods(int price) {
this.price = price;
next = null;
}
}
Since it is for testing, it is accessible publicly without getters and setters. The constructor is also only for the price (that is, name is just a decoration).
Array class (one-way list)
Next, create an array class TestGoodsArray for TestGoods. The method creates only the minimum required, add (), clear () and connect (). There is no get (), and you can directly touch start etc. (It's bad manners). I won't use it this time, but I also created a size field.
TestGoodsArray.java
/**Array of TestGoods*/
public class TestGoodsArray {
public TestGoods start; //Start of one-way link object
public TestGoods last; //The last object
public int size;
/**constructor*/
public TestGoodsArray() {
clear();
}
/**Empty the contents*/
public void clear() {
start = null;
last = null;
size = 0;
}
/**Add element*/
public boolean add(TestGoods goods) {
size++;
if (start == null) {
start = goods;
last = goods;
return true;
}
last.next = goods; //Connect links
last = goods;
return true; // (For the time being, Collection.According to the general rules of add)
}
/**Connect elements*/
public void connect(TestGoodsArray link) {
if (link == null) { return; }
if (start == null) {
start = link.start;
last = link.last;
size = link.size;
return;
}
size += link.size;
last.next = link.start;
last = link.last;
}
}
Radix sort part
The substance of sorting is simple. As explained above, the int is separated by 8 bits, so the bucket size is 256. I used bitRadixSort as the file name because I used bit delimiters as digits, but wasn't it awkward? The return value of the sort is the processing execution time (nanoseconds).
Instead of always checking all four digits in any array, I checked the maximum value in the first scrutiny and tried to reduce the number of loops if the upper digit was not used. This reduced the processing time to about 1/6 for arrays that only show single digit values. The source of the part that finds the maximum value only at the beginning is ugly (I wrote two similar loops because it seemed to be slow when judging the condition in the loop), but please forgive me for the time being.
BitRadixSort.java
/**
*Radix sort (treat int as 4 digits every 8 bits)
*It does not take up much memory compared to general radix sort.
*The price is to rewrite the original array.
* */
public class BitRadixSort {
TestGoodsArray[] bucket = new TestGoodsArray[256]; ///Digit bucket
/**constructor*/
public BitRadixSort() {
for (int i = 0; i < 256; i++) {
bucket[i] = new TestGoodsArray();
}
}
/**
* @param array The array you want to sort. The array is rewritten directly.
* @return Time taken for sorting(nano seconds)
*/
public long sort(TestGoodsArray array) {
long stTime = System.nanoTime(); //For processing measurement
int bitShift = 0;
TestGoods link;
int maxVal = Integer.MIN_VALUE;
int i;
int cnt = 4; //Maximum number of check digits= 4
do {
//Clear bucket
for (i = 0; i < 256; i++) {
bucket[i].clear();
}
link = array.start; //From the beginning of the array
//Put in a bucket for the digit of the value
if (cnt == 4) {
//Find the maximum value only at the beginning of the loop. Also, you don't have to do bitShift at the beginning of the loop.
do {
int a = link.price;
if (a > maxVal) { maxVal = a; }
TestGoods linkOld = link;
bucket[a & 255].add(linkOld); //Put in a bucket of digits
link = link.next; //To the next link
linkOld.next = null; //Cut the link in the bucket
} while (link.next != null);
} else {
//Second and subsequent loops
do {
int a = link.price;
TestGoods linkOld = link;
bucket[(a >> bitShift) & 255].add(linkOld); //Put in a bucket of digits
link = link.next; //To the next link
linkOld.next = null; //Cut the link in the bucket
} while (link.next != null);
}
//Connect the buckets to make an array
array.clear(); //array is empty once
for (i = 0; i < 256; i++) {
if (bucket[i].start != null) {
array.connect(bucket[i]);
}
}
array.last.next = null; //Just in case
bitShift += 8; //To the next 8 bits
if (cnt == 4) { //If it is the first loop, reduce the number of loops by the maximum value
if ((maxVal & 0xff000000) == 0) {
cnt--;
if ((maxVal & 0xff0000) == 0) {
cnt--;
if ((maxVal & 0xff00) == 0) {
cnt--;
}
}
}
}
} while (--cnt > 0);
return System.nanoTime() - stTime; //Returns the time taken
}
}
As you can see from this source, new has never been used during sorting. It's just a link break. This seems a little early.
Main class for operation verification
The last is the main class for operation verification. After sorting, we are testing if the values are aligned correctly (in ascending order). I'm also trying Collections.sort for a time comparison. According to the API documentation, the algorithm of Collections.sort Is modified [Merge Sort](https://qiita.com/drken/items/44c60118ab3703f7727f#5-%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3% 83% BC% E3% 83% 88-on-log-n). The values to be sorted are randomly generated, but the same random values are used in radix sort and Collections.sort so that there is no difference between the values.
BitRadixTest.java
import java.util.*;
public class BitRadixTest {
static final int N = 10000; ///Array size
static final int VARMAX = 0x01000000; ///Maximum possible value of the contents of the array
/** main */
public static void main(String[] args) {
int i;
TestGoodsArray array_Radix = new TestGoodsArray(); //Allocate an array for BitRadix sort
ArrayList<TestGoods> array_Csort = new ArrayList<TestGoods>(N); // Collections.Allocate an array for sort
Random rnd = new Random();
//Creating test data(Fill with a random value greater than or equal to 0 and less than VARMAX)
for (i = 0; i < N; i++) {
int val = rnd.nextInt(VARMAX);
array_Radix.add(new TestGoods(val)); //Set the same value in two test arrays
array_Csort.add(new TestGoods(val));
}
// BitRadix sort
BitRadixSort radix = new BitRadixSort();
long time_bitRadix = radix.sort(array_Radix);
// Csort
long stTime = System.nanoTime();
Collections.sort(array_Csort, new Comparator<TestGoods>() {
public int compare(TestGoods obj1, TestGoods obj2) {
return obj1.price - obj2.price;
}
});
long time_Csort = System.nanoTime() - stTime;
//Data validation
int lastVal = Integer.MIN_VALUE;
TestGoods link = array_Radix.start;
do {
int val = link.price;
if (val < lastVal) {
System.out.println("\nError !! (last=" + lastVal + ", val=" + val);
}
//System.out.print(val + ", "); //Uncomment if you want to see the contents of the array
lastVal = val;
link = link.next;
} while (link != null);
//System.out.println(""); //Uncomment if you want to see the contents of the array
System.out.println("Radix time = " + time_bitRadix + " ns");
System.out.println("Arrays time = " + time_Csort + " ns");
}
}
Execution result
Comparing the execution time with Collections.sort when the maximum value is 0x10000000 (that is, 4 digits in 8-bit radix), it is as follows in my environment (due to the randomness of the value). The execution time changes every time, so this is just an example).
| Array size | Radix sort | Collections.sort |
|---|---|---|
| 100 | 171262 | 948590 |
| 1000 | 567246 | 3036774 |
| 10000 | 4531319 | 17188987 |
| 100000 | 30454387 | 75877154 |
What! The result is that radix sort is faster in all cases, regardless of the array size. If you set the maximum value to 200 (that is, one digit in 8-bit radix), the array size is 100 for 1/2 and 100000 for 1/6. In other words, as far as positive integers are concerned, this algorithm seems to be able to sort faster than the Java library. While the time measurement of Collections.sort includes the generation of classes for comparison operations, there is a difference that the bucket generation of radix sort is outside the measurement time, but if the array size is 100,000, it may be an error. I think. It was also crazy to add a one-way list to the data structure.
home work
Homework # 1: Dealing with negative numbers
This BitRadixSort assumes that all values to be sorted are positive integers. To accommodate negative numbers, when connecting links at the end of the 4th digit sort, connect the buckets 128-255 first, then 0-127. is. This is because the int representation is two's complement and the most significant bit is a negative symbol.
Homework # 2: Generalization of the TestGoodsArray class
The TestGoodsArray class doesn't even have get (), so it's better to implement it. You need to go through the links to get the i-th element. It is also necessary to handle the error when there is no i-th. Also, it would be inconvenient if there was no iterator for sequentially fetching objects from the array. (Maybe just using ArryList.addAll () to join the links will give you some speed, unverified)
Homework # 3: Dealing with common objects
This time I put the one-way link field directly in TestGoods, but I would like to be able to sort this even with common objects. However, I find it quite difficult to be able to sort by Integer [] array. Instead of just pulling the one-way link out, you have to give the sort program's arguments what fields to sort by.
By the way, not only sorting in ascending order but also in descending order is possible only by reversing the way the buckets are connected. However, there is no choice but to make it possible to specify the reverse order with the argument of sort ().
At this point, I think many people can use it as a library that can sort ints in a short time. However, as you can see from the above source, I am immature as a programmer, so I would like to ask an excellent person including other customizations.
Homework # 4: Dealing with decimal points
The single-precision floating-point number format float in Java has a size of 32 bits. This format is [IEEE 754](https://ja.wikipedia.org/wiki/%E5%8D%98%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95 % E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0 # IEEE_754_% E3% 81% A7% E3% 81% AE% E5% 8D% 98% E7% B2% BE % E5% BA% A6% E6% B5% AE% E5% 8B% 95% E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0% E3% 81% AE% E5 It is specified by% BD% A2% E5% BC% 8F: _binary32) and consists of 1 bit of code, 8 bits of exponent part, and 23 bits of mantissa part.
Since the exponent part is higher than the mantissa part, even float should be sorted by the exact same algorithm as radix sort if it can be obtained as 4 bytes by some method. In that case, the processing speed can be expected to be reasonably fast. Double-precision floating-point numbers have 64 bits, so I imagine that radix sort will be slow.