この記事では、Java のスタックから重複要素を削除する 2 つの方法を検討します。 ネストされたループ を使用した単純なアプローチと、HashSet を使用したより効率的な方法を比較します。目標は、重複の削除を最適化する方法を実証し、各アプローチのパフォーマンスを評価することです。

問題ステートメント

重複した要素をスタックから削除する Java プログラムを作成します。

入力

Stack data = initData(10L);

出力

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

特定のスタックから重複を削除するには、2 つのアプローチがあります -

• 単純なアプローチ: 2 つの ネストされたループを作成して、どの要素が既に存在するかを確認し、結果スタックの戻り値に要素が追加されるのを防ぎます。
• HashSet アプローチ: Set を使用して一意の要素を保存し、その O(1) 複雑性を利用して要素が存在するかどうかを確認します。

ランダムなスタックの生成とクローン作成

以下は、Java プログラムが最初にランダムなスタックを構築し、その後使用するためにその複製を作成します -

private static Stack initData(Long size) {
    Stack stack = new Stack  ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i  manualCloneStack(Stack  stack) {
    Stack  newStack = new Stack  ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

initData は、指定されたサイズと 1 ～ 100 の範囲のランダムな要素を持つスタックの作成に役立ちます。

manualCloneStack は、別のスタックからデータをコピーしてデータを生成し、それを 2 つのアイデア間のパフォーマンス比較に使用します。

Naïve アプローチを使用して特定のスタックから重複を削除します

以下は、素朴なアプローチを使用して特定のスタックから重複を削除するステップです -

• タイマーを開始します。
• 一意の要素を格納するために空のスタックを作成します。
• while ループを使用して繰り返し、元のスタックが空になるまで続行し、最上位の要素をポップします。
• resultStack.contains(element) を使用して重複をチェックし、要素がすでに結果スタックにあるかどうかを確認します。
• 要素が結果スタックにない場合は、結果スタックに追加します。
• 終了時刻を記録し、費やした合計時間を計算します。
• 返される結果

例

以下は、素朴なアプローチを使用して特定のスタックから重複を削除する Java プログラムです -

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack  ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

素朴なアプローチの場合、

while (!stack.isEmpty())

resultStack.contains(element)

最適化されたアプローチ (HashSet) を使用して、指定されたスタックから重複を削除します。

以下は、最適化されたアプローチを使用して特定のスタックから重複を削除する手順です-

• タイマーをスタート
• 表示された要素を追跡するためのセットを作成します (O(1) 複雑さチェック用)。
• 固有の要素を保存するための一時スタックを作成します。
• を使用して繰り返し、ループ はスタックが空になるまで継続します。
• スタックから一番上の要素を削除します。
• 重複を確認するには、seen.contains(element) を使用して、要素がすでにセット内にあるかどうかを確認します。
• 要素がセットにない場合は、表示されているスタックと一時スタックの両方に追加します。
• 終了時刻を記録し、費やした合計時間を計算します。
• 結果を返します

例

以下は、HashSet を使用して指定されたスタックから重複を削除する Java プログラムです -

public static Stack idea2(Stack stack) {
    long start = System.nanoTime();
    Set seen = new HashSet();
    Stack tempStack = new Stack();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

最適化されたアプローチには

Set seen

データを初期化します。
• initData(Long size) メソッドを使用して、ランダムな整数で満たされたスタックを作成します。
  
スタックのクローンを作成します。
• cloneStack(スタック スタック) メソッドを使用して、元のスタックの正確なコピーを作成します。
• initData. で初期スタックを生成します
• cloneStack を使用してこのスタックのクローンを作成します。
• 単純なアプローチ を適用して、元のスタックから重複を削除します。
• 最適化されたアプローチを適用して、複製されたスタックから重複を削除します。
各方法にかかる時間と、両方のアプローチによって生成される固有の要素を表示します

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack initData(Long size) {
        Stack stack = new Stack();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i  cloneStack(Stack stack) {
        Stack newStack = new Stack();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack idea1(Stack stack) {
        long start = System.nanoTime();
        Stack resultStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack idea2(Stack stack) {
        long start = System.nanoTime();
        Set seen = new HashSet();
        Stack tempStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack data1 = initData(10L);
        Stack data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: "   idea1(data1));
        System.out.println("Unique elements using idea2: "   idea2(data2));
    }
}

public static void main(String[] args) {
    Stack data1 = initData();
    Stack data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}