Java 비트맵 정렬 사용 방법
/**
* Performs a sort on the section of the array between the given indices
* using a mergesort with exponential search algorithm (in which the merge
* is performed by exponential search). n*log(n) performance is guaranteed
* and in the average case it will be faster then any mergesort in which the
* merge is performed by linear search.
*
* @param in -
* the array for sorting.
* @param out -
* the result, sorted array.
* @param start
* the start index
* @param end
* the end index + 1
*/
@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);
}
}
예를 들어 {1, 2, 3, 5, 8, 13}은 다음 집합을 사용하여 표시합니다.
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
위조 코드는 다음과 같습니다.
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) output i
자바 코드로 시도해 보니 과연 효율이 좋군요
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");
}
}
：
java sort run time : 1257737334ns
uniqueSort run time : 170228290ns
java sort run time : 1202749828ns
uniqueSort run time : 169327770ns
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");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
