第 7 回 前半のまとめとさまざまなテクニック

これは、単語ごとに集計を行うので、連想配列として使用できる Map 系のデー タ構造を使います。 さらに、アルファベット順に整列するので java.util.TreeMap を使用します。

プログラムは単語を取り出すごとに、その単語の連想配列を呼び出して 1 加 算するというものです。 単語のパターンは java.util.regex.Pattern により指定します。 そして、この Pattern オブジェクトに対して、 matcher メソッドで Matcher オブジェクトを作成します。 この時、 matcher メソッドの引数は java.lang.CharSequence となっている ため、 java.io.InputStream や java.io.Reader ではなく java.lang.String オブジェクトで与えます。 得られた、 Matcher オブジェクトに関しては、 find メソッドで検索し、 group メソッドで文字列を取り出します。

import java.io.*;
import java.util.*;
import java.util.regex.*;
class Rei {
    public static void main(String[] arg) throws IOException {
	final BufferedReader br = new BufferedReader(
			     new InputStreamReader(System.in));
	final TreeMap<String,Integer> hindo = new TreeMap<>();
	final Pattern word = Pattern.compile("\\p{Alpha}\\p{Alnum}*");

	String line;
	while((line = br.readLine())!=null){
	    Matcher m = word.matcher(line);
	    while(m.find()){
		if(hindo.containsKey(m.group())){
		    hindo.put(m.group(),hindo.get(m.group())+1);
		}else{
		    hindo.put(m.group(),1);
		}
	    }
	}
	for(Map.Entry<String,Integer> e : hindo.entrySet()){
	    System.out.println(e.getKey()+": "+e.getValue());
	}
    }
}

これは、単語ごとに集計を行うので、連想配列として使用できるディクショナリのデー タ構造を使います。

プログラムは単語を取り出すごとに、その単語の連想配列を呼び出して 1 加 算するというものです。 単語のパターンを re.compile でコンパイルし変数 pattern にオブジェクト として収めます。 そして、このオブジェクトに対して、 finditer メソッドでマッチする部分を 順に取り出す イテレータを作成します。 得られたイテレータで順に取り出すオブジェクトに対して、 group メソッドで文字列を取り出します。

import re

hindo = {}
pattern = re.compile(r"[a-zA-Z][a-zA-Z0-9]*")
try:
    while True:
        line = input()
        m = pattern.finditer(line)
        for i in m:
            word = i.group()
            if word in hindo:
                hindo[word] += 1
            else:
                hindo[word] = 1
except EOFError:
    pass
for k,v in sorted(hindo.items()):
    print("{0}: {1}".format(k,v))

Thread の基本的な作り方は次の通りです。

1. java.lang.Thread を継承したクラスを作り、 public void run() メソッドを 実装する。
2. 作成したクラスのオブジェクトを作り、 start() メソッドを呼び出す。

さて、Thread の基本的な作り方には次の2通りがあります。

1. threading.Thread クラスを継承する方法
2. threading.Thread に関数を与えてオブジェクトを作る方法
1. threading.Thread を継承したクラスを作り、run() メソッドを 実装する。
2. 作成したクラスのオブジェクトを作り、 start() メソッドを呼び出す。

なお、 Java は多重継承ができないため、この作り方では特定のサブクラスを スレッド化できません。 そのため、 Thread を継承する代わりに、 java.lang.Runnable インターフェ イスを実装する方法があります。

1. java.lang.Runnable を実装したクラスを作る。 つまり、 public void run() メソッドを実装する。
2. 作成したクラスのオブジェクトを作り、 さらに java.lang.Thread のコンス トラクタに与えて Thread のオブジェクトを作る。
3. Thread の start() メソッドを呼び出す。

class A{
}
class B extends A implements Runnable {
    public B(){
	super();
    }
    @Override
    public void run(){
	System.out.println("This is B");
    }
}
class C extends A implements Runnable {
    public C(){
	super();
    }
    @Override
    public void run(){
	System.out.println("This is C");
    }
}
class Rei {
    public static void main(String[] arg){
	final Thread[] tarray = new Thread[2];
	tarray[0] = new Thread(new B());
	tarray[1] = new Thread(new C());
	for(Thread t : tarray){
	    t.start();
	}
    }
}

