في هذه المقالة، سنستكشف طريقتين لإزالة العناصر المكررة من المكدس في 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

لإزالة التكرارات من مكدس معين، لدينا طريقتان -

• منهج ساذج: أنشئ حلقتين متداخلتين لمعرفة العناصر الموجودة بالفعل ومنع إضافتها إلى إرجاع مكدس النتائج.
• منهج 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 يساعد في إنشاء البيانات عن طريق نسخ البيانات من مكدس آخر، واستخدامها لمقارنة الأداء بين الفكرتين.

إزالة التكرارات من مكدس معين باستخدام أسلوب السذاجة

فيما يلي خطوة إزالة التكرارات من مكدس معين باستخدام أسلوب Naïve −

• بدء تشغيل الموقت.
• إنشاء مكدس فارغ لتخزين العناصر الفريدة.
• قم بالتكرار باستخدام حلقة while واستمر حتى تصبح المكدس الأصلي فارغًا، ثم قم بإخراج العنصر العلوي.
• تحقق من التكرارات باستخدام resultStack.contains(element) لمعرفة ما إذا كان العنصر موجودًا بالفعل في حزمة النتائج.
• إذا لم يكن العنصر موجودًا في مكدس النتائج، فأضفه إلى resultStack.
• سجل وقت الانتهاء واحسب إجمالي الوقت المستغرق.
• إرجاع النتيجة

مثال

يوجد أدناه برنامج Java لإزالة التكرارات من مكدس معين باستخدام أسلوب Naïve −

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) للتحقق مما إذا كان العنصر موجودًا بالفعل في المجموعة.
• إذا لم يكن العنصر موجودًا في المجموعة، فأضفه إلى كل من المكدس المرئي والمؤقت.
• سجل وقت الانتهاء واحسب إجمالي الوقت المستغرق.
• إرجاع النتيجة

مثال

يوجد أدناه برنامج 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(حجم طويل) لإنشاء مكدس مليء بأعداد صحيحة عشوائية.
  
• استنساخ المكدس نستخدم طريقة cloneStack(Stack Stack) لإنشاء نسخة طبق الأصل من المكدس الأصلي.
• قم بإنشاء المكدس الأولي باستخدام 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);
}