ゆの in Javaとかに嵌って放出が遅れましたが、ソート祭りの話題。

非破壊で順序を変更してとりだす

GoFデザインパターンのIteratorパターンを用いて元になるListには手を加えずに ソートと同じような効果を得るサンプルです。

public class SortIterator<T> implements Iterator<T>, Iterable<T> {
  /** ソート対象 */
  private Iterable<T> target;
  /** ソート用Comparator.この実装を変えることで並ばせ方を変えられる */
  private Comparator<T> comparator;
  private T preElement;
  private List<T> equalValues;

  /**
   * コンストラクタ
   * @param target ソート対象。SetやListなどを渡すことができる
   * @param comparator 並ばせ方を決めるComparatorの実装
   */
  public SortIterator(Iterable<T> target, Comparator<T> comparator) {
    this.target = target;
    this.comparator = comparator;
    this.equalValues = new ArrayList<T>();
  }

  @Override
  public boolean hasNext() {
    T min = null;
    targetLoop:
    for (T elem : this.target) {
      // 前回までに返した値より小さいものは飛ばす
      if (this.preElement != null &&
          this.comparator.compare(this.preElement, elem) < 0) {
        continue;
      }
      // 前回と同じ値のものは、重複を確認してすでに返した値なら飛ばす
      if (this.preElement != null &&
          this.comparator.compare(this.preElement, elem) == 0) {
        // 参照の同値性で判断するために敢えてcontains()は使わない
        // contains()だとequals()による比較になるため
        for (T value : this.equalValues) {
          if (value == elem) {
            continue targetLoop;
          }
        }
        this.preElement = elem;
        this.equalValues.add(elem);
        return true;
      }
      // 前回までに返した値より大きいもののうち、最小のものを探す
      if (min == null) {
        min = elem;
        continue;
      }
      if (this.comparator.compare(min, elem) < 0) {
        min = elem;
      }
    }
    if (min == null) {
      return false;
    }
    this.equalValues.clear();
    this.equalValues.add(min);
    this.preElement = min;
    return true;
  }

  @Override
  public T next() {
    return this.preElement;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }

  @Override
  public Iterator<T> iterator() {
    return this;
  }
}

これを以下のように呼び出します。

    List<Integer> list = new ArrayList<Integer>();
    list.add(new Integer(3));
    list.add(new Integer(1));
    list.add(new Integer(4));
    list.add(new Integer(2));
    list.add(new Integer(1));

    SortIterator<Integer> ite = new SortIterator<Integer>(list,
        new Comparator<Integer>(){
          @Override
          public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
          }
    });
    for (int i : ite) {
      System.out.println(i);
    }

出力結果は

1 1 2 3 4

ちゃんと整列していますね。

解説

このクラスではソート対象のIterableと比較に用いるComparatorを保持して hasNext()のたびに今までに返した値より大きいもののうち一番小さいもの、 つまり「次に小さい奴」を探してnext()でそのオブジェクトを返します。

最初に「データをちょうだい」と言われた時に「一番小さい奴」を探して返し、 「次のデータをちょうだい」と言われたら「次に小さい奴」を探して返し、 …。

でも、それで利用側から見ると並び変わったように見えるんですね。

設計に利用するヒント

Listの中身そのものを並び替えた方が効果的なシチュエーションの方が多いかもしれませんが、 一時的に他の並び方を使いたいという場合はIterator側に並び替えを仕込むのも一つの手です。

これは非破壊であることがメリットで、複数のスレッドからオブジェクトの持ついろんな属性での 並び替えを並列に取得することもできます(その間に元のListが変更されると動きがおかしくなりますが…)。

そういう意味ではImmutableパターン、つまりオブジェクトを変更不可能にすることで 並列時の安全性を確保するようなケースで有用です。

データを利用する人が多岐にわたる場合、自分の都合だけで並び替えるわけにいかないかもしれません。 そのような場合に、外付けでデータの順番が変わったように見せる手法があることを知っておくと うまい設計を起こすヒントになるかもしれません。

外から利用する分には中のデータの表現方法なんて隠蔽されていて関心の外ですから、 必要になった時に自転車操業的に「次に小さい奴」を探して渡す、でも大丈夫なんですよね。