なお、この方法では、 Thread のメンバ変数を実装時に使えません。 但し、 sleep などは、 Thread のスタティックな関数なので Thread.sleep() 使用できます。

なお、クラスにせずに通常のメソッドを並列化する方法もあります。 この場合は、関数名は何でも良いです。

import threading
import time

max = 100
sb=""
def run():
    global sb
    for i in range(1,max):
        time.sleep(0.001)
        sb += "{0} ".format(i)
th1 = threading.Thread(target=run)
th2 = threading.Thread(target=run)
th1.start()
th2.start()
th1.join()
th2.join()
print(sb)

次に、このプログラムの実行時に EOF を送ると、すべてのスレッドを止めるこ とを考えます。 このために interrupt を各スレッドで呼び出し、各スレッドで処理することを考えます。 このため、すべてのスレッドを管理し、動作しているスレッドのみに次々と interrupt を呼び出す方法も考えられます。 しかし、ここでは java.lang.ThreadGroup クラスを使うことを考えます。 Thread を作ると きに ThreadGroup オブジェクトをあらかじめ作っておき、 コンストラクタで ThreadGroup オブジェクトを指定することで、 ThreadGroup に関するコントロールを受け付けるようになります。 このようにしておき、 ThreadGroup オブジェクトにinterrupt メッセージを 送ると、関連付けたすべてのスレッドに interrput メッセージが届きます。

main 関数では EOF を受け取ったら処理を終え、 ThreadGroup tg に interrupt メッセージを送り、終了します。

Writer クラスでは、interrupt メソッドが実行されます。 ここでは、 interrupt メソッドとして、終了条件を表すフラグを設定した後、 super.interrupt() により Thread クラスに interrupt メッセージを送りま す。 これで、 InterruptedException が発生します。 すると、 sleep で待機していた run メソッドにおいて例外処理が行われ、メッ セージが出力されます。 そして、再度ループに入りますが、ループの終了条件で終了フラグの検査を行 い、終了します。

import java.io.*;
class Writer extends Thread {
    final private String message;
    private boolean active;
    public Writer(ThreadGroup tg, String message){
	super(tg,"");
	active=true;
	this.message=message;
    }
    @Override
    public void interrupt(){
	active=false;
	super.interrupt();
    }
    @Override
    public void run(){
	for(int i=1; (i<=10)&&active ;i++){
	    System.out.println(i+": "+message);
	    try{
		sleep(3000);
	    }catch(InterruptedException e){
		System.out.println(message+" interrupted");
	    }
	}
    }
}
class Rei {
    public static void main(String[] arg) throws IOException {
	final BufferedReader br = new BufferedReader
	    (new InputStreamReader(System.in));
	final ThreadGroup tg = new ThreadGroup("");
	String line;
	while((line=br.readLine())!=null){
	    Writer w = new Writer(tg,line);
	    w.start();
	}
	tg.interrupt();
    }
}

次に、このプログラムの実行時に EOF を送ると、すべてのスレッドを止めるこ とを考えます。 このために グローバル変数で割り込みが発生しているかどうかの変数を用意し、 すべてのプロセスを止めるための割り込みが発生したときは、メインループで その変数を変化させます。

主ループで EOF を受け取ったら処理を終え、グローバル変数 interruputed を True にセットして、終了します。

Writer クラスでは、run メソッド中で interruputed 変数を監視して、 True になっている場合は、ループを終了するようにします。

import threading
import time

class Writer(threading.Thread):
    def __init__(self,mes):
        super().__init__()
        self.message = mes
    def run(self):
        for i in range(1,11):
            if interrupted:
                print("{0} interrupted".format(self.message))
                break
            print("{0}: {1}".format(i,self.message))
            time.sleep(3)
interrupted = False
try:
    while True:
        line = input()
        w = Writer(line)
        w.start()
except EOFError:
    interrupted = True

boolean 先手必勝(局面){
  先手が勝っている→ return true;
  どの局面でも後手必敗→ return true;
  そうでなければ return false;
}
boolean 後手必敗(局面){
  後手が負けている→ return true;
  少なくとも一つの局面で先手必勝→ return true;
　そうでなければ  return false;
}

なお、この「どの局面でも」は、一つでも「後手必敗」でないなら成立しませ んので、つぎのように書き換えられます。

