Kod efficiency

Bir çox yolla kodun keyfiyyətini ölçmək olar. Ən əsas və vaciblərdən biri kodun baxımlılığıdır (maintainability). Kodun baxımlılığına aid olan xüsusiyyətlər arasında oxunaqlıq (readability), modulluq (modularity) və s. var.

Ancaq keyfiyyətli kodun başqa bir aspekti də var — kodun səmərəliliyi (efficiency). Ola bilər ki, iki kod parçası olsun, ikisi də eyni işi görsün, amma biri daha sürətli olsun.

Məsələn:

Aşağıdakı nümunələrdə iki funksiyada cüt rəqəmləri konsola yazdırır

const versionOne = () => {
  let num = 2;
  while (num <= 100) {
    if (num % 2 === 0) {
      console.log(num);
    }
    // bir-bir artır
    num += 1;
  }
};

const versionTwo = () => {
  let num = 2;
  while (num <= 100) {
    if (num % 2 === 0) {
      console.log(num);
    }
    // Burada isə iki-iki artırırıq, hansı ki, cüt rəqəm istəyirik
    num += 2;
  }
};

Yuxarıdakı kodlardan versionTwo funksıyası daha surətlidir. Çünki birinci kod 100 dəfə dövr edir, ikinci isə 50 dəfə. Birinci kod, ikinciyə görə ikiqat addım(steps) atır.

Sürətli kod yazmağın ilk addımı, data strukturu nədir və fərqli data strukturlarının kodumuzun sürətinə necə təsir edə biləcəyini anlamaqdır.

Data Strukturu

Data geniş bir ifadədir və bir çox informasiyaya istinad edir. Numbers, String. Sadə amma klassik olan ‘Hello World’ proqramındakı string ‘Hello World’ bir datadır. Hətta ən mürəkkəb məlumat parçaları da adətən bir çox ədəd və string-ə ayrılır.

Data strukturları məlumatın necə saxlandığını bildirir. Eyni data fərqli şəkillərdə saxlanıla bilər.

Məsələn, gəlin bir koda baxaq.

const x = 'Salam!';
const y = 'Dostum';
const z = 'necesən?';
console.log(x, y, z); // Salam! Dostum necesən?

Kodumuzun necə saxlandığını demək istəsək deyərdik ki, üç müstəqil string-imiz var, hər biri dəyişkəndə(variable) saxlanılır. Amma eyni data array-də də saxlanıla bilər.

const array = ['Salam!', 'Dostum', 'necesən?'];
console.log(array[0], array[1], array[2]); // Salam! Dostum necesən?

Data strukturuna bağlı olaraq, proqramınızın işləmə sürəti qatlarla dəyişir. Minlərlə insanın eyni anda istifadə etdiyi bir veb tətbiqi qurursunuzsa, seçdiyiniz data strukturları proqramınızın işləyib-işləməyəcəyini təsir edir

Burada , iki data strukturu array və set baxacayıq. Hər iki data strukturu bir-birinə bənzəsə də, hər biri performansa fərqlı təsir edir.

Fundamental Data Strukturu Array

Array ən fundamental və birinci öyrəndiyimiz data strukturlarından biridir. Artıq bilirik ki, array bir çox vəziyyətdə necə faydalı ola bilər. Bir nümunəyə baxaq.

Tutaq ki, bir Array-imiz var

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];

Bu array özündə 5 ədəd string saxlayır. Array-ın özünə məxsus jargonu var. Array-in size dedikdə, onun saxladığı elementlərinin sayını nəzərdə tuturuq. Bizim array-ın size 5-dır

Array-in index-i, bir datanın array-də harada yerləşdiyini göstərən rəqəmdir. Bir çox proqramlaşdırma dili indeksi sıfırdan başladır. Bizim nümunədə “Alma” 0-cı indexdə, “Üzüm” isə 4-cü indexdədir.

Hər hansı bir data strukturunun performansını anlamaq üçün — məsələn, array — bizim kodumuzun data strukturu ilə necə qarşılıqlı əlaqədə olduğunu təhlil etməliyik.

Bir çox data strukturu dörd əsas şəkildə istifadə olunur ki, bunlara biz operations deyirik. Operations bunlardır:

