The use of Java bitmap sorting
- 2020-04-01 01:39:23
- OfStack
The sorting algorithm of container classes in the Java JDK mainly USES insertion sort and merge sort, which may be implemented differently in different versions. The key code is as follows:
@SuppressWarnings("unchecked")
private static void mergeSort(Object[] in, Object[] out, int start,
int end) {
int len = end - start;
// use insertion sort for small arrays
if (len <= SIMPLE_LENGTH) {
for (int i = start + 1; i < end; i++) {
Comparable<Object> current = (Comparable<Object>) out[i];
Object prev = out[i - 1];
if (current.compareTo(prev) < 0) {
int j = i;
do {
out[j--] = prev;
} while (j > start
&& current.compareTo(prev = out[j - 1]) < 0);
out[j] = current;
}
}
return;
}
int med = (end + start) >>> 1;
mergeSort(out, in, start, med);
mergeSort(out, in, med, end);
// merging
// if arrays are already sorted - no merge
if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
System.arraycopy(in, start, out, start, len);
return;
}
int r = med, i = start;
// use merging with exponential search
do {
Comparable<Object> fromVal = (Comparable<Object>) in[start];
Comparable<Object> rVal = (Comparable<Object>) in[r];
if (fromVal.compareTo(rVal) <= 0) {
int l_1 = find(in, rVal, -1, start + 1, med - 1);
int toCopy = l_1 - start + 1;
System.arraycopy(in, start, out, i, toCopy);
i += toCopy;
out[i++] = rVal;
r++;
start = l_1 + 1;
} else {
int r_1 = find(in, fromVal, 0, r + 1, end - 1);
int toCopy = r_1 - r + 1;
System.arraycopy(in, r, out, i, toCopy);
i += toCopy;
out[i++] = fromVal;
start++;
r = r_1 + 1;
}
} while ((end - r) > 0 && (med - start) > 0);
// copy rest of array
if ((end - r) <= 0) {
System.arraycopy(in, start, out, i, med - start);
} else {
System.arraycopy(in, r, out, i, end - r);
}
}
There is a very interesting sorting algorithm in the program called bitmap method. The idea is to use 1 bit to indicate the existence of integers in [0~n-1]. 1 means there is, 0 means there is not. Map a positive integer to a bit collection, and each bit represents the existence of a positive integer mapped to it.
For example, {1,2,3,5,8,13} is represented by the following collection:
1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
The pseudo-code is as follows:
For (i In [0 ~ n - 1)) Bit [I] = 0;
For (i In [0 - n - 1))
If (I in input file)
Bit [I] = 1
For (i In [0 - n - 1))
If (bit [I] = = 1)
The output of I
Try it out with Java code and it works:
public class javaUniqueSort {
public static int[] temp = new int[1000001];
public static List<Integer> tempList = new ArrayList<Integer>();
public static int count;
public static void main(final String[] args) {
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();
for (int i = 1; i <= 1000000; i++) {
firstNum.add(i);
secondNum.add(i);
}
Collections.shuffle(firstNum);
Collections.shuffle(secondNum);
getStartTime();
Collections.sort(firstNum);
getEndTime("java sort run time ");
getStartTime();
secondNum = uniqueSort(secondNum);
getEndTime("uniqueSort run time ");
}
public static List<Integer> uniqueSort(final List<Integer> uniqueList) {
javaUniqueSort.tempList.clear();
for (int i = 0; i < javaUniqueSort.temp.length; i++) {
javaUniqueSort.temp[i] = 0;
}
for (int i = 0; i < uniqueList.size(); i++) {
javaUniqueSort.temp[uniqueList.get(i)] = 1;
}
for (int i = 0; i < javaUniqueSort.temp.length; i++) {
if (javaUniqueSort.temp[i] == 1) {
javaUniqueSort.tempList.add(i);
}
}
return javaUniqueSort.tempList;
}
public static void getStartTime() {
javaShuffle.start = System.nanoTime();
}
public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}
Running time:
java sort run time : 1257737334ns
uniqueSort run time : 170228290ns
java sort run time : 1202749828ns
uniqueSort run time : 169327770ns
If there is duplicate data, the following can be modified:
public class javaDuplicateSort {
public static List<Integer> tempList = new ArrayList<Integer>();
public static int count;
public static void main(final String[] args) {
Random random = new Random();
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();
for (int i = 1; i <= 100000; i++) {
firstNum.add(i);
secondNum.add(i);
firstNum.add(random.nextInt(i + 1));
secondNum.add(random.nextInt(i + 1));
}
Collections.shuffle(firstNum);
Collections.shuffle(secondNum);
getStartTime();
Collections.sort(firstNum);
getEndTime("java sort run time ");
getStartTime();
secondNum = uniqueSort(secondNum);
getEndTime("uniqueSort run time ");
}
public static List<Integer> uniqueSort(final List<Integer> uniqueList) {
javaDuplicateSort.tempList.clear();
int[] temp = new int[200002];
for (int i = 0; i < temp.length; i++) {
temp[i] = 0;
}
for (int i = 0; i < uniqueList.size(); i++) {
temp[uniqueList.get(i)]++;
}
for (int i = 0; i < temp.length; i++) {
for (int j = temp[i]; j > 0; j--) {
javaDuplicateSort.tempList.add(i);
}
}
return javaDuplicateSort.tempList;
}
public static void getStartTime() {
javaShuffle.start = System.nanoTime();
}
public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}
This algorithm still has obvious limitations, such as to know the maximum value in the data, more important is the degree of data density, such as the maximum value of 1000000 and the array size of only 100, the efficiency will decline very significantly... However, the use of bitmaps for sorting is quite impressive. Bitmaps are commonly used to store data, to determine whether a particular data store exists or whether an array is duplicated.