비트 맵 정렬 (비트 맵 기술 응용)
1. 문제 설명
정수 n 보다 크 지 않 은 k 개의 서로 다른 정수 (k < n) 를 정 하고 이 정수 들 을 정렬 합 니 다.본 논문 에서 토론 한 내용 은 구체 적 으로 (제2 판) 의 제1장 을 참조 할 수 있다.
2. 문제 분석
정렬 에 대해 서 는 정렬, 정렬, 빠 른 정렬, 힐 정렬 등 여러 가지 정렬 방법 이 있 습 니 다.모든 서열 에는 서로 다른 용도 가 있다.왜 비트 맵 정렬 이 필요 합 니까?모든 내부 정렬 (상기 언급) 은 모든 정렬 요 소 를 메모리 에 한꺼번에 불 러 와 야 합 니 다.만약 에 1000, 000 개의 정수 가 있 고 모든 정수 4 바이트 가 있다 면 적어도 4000, 000 B 가 약 4MB 의 메모리 공간 이 필요 하 다 는 것 을 의미한다. 만약 에 1MB 의 메모리 공간 만 사용 할 수 있다 면 어떻게 해 야 합 니까?
많은 문제 들 이 통용 되 는 구 해 전략 을 가지 고 있 지만 통용 되 는 것 외 에 문제 의 실제 수요 와 특징 에 따라 맞 춤 형 해결 방안 을 발굴 해 야 한다.이곳 의 특징 은 모든 정수 가 n 보다 크 지 않 고 정수 가 서로 중복 되 지 않 는 다 는 것 이다.이 특징 을 어떻게 이용 합 니까?
비트 맵 기술 을 채택 할 수 있다.비트 맵 기술 이란 문 제 를 비트 문자열 에 투사 하여 비트 문자열 을 처리 한 후에 비트 문자열 을 문제 공간 에 역사 하 는 것 이다.구체 적 으로 보면 배열 이 20 보다 크 지 않 은 요소 배열 [5, 2, 12, 18, 7, 9, 13, 19, 16, 4, 6] 을 정렬 하려 면 이 를 비트 문자열 11001001101000 에 투사 할 수 있다. 그 중에서 1 은 배열 요소 가 나타 난 위치 (가장 높 은 위 치 는 뒤에 있 고 가장 낮은 위 치 는 왼쪽, 이하 0 시작) 를 나타 내 고 낮은 위치 에서 높 은 위치 로 스 캔 하면 얻 을 수 있다.{2, 4, 5, 6, 9, 12, 13, 16, 18, 19} 이렇게 정렬 하면 됩 니 다. 비트 맵 기술 에 따 르 면 1000, 000 개의 반복 되 지 않 는 정수 배열 의 정렬 은 약 1000, 000 b = 0.125MB 메모리 공간 만 필요 합 니 다.
3. 상세 설계
[ 1 ] 입력: 정렬 되 지 않 은 배열, 배열 의 각 수 는 서로 같 지 않 고 특정한 정수 n 보다 크 지 않 으 며 [0, n - 1] 구간 에 조밀 하 게 분포 되 어 있 습 니 다.
[ 2 ] 출력: 정렬 된 배열
[ 3 ] 데이터 구조: 비트 벡터. 비트 맵 정렬 의 관건 은 비트 벡터 의 실현 에 있 습 니 다. 비트 벡터 는 '1 설정', '0 제거', '비트 가 1 인지 테스트' 등 이 있 습 니 다. 실현 측면 에서 하나의 정형 배열 을 사용 하여 실현 할 수 있 습 니 다 (자바 에 서 는 이동, 비트 연산 이 모두 정 수 를 기본 단위 로 하기 때 문 입 니 다).이 는 32 비트 당 한 그룹 임 을 의미 합 니 다. 비트 벡터 길 이 는 32 의 배수 로 프로 그래 밍 하기에 편리 합 니 다. 64 비트 가 있다 고 가정 하면 59 번 째 위치 1. 59 / 32 = 1, 59% 32 = 27; 이것 은 1 조 a [1] 의 27 위 를 배치 해 야 한 다 는 것 을 의미한다. 이 를 실현 합 니 다. 나머지 는 세부 적 인 문제 입 니 다. 예 를 들 어 경계 가 틀 리 지 않도록 하 는 것 입 니 다. 비트 문자열 방향 은 a [p] a [p - 1]. a [1] a [0], p = N / 32, N 은 n 보다 작 지 않 은 32 배수 의 최소 정수 로 규정 되 어 있 습 니 다. a [p] 는 가장 높 은 32 비트 이 고 a [0] 는 가장 낮은 32 비트 입 니 다.
4. 알고리즘 설명
STEP 1: 문제 설명 에 따라 비트 벡터 의 자릿수 를 확정 하고 비트 벡터 bv 를 초기 화 합 니 다.
STEP 2: 배열 의 모든 요소 에 대해 그 수 치 를 위치 로 하고 비트 벡터 에 해당 하 는 위치 1.
STEP 3: 낮은 위치 에서 높 은 위치 로 스 캔 하고 비트 벡터 의 모든 위치 가 1 이면 이 위치의 위치 아래 표 시 를 출력 하여 최종 정렬 배열 의 요소 값 으로 합 니 다.
5. 자바 코드 구현
package datastructure.vector;
/**
* n
*
*/
public class NBitsVector {
private static final int BITS_PER_INT = 32;
private static final int SHIFT = 5;
//
private int[] bitsVector;
//
private int bitsLength;
public NBitsVector(int n) {
int i = 1;
while (i * BITS_PER_INT < n) { i++;}
this.bitsLength = i * BITS_PER_INT;
if (bitsVector == null) {
bitsVector = new int[i];
}
}
/**
* setBit: i
* @param i
*/
public void setBit(int i) {
bitsVector[i >> SHIFT] |= 1 << (i & 0x1f);
}
/**
* clrBit: i
* @param i
*/
public void clrBit(int i) {
bitsVector[i >> SHIFT] &= ~(1 << (i & 0x1f));
}
/**
* testBit: i 1
* @param i
* @return i 1, true, false
*/
public boolean testBit(int i) {
return (bitsVector[i >> SHIFT] & 1 << (i & 0x1f)) != 0;
}
/**
* clr:
*/
public void clr() {
int vecLen = bitsVector.length;
for (int i = 0; i < vecLen; i++) {
bitsVector[i] = 0;
}
}
/**
* getBitsLength:
*/
public int getBitsLength() {
return bitsLength;
}
/**
* i ， 1 。
* @param i i
*/
public String intToBinaryStringWithHighZero(int i) {
String basicResult = Integer.toBinaryString(i);
int bitsForZero = BITS_PER_INT - basicResult.length();
StringBuilder sb = new StringBuilder("");
while (bitsForZero-- > 0) {
sb.append('0');
}
sb.append(basicResult);
return sb.toString();
}
public String toString() {
StringBuilder sb = new StringBuilder("Bits Vector: ");
for (int i = bitsVector.length-1; i >=0 ; i--) {
sb.append(intToBinaryStringWithHighZero(bitsVector[i]));
sb.append(" ");
}
return sb.toString();
}
public static void main(String[] args)
{
NBitsVector nbitsVector = new NBitsVector(64);
nbitsVector.setBit(2);
System.out.println(nbitsVector);
nbitsVector.setBit(7);
nbitsVector.setBit(18);
nbitsVector.setBit(25);
nbitsVector.setBit(36);
nbitsVector.setBit(49);
nbitsVector.setBit(52);
nbitsVector.setBit(63);
System.out.println(nbitsVector);
nbitsVector.clrBit(36);
nbitsVector.clrBit(35);
System.out.println(nbitsVector);
System.out.println("52: " + nbitsVector.testBit(52));
System.out.println("42: " + nbitsVector.testBit(42));
nbitsVector.clr();
System.out.println(nbitsVector);
}
}
package algorithm.sort;
import java.util.Arrays;
import datastructure.vector.NBitsVector;
/**
*
*
*/
public class BitsMapSort {
private NBitsVector nBitsVector;
public BitsMapSort(int n) {
if (nBitsVector == null) {
nBitsVector = new NBitsVector(n);
}
}
public int[] sort(int[] arr) throws Exception {
if (arr == null || arr.length == 0) {
return null;
}
nBitsVector.clr();
int arrLen = arr.length;
for (int i=0; i < arrLen ; i++) {
if (arr[i] < 0 || arr[i] > nBitsVector.getBitsLength()-1) {
throw new Exception(" " + arr[i] + " ， ");
}
if (nBitsVector.testBit(arr[i])) {
throw new Exception(" : " + arr[i] + " ， ！");
}
nBitsVector.setBit(arr[i]);
}
int bitsLength = nBitsVector.getBitsLength();
int count = 0;
for (int i=0; i < bitsLength; i++) {
if (nBitsVector.testBit(i)) {
arr[count++] = i;
}
}
return arr;
}
public static int maxOfArray(int[] arr)
{
int max = arr[0];
for (int i=1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void test(int[] arr)
{
try {
// 63 maxOfArray(arr)
BitsMapSort bms = new BitsMapSort(64);
System.out.println(" ： " + Arrays.toString(arr));
int[] sorted = bms.sort(arr);
System.out.println(" ： " + Arrays.toString(sorted));
}
catch(Exception e) {
System.out.println(e.getMessage());
}
}
public static void main(String[] args)
{
int[] empty = null;
test(empty);
empty = new int[0];
test(empty);
int[] unsorted = new int[] { 15, 34, 46, 52, 7, 9, 5, 10, 25, 37, 48, 13};
test(unsorted);
int[] unsorted2 = new int[] { 15, 34, 46, 52, 7, 9, 5, 7, 25, 37, 48, 13};
test(unsorted2);
int[] unsorted3 = new int[] { 15, 34, 46, 52, 7, 9, 5, 72, 25, 37, 48, 13};
test(unsorted3);
}
}
6. C 소스 프로그램:
/*
* bitvec.c : N * author: shuqin1984 2011-08-31
*/
#include <assert.h>
#define N 10000000
#define M ((N%32==0) ? (N/32) : (N/32+1))
#define SHIFT 5
#define mod32(n) ((n) - (((n) >> SHIFT) << SHIFT))
int bitvec[M]; // N M
int test(int i); // i 1
void set(int i); // i 1
void clear(int i); // i
void clearAll(); //
void show(); //
void printb(int x, int i); // x i
void printbz(int x, int n); // ( n )，
int test(int i)
{
assert(i >= 0);
return (bitvec[i>>SHIFT] & (1 << mod32(i))) != 0;
}
void set(int i)
{
assert(i >= 0);
bitvec[i>>SHIFT] |= (1 << mod32(i));
}
void clear(int i)
{
assert(i >= 0);
bitvec[i>>SHIFT] &= ~(1 << mod32(i));
}
void clearAll()
{
int i;
for (i = 0; i < M; i++) {
bitvec[i] = 0;
}
}
void show()
{
int i = 0;
if (M == 1) {
printbz(bitvec[i], N);
}
else {
int bits = (N%32==0)? 32: (N%32);
printbz(bitvec[M-1], bits);
for (i=M-2; i >=0 ; i--) {
printbz(bitvec[i], 32);
}
}
printf("
");
}
void printb(int x, int i)
{
printf("%c", '0' + ((((unsigned)x) & (1 << i)) >> i));
}
void printbz(int x, int n)
{
int i;
for (i = n-1; i >= 0; i--) {
printb(x, i);
}
}
/*
* bitsort.c:
* author: shuqin1984 2011-8-31 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <limits.h>
#include "bitvec.c"
#define MAX_LEN 10
void bitsort(char* filename);
void bitsortf();
void runtime(void (*f)());
void testdata(int, int);
int randRange(int low, int high);
int main()
{
srand(time(0));
printf("sizeof(int) = %d
", sizeof(int));
printf("RAND_MAX = %d
", RAND_MAX);
printf("INT_MAX = %d
", RAND_MAX);
runtime(bitsortf);
getchar();
return 0;
}
/*
* ， ， output.txt
*/
void bitsort(char* filename)
{
int i;
char buf[MAX_LEN];
FILE* fin = fopen(filename, "r");
if (fin == NULL) {
fprintf(stderr, "can't open file: %s", filename);
exit(1);
}
while (fgets(buf, MAX_LEN, fin)) {
set(atoi(buf));
}
fclose(fin);
// show();
FILE* fout = fopen("output.txt", "w");
if (fout == NULL) {
fprintf(stderr, "can't open file: %s", "output.txt");
exit(1);
}
for (i = 0; i < N; i++) {
if (test(i)) {
fprintf(fout, "%d
", i);
}
}
fclose(fout);
printf("---------- sort successfully ---------------");
printf("
");
}
void bitsortf()
{
bitsort("data.txt");
}
void runtime(void (*f)())
{
printf("runtime ...
");
int scale = 10;
while (scale <= N) {
testdata(scale, N);
clock_t start = clock();
(*f)();
clock_t end = clock();
printf("scale: %d\t cost : %8.4f
", scale, (double)(end-start)/CLOCKS_PER_SEC);
printf("---------------------------------------------------");
printf("
");
scale *= 10;
}
}
/*
* ： max num ， data.txt
*/
void testdata(int num, int max)
{
int i;
assert(num <= max);
FILE* fout = fopen("data.txt", "w");
if (fout == NULL) {
fprintf(stderr, "can't open file: %s", "data.txt");
exit(1);
}
for (i = 0; i < num; i++) {
fprintf(fout, "%d
", (rand()*rand()) % max);
}
fclose(fout);
printf("---------- testdata successfully ---------------");
printf("
");
}
/*
* randRange:
*/
int randRange(int low, int high)
{
assert (high <= low) ;
return rand() % (high-low) + low;
}
7. 추가 설명
비트 맵 기술 은 매우 효과 적 인 구 해 기술 이 라 고 할 수 있 습 니 다. 파일 관리 에 응용 되 었 습 니 다. 그 역할 은 2 분 검색 기술 과 유사 합 니 다. 비트 맵 기술 은 중복 정 수 를 검 측 할 수 있 고 정수 가 부족 합 니 다. 예 를 들 어 43 억 여 개 에서 2 ^ 32 보다 크 지 않 은 무 작위 정수 배열 에서 중복 정 수 를 찾 을 수 있 습 니 다 (서랍 원리 에 따라 반드시 존재 한 다 는 것 을 알 수 있 습 니 다).책 을 읽 을 때 는 문제 의 해결 방안 뿐만 아니 라 그 뒤의 통용 기술 도 깨 달 아야 한다.
만약 문제 가 정수 배열 에 대한 정렬 이 아니 라 일련의 기록 에 대한 정렬 이 라면 기 존 알고리즘 을 어떻게 이용 합 니까? 특정한 함수 로 기 록 된 키 워드 를 계산 하여 서로 중복 되 지 않 는 정수 (이 과정 은 산열 법 과 유사 합 니 다) 를 얻 은 다음 에 비트 맵 기술 로 정수 배열 을 정렬 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
