Javaでスリープソートを実装してみた。 #Java

スリープソートとは?

配列内の値だけ並列にsleep処理をし、終わったものから配列に格納してソートするもの。
今回は終わったものから配列に格納する処理が思いつかなかっため、Threadクラスを継承したSleepThreadクラスに処理終了順を持たせる方針で対応した。

経緯

現在進行形でIT研修中。
同期がスリープソートというものを紹介してくれたので実装してみた。
拙い部分もあるが、新卒一年目SEということでどうか温かい目で、、、
アドバイス等あればお願いします。

実装

SleepSort.java

import java.util.Random;
import java.util.Scanner;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * スリープソート
 */
class SleepSort {
  
  /**
   * スリープソートを実行します。
   * @param args コマンドライン引数
   */
  public static void main(String[] args) {
    // 標準入力から配列サイズを受け取る
    Scanner scanner = new Scanner(System.in);
    System.out.print("配列サイズを入力してください。: ");
    final int arraySize = scanner.nextInt();

    // ソート前配列
    final int[] beforeArray = createArray(arraySize);
    // ソート後配列
    final int[] afterArray = new int[arraySize];
    // スレッド格納配列
    final Thread[] threads = new SleepThread[arraySize];
    // 処理終了順を保持するカウンター
    final AtomicInteger finishCountar = new AtomicInteger(0);

    // スリープスレッドを初期化し、実行
    for (int i = 0; i < arraySize; i++) {
      threads[i] = new SleepThread(beforeArray[i], finishCountar);
      threads[i].start();
    }

    // スレッドの処理が全て終了するまで待つ
    while(finishCountar.get() != arraySize) {
      System.out.println("待機中...");
    }

    // ソート後配列を初期化
    for (int i = 0; i < arraySize; i++) {
      SleepThread sleepThread = (SleepThread) threads[i];
      afterArray[sleepThread.getFinishOrder()] = sleepThread.getSleepTime();
    }

    // ソート前配列、ソート後配列を表示
    printArray("ソート前", beforeArray);
    printArray("ソート後", afterArray);

    // 事後処理
    scanner.close();
  }

  /**
   * 配列サイズを受け取り、ランダムな値で配列を作成します。
   * @param arraySize 配列サイズ
   * @return 配列
   */
  public static int[] createArray(int arraySize) {
    Random random = new Random();
    final int[] array = new int[arraySize];
    for (int i = 0; i < arraySize; i++) {
      array[i] = random.nextInt(100);
    }
    return array;
  }

  /**
   * 配列の状態と配列を表示します。
   * @param status 配列の状態
   * @param array 配列
   */
  public static void printArray(String status, int[] array) {
    System.out.print(status + ": ");
    for (int num : array) {
      System.out.print(num + " ");
    }
    System.out.println();
  }
}

SleepThread.java

import java.util.concurrent.atomic.AtomicInteger;

/**
 * スリープスレッド
 */
class SleepThread extends Thread {

  /** 処理停止時間(配列の要素) */
  private int sleepTime;

  /** 処理終了順(配列の添字) */
  private int finishOrder;

  /** 処理終了順を保持するカウンター */
  private AtomicInteger finishCountar;

  /**
   * コンストラクタ
   * @param sleepTime 処理停止時間
   * @param finishCountar　処理終了順を保持するカウンター
   */
  SleepThread(int sleepTime, AtomicInteger finishCountar) {
    this.sleepTime = sleepTime;
    this.finishCountar = finishCountar;
  }

  @Override
  public void run() {
    try {
      // sleepTime分処理停止
      // 配列のサイズが大きくなると、sleepTimeだけではすぐに終わるスレッドが出てくる。
      // sleepTime*100などする対策がある。
      Thread.sleep(sleepTime);
      // sleepが終わり次第、終わった順を記録
      this.finishOrder = finishCountar.getAndIncrement();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }

  public int getSleepTime() {
    return sleepTime;
  }

  public int getFinishOrder() {
    return finishOrder;
  }
}

実行結果

下記から分かる通り、配列のサイズが大きくなると誤差が出てくる。
原因としては、sleepする時間が短いため、添字が大きい部分のスレッドを作っている間にsleepメソッドが終了してしまうのではないかなと。
対策としては、sleepTimeに×100などすれば解決する。が、そうすると処理時間に時間がかかってしまう。
スレッド同時にスタート！ということができるのであろうか。。

配列サイズが5の場合
配列サイズが10の場合
配列サイズが100の場合

まとめ

今回はSleepSortを実際に実装してみた。
Threadについては理解が浅かったのでいい勉強になった。
だが、Threadについて調べていくとだんだん難しい話になってわからなくなる。
難しい話になっても理解できるようになっていきたい。

最後まで読んでいただきありがとうございました。