سوال بپرسید

چرا در C++ سرعت پردازش در یک آرایه مرتب شده سریع تر از آرایه نامرتب است؟

سوال بپرسید

بنده یک تکه کد C++ (سی پلاس پلاس) دارم که نتایج عجیب و غریبی برای من داشته است. توی این قطعه کد یک آرایه دارم که داده های آن را به صورت منظم، با استفاده از دستور sort مرتب کردم.

حالا در خروجی نتایج خودم متوجه شدم که این کد شش برابر سریع تر از حالتی عمل می کند که آرایه ها نامرتب هستند!؟

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

بدون دستور زیر این کدها در مدت زمان ۱۱.۵۴ ثانیه اجرا شد.

std::sort(data, data + arraySize);

این درحالی بود که وقتی این دستور را قرار دادم مدت زمان اجرای برنامه به ۱‍.۹۳ ثانیه کاهش پیدا کرد.

در ابتدا فکر کردم که این نتیجه چیزی نیست جز یک خطای کامپایلری و تصمیم گرفتم با استفاده از یک زبان دیگر مانند جاوا همین نتایج را بررسی کنم:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

با اجرای این کدها در زبان جاوا متوجه شدم که دقیقا همان نتایج برای این زبان وجود داشت.

در ابتدا من فکر کردم که این نتایج به دلیل کش شدن (Cache) داده های مرتب در حافظه است ولی بعدا دیدم که این یک تفکر اشتباه می باشد، چون آرایه ها به خودی خود تولید شده اند و چیزی در حافظه پنهان نشده است.

اما دو سوال اصلی من پس از مطرح کردن این مباحث اینه: