Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.
Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin. Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Nega tartiblangan massiv tartiblanmagan massivdan tezroq?

+8 ovoz
133 marta ko‘rilgan
so‘radi 04 fevral, 17 Baron (858 bal)
tahrirlandi 10 fevral, 17 Baron

Quyidagi dastur bajarilishi natijasida juda qiziq holatga duch keldim. Berilganlarni tartiblash kodni deyarli 6 barobar tezroq ishlashiga olib kelmoqda.

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

int main()
{
    // Berilganlarni hosil qilish
    const unsigned arraySize = 32768;
    int data[arraySize];

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

    // !!! Shu orqali keyingi sikl tezroq bajarilmoqda
    std::sort(data, data + arraySize);

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

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Asosiy sikl
        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); olib tashlanganda kod ~11.5 sekund bajarildi
    
  • Tartiblangan berilganlar bilan esa ~1.9 sekund bajarildi.

Balkim dasturlash tiliga yoki kompilyatorga bog'liqdir deb o'yladim, keyin Javada tekshirib ko'rdim:

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

public class Main
{
    public static void main(String[] args)
    {
        // Berilganlarni hosil qilish
        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;

        // !!! Shu orqali pastdagi sikl tezroq ishlamoqda
        Arrays.sort(data);

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

        for (int i = 0; i < 100000; ++i)
        {
            // Asosiy sikl
            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);
    }
}

Natijalar C++ tilidagi natijalar bilan deyarli bir xil chiqdi. Ya'ni tartiblangan massiv bilan ishlaganda kod tezroq bajarilmoqda.

Nima sabab bilan bunday bo'lmoqda? Nega tartiblangan massiv bilan ishlaganda tartiblanmagan massiv bilan ishlagandan ko'ra tezroq natijaga erishilmoqda? Koddan ko'rinib turibdi, massivning tartiblanganligi natijaning chiqishiga ta'sir qilmaydi.

izoh qoldirdi 04 fevral, 17 alimovich (284 bal)
Kodiz xatoga o'xshayapti. Har safar har safar sum har xil bo'lyaptimi?
izoh qoldirdi 05 fevral, 17 Baron (858 bal)
1-dan, kod xato bo'lsa xato joyini topib ko'rsating, ikkinchidan, savolda sum har xil chiqvotti degan joyi umuman yo'q, yaxshilab e'tib bersangiz c++ dagi kodda ham, javadagi kodda ham shart va sum yig'ish qismi bir xil! Savol massivning tartiblangan holati va tartiblanmaga holati haqida!
izoh qoldirdi 09 fevral, 17 Sardor Dushamov (1,660 bal)
bu o'sha mashxur savolku )
izoh qoldirdi 09 fevral, 17 Baron (858 bal)
Ha, ammo javobini yozadigan mard topilmayapti :)
izoh qoldirdi 09 fevral, 17 vejon (2,980 bal)
Baron, alimovichni izohlariga qoldirgan izohiz nazarimda ozgina qo'pol chiqibdi...

Iltimos, saytga kiring yoki ro‘yxatdan o‘ting va shunda ushbu savolga javob berishingiz mumkin bo‘ladi.

Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.

Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin.

Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Telegram kanal YordamUzRss

...