『プログラミング珠玉』第二章:ああ!アルゴリズム——左回転&&変位語

この章ではアルゴリズムの役割について説明します.「難しいように見える問題にも簡単な、思いがけない答えがあります.」プログラミングの前、中和した後に真剣に考えたいプログラマーは、この霊光を捉える機会があります.
文章は3つの問題から展開して、私は一人で先に考えて、解決方法はすべて比較的に非効率で、空間を浪費して時間を浪費することを発見しました.
a.最大40億個のランダム配列を含む32ビット整数のシーケンスファイルを指定し、ファイルにない32ビットの整数(ファイルに少なくとも1つ欠けている数はなぜですか?232>40億ドルなので少なくとも1つ欠けています)を見つけます.十分なメモリがある場合、この問題をどのように解決しますか?外部の「一時」ファイルがいくつかある場合、数百バイトのメモリしかありませんが、この問題を解決するにはどうすればいいですか?
b.n元の1次元ベクトルをi個の位置に左に回転させる.例えば、n=8、i=3のとき、ベクトルabcdefghabcはdefghabcに回転する.簡単なコードは、n元の中間変数を使用して、nステップ内でこの作業を完了します.数十バイトの余分なメモリスペースだけを使って、nに比例する時間でベクトルの回転を完了できますか?
c.英語辞書を1つ与え、その中のすべての変位語の集合を探し出す.たとえば、「pots」,「stop」と「tops」は互いに変位語であり、各単語は他の単語のアルファベットの順序を変えることで得ることができるからである.
a問題については,第一時間に「二分探索」という方法を考えるべきである.log n時間内にシーケンスファイルの検索を完了します.しかし,順序が前提であるため,これも二分探索の弊害である.非ソートの整数をソートするには、少なくともnの比例時間が必要です.この問題で述べた「二分検索」は、その章が「二分検索」の検証に言及されているため、第4章で実現します.2番目の質問では、数百バイトのメモリしかない場合は、前章で説明したビットマップストレージの方法を使用して40億個の整数を格納できます.
b問題については、私は最初に問題に言及した方法を実現することを考えますが、非常に効果的ではありません.文章の中で3つの方法に言及した(私は2つを実現し、3つ目は比較的簡単だ)
各メソッドの回転の実行時間を記録する抽象クラスがあります.

package ckj.chapter2.swap;

public abstract class Rotation {
	public char[] m_input;
	public String m_rotname;
	public int m_length;
	public int m_rotdist;
	
	public Rotation(String input,int rotdist){
		this.m_input = input.toCharArray();
		this.m_length = input.length();
		this.m_rotdist = rotdist;
	}
	
	public abstract void rotate();
	
	/**
	 * the cost time of the rotation
	 */
	public void rotCost(){
		//printChar("before----->");
		long t1 = System.currentTimeMillis();
		rotate();
		long cost = System.currentTimeMillis() - t1 ;
		System.out.println("The cost of "+this.m_rotname+" :  " + cost);
		//printChar("after----->");
	}
	
	/**
	 * print out the char array with the string name before
	 * @param str
	 */
	private void printChar(String str){
		System.out.println(str);
		for(int i = 0 ; i < this.m_length ; i ++){
			System.out.print(this.m_input[i]);
		}
		System.out.println();
	}

}

第1の方法は、本の言い方では、x[0]を一時変数tに移動し、x[i]からx[0]に移動し、x[2 i]からx[i]に移動するなど、x[0]の要素を取るまで、このときtから値を取ってプロセスを終了するように変更するテクニックがある.

package ckj.chapter2.swap;

public class MagicRotate extends Rotation {

	public MagicRotate(String input,int rotdist){
		super(input,rotdist);
		this.m_rotname = "Magic Rotation";
	}
	@Override
	public void rotate() {
		if (this.m_rotdist == 0 ) return;
		for ( int i = 0 ; i < gcd(this.m_rotdist,this.m_length) ; i ++){
			/* move i-th values of blocks */
			char t = m_input[i];
			int j = i,k ;
			while(true){
				k = j + m_rotdist ;
				if ( k >= m_length )
					k -= m_length ;
				if (k == i)
					break;
				m_input[j] = m_input[k];
				j = k;
			}
			m_input[j] = t;
		}
	}

	/**
	 * To find the greatest common divisor between i & j
	 * @param i 
	 * @param j
	 * @return the greatest common divisor
	 */
	private int gcd(int i, int j) {
		if ( i < j) return gcd(j,i);
		if ( i%j == 0 ) return j;
		while (i != j){
			return gcd(i%j,j);
		}
		return 0;
	}
}

の第2の方法はブロック回転である.回転は変数abを交換し,変数baを得る.aがbより短い場合はbをbに分ける
lとb
r,使
b
rはaと同じ長さを有し、交換aとbrはbrを得る
bl a、そして最後にbr blを交換し、(長さが異なる場合は上記の手順を繰り返す)、最後に結果bl br aを得ることができる.

package ckj.chapter2.swap;

public class MagicRotate extends Rotation {

	public MagicRotate(String input,int rotdist){
		super(input,rotdist);
		this.m_rotname = "Magic Rotation";
	}
	@Override
	public void rotate() {
		if (this.m_rotdist == 0 ) return;
		for ( int i = 0 ; i < gcd(this.m_rotdist,this.m_length) ; i ++){
			/* move i-th values of blocks */
			char t = m_input[i];
			int j = i,k ;
			while(true){
				k = j + m_rotdist ;
				if ( k >= m_length )
					k -= m_length ;
				if (k == i)
					break;
				m_input[j] = m_input[k];
				j = k;
			}
			m_input[j] = t;
		}
	}

	/**
	 * To find the greatest common divisor between i & j
	 * @param i 
	 * @param j
	 * @return the greatest common divisor
	 */
	private int gcd(int i, int j) {
		if ( i < j) return gcd(j,i);
		if ( i%j == 0 ) return j;
		while (i != j){
			return gcd(i%j,j);
		}
		return 0;
	}
}

3つ目の方法は求逆方法です.abから、まずaに対してarを求めて、更にbに対してbrを求めて、最後にarbr全体に対してrを求めるこの方法は比較的に実現しやすくて、少し遅い時補充します.
最後に呼び出されたメイン関数MainClass.java

package ckj.chapter2.swap;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class MainClass {

	private static final int _SIZE = 1000000;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[] inputchar = new char[_SIZE];
		/* produce a string repeated 123...789123...789123...789123... totally _SZIE digits  */
		for ( int i = 0 ; i < _SIZE ; i ++)
			inputchar[i] = (char)(i%9+49);
		String input = new String(inputchar);
		
		/* write the string to rotate in a file named "rotationString.txt" */
		writeFile(input,false);
		
		for (int rotdist = 1; rotdist < 50; rotdist++) {
			System.out.println("No. " +rotdist+" ----->");
			Rotation mr = new MagicRotate(input, rotdist);
			mr.rotCost();
			//writeFile(new String(mr.m_input),true);
			mr = new BlockRotate(input, rotdist);
			mr.rotCost();
			//writeFile(new String(mr.m_input),true);
		}
	}

	private static void writeFile(String input,boolean flag) {
		try {
			File file = new File("rotationString.txt");
			FileOutputStream fos = new FileOutputStream(file,flag);
			OutputStreamWriter osw = new OutputStreamWriter(fos);
			BufferedWriter bw = new BufferedWriter(osw);
			bw.write(input);
			bw.newLine();
			bw.newLine();
			bw.close();
			osw.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

c問題に対して、使う思想は“標識”です.コンテンツを直接検索するのではなく、タグでデータをタグ付けします.例えば単語ここでmississippi識別子は「i 4 m 1 p 2 s 4」と書くことができ、それぞれアルファベットが出現した回数を表し、アルファベットは昇順に並べ替える.

package ckj.chapter2.words;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class WordManipulation {
	private Map<String, List<String>> result ;
	private String[] wordInput;
	
	public WordManipulation(String[] word){
		this.wordInput = word;
	}
	
	/**
	 * string sort to find a lable like (mississippi,i4m1p2s4)
	 * @param word The string to be sorted
	 * @return the string sorted
	 */
	private String sort(String word){
		Map<Character,Integer> map = new TreeMap<Character,Integer>();
		for ( int i = 0 ; i < word.length() ; i ++ ){
			char temp = word.charAt(i);
			if ( map.get(temp) == null){
				map.put(temp, 1);
			} else {
				int value = map.get(temp);
				map.put(temp, ++value);
			}
		}
		return map.toString();
	}
	
	/**
	 * squash the same label into a ArrayList 
	 * @param map
	 */
	private void squash(Map<String,String> map){
		result = new TreeMap<String, List<String>>();
		Set<Map.Entry<String,String>> entrySet = map.entrySet();
		for (Map.Entry<String, String> entry:entrySet){
			String strKey = entry.getKey();
			String strValue = entry.getValue();
			System.out.println(strKey+" ----> "+ strValue);
			List<String> resultList;
			if (result.get(strValue) == null){
				resultList = new ArrayList<String>();
				
			} else {
				resultList = result.get(strValue) ;
			}
			resultList.add(strKey);
			result.put(strValue, resultList);
		}
	}
	
	/**
	 * calculate the anagram
	 */
	public void doCalculate(){
		Map<String,String> temp = new TreeMap<String,String>();
		for(int i = 0 ; i < this.wordInput.length ; i ++){
			temp.put(this.wordInput[i], sort(this.wordInput[i])) ;
		}
		squash(temp);
		print();
	}
	
	private void print(){
		System.out.println(result.values());
	}

}

最後のメイン関数は、コンソールで目的の単語を入力することで、すべての変位語を見つけることができます.「over」で終わる単語として入力します.
ファイルの読み書きjava . 入力した単語をwordsに格納します.txtのファイルでは、以降の実行で、主関数のwfをcreateWordsFile()文コメントは、単語を入力しなくてもいいです.

package ckj.chapter2.words;

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

public class WordsFile {
	private String fileName ;
	public WordsFile(){
		this("words.txt");
	}
	public WordsFile(String fileName){
		this.fileName = fileName;
	}
	private void createWordFile(String fileName){
		System.out.println("input your words you want to find the anagram (with typing 'over' to end):");
		try {
			File file = new File(fileName);
			FileOutputStream fos = new FileOutputStream(file);
			OutputStreamWriter osw = new OutputStreamWriter(fos);
			BufferedWriter bw = new BufferedWriter(osw);
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String s;
			while(!(s = br.readLine()).equalsIgnoreCase("over")){
				bw.write(s);
				bw.newLine();
			}
			bw.flush();
			br.close();
			bw.close();
			osw.close();
			fos.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public void createWordFile(){
		createWordFile(this.fileName);
	}
	
	private String[] readWordFile(String fileName){
		
		try {
			File file = new File(fileName);
			FileInputStream fis = new FileInputStream(file);
			InputStreamReader isr = new InputStreamReader(fis);
			BufferedReader br = new BufferedReader(isr);
			String s ;
			String result = "";
			while((s=br.readLine())!=null){
				result +=  s +" " ;
			}
			System.out.println("result---->"+result);
			br.close();
			isr.close();
			return result.split(" ");
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
		
	}
	
	public String[] readWordFile(){
		return this.readWordFile(this.fileName);
	}
}

メイン関数はMainClassを呼び出します.java

package ckj.chapter2.words;

public class MainClass {

	public static void main(String[] args) {
		WordsFile wf = new WordsFile();
		/*  barring it's the first time to run this program , you should run the next code  .  */
		wf.createWordFile();
		//
		WordManipulation wm = new WordManipulation(wf.readWordFile());
		wm.doCalculate();
	}

}

この章の内容は主に2つの「二分探索」の効率化と「標識」等価関係の使用である.