EvbCFfp1XB

problem and my answer.

May 2012

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
* Chapter 13. External Sort - Problem1 - Robert Sedgewick Algorithms in C++<br>
* 読者は、どのように"外部選択"を行うか?ここで、外部選択とは、主記憶に納まらないほど要素数Nが大きいファイルの中でk番目に大きい要素を見つけることである。
*/
public class Chapter13ExternalSortProblem1 {
private static final String ENCODING = "UTF-8";
private static final File FILE = new File(
"Chapter13ExternalSortProblem1.txt");
private static final File TEMPORARYFILE = new File("temporary.txt");

public static void main(String[] args) throws IOException {
long start = System.nanoTime();
int n = 10000;
write(n, FILE, ENCODING);
mergesort(FILE, TEMPORARYFILE, ENCODING);
isSorted(FILE, ENCODING);
int k = 1 + (int) (n * Math.random());
int v = select(k, FILE, ENCODING);
System.out.format("%d %d\n", k, v);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static int select(int k, File file, String encoding)
throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
new FileInputStream(file), encoding));
String s = null;
for (int i = 0; i < k; i++) {
s = reader.readLine();
if (s == null) {
System.out.println("unselect");
return -1;
}
}
return Integer.parseInt(s);
}

private static void isSorted(File file, String encoding) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
new FileInputStream(file), encoding));
int a = Integer.MIN_VALUE;
for (String s = reader.readLine(); s != null; s = reader.readLine()) {
int b = Integer.parseInt(s);
if (a > b) {
System.out.println("unsorted");
break;
}
a = b;
}
}

private static void mergesort(File file, File temporaryfile, String encoding)
throws IOException {
A: for (int n = 1;; n *= 2) {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(
new FileOutputStream(temporaryfile), encoding));
BufferedReader a = new BufferedReader(new InputStreamReader(
new FileInputStream(file), encoding));
BufferedReader b = new BufferedReader(new InputStreamReader(
new FileInputStream(file), encoding));
boolean aHasNext = true;
boolean bHasNext = true;
for (int i = 0; aHasNext && bHasNext; i++) {
bHasNext = next(b, n);
merge(writer, a, b, n);
aHasNext = next(a, n);
if (i == 0 && !aHasNext) {
copy(file, temporaryfile, encoding);
break A;
}
}
copy(file, temporaryfile, encoding);
}
}

private static void copy(File from, File to, String encoding)
throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(
new FileOutputStream(from), encoding));
BufferedReader reader = new BufferedReader(new InputStreamReader(
new FileInputStream(to), encoding));
writer.write("");
for (String s = reader.readLine(); s != null; s = reader.readLine()) {
writer.append(s + "\n");
}
writer.flush();
}

private static boolean next(BufferedReader a, int n) throws IOException {
for (int i = 0; i < n; i++) {
String s = a.readLine();
if (s == null) {
return false;
}
}
return true;
}

private static void merge(BufferedWriter writer, BufferedReader ra,
BufferedReader rb, int n) throws IOException {
int an = 1;
int bn = 1;
String linea = ra.readLine();
if (linea == null) {
return;
}
int a = getInt(linea);
String lineb = rb.readLine();
if (lineb == null) {
bn = n + 1;
}
int b = getInt(lineb);
for (int i = 0; i < 2 * n; i++) {
if (an > n) {
if (bn > n) {
break;
} else {
writer.append(b + "\n");
if (bn < n) {
lineb = rb.readLine();
if (lineb == null) {
bn = n;
}
b = getInt(lineb);
}
bn++;
}
} else {
if (bn > n) {
writer.append(a + "\n");
if (an < n) {
linea = ra.readLine();
if (linea == null) {
an = n;
}
a = getInt(linea);
}
an++;
} else {
if (a <= b) {
writer.append(a + "\n");
if (an < n) {
linea = ra.readLine();
if (linea == null) {
an = n;
}
a = getInt(linea);
}
an++;
} else {
writer.append(b + "\n");
if (bn < n) {
lineb = rb.readLine();
if (lineb == null) {
bn = n;
}
b = getInt(lineb);
}
bn++;
}
}
}
}
writer.flush();
}

private static int getInt(String linea) {
if (linea == null) {
return Integer.MAX_VALUE;
} else {
return Integer.parseInt(linea);
}
}

private static void write(int n, File file, String encoding)
throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(
new FileOutputStream(file), encoding));
for (int i = 0; i < n; i++) {
int d = (int) (Integer.MAX_VALUE * Math.random());
writer.append(d + "\n");
}
writer.flush();
}
}

/**
* Chapter 13. External Sort - Problem3 - Robert Sedgewick Algorithms in C++<br>
* 置き換え選択でNレコードのファイルから最初のランを作り出すときに、最悪の場合が生じるのはどのような状況か?ここで、大きさM(M<N)
* の順位キューを用いるものとする。
*/
public class Chapter13ExternalSortProblem3 {
public static void main(String[] args) {
int N = 100;
int M = 10;
Data[] a = new Data[N];
for (int i = 0; i < a.length; i++) {
a[i] = new Data();
a[i].info = a.length - i;
}
int ai = 0;
PriorityQueueByHeap pq = new PriorityQueueByHeap(M);
for (int i = 0; i < a.length; i++) {
if (!pq.isFull()) {
pq.add(a[i]);
} else {
a[ai++] = pq.replace2(a[i]);
}
}
for (; !pq.isEmpty();) {
a[ai++] = pq.getMin();
}
int count = 0;
for (int i = 0; i < a.length; i++) {
count++;
if (i + 1 < a.length && a[i].info > a[i + 1].info) {
System.out.format("%d,", count);
count = 0;
}
}
System.out.format("%d\n", count);
}

private static class Data {
int info;
boolean nextBlock;

static int compare(Data a, Data b) {
if (a.nextBlock) {
if (b.nextBlock) {
return a.info < b.info ? -1 : a.info > b.info ? 1 : 0;
} else {
return 1;
}
} else {
if (b.nextBlock) {
return -1;
} else {
return a.info < b.info ? -1 : a.info > b.info ? 1 : 0;
}
}
}
}

private static class PriorityQueueByHeap {
private Data[] heap;
private int N;

public PriorityQueueByHeap(int size) {
heap = new Data[size + 1];
N = 0;
}

public void delete(int i) {
heap[i] = heap[N--];
downheap(i);
}

public void print() {
int l = Integer.toBinaryString(N).length();
int sl = 1;
for (int i = 1; i <= N; i++) {
int length = Integer.toString(heap[i].info).length();
if (length > sl) {
sl = length;
}
}
int space = 1;
for (int i = 1, length = 1; i <= N; i++) {
if (length != Integer.toBinaryString(i).length()) {
System.out.println();
length = Integer.toBinaryString(i).length();
int n = 1 << (l - length);
space = n + (n - 1) * sl;
}
System.out.format("%" + sl + "d%s%" + space + "s",
heap[i].info, heap[i].nextBlock ? "." : "", "");
}
System.out.println();
}

private void upheap(int k) {
Data v = heap[k];
heap[0] = new Data();
heap[0].info = Integer.MIN_VALUE;
heap[0].nextBlock = false;
for (; Data.compare(heap[k / 2], v) >= 0; k = k / 2) {
heap[k] = heap[k / 2];
}
heap[k] = v;
}

private void downheap(int k) {
Data v = heap[k];
for (int i = 0; k <= N / 2;) {
i = k + k;
if (i < N && Data.compare(heap[i], heap[i + 1]) > 0) {
i++;
}
if (Data.compare(v, heap[i]) <= 0) {
break;
}
heap[k] = heap[i];
k = i;
}
heap[k] = v;
}

public Data replace(Data v) {
heap[0] = v;
downheap(0);
return heap[0];
}

public Data replace2(Data v) {
Data d = heap[1];
if (v.info < d.info) {
v.nextBlock = true;
}
heap[1] = v;
downheap(1);
if (heap[1].nextBlock) {
for (int i = 0; i < heap.length; i++) {
heap[i].nextBlock = false;
}
}
return d;
}

public void add(Data v) {
heap[++N] = v;
upheap(N);
}

public boolean isEmpty() {
return N == 0;
}

public boolean isFull() {
return N == heap.length - 1;
}

public Data getMin() {
Data v = heap[1];
if (v.nextBlock) {
for (int i = 0; i < heap.length; i++) {
heap[i].nextBlock = false;
}
}
heap[1] = heap[N--];
downheap(1);
return v;
}
}
}

