جدوى LinkedList مقابلمجموعة من أجل فرز مقابللم يتم فرزها البيانات ؟

Question

مقارنة LinkedLists و المصفوفات في حين أيضا مقارنة خلافاتها مع فرز البيانات التي لم يتم فرزها

• إضافة
• إزالة
• استرجاع
• الفرز
• عموما السرعة
• عموما استخدام الذاكرة

الأسئلة الفعلية

مناقشة إمكانية تنفيذ البيانات التي لم يتم فرزها تعيين قائمة مرتبطة بدلا من صفيف.ماذا سيكون المفاضلات في شروط الإدراج, إزالة, استرجاع ذاكرة الكمبيوتر و سرعة التطبيق ؟

مناقشة جدوى تنفيذ فرز البيانات تعيين قائمة مرتبطة بدلا من صفيف.ماذا سيكون المفاضلات في شروط الإدراج, إزالة, استرجاع ذاكرة الكمبيوتر و سرعة التطبيق ؟

بناء على إجاباتك على الأسئلة السابقة ، تلخيص التكاليف والفوائد من استخدام القوائم المرتبطة في التطبيق.

إجاباتي/الإدخال:

LinkedLists إلى تخصيص الذاكرة في كل مرة عقدة جديدة إضافة مفيدة عند إضافة العديد من العقد و حجم يتغير باستمرار ولكن عموما أبطأ عند إضافة بعض العناصر

المصفوفات الذاكرة المخصصة في بيجينينج من تشغيل برنامج, تغيير حجم قائمة بطيئة (إضافة العديد من العناصر بطيئة إذا كان لديك تغيير)

استرجاع أسرع في مجموعة بسبب الفهرسة

إضافة/إزالة أسرع في LinkedList بسبب مؤشرات

Answer 1

على غير مصنف مقابل.مرتبة.سأفعل واحدة، ثم أنت حقا بحاجة إلى القيام بواجبك المنزلي

يحتاج ترميز Stackoverflow حقًا إلى جداول للقيام بذلك.تريد أن تقول كم هي "تكلفة" العملية بالنسبة للقائمة غير المصنفة/المصفوفة، والمرتبة/المصفوفة، والقائمة غير المصنفة/المرتبطة، والقائمة المصنفة/المرتبطة

نقطة أخيرة:"سرعة التطبيق" هي تلميح للنظر في أكثر من مجرد سرعة العمليات الفردية.

* Adding

غير مصنف:إضافة المصفوفة هي O(1) ما لم تكن هناك حاجة لتغيير الحجم - فقط أضفها إلى النهاية.قد ترغب في مناقشة استراتيجية تغيير الحجم التي تقلل من النفقات العامة (تلميح:لا تزيد الحجم بمقدار واحد فقط)

مرتبة:إضافة المصفوفة هو O(n) - العثور على مكان إضافتها هو O(log(n))، لكنك تحتاج إلى نقل نصف العناصر لأعلى (في المتوسط) لإنشاء rom للعنصر الجديد

غير مصنف:القائمة المرتبطة هي O(1) - قم بإضافتها إلى بداية القائمة أو نهايتها.

مرتبة:القائمة المرتبطة هي O(n) - على الرغم من أنه يمكنك إضافة العنصر في O(1) مرة أخرى، إلا أنك تحتاج إلى مسح نصف القائمة في المتوسط ​​للعثور على المكان المناسب لوضعها.

لذا، إليكم الباقي.انشر إجابة وسنقوم بنقدها، ولكن للحصول على أقصى استفادة من تعليمك الباهظ الثمن (المفترض)، فإنك تحتاج حقًا إلى القيام ببعض الأعمال في هذا الشأن :)

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage

Answer 2

لست متأكدًا من الفصل الذي يناسبه هذا، ولكن بالنسبة لبرنامج CS، سيتعين عليك القيام بعمل أفضل من "بطيء" و"سريع".حاول قياس ذلك من حيث عدد العمليات المطلوبة.يجب أن تكون على دراية بالآلات المستخدمة عادةً لمثل هذا القياس الكمي - استخدم تلك الآلات.

Answer 3

Here is a C++ code that illustrates that sorting the data miraculously makes the code faster than the unsorted version. Let’s try out a sample C++ program to understand the problem statement better.

// CPP برنامج لإظهار تجهيز // الوقت من فرز و لم يتم فرزها مجموعة

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;

    return 0;
}

//الناتج من الكود

Output :

Execution 1:
Time for an unsorted array: 0.00108
Time for a sorted array: 0.00053

Execution 2:
Time for an unsorted array: 0.001101
Time for a sorted array: 0.000593

Execution 3:
Time for an unsorted array: 0.0011
Time for a sorted array: 0.000418
Observe that time taken for processing a sorted array is less as compared to an unsorted array. The reason for this optimization for a sorted array is branch prediction.

Answer 4

@ بول:شكرًا

• إزالة

غير مرتبة ومرتبة:إزالة المصفوفة هي O(n) - يجب نقل كل العناصر لملء "الفتحة"

غير مرتبة ومرتبة:القائمة المرتبطة هي O(1) - قم بتغيير المؤشرات حسب الحاجة