admin のすべての投稿

10.String Searching

文字列を検索する – indexOf/lastIndexOfメソッド

文字列に含まれる部分文字列を検索するには、indexOfメソッドを利用します。indexOfメソッドは、指定された部分文字列が最初に登場した位置を、文字列の先頭を0としたインデックス番号で返します。文字列が見つからなかった場合、戻り値は-1となります。
第2引数で、検索開始位置を指定することもできます。

1
2
3
String str = "にわにはにわにわとりがいる";
System.out.println(str.indexOf("にわ"));  // 結果:0
System.out.println(str.indexOf("にわ", 1));   // 結果:4

部分文字列を文字列の末尾から検索するならば、lastIndexOfメソッドを利用してください。

1
System.out.println(str.lastIndexOf("にわ"));  // 結果:6

match() 正規表現を使った検索

 正規表現を使って、文字列(String)を検索します。結果は文字列の配列として返されます。
【構文】
match(str, regexp)
【パラメータ】
str 検索対象の文字列
regexp 検索条件をあらわす正規表現
【戻り値】
String[] (一致する文字がないときはnull)

 次の例は文字列からデータを取り出します。

String t = "本日の気温は28度です";
String[] m = match(t, "([0-9]+)度");	// 「度」の前の数値を取り出す

if(m != null) {
  println("t=" + m[1]);				// 検索結果(m[1])を出力
  println(m[0]);						// 一致した文字全体(m[0])を出力
} else {
  println("不一致");
}

 

参考:

9.Set

Set構造は、要素を順番付けしないで管理するデータ構造です。
「HashSet」「TreeSet」の2種類があります。

Set構造

Listのような順番付けや、Mapのようなキー管理もないため、要素の取得にはIteratorや拡張for構文で取得します。
このようなことからHashSetは要素の取得順は保証されませんが、TreeSetは自動ソートされて管理されるのでソートされた順番で要素が取得されます。
また、HashSetは要素にnullを使用する事が可能ですが、TreeSetはnullを使用する事ができません。
Set構造は、要素の重複は不可です。(同じキーがセット(add)された場合は上書きされます。)

セット(HashSet)

HashSet も配列を扱いますが、要素の重複が許されない、順序の保障が無い点が ArrayList や LinkedList と異なります。要素を参照する際には Iterator を用います。

§HashSetTest.java
import java.util.*;

class HashSetTest {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add("AAA");
        set.add("BBB");
        set.add("CCC");
        set.add("AAA");
        Iterator it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

実行結果は下記のようになります。AAA を 2回 add() していますが、重複要素がひとつにマージされます。結果の順序は add() した順序に関係なくバラバラになります。

C:\java>java HashSetTest
CCC
AAA
BBB

下記などのメソッドが用意されています。

  • set.add(o) – オブジェクト o を配列の末尾に追加する
  • set.clear() – 配列をクリアする
  • set.contains(o) – オブジェクト o と等しい要素があるか調べる
  • set.isEmpty() – 空かどうか調べる
  • set.remove(o) – オブジェクト o にマッチする要素を削除する
  • set.size() – 要素の個数を得る

2016-09-04 (4)

セット (TreeSet)

TreeSet も HashSet と同じように使用できます。要素が自動的にソートされる点が HashSet と異なります。

§HashSetTest.java
import java.util.*;

class TreeSetTest {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        set.add("CCC");
        set.add("AAA");
        set.add("BBB");
        set.add("AAA");
        Iterator it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

C:\java>java TreeSetTest
AAA
BBB
CCC

2016-09-04 (3)

8.Sort

ソートとは

ソートとは,複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の2つがあります。

  • 昇順:小さいものから大きなものへ
  • 降順:大きなものから小さなものへ
  •  

    並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所(文字列)による並べ替えが行われます。

    ソートアルゴリズム

    ソートの処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。

    ソートを行うアルゴリズムの例として次のものが挙げられます。

    • 基本形
      • 基本交換法:バブルソート
      • 基本選択法:直接選択法
      • 基本挿入法
    • 応用形
      • 改良交換法:クイックソート
      • 改良選択法:ヒープソート
      • 改良挿入法:シェルソート

    バブルソート

    バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がと遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法隣接交換法ともいう。(単に交換法と言う場合もある)

    バブルソートサンプル

    final int    NUMBER_OF_RANDOM_DATA = 500;
    final String DATA_FILE_NAME        = "RandomData.txt";
    final int    DIAMITER              = 5;
    
    ArrayList nums = new ArrayList();
    int i = 0; // ソート回数。drawする度にカウントアップ
    
    void setup(){
      //ランダムなデータの読み込み
      loadData();
      //ディスプレイウインドウの設定
      size(500,500);
      background(0,0,0);
      frameRate(60);
      stroke(255,0,0);
    }
    