/**
* Chapter 13. External Sort - Problem2 - Robert Sedgewick Algorithms in C++<br>
* 置き換え選択アルゴリズムを実現して、内部記憶の大きさの約2倍の長さのランが作られることを調べてみよ。
*/
public class Chapter13ExternalSortProblem2 {
public static void main(String[] args) {
Data[] a = new Data[100];
for (int i = 0; i < a.length; i++) {
a[i] = new Data();
a[i].info = (int) (a.length * Math.random());
}
int ai = 0;
PriorityQueueByHeap pq = new PriorityQueueByHeap(6);
for (int i = 0; i < a.length; i++) {
if (!pq.isFull()) {
pq.add(a[i]);
} else {
a[ai++] = pq.replace2(a[i]);
}
}
for (; !pq.isEmpty();) {
a[ai++] = pq.getMin();
}
int count = 0;
for (int i = 0; i < a.length; i++) {
count++;
if (i + 1 < a.length && a[i].info > a[i + 1].info) {
System.out.format("%d,", count);
count = 0;
}
}
System.out.format("%d\n", count);
}

private static class Data {
int info;
boolean nextBlock;

static int compare(Data a, Data b) {
if (a.nextBlock) {
if (b.nextBlock) {
return a.info < b.info ? -1 : a.info > b.info ? 1 : 0;
} else {
return 1;
}
} else {
if (b.nextBlock) {
return -1;
} else {
return a.info < b.info ? -1 : a.info > b.info ? 1 : 0;
}
}
}
}

private static class PriorityQueueByHeap {
private Data[] heap;
private int N;

public PriorityQueueByHeap(int size) {
heap = new Data[size + 1];
N = 0;
}

public void delete(int i) {
heap[i] = heap[N--];
downheap(i);
}

public void print() {
int l = Integer.toBinaryString(N).length();
int sl = 1;
for (int i = 1; i <= N; i++) {
int length = Integer.toString(heap[i].info).length();
if (length > sl) {
sl = length;
}
}
int space = 1;
for (int i = 1, length = 1; i <= N; i++) {
if (length != Integer.toBinaryString(i).length()) {
System.out.println();
length = Integer.toBinaryString(i).length();
int n = 1 << (l - length);
space = n + (n - 1) * sl;
}
System.out.format("%" + sl + "d%s%" + space + "s",
heap[i].info, heap[i].nextBlock ? "." : "", "");
}
System.out.println();
}

private void upheap(int k) {
Data v = heap[k];
heap[0] = new Data();
heap[0].info = Integer.MIN_VALUE;
heap[0].nextBlock = false;
for (; Data.compare(heap[k / 2], v) >= 0; k = k / 2) {
heap[k] = heap[k / 2];
}
heap[k] = v;
}

private void downheap(int k) {
Data v = heap[k];
for (int i = 0; k <= N / 2;) {
i = k + k;
if (i < N && Data.compare(heap[i], heap[i + 1]) > 0) {
i++;
}
if (Data.compare(v, heap[i]) <= 0) {
break;
}
heap[k] = heap[i];
k = i;
}
heap[k] = v;
}

public Data replace(Data v) {
heap[0] = v;
downheap(0);
return heap[0];
}

public Data replace2(Data v) {
Data d = heap[1];
if (v.info < d.info) {
v.nextBlock = true;
}
heap[1] = v;
downheap(1);
if (heap[1].nextBlock) {
for (int i = 0; i < heap.length; i++) {
heap[i].nextBlock = false;
}
}
return d;
}

public void add(Data v) {
heap[++N] = v;
upheap(N);
}

public boolean isEmpty() {
return N == 0;
}

public boolean isFull() {
return N == heap.length - 1;
}

public Data getMin() {
Data v = heap[1];
if (v.nextBlock) {
for (int i = 0; i < heap.length; i++) {
heap[i].nextBlock = false;
}
}
heap[1] = heap[N--];
downheap(1);
return v;
}
}
}

import java.util.Arrays;