Read (Oxuma): Data strukturundan məlumatı oxumaq.
Search (Axtarış): Data strukturunda müəyyən bir elementi axtarmaq.
Insert (Əlavə etmə): Data strukturuna yeni bir element əlavə etmək.
Delete (Silmə): Data strukturundan müəyyən bir elementi silmək.

Kodun sürətini ölçmə

Biz operations sürətini necə ölçə bilərik?

Kitabdan alıntı:

əgər bu kitabdan yalnız bir şey götürsəniz, o da bu olsun: əməliyyatın nə qədər “sürətli” olduğunu ölçərkən, biz operation-ın saf vaxt baxımından nə qədər sürətli olduğunu nəzərə almırıq, nə qədər addım(steps) olduğunu ölçürük.

Bunu yuxarıda cüt rəqəmləri konsola yazdırmaq kontekstində görmüşük. O funksiyanın ikinci versiyası daha sürətli idi, çünki birinci versiyanın etdiyi addımların yarısını atırdı.

Bəs niyə kodu addımlara (steps) görə ölçürük?

Çünki heç vaxt əminliklə deyə bilmərik ki, hər hansı bir operations məsələn, beş saniyə çəkir. Bir kod müəyyən bir kompüterdə beş saniyə çəkə bilər, amma həmin eyni kod köhnə bir kompüterdə daha uzun çəkə bilər. Üstəlik, bu kod super kompüterlərdə çox daha sürətli işləyə bilər. Vaxtla əməliyyatın sürətini ölçmək düzgün deyil, çünki vaxt hər zaman işlədiyi cihaza görə dəyişəcək.

Ancaq, biz əməliyyatın sürətini nə qədər hesablama addımı (computational steps) apardığına görə ölçə bilərik. Əgər Operation A 5 addım, Operation B isə 500 addım çəkirsə, biz əminliklə deyə bilərik ki, Operation A bütün cihazlarda həmişə Operation B-dən daha sürətli olacaq.Buna görə də, addımların sayını ölçmək əməliyyatın sürətini analiz etmək üçün əsasdır.

Operasiyanın sürətini ölçmək “time complexity” və ya “efficiency” adlanır.

Reading

Kompüter array-dən məlumatı bircə addımda oxuya bilər.

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];

Məsələn, array-imizdən 2-ci indexi istəsək, bizə ‘Xurma’ nı qaytaracaq.

Kompüterin yaddaşı hüceyrə(cells) şəklində təşkil olunur. Hər bir hüceyrə müəyyən bir məlumatı saxlayır və xüsusi adresi olur. Bu hüceyrələr ardıcıl olaraq sıralanır

source

Proqram, array yaratdıqda ardıcıl olaraq boş hüceyrələrdən ibarət bir set ayırır. Proqramda istifadə etmək üçün. Məsələn, əgər beş element saxlamaq üçün bir array yaradsaq, kompüterimiz beş hüceyrədən ibarət bir sıra tapacaq və onu bizim array kimi təyin edəcək.

Açıklama yazısı

Şəkildə göründüyü kimi, bizim array 0054-cü adresdən başlayır və 0058-ə qədər gedir.

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];
// index  =>    0      1       2       3       4
// address =>  0054  0055    0056    0057    0058

Kompüter array yaratdıqda, array-in hansı adresdən başladığını qeyd edir. Əgər biz birinci elementi gətir deyəriksə, birbaşa birinci elementdəki məlumatı gətirir. Bu, sadəcə bir addım(step) alır.

Kompüter istənilən indexi tapa bilər, sadə bir hesablama ilə. Əgər biz index 3-dəki məlumatı istəyiriksə; başlanğıc indexinin adresinin üzərinə bizim istədiyimiz index əlavə ediləcək.

Yəni, bizim indexin adresi 0054-dən başlayır və bizə 3-cü index lazımdır.0054 + 3 = 0057. Kompüter artıq bildi ki, index 3, 0057-dir və bizə məlumatı verəcək: ‘Armud’.

Searching

Reading-də nə edirdik? Index verirdik və kompüter bizə dəyəri qaytarırdı. Searching-də isə value veririk və deyirik ki, valuenın olduğu indexi bizə qaytar.

Hər ikisi bir-birinə bənzəsə də, efficiency baxımından çox fərq var. Reading daha sürətlidir, çünki kompüter istənilən index-i asanlıqla tapa bilir. Amma Searching-də isə value-a görə axtarırıq index yoxdur