    void loadData(){
      String lines[] = loadStrings(DATA_FILE_NAME);
      for(String val : lines){
        nums.add(int(val));
      }
    }
    
    void onePassOfBubbleSort(){
      for ( int j = NUMBER_OF_RANDOM_DATA - 1; j > i; j--){
        if ( nums.get(j) < nums.get(j-1) ){
          int temp = nums.get(j);
          nums.set(j,nums.get(j-1));
          nums.set(j-1,temp);
        }
      }
    }
    
    void draw(){
      if (i < NUMBER_OF_RANDOM_DATA - 1){
        //ソート1パス
        onePassOfBubbleSort();
        //結果をプロット
        println("Count " + i);
        clear(); 
        for (int k=0; k < nums.size(); k++) {
          ellipse(k,nums.get(k),DIAMITER,DIAMITER);
        }
        ++i;
      }
    }
    

    2016-09-04 (2)

    7.Recursive

    再帰とは

    再帰(Recursion)とは,再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは,自分自身の定義の中に,自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

    階乗

    整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。

    n! = n × (n-1) × (n-2) × ... × 2 × 1 

    この式を再帰的定義に書き換えると,次のようになります。

    n! = n × (n-1)!  (ただし,0!=1)

    次の階乗のsketch、Factorial.pdeは10の階乗を行う例

    1. 繰り返し構文を使ったメソッド factorial_for
    2. 再帰するメソッド factorial_recursive
    // 繰り返し構文を用いたメソッド
    long factorial_for(long i){
      if(i < 0){
        println("Error! Invarid input.<using for>");
        return -1;
      } else {
        long result = 1;
        for (int j = 1; j <= i; ++j){
          result *= j;
        }
        return result;
      }
    }
    // 再帰を用いたメソッド
    long factorial_recursive(long i){
      if(i < 0){
        println("Error! Invarid input.<using recursive>");
        return -1;
      } else if(i == 0){
        return 1;
      } else {
        return i * factorial_recursive(i - 1);
      }
    }
    
    void setup(){
      long num    = 0;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
      num    = 10;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
      num    = -10;
      // using for
      println("using for       : factorial(" + num + ") = "
               + factorial_for(num) );
      // using recursive
      println("using recursive : factorial(" + num + ") = "
               + factorial_recursive(num) );
    
    }

    ユークリッドの互除法

    8王妃問題を解く

    再帰を活用するメリットとデメリット

    再帰を活用するメリットは,「(場合によっては)問題をシンプルに記述できること」です。しかし,再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題,デメリットを抱えています。

    そのデメリットを話す前に,計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は,これまで何度か取り扱って来た計算量の考え方で,そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は,そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

    再帰のアルゴリズムは,自分自身を1回呼ぶ度に,自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば,必要なメモリ容量も多くなります。つまり,再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

    かつて,コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が,再帰を言語の仕組みとして用意しなかった理由の一つは,再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在,パーソナルコンピュータのメモリは数ギガバイトを持つようになったため,この問題が大きく扱われることはあまりありません。ただ,再帰を使ったプログラムによってはメモリを圧迫しますので,利用にあたっては慎重になりましょう。

    そのため,再帰アルゴリズムを使用するべき場合とは,コードを劇的にシンプルにできる場合に限ると考えておくべきです。

    6.Stack and Queue

    キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

    キュー

    キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。

    • 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
    • コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

    データを追加する操作をエンキュー(enqueue)。
    データを取り出す操作をデキュー(dequeue)という。

    スタック

    スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。

    • 積ん読 (本を重ねて積んでいくと上からしか取れない)
    • コンピューターで割込みやサブルーチンを支援するために極めて有用である

     

     

    スタックにデータを入れる操作をプッシュ(push)という。
    スタックからデータを取り出す操作をポップ(pop)という。

    キューとスタックの実装

    オブジェクトの後入れ先出し(LIFO)スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し(FIFO)を表す待ち行列(キュー)は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

    一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

    import java.util.*;
    
    String[] item = {"Apple", "Banana", "Cocoa"};
    Queue q = new LinkedList();
    Stack s = new Stack();
    for(String i: item) {
      q.offer(i); // enqueue
      s.push(i);  // push
    }
    while(q.size() > 0) {
      println("QUEUE:" + q.poll());
    }
    while(s.size() > 0) {
      println("STACK:" + s.pop());
    }
    

     

    2016-09-04 (5)

    キューがスタックに近い形で利用可能になっているのが、実感できます。

    参考:

    • http://www.atmarkit.co.jp/fjava/javatips/182java064.html ーーGenericsを用いたスタックとキューのサンプルプログラム