boolean 先手必勝(局面){
  先手が勝っている→ return true;
  その局面において次に後手が可能な各局面において
  {
      if(!後手必敗(その局面)){
        return false;
      }
  }
  return true;
}

同様に「少なくとも一つ」はつぎのように書き換えられます。

boolean 後手必敗(局面){
  後手が負けている→ return true;
  その局面において次に先手が可能な各局面において
  {
      if(先手必勝(その局面)){
        return true;
      }
  }
  return false;
}

def 先手必勝(局面){
  先手が勝っている→ return True
  どの局面でも後手必敗→ return True
  そうでなければ return False
}
def 後手必敗(局面){
  後手が負けている→ return True
  少なくとも一つの局面で先手必勝→ return True
　そうでなければ  return False
}

なお、この「どの局面でも」は、一つでも「後手必敗」でないなら成立しませ んので、つぎのように書き換えられます。

def 先手必勝(局面){
  先手が勝っている→ return True
  その局面において次に後手が可能な各局面において
      if not 後手必敗(その局面):
        return False
  return True

同様に「少なくとも一つ」はつぎのように書き換えられます。

def 後手必敗(局面){
  後手が負けている→ return True
  その局面において次に先手が可能な各局面において
      if 先手必勝(その局面):
        return True
  return False

簡単のためにゲーム盤は単なる 9 文字の文字列とします。 書き換えを可能にするために java.lang.StringBuilder 型をコンポジション する型とします。 最初は空白 9 個で初期化します。 また、盤をコピーするため、コピーコンストラクタも用意します。 一方、手を置くために setCharAt メソッドを put メソッドとして、また探索 を行うため indexOf メソッドはそのまま実装します。 あと、 toString では盤の形で表示できるようにします。 最後に、 win メソッドで勝ちパターンかどうかを判定します。

import java.util.Iterator;
public class Ban implements Iterable<Integer>, Cloneable{
    final private StringBuilder str;
    public Ban(){
	str = new StringBuilder("         ");
    }
    public Ban(Ban ban){ // コピーコンストラクタ
	this.str = new StringBuilder(ban.str.toString());
    }
    public void put(char player, int te){
	str.setCharAt(te,player);
    }
    public int indexOf(String str){
	return this.str.indexOf(str);
    }
    @Override
    public String toString(){
	return "---\n"
	    +str.substring(0,3)+"\n"
	    +str.substring(3,6)+"\n"
	    +str.substring(6,9)+"\n"
	    +"---";
    }
    private static final int[][] winPattern = 
    {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
    public boolean win(char player){
	for(int[] retsu : winPattern){
	    boolean result=true;
	    for(int i : retsu){
		if(player != str.charAt(i)){
		    result = false;
		    break;
		}
	    }
	    if(result){
		return true;
	    }
	}
	return false;
    }
    @Override
    public Iterator<Integer> iterator(){
	return new Tsuginote(this.str.substring(0,9));
    }
}

ゲーム盤は 9 文字のリストとします。 最初は空白 9 個で初期化します。 また、盤をコピーするため、コピーコンストラクタも用意します。 コピーコンストラクタでは盤をコピーします。 一方、 put メソッドで手を配置し、また探索 を行うため indexOf メソッドでは未検出に対しては例外を -1を返すようにし、 また、オフセットも指定できるようにします。 あと、 str で盤の形で表示できるようにします。 最後に、 win メソッドで勝ちパターンかどうかを判定します。 Ban を Iterable にするために __iter__メソッドを実装します。

class Ban:
    def __init__(self, ban=None):
        if ban == None:
            self.banlist = list("         ")
        else:
            self.banlist = ban.banlist.copy()
    def put(self, player, te):
        self.banlist[te]=player

    def indexOf(self, s, min = 0):
        try:
            return self.banlist.index(s,min)
        except ValueError:
            return -1
    def str(self):
        return "---\n" \
	    +"".join(self.banlist[0:3:1])+"\n" \
	    +"".join(self.banlist[3:6:1])+"\n" \
	    +"".join(self.banlist[6:9:1])+"\n" \
	    +"---"
    winPattern=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    def win(self, player):
        for retsu in self.winPattern:
            result=True
            for i in retsu:
                if player != self.banlist[i]:
                    result = False
                    break
            if result:
                return True
        return False
    def __iter__(self):
        return Tsuginote(self.banlist)

Ban.java

package marubatsu;
import java.util.Iterator;
public class Ban implements Iterable<Integer>, Cloneable{
	final private StringBuilder str;
	public Ban(){
		str = new StringBuilder("         ");
	}
	public Ban(Ban ban){ 
		this.str = new StringBuilder(ban.str.toString());
	}
	public Ban(int[] te) {
		str = new StringBuilder("         ");
		char p = Constant.players[0];
		char e = Constant.players[1];
		for(int t : te) {
			str.setCharAt(t, p);
			char temp=p;
			p=e;
			e=temp;
		}
	}
	
	public void put(char player, int te){
		str.setCharAt(te,player);
	}
	public int indexOf(String str){
		return str.indexOf(str);
	}
	public double score(char player, char enemy, int k) {
		if(win(player)) {
			return 1;
		}
		if(win(enemy)) {
			return -1;
		}
		if(indexOf(" ")==-1){
			return 0; //Draw
		}
		if(k==0) return 0;
		Ban tsugi = new Ban(this);
		double s = Constant.maxscore;
		for(int te: tsugi){
			tsugi.put(enemy,te);
			double s2 = -tsugi.score(enemy, player, k-1);
			if(s2 < s) {
				s = s2;
			}
			tsugi.put(' ',te);
		}
		return s/2;
		
		
	}
	@Override
	public String toString(){
		return "---\n"
				+str.substring(0,3)+"\n"
				+str.substring(3,6)+"\n"
				+str.substring(6,9)+"\n"
				+"---";

	}
	private static final int[][] winPattern = 
		{{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
	public boolean win(char player){
		for(int[] retsu : winPattern){
			boolean result=true;
			for(int i : retsu){
				if(player != str.charAt(i)){
					result = false;
					break;
				}
			}
			if(result){
				return true;
			}
		}
		return false;
	}
	@Override
	public Iterator<Integer> iterator(){
		return new Tsuginote(this.str.substring(0,9));
	}
}

class Ban:
    def __init__(self, ban=None):
        if ban == None:
            self.banlist = list("         ")
        else:
            self.banlist = ban.banlist.copy()
    def put(self, player, te):
        self.banlist[te]=player
    def indexOf(self, s, min = 0):
        try:
            return self.banlist.index(s,min)
        except ValueError:
            return -1
    def str(self):
        return "---\n" \
	    +"".join(self.banlist[0:3:1])+"\n" \
	    +"".join(self.banlist[3:6:1])+"\n" \
	    +"".join(self.banlist[6:9:1])+"\n" \
	    +"---"
    winPattern=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    def win(self, player):
        for retsu in self.winPattern:
            result=True
            for i in retsu:
                if player != self.banlist[i]:
                    result = False
                    break
            if result:
                return True
        return False
    def __iter__(self):
        return Tsuginote(self.banlist)
    def score(self, player, enemy, k):
        if self.win(player):
            return 1
        if self.win(enemy):
            return -1
        if self.indexOf(" ")==-1:
            return 0; #Draw
        if k==0:
            return 0
        tsugi = Ban(self)
        s = Constant.MAXSCORE
        for te in tsugi:
            tsugi.put(enemy,te)
            s2 = -tsugi.score(enemy, player, k-1)
            if s2 < s:
                s = s2
            tsugi.put(' ',te)
        return s/2.0

Comp2.java

package marubatsu;
public class Comp2 implements Comp {
	@Override
	public int te(Ban ban) {
		int arg=-1;
		int max=-2;
		Ban tsugi = new Ban(ban); 
		for(int i : ban){
			tsugi.put(Constant.players[1],i);
			double value = tsugi.score(Constant.players[1],
				Constant.players[0], Constant.depth);
			if(value > max) {
				arg = i;
				max = value;
			}
			tsugi.put(' ',i);
		}
		return arg;
	}
}

Comp2クラス

class Comp2:
    def te(self,ban):
        arg=-1;
        maxvalue=-2;
        tsugi = Ban(ban)
        for i in ban:
            tsugi.put(Constant.players[1],i)
            value = tsugi.score(Constant.players[1],\
                    Constant.players[0], Constant.MAXDEPTH)
            if value > maxvalue:
                arg = i
                maxvalue = value
            tsugi.put(' ',i)
        return arg