В этой статье мы рассмотрим два метода удаления повторяющихся элементов из стека в Java. Мы сравним простой подход с вложенными циклами и более эффективный метод с использованием 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 подхода:

• Наивный подход: создайте два вложенных цикла, чтобы увидеть, какие элементы уже присутствуют, и предотвратить их добавление в возвращаемый стек результатов.
• Подход 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 помогает генерировать данные путем копирования данных из другого стека и использования их для сравнения производительности двух идей.

Удалить дубликаты из заданного стека, используя наивный подход

Ниже приведен шаг по удалению дубликатов из данного стека с использованием наивного подхода —

• Запустите таймер.
• Создайте пустой стек для хранения уникальных элементов.
• Выполните итерацию с использованием цикла 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)).
• Создайте временный стек для хранения уникальных элементов.
• Итерация с использованием цикла while продолжается до тех пор, пока стек не станет пустым.
• Удалить верхний элемент из стека.
• Чтобы проверить дубликаты, мы будем использовать seen.contains(element), чтобы проверить, находится ли элемент уже в наборе.
• Если элемента нет в наборе, добавьте его как в видимый, так и во временный стек.
• Запишите время окончания и подсчитайте общее потраченное время.
• Вернуть результат

Пример

Ниже приведена Java-программа для удаления дубликатов из заданного стека с помощью HashSet —

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(Stack stack) для создания точной копии исходного стека.
• Сгенерируйте исходный стек с помощью initData.
• Клонируйте этот стек, используя cloneStack.
• Примените наивный подход для удаления дубликатов из исходного стека.
• Примените оптимизированный подход для удаления дубликатов из клонированного стека.
• Отобразите время, затраченное на каждый метод, и уникальные элементы, полученные с помощью обоих подходов.

Пример

Ниже представлена ​​программа на Java, которая удаляет повторяющиеся элементы из стека, используя оба упомянутых выше подхода –

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);
}

Как уже отмечалось, время реализации идеи 2 короче, чем для идеи 1, поскольку сложность идеи 1 равна O(n²), а сложность идеи 2 — O(n). Так вот, когда количество стеков увеличивается, время, затрачиваемое на расчеты, тоже увеличивается на его основе.