Java でのリストの反転 – インプレースとアウトオブプレース

この短いチュートリアルでは、Java でリストのインプレースとアウトオブプレースを逆にする方法を学びます。

インプレースとアウトオブプレースの反転

リストに対して操作を実行する場合 – 操作がインプレースで行われるか (変更が元のオブジェクトに適用される)、またはアウトオブプレースで実行されるか (変更がコピーに適用され、元のオブジェクトに適用される) を検討する必要がある場合があります。オブジェクトは変更されません)。

一部の言語とライブラリは、異なる既定の動作を好みます。 Java では、リストの反転に関するほとんどの操作は次のようになります。 所定の位置に.

これがあなたの望む動作であれば - 素晴らしいです! そうでない場合は、コピーを元に戻す前に、リストのコピーを作成する必要があります。

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

注： 　 clone() 方法 しない ディープ コピーを作成します。 を使用してリストを作成する new ArrayList(list) しない ディープ コピーを作成します。 ディープ コピーを作成することは推奨されておらず、一般的な方法で行うのは驚くほど困難です (また、リストのデータ型によっては意味をなさない場合もあります)。 これはあなたが逆転するのを止めません list & の要素を持っている listCopy 反転していますが。

Collections.reverse（）

　 Collections.reverse() method は、コレクションを元に戻すための標準的な方法であり、「行方不明」として機能します。 List.reverse() 方法。 リストをその場で逆にします。

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Collections.reverse(list);

System.out.println(list);     
System.out.println(listCopy); 

Guava の Lists.reverse(list)

プロジェクトですでに Google Guava を使用している場合は、 Lists を提供するクラス reverse() このメソッドは、元のリストをその場で並べ替えませんが、コピーを作成し、コピーを逆にします。

List list = new ArrayList(Arrays.asList(1, 2, 3));
List reversedList = Lists.reverse(list);

System.out.println(list);         
System.out.println(reversedList); 

まだお持ちでない場合は、Maven を使用して Google Guava をプロジェクトに追加できます。 pom.xml ファイル：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>

またはGradle経由：

implementation group: 'com.google.guava', name: 'guava'

注： Google Guava をまだ持っていない場合、またはプロジェクトの他の部分で使用するつもりがない場合は、この操作のためだけにインポートしないでください。 Collections.reverse() 方法。 Guava は大きな依存関係であり、この操作だけに使用するのは非常にやり過ぎです。

List.add() と List.remove()

リストを逆にするだけでなく、追加の操作を実行したい場合は、元のリストを反復処理し、要素を末尾から削除し、任意のメソッドに渡し、リストの先頭に追加し直すことができます。

public static int process(int input) {
    return input;
}

List list = new ArrayList(Arrays.asList(1, 2, 3));

for (int i = 0, j = list.size()-1; i <= j; i++) {
    int lastValue = process(list.remove(j));
    list.add(i, lastValue);
}

System.out.println(list);  

ベンチマーク

それで、どれが最速ですか？ これは、操作をインプレースで実行するかアウトオブプレースで実行するかによっても異なります。

インプレースリバーサルベンチマーク

アウトオブプレースから始めて、XNUMX つの方法すべてで両方のアプローチをベンチマークしてみましょう。

List list = new Random().ints(100, 1, 11)
                .boxed()
                .collect(Collectors.toList());

int runs = 1000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListCollections(list);
}
long end1 = System.currentTimeMillis();
System.out.println(String.format("Collections.reverse() took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListGuava(list);
}
long end2 = System.currentTimeMillis();
System.out.println(String.format("Guava's Lists.reverse() took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListManually(list);
}
long end3 = System.currentTimeMillis();
System.out.println(String.format("Manually took: %s miliseconds", end3-start3));

System.out.println("Original list: " + list);

この結果：

Collections.reverse() took: 3 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 13 miliseconds
Original list: [6, 7, 9, 7, 2, 5, 4, 1, 3, 2, 2, 6, ...

要素数を 100 から 1000 に増やすとどうなりますか?

Collections.reverse() took: 9 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 133 miliseconds
Original list: [10, 2, 2, 6, 2, 4, 7, 3, 9, 2, 7, 5, ...

Guava は 4ms マークを保持しています! 手動のアプローチは、時間の複雑さが最悪で、直線的に増加しました。 Collections.reverse() スケールアップの影響は少なくなりますが、Guava の実装は最も影響を受けません。 ただし、Guava アプローチのリストを手動でコピーしないことに注意してください。 「オリジナル」と「逆」のリストを持つという考えを捨てると、ベンチマークは変化しますか?

アウトオブプレース リバーサル ベンチマーク

1000 個の要素があり、各メソッドから手動コピーを削除してコードを再実行すると、リストの反転されていないコピー (時間測定から除外されました) で動作します。

Collections.reverse() took: 7 miliseconds
Guava's Lists.reverse() took: 3 miliseconds
Manually took: 131 miliseconds
Original list: [6, 8, 10, 7, 3, 8, 7, 1, 1, 9, 5, ...

グアバ まだ 一貫して両方を上回るパフォーマンスを維持しています Collections.reverse() そして手動アプローチ。

まとめ

この短いガイドでは、操作から元のリストを保持しながら、Java でリストをインプレースおよびアウトオブプレースで逆にする方法を学びました。 私たちは使用しました Collections.reverse() メソッド、Google Guava の Lists.reverse() メソッドと手動アプローチ。