ほくそ笑む

R言語と統計解析について

とあるソート前のインデックス (あるいは、ラノベ的プログラミング)

次のような配列があるとします。

double[] values = new double[] { 1.1, 3.3, 5.5, 4.4, 2.2 };

この配列をソートするには

Arrays.sort(values);
System.out.println(Arrays.toString(values));

[1.1, 2.2, 3.3, 4.4, 5.5]

とすればいいですね。
ここで、ソート後の配列のソート前の添え字(インデックス)がほしい場合、どうすればいいでしょうか?
つまり、次のような配列がほしいとします。

[0, 4, 1, 3, 2]

1.1 はソート前の配列の 0 番目、2.2 はソート前の配列の 4 番目... という意味ですね。

単純な方法

単純な方法はインデックス付き value のクラスをつくってやることです。

class ValueWithIndex {
	public int index;
	public double value;

	public ValueWithIndex(int index, double value) {
		this.index = index;
		this.value = value;
	}
}

このようなクラスを作っておけば、Collections.sort() によって添え字を保持したままソートすることができます。

double[] values = new double[] { 1.1, 3.3, 5.5, 4.4, 2.2 };

List<ValueWithIndex> valueList = new ArrayList<ValueWithIndex>();
for (int i = 0; i < values.length; i++) {
	valueList.add(new ValueWithIndex(i, values[i]));
}

Collections.sort(valueList, new Comparator<ValueWithIndex>() {
	@Override
	public int compare(ValueWithIndex v1, ValueWithIndex v2) {
		return Double.compare(v1.value, v2.value);
	}
});

int[] indexes = new int[valueList.size()];
for (int i = 0; i < indexes.length; i++) {
	indexes[i] = valueList.get(i).index;
}

System.out.println(Arrays.toString(indexes));

[0, 4, 1, 3, 2]

ところでソート前の添え字を得るためには新しいクラスを作らなければならないのでしょうか?
インデックスを得るためだけにクラスを作るのは、やりすぎなような気がします。
これではインデックスが出しゃばりすぎです。インデックスはもっと空気のような存在であるべきです。

ソート前の添え字は新しいクラスを作らなければ得られない?まずはそのふざけた幻想をぶち壊す!

というわけで、クラスを作らないやり方です。

final double[] values = new double[] { 1.1, 3.3, 5.5, 4.4, 2.2 };

Integer[] indexes = new Integer[values.length];
for (int i = 0; i < indexes.length; i++) {
	indexes[i] = i;
}

Arrays.sort(indexes, new Comparator<Integer>() {
	@Override
	public int compare(Integer i1, Integer i2) {
		return Double.compare(values[i1], values[i2]);
	}
});

System.out.println(Arrays.toString(indexes));

これは、インデックスの配列を、values の値で比較するコンパレータを使ってソートしています。
この方法であれば、わざわざ新しいクラスを作る必要はありません。
ただし、この結果からソート後の配列を得るためには

double[] sortedValues = new double[indexes.length];
for (int i = 0; i < indexes.length; i++) {
	sortedValues[i] = values[indexes[i]];
}
System.out.println(Arrays.toString(sortedValues));

のように書かなければなりません。これはちょっと面倒です。
たとえるなら、インデックスは出しゃばらなくなったけど、ヒロイン不在の状態というわけです。
どうすればいいでしょうか?

あ、あんたのために添え字付きでソートしたんじゃないんだからね!

ここで、TreeMap に登場してもらいましょう。
TreeMap は値を入れるとキーでソートされた順に保持してくれる Map です。
この TreeMap に対して、キーに values を、バリューに添え字を入力してみましょう。

double[] values = new double[] { 1.1, 3.3, 5.5, 4.4, 2.2 };

TreeMap<Double, Integer> mikoto = new TreeMap<Double, Integer>();
for (int i = 0; i < values.length; i++) {
	mikoto.put(values[i], i);
}

Integer[] indexes = mikoto.values().toArray(new Integer[0]);
Double[] sortedValues = mikoto.keySet().toArray(new Double[0]);

System.out.println(Arrays.toString(indexes));
System.out.println(Arrays.toString(sortedValues));

[0, 4, 1, 3, 2]
[1.1, 2.2, 3.3, 4.4, 5.5]

すると、あら不思議、values(キー)が勝手にソートされて保持されてしまいます。
たったこれだけでソート前のインデックスが簡単に得られてしまいます。
まるで「そんなつもりはないんだからね!ただの仕様なんだからね!」と言ってるかのようです。
なんというツンデレクラス。
これでヒロインは TreeMap に決定です。
TreeMap の登場で indexes はほぼ空気です。なくてもいいくらいです。

おわりに

ソート前のインデックスを得る3つの方法を紹介しました。
もちろん、僕のオススメは TreeMap を使った方法です。
ところで、速度のほうはどうなんでしょうか?
1000000 件のデータをソートして速度を測ってみると、次のようになりました。

方法1 (クラス使用) 995 msec
方法2 (クラス無し) 930 msec
方法3 (TreeMap) 2264 msec

明らかに TreeMap 遅いですね。
つまり、これは、TreeMap はオクテだということです。
ツンデレでオクテだなんて、ヒロインに最適ですね。
というわけで、これからも僕は TreeMap を愛していきたいと思います。
以上。