Kompüter yalnız adresləri görə bilir, adreslərdə hansı value-ların olduğunu bilmir. Həmin value-ları tapmaq üçün axtarış etməlidir.

Tutaq ki, bizim dəyərimiz ‘Armud’dur. Kompüter ‘Armud’u sıra ilə array-ın içində axtarmalıdır.

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];
// index  =>    0      1       2       3       4
// address =>  0054  0055    0056    0057    0058

Sıra ilə yoxlayır: 0-cı indexdə ‘Alma’ var, davam edir, 1-ci indexdə ‘Banan’ var, davam edir…. Bu şəkildə, dəyəri tapana qədər sıra ilə davam edir. 3-cü indexə çatanda artıq ‘Armud’u tapır və tapdıqdan sonra axtarışı dayandırır.

Addım-addım görək:

arr[0] — "Alma". "Armud" deyil (1 addım).
arr[1] — "Banan". "Armud" deyil (2 addım).
arr[2] — "Xurma". "Armud" deyil (3 addım).
arr[3] — "Armud". Tapıldı (4 addım).

Deməli, 4 stepdə tapdı.

Bu axtarışa, hansı ki, kompüter hər bir hüceyrəni (cell) sıra ilə yoxlayır, linear search deyilir.

Bizim array-də maksimum addım 5 olacaq, çünki 5 ədəd data var. Əgər 500 olsa, 500 addım atacaq.

Üzüm-u axtarsaq:

arr[0] — "Alma"
arr[1] — "Banan"
arr[2] — “Xurma”
arr[3] — “Armud”
arr[4] — “Üzüm” (Tapıldı, 5-ci addım)

Əgər Kivi yoxdursa, bütün array yenə də yoxlanacaq, yəni N addım.

Linear Search-də maksimum addım sayı array-dəki elementlərin sayına bərabərdir. Yəni, əgər array-də N element varsa, ən pis halda axtarış N addım çəkəcək.

Searching Reading-dən daha az effektivdir(efficiency), çünki searching bir neçə addım tələb edə bilər, reading həmişə yalnız bir addım çəkir, array-in ölçüsündən asılı olmayaraq.

Insertion

Array-ə yeni data əlavə edilməsinin effektivliyi (efficiency) onu array daxilində hara əlavə etdiyinizdən asılıdır.

Məsələn, biz array-mizin sonuna ‘kivi’ ni əlavə etmək istəsək, bu bir addım olacaq.

Biz array yaradarkən, kompüter array-in size-ını izləyir. Kompüter array-in başlanğıc ünvanınıda bilir, əgər array başlanğıcı 0054-dürsə və size 5-dirsə, bu deməkdir ki, sonuncu ünvan 0058-dir.

Sonuncu ünvanı bildiyi üçün, onnan bir sonrakı adresə, yəni 0059-a yeni datanı əlavə edir, bunu bir addımda edir.

Array-in əvvəlinə və ya ortasına yeni bir data əlavə etmək istəsək, əlavə etdiyimiz data üçün yer açmaq məqsədilə bəzi dataları hərəkət etdirməliyik. Bu da əlavə addımlar deməkdir.

Məsələn, alma ilə bananın arasına kivi əlavə etmək istəyirik.

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];
// index  =>    0      1       2       3       4
// address =>  0054  0055    0056    0057    0058

Kompüter addım-addım nə edir:

“Üzüm” 0058 ünvanından 0059 ünvanına shift olunur. -Burda təzə yer açır-
“Armud” 0057 ünvanından 0058 ünvanına shift olunur.
“Xurma” 0056 ünvanından 0057 ünvanına shift olunur.
“Banan” 0055 ünvanından 0056 ünvanına shift olunur.
“Kivi” 1-ci indekse yerləşir (0055).


Index 0    => "Alma"   => 0054
Index 1    => "Kivi"   => 0055 (Yeni əlavə edilmiş data)
Index 2    => "Banan"  => 0056
Index 3    => "Xurma"  => 0057
Index 4    => "Armud"  => 0058
Index 5    => "Üzüm"   => 0059

5 addım oldu. İlk 4-ü sağa doğru shift etmək, sonuncu addım isə datanın yerinə qoymaq.

Array-ə məlumat əlavə edərkən, ən çox addım tələb edən vəziyyət, data-nı array-in əvvəlinə əlavə edildiyi haldır. Bu halda, bütün digər dəyərləri bir hüceyrə sağa hərəkət etdirmək lazımdır. Bu əməliyyat N elementli bir array-də N+1 addım çəkə bilər, çünki bütün elementləri hərəkət etdirmək və sonra yeni dəyəri əlavə etmək.

Deletion

Deletion Array-dan müəyyən bir index-dəki dəyərin silinməsi prosesidir.

Array-ımızə baxaq:

const arr = ['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];
// index  =>    0      1       2       3       4
// address =>  0054  0055    0056    0057    0058

Buradan, index 2-dəki “Xurma”-nı silək. Array yaddaşda belə görünəcək:

["Alma","Banan", empty cell ,"Armud","Üzüm"];

Silmə əməliyyatı bir addım (step) alır, amma silmə sonrası ortada boş bir hüceyrə qalır və “Armud” və “Üzüm” sağa doğru hərəkət etməlidir.

Index 0   => "Alma"   => 0054
Index 1   => "Banan"  => 0055
Index 2   => EMPTY CELL => 0056
Index 3   => "Armud"  => 0057
Index 4   => "Üzüm"   => 0058

Index 0    => "Alma"  =>  0054
Index 1   => "Banan" =>  0055
Index 2   => "Armud" =>  0056
Index 3   => "Üzüm"  =>  0057

Array sonunda belə görünəcək. Burada 2 addım oldu: 1-ci addımda ‘Armud’ shift edildi, 2-ci addımda isə ‘Üzüm’ shift edildi. Ümumi silmə 3 addım oldu.

Insertion kimi ən pis hal əvvəlki elementi silib, bütün elementləri shift etməkdir. Əgər array-in 0-cı indexi boş olsa, bütün array-dakı elementləri shift etməliyik. Məsələn, 500 elementli bir array-da 1 step silmək olacaq, qalan 499 step isə elementlərin yerini dəyişmək üçün tələb olunur.

Yəni N elementli bir array-də N addım çəkə bilər.

Sets

Set data strukturu təkrar elementlərə icazə vermir.

const mySet = new Set(['Alma', 'Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm']);
console.log(mySet);
// Set(5) { 'Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm' }

Bu kodda iki dəfə “Alma” əlavə edilsə də, Set yalnız birini saxlayır, çünki təkrarlanan elementlər avtomatik olaraq silinir. Bu, Set-in təməl xüsusiyyətidir

Operation-lar

Reading — Array-dəki kimi yalniz 1 addim olur

Searching — Array-dəki kimi N addim olur

Deletion —Array-dəki kimi N addim olur

Insertion isə fərqlidir, çünki Set əmin olmalıdır ki, bizim əlavə etdiyimiz element artıq Set-in içində yoxdur. Biz Set-ə yeni element əlavə etdikdə, kompüter əvvəlcə Set-in içini axtarır (search edir), sonra isə əlavə etmə əməliyyatını (insertion) yerinə yetirir.

['Alma', 'Banan', 'Xurma', 'Armud', 'Üzüm'];

Tutaq ki biz setmizin sonuna “Kivi” elave etmek istetek

Addım-addım görək:

“Alma”. “Kivi” deyil (1 addım).
“Banan”. “Kivi” deyil (2 addım).
“Xurma”. “Kivi” deyil (3 addım).
“Armud”. “Kivi” deyil (4 addım).
“Üzüm”. “Kivi” deyil (5 addım).
Və ən sona əlavə edir (6 addım).

Nəticə: İnsertion N+1 addım alır.

Ancaq əgər biz Set-in əvvəlinə element əlavə etmək istəsək, bu 2N + 1 olacaq, çünki əvvəlcə N addım ilə search edirik ki, əlavə etdiyimiz elementin unikal olduğunu yoxlayaq. Daha sonra, N addım ilə digər elementləri sağa doğru shift edirik və sonuncu 1 addım isə yeni elementi yerinə əlavə etməkdir.

N addım search etmək üçün,
N addım shift etmək üçün,
1 addım isə elementin əlavə edilməsi üçün tələb olunur.

Bu da deməkdir ki, total addımlar 2N + 1 olacaq. Ancaq array-da bu N + 1 idi.

Bir sonrakı bölüm üçün: https://medium.com/%40eliqarayev/niy%C9%99-alqoritm-vacibdir-275ed190ceb1