intro.
randomNumber.txt 라는 텍스트 파일로 7자리 양의 정수 1,000,000 개가 출력된다
- BitSet 클래스를 이용한 1,000,000개 데이터 정렬 ( BitmapSort.java )
데이터 파일인 randomNumber.txt 파일을 읽고, 정렬한 데이터를 sortedNumber.txt 로 출력한다
프로그래밍은 일종의 창작이다. 주어진 언어의 Spec 을 바탕으로 하고 사용자가 원하는 프로그램을 만들어 내는 것이다. 그런 프로그래밍에 가장 필요한건 무엇일까? 물론 언어의 이해정도가 가장 크겠지만 그런 기본기를 갖춘 프로급 위치에서는 프로그램 설계에 구현되는 논리, 방법, 구성 등이 더욱 중요한 지표가 된다
그 동안 여러 권의 자바 관련 책들을 보아 왔지만 자바 언어의 기초에 관련된 책들만 본 것 같다. 중급으로 가는길.. 그 방법은 앞서 언급한 사고력에 바탕을 둔 창작성이지 않을까?
그런 중 '생각하는 프로그래밍' 이란 책을 알게되었고 프로그래밍에 있어서 기초에서 벗어나는 통찰과 창조의 영역을 공부하고 싶었다. 사실상 필연이라고 봐도 될 듯 하다. 그런 지식에 대한 갈망이 이 책을 찾게 되는 이유일지도 모르겠다
column1은 데이터 정렬에 관한 문제이다
문제는 다음과 같다
입력 : 최대 n개의 양의 정수를 포함하는 파일로, 각 숫자는 n보다 작고, n=10^7 이다
어떤 숫자가 두 번 이상 나오는 것은 치명적 에러이다
정수 이외에 관련된 데이터는 없다
출력 : 입력된 정수를 오름차순으로 정렬한 리스트
제약조건 : 메모리를 많아야 대략 1MB 정도 사용할 수 있고, 디스크 공간은 충분하다
실행시간은 최대 몇 분 정도가 될 수 있고, 10초 정도 안에 작업을 끝낼 수 있으면 충분하다
일반적인 데이터 정렬로는 해당 숫자의 크기(bit)가 크고 처리해야할 데이터 수가 많기 때문에 주어진 메모리로는 40번 작업을 해서 정렬해야 한다. 하지만 책에 소개되어진 bitmap 구조를 이용하여 원하는 정렬을 구현한다. 비트맵 데이터 구조는 원소가 중복되지 않고 원소와 관련된 다른 데이터도 없는 촘촘한 유한 집합 이라는 특성을 이용하여 정렬한 것이다
1. 7자리의 중복되지 않는 양의 정수는 999,999 보다 크고 10,000,000 보다 작은 숫자이다
1,000,000 ~ 9,999,999 까지의 숫자 범위가 주어진 양의 정수의 범위가 된다
2. 10,000,000 자리의 2진수를 만든다고 생각한다면 그 자리에 대한 index 값을 이용하여 해당 자리에 값의 유무만 판단하게 되면(중복되지 않으므로) 일정 범위에서 값의 유무를 판단하고 정렬되어진(숫자의 index 이므로) 2진수를 구할 수 있다. 값이 있는 인덱스를 순서대로 취하면 그 인덱스가 원하는 값이 된다
3. 구현한 Java 코드
- 7자리 중복되지 않는 양의 정수 1,000,000개 만들기 ( Number.java )
| // 7자리 양의 정수 랜덤 생성 import java.io.*; import java.util.*; public class Number { public static void main(String[] args) { int k = 1000000; // 만들 숫자 갯수 int n = 7; // 몇자리 세팅 BitSet bitSet = new BitSet(k); // 정렬을 위한 비트셋 bitSet.clear(); // 비트셋 초기화 false 세팅 int kn = (int)((Math.pow(10,n)-1)-(Math.pow(10,n-1)-1)); // 자리수에 맞는 범위값, Math.pow : 제곱 구하기 try { File file = new File("randomNumber.txt"); BufferedWriter writer = new BufferedWriter(new FileWriter(file)); int l = 0; while ( l < k ) { int m = (int)(Math.random()*kn+(Math.pow(10,n-1))); if ( !bitSet.get(m) ) { bitSet.set( m, true ); writer.write(Integer.toString(m)); writer.newLine(); l++; } } writer.close(); } catch (IOException ex) { ex.printStackTrace(); } } } |
|
import java.io.*; import java.util.*; public class BitmapSort { public static void main(String[] args) { int[] num = new int[1000000]; // 데이터를 넣을 배열 생성 BitSet bitSet = new BitSet(10000000); // 정렬을 위한 비트셋 bitSet.clear(); // 비트셋 초기화 false 세팅 try { File myFile = new File("randomNumber.txt"); BufferedReader reader = new BufferedReader(new FileReader(myFile)); // 데이터 파일 읽기 int j=0; String line = null; while ( (line = reader.readLine()) != null ) { StringTokenizer tokenizer = new StringTokenizer(line); num[j] = Integer.parseInt (tokenizer.nextToken() ); bitSet.set(num[j], true); // num[j] 의 값이 bitSet 의 인덱스로 j++; } reader.close(); File file = new File("sortedNumber.txt"); BufferedWriter writer = new BufferedWriter(new FileWriter(file)); // 파일 출력 for ( int k=0 ; k<bitSet.length() ; k++ ) { writer.write(Integer.toString(k)); writer.newLine(); } } writer.close(); } catch (IOException ex) { ex.printStackTrace(); } } } |