/**
* Chapter 12. Mergesort - Problem10 - Robert Sedgewick Algorithms in C++<br>
* 大きさが1000のランダムなファイルに対して実験を行い、"自然に存在する順序"を活用するアイデアが改良に結びつかないという本文中にあった意見を検討してみよ
* 。
*/
public class Chapter12MergesortProblem10 {
public static void main(String[] args) {
int[] a = new int[1000000];
random(a);
int[] copy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
mergesortBySortedSubArray(a, 0, a.length - 1);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
isSorted(a, copy);
}

private static void mergesortBySortedSubArray(int[] a, int l, int r) {
int[] b = new int[a.length];
for (;;) {
for (int i = l; i <= r;) {
int p1 = lastIndexOfSortedSubArray(a, i, r);
if (i == l && p1 == r) {
return;
}
int p2 = lastIndexOfSortedSubArray(a, p1 + 1, r);
mergeAB(b, i, p2, a, i, p1, a, p1 + 1, p2);
i = p2 + 1;
}
for (int i = l; i <= r; i++) {
a[i] = b[i];
}
}
}

private static int lastIndexOfSortedSubArray(int[] a, int l, int r) {
for (int i = l + 1; i <= r; i++) {
if (a[i - 1] > a[i]) {
return i - 1;
}
}
return r;
}

private static void mergeAB(int[] c, int cl, int cr, int[] a, int al,
int ar, int[] b, int bl, int br) {
for (int ai = al, bi = bl, ci = cl; ci <= cr; ci++) {
if (ai > ar) {
c[ci] = b[bi++];
} else if (bi > br) {
c[ci] = a[ai++];
} else {
c[ci] = a[ai] <= b[bi] ? a[ai++] : b[bi++];
}
}
}

private static void isSorted(int[] a, int[] copy) {
Arrays.sort(copy);
for (int i = 0; i < copy.length; i++) {
if (a[i] != copy[i]) {
System.out.println("unsorted");
break;
}
}
}

private static void random(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = (int) (a.length * Math.random());
}
}
}

import java.util.Arrays;

/**
* Chapter 12. Mergesort - Problem9 - Robert Sedgewick Algorithms in C++<br>
* 再帰版マージソートで、配列を使って、2ウェイ併合の代わりに3ウェイ併合を使うものを考えよ。
*/
public class Chapter12MergesortProblem9 {
public static void main(String[] args) {
int[] a = new int[1000000];
random(a);
int[] copy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
mergesort3way(a, new int[a.length], 0, a.length - 1);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
isSorted(a, copy);
}

private static void mergesort3way(int[] a, int[] b, int l, int r) {
if (r <= l) {
return;
}
int p1 = (l + l + r) / 3;
int p2 = (l + r + r) / 3;
mergesort3way(a, b, l, p1);
mergesort3way(a, b, p1 + 1, p2);
mergesort3way(a, b, p2 + 1, r);
mergeABC(b, l, r, a, l, p1, a, p1 + 1, p2, a, p2 + 1, r);
for (int i = l; i <= r; i++) {
a[i] = b[i];
}
}

private static void mergeABC(int[] d, int dl, int dr, int[] a, int al,
int ar, int[] b, int bl, int br, int[] c, int cl, int cr) {
for (int ai = al, bi = bl, ci = cl, di = dl; di <= dr; di++) {
if (ai > ar) {
if (bi > br) {
d[di] = c[ci++];
} else if (ci > cr) {
d[di] = b[bi++];
} else {
d[di] = b[bi] <= c[ci] ? b[bi++] : c[ci++];
}
} else if (bi > br) {
if (ci > cr) {
d[di] = a[ai++];
} else {
d[di] = a[ai] <= c[ci] ? a[ai++] : c[ci++];
}
} else if (ci > cr) {
d[di] = a[ai] <= b[bi] ? a[ai++] : b[bi++];
} else {
d[di] = a[ai] <= b[bi] ? a[ai] <= c[ci] ? a[ai++] : c[ci++]
: b[bi] <= c[ci] ? b[bi++] : c[ci++];
}
}
}

private static void isSorted(int[] a, int[] copy) {
Arrays.sort(copy);
for (int i = 0; i < copy.length; i++) {
if (a[i] != copy[i]) {
System.out.println("unsorted");
break;
}
}
}

private static void random(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = (int) (a.length * Math.random());
}
}
}

このページのトップヘ