22 Aralık 2023

Diziler

Objeler değerlerin anahtarlı bir şekilde koleksiyon halinde tutulmasını sağlar.

Fakat bazı durumlarda sıralı koleksiyon tutmak gerekebilir, 1., 2. ve 3. elemente ihtiyaç olabilir. Örneğin kullanıcıların, ürünlerin, HTML elementlerinin liste halinde tutulmasını istediğinizde;

Obje kullanmak mantıklı değildir, çünkü elemanların sırasını tutmaz bu objeler. Var olanların “arasına” yeni bir özellik girilemez. Objeler böyle kullanımlara uygun değildir.

Bunun için özel bir veri yapısı vardır. Array sıralı koleksiyonları tutar.

Tanımlama

Boş dizi oluşturmak için iki yöntem vardır:

          let arr = new Array();
let arr = [];
        

Neredeyse her zaman ikinci yazım kullanılır. Başlangıç değerlerini köşeli parantez içinde verebilirsiniz:

let meyveler = ["Elma", "Portakal", "Erik"];

Diziler sıfır ile başlarlar.

let meyveler = ["Elma", "Portakal", "Erik"];

alert( meyveler[0] ); // Elma
alert( meyveler[1] ); // Portakal
alert( meyveler[2] ); // Erik

Elamanı değiştirmek mümkündür:

meyveler[2] = 'Armut'; // Şimdi ["Elma", "Portakal", "Armut"]

… Veya diziye yeni bir eleman eklemek mümkündür:

meyveler[3] = 'Limon'; // Şimdi ["Elma", "Portakal", "Armut", "Limon"]

Dizide bulunan elemanların boyutu length metodu ile öğrenilebilir:

let meyveler = ["Elma", "Portakal", "Erik"];

alert( meyveler.length ); // 3

Ayrıca alert kullanarak tüm dizinin gösterilmesi de mümkündür:

let meyveler = ["Elma", "Portakal", "Erik"];

alert( meyveler ); // Elma,Portakal,Erik

Dizi her türlü elemanı tutabilir.

Örneğin:

// Karmaşık tipler
let arr = [ 'Elma', { isim: 'Ahmet' }, true, function() { alert('merhaba'); } ];

// Birinci indeksteki değeri al ve "isim" özelliğini görüntüle
alert( arr[1].isim ); // John

// 3. indeksteki fonksiyonu al ve çalıştır.
arr[3](); // merhaba

Diziler objeler gibi virgül ile bitebilir:

          let meyveler = [
  "Elma",
  "Portakal",
  "Erik",
];
        

“Sürekli virgül” stili yeni eleman ekleme veya çıkarma işlemlerini kolaylaştırır.

pop/push, shift/unshift işlemleri için metodlar

Kuyruk dizilerin en fazla kullanıldığı yerdir. Bilgisayar biliminde, sıralı elemanların koleksiyonları iki operasyonu desteklemelidir:

Sonuna yeni eleman eklemeli : push.
shift ile başlangıçtan eleman alındığında ikinci eleman birinci olmalı.

Diziler bu iki işlemi de destekler.

Bu işlemler ile çokça karşılaşılır. Örneğin, kuyruktaki mesajların hepsinin ekranda gösterilmesi gerekebilir.

Dizilerin diğer bir kullanım amacı ise diğer bir veri yapısı içindir. Stack

İki operasyonu destekler

push : sona eleman ekler.
pop : sondan eleman alır.

Bundan dolayı yeni elemanlar her zaman sondan alınır veya sona eklenir.

Yığın bir deste kart olarak düşünülebilir: yeni kartlar eklendiğinde en üste konulur veya en üstten alınır.

Yığına en son eklenen eleman ilk olarak alınır, Buna LIFO (Last-In-First-Out) Son giren ilk çıkar prensibi denir. Kuyruklar için ise FIFO (First-In-First-Out) yani ilk giren ilk çıkar prensibi kullanılır.

JavaScript’te diziler yığın veya kuyruk olarak kullanılabilirler. Başlangıca veya sona yeni eleman eklenebilir veya çıkartılabilir.

Bilgisayar biliminde bu işlemlere izin veren veri yapılarına deque denir.

Dizilerin sonu ile ilgili metodlar:

pop

Dizinin son elemanını döndürür:

let meyveler = ["Elma", "Portakal", "Armut"];

alert( meyveler.pop() ); // Armutu sil ve bunu ekranda bildir.

alert( meyveler ); // Elma, Portakal

push

Dizinin sonuna elaman ekler:

let meyveler = ["Elma", "Portakal"];

meyveler.push("Armut");

alert( meyveler ); // Elma, Portakal, Armut

fruit.push() ile fruit[fruits.length] = ... birbiri ile aynı anlama gelirler.

Dizilerin başlangıcı ile ilgili metodlar:

shift

Dizinin ilk elemanını döndürür:

          let meyveler = ["Elma", "Portakal", "Armut"];

alert( meyveler.shift() ); // Elmayı sil ve bunu ekranda bildir.

alert( meyveler ); // Portakal, Armut

unshift

Dizinin başlangıcına eleman ekleme:

          let meyveler = ["Portakal", "Armut"];

meyveler.unshift('Elma');

alert( meyveler ); // Elma, Portakal, Armut

push ve unshift metodları aynı anda birden fazla eleman ekleyebilirler:

let meyveler = ["Elma"];

meyveler.push("Portakal", "Armut");
meyveler.unshift("Ananas", "Limon");

// ["Ananas", "Limon", "Elma", "Portakal", "Armut"]
alert( meyveler );

Özellikler

Dizi özel bir tip objedir. arr[0] ile özelliğe erişme aslında objelerden gelen bir yazım şeklidir. Sayılar anahtar olarak kullanılmaktadır.

Objeleri daha genişleterek sıralı veri koleksiyonları ve length gibi özellikler alması sağlanmıştır. Fakat derininde diziler objedir.

Hatırlarsanız, JavaScript’te sadece 7 basit tip bulunmaktadır. Dizi obje olduğundan obje gibi davranır.

Örneğin referans ile kopyalanır:

let meyveler = ["Muz"]

let arr = meyveler; // iki değişken aynı diziye referans verir. ( referans ile kopyalama )

alert( arr === fruits ); // true

arr.push("Armut"); // diziyi referans ile düzenleme

alert( meyveler ); // Muz, Armut - 2 eleman

… Fakat dizileri asıl önemli kılan içinde neler olduğudur. JavaScript motoru elemanları ardışık hafıza alanlarında tutmaya çalışır. Böylece diziler çok hızlı şekilde çalışabilirler.

Fakat eğer “sıralı koleksiyon” olan diziden çıkılır ve obje olarak çalıştırılırsa her şey bozulur.

Örneğin, teknik olarak aşağıdaki örnek bunu yansıtır:

          let meyveler = []; // Dizi yap

meyveler[99999] = 5; // boyutundan çokça büyük bir özelliğe veri ata.

meyveler.yas = 25; // doğrudan özelliğe isim vererek atama yap.

Diziler tabanda obje olduğundan dolayı yukarıdaki işlem geçerlidir. İstendiği şekilde özellik eklenebilir.

Fakat bu durumda JavaScript motoru bizim diziler ile değil de normal objeler üzerinde çalıştığımızı sanar. Bundan dolayı diziye özel optimizasyon uygulanmayacaktır.

Diziyi yanlış kullanma biçimleri:

Sayısal olmayan bir özellik ekle arr.test = 5
Delikler yap: arr[0] ekle sonra arr[1000] ekle ( arada hiçbir değer yok)
Diziyi ters sıralı şekilde doldur, arr[1000], arr[999] vs.

Dizileri sıralı şekilde veri tutan özel bir yapı olarak düşünün. Bunun için özel metodlara sahiptir. JavaScript motoru içerisinde diziler çok etkili ve hızlı bir şekilde çalıştırılmak üzere ayarlanmıştır. Sizde bu şekilde kullanmaya hassasiyet gösterin. Eğer özelliği belirtmek istiyorsanız, belki de normal obje kullanmanız gerekmektedir {}

Performans

push/pop metodları hızlı çalışır, shift/unshift ise yavaş

Peki neden dizinin başlangıcı ile bitişine eleman eklemek arasında hız farkı olmaktadır? Çalışma anında neler oluyor bakalım:

meyveler.shift(); // Başlangıçtan bir eleman al

0 indeksinde bulunan elemanı silmek yeterli değildir. Diğer elemanların tekrar numaralanması gerekmektedir.

shift metodunun yapması gereken 3 işlem vardır:

0 indeksinde bulunan elemanın silinmesi
Tüm elemanların sola kaydırılması, indekslerin tekrar numaralandırılması 1’den 0’a, 2’den 1’e vs.
uzunluk özelliğini güncelle.

Daha fazla elaman, daha fazla taşınma süresi , daha fazla hafıza içi işlem demektir.

Aynı şey unshift için de geçerlidir: dizilerin başına eleman ekleneceği zaman öncelikle elemanların sağa kaydırılarak indeks artırılması gerekir.

Peki push/pop için böyle işlemlere gerek yok mu? Sondaki elemanı alabilmek için pop metodu indexi siler ve length’i bir azaltır.

pop metodunun yaptığı işlemler:

fruits.pop(); // Sondan bir eleman al

pop hiçbir şey taşımaz çünkü diğer elemanların index’i değişmez. Bundan dolayı aşırı derecede hızlıdır.

push’da aynı şekilde sona ekler.

Döngüler

En eski yöntem for döngüsü kullanarak indeksler üzerinden dönmektir:

let dizi = ["Elma", "Portakal", "Armut"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

Diziler için diğer yöntem ise, for..of’tur:

let meyveler = ["Elma", "Portakal", "Erik"];

// Dizi elemanları üzerinden döner.
for(let meyve of meyveler) {
  alert( meyve );
}

for..of var olan elemanın kaçıncı eleman olduğunun görülmesine izin vermez, sadece değeri döner. Fakat çoğu durumda bu daha kısa ve yeterli bir kullanımdır.

Teknik olarak diziler objedir, bundan dolayı for..in kullanmak mümkündür.

let arr = ["Elma", "Portakal", "Erik"];

for (let key in arr) {
  alert( arr[key] ); // Elma, Portakal, Erik
}

Fakat bu bazı problemlere neden olur:

for..in döngüsü var olan tüm özelliklerin üzerinden geçer, sadece sayısal olanların değil.

“dizi-benzeri” objeler bazı tarayıcı ve diğer çevrelerde kullanılmaktadır. Bunlar “dizi gibi dururlar”, length ve indeks özelliklerine sahiptirler fakat sayısal olmayan özelliklere sahip metodlar da bulunmaktadır. Genelde bunlara ihtiyaç duyulmaz. for..in döngüsü bunları da listeler. Bundan dolayı dizi-benzeri bir obje ile çalışılacaksa, bu “ekstra” özellikler problem teşkil edebilir.
for..in döngüsü genel objeler için kullanışlıdır, diziler için değil. Bundan dolayı diziler için kullanıldığında 10-100 kata kadar daha yavaştır. Tabi hala hızlı sayılır. Bu hız sadece darboğaz (bottleneck) olduğunda önem kazanır, aksi halde anlamsızdır. Fakat yine de bu farkı bilmek iyidir.

Genel olarak, for..in diziler ile kullanılmaz.

“length” ile ilgili bir not.

length özelliği dizi düzenlendiğinde otomatik olarak güncellenir. Tam olarak bu uzunluk dizideki eleman sayısı değildir, en büyük sayısal indeksin bir fazlasıdır.

Örneğin indeksi büyük tek bir elemanlı dizi büyük uzunluk verir:

let meyveler = [];
meyveler[123] = "Elma";

alert( meyveler.length ); // 124

Genelde diziler bu şekilde kullanılmaz.

length hakkında diğer bir ilginç bilgi ise bu özelliğin yazılabilir olmasıdır.

Eğer elle bu değeri yükseltirseniz hiçbir şey olmaz, fakat düşürürseniz dizideki elemanlar silinir. Bu işlem geri döndürülemez, örneğin:

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 2 elemana düşür
alert( arr ); // [1, 2]

arr.length = 5; // uzunluğu geri al
alert( arr[3] ); // undefined: değer dönmez

Dizinin içerisini silmenin kolay yolu : arr.length=0.

new Array()

Dizi yaratmanın bir diğer yolu ise aşağıdaki gibidir:

let arr = new Array("Elma", "Armut", "vs");

Bu şekilde yazım daha nadir kullanılır, [] kullanımı daha kısadır. Farklı bir özelliği daha vardır:

Eğer new Array sayı argümanı ile çağırılırsa, yeni bir boş dizi yaratır. İçerisine bir şey koymaz ve dizinin boyutunu belirtilen değer kadar tanımlar.

Bu özellik yanlış kullanıma müsaittir:

let arr = new Array(2); //  [2] diye bir dizi mi oluşturacak ?

alert( arr[0] ); // undefined! böyle bir eleman yok

alert( arr.length ); // length 2

Yukarıda new Array(sayı)'nın tüm elemanları undefined döndürür.

Böyle sürprizler ile karşılaşmamak için genelde [] kullanılır.

Çok Boyutlu Diziler

Dizilerin elemanları dizi olabilir. Matrisleri tutmak için çok boyutlu diziler kullanılabilir:

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // merkez eleman

toString

Dizilerin kendi toString uygulaması mevcuttur. Bu dizilerin arasına virgül konularak geri döndürülür.

Örneğin:

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // true

Şu şekilde denenirse:

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

Dizilerin Symbol.toPrimitive özellikleri yoktur, valueOf metodu da bulunmamaktadır. Sadece toString çevirimi mevcuttur. Bundan dolayı [] boş karakter dizisi döndürür , [1] 1, veya [1,2] "1,2" döndürür.

"+" operatörü karakter dizisine ekleme yaptığında diğer bölümü de karakter dizisine çevirir. Bundan dolayı sonraki adım şu şekilde görülür:

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

Özet

Dizi özel bir çeşit objedir, verilerin sıralı bir şekilde saklanması için uygun bir tiptir.

Tanım:

          // köşeli parantez ile (genel kullanılan)
let arr = [item1, item2...];

// new Array (Çok nadir kullanım)
let arr = new Array(item1, item2...);
        

new Array(number) verilen boyutlarda yeni bir dizi yaratır, fakat eleman olmadan.

length özelliği dizinin boyu ve daha net olmak gerekirse son index sayısı + 1 şeklindedir. Dizi metodları tarafından otomatik olarak ayarlanır.
Eğer length’i elle küçültürseniz dizi de kısalacaktır, tabi bu veri kayıplarına neden olabilir.

Dizi üzerinde aşağıdaki işlemler yapılabilir:

push(...items) items’ı sona ekler.
pop() sondan bir eleman siler ve döndürür.
shift() başlangıçtan eleman siler ve bunu döndürür.
unshift(...items) başlangıca items ekler.

Dizinin elemanlarını for döngüsü ile dönme:

for(let i=0; i<arr.length; i++) – hızlı çalışır ve eski tarayıcılara uyarlıdır.
for(let item of arr) – sadece elemanların yazımı için modern yazım sağlar.
for(let i in arr) – kullanılamaz.

Dizilere üzerinden tekrar geçilecektir. Diğer ekleme, silme, elemanların alınması, sıralanması gibi konulara Dizi Metodları bölümünde değinilecektir.

Görevler

Dizi kopyalandı mı?

Aşağıdaki kodun çıktısı nedir?

          let meyveler = ["Elma", "Armut", "Portakal"];

// kopyaya yeni bir değer ekleme.
let sepet = meyveler;
sepet.push("Muz");

// meyveler değişkeninin içinde ne vardır?
alert( fruits.length ); // ?
        

The result is 4:

let meyveler = ["Elma", "Armut", "Portakal"];

let sepet = meyveler;

sepet.push("Muz");

alert( sepet.length ); // 4

Diziler obje olduklarından dolayı sepet ve meyveler aynı diziye referans verirler.

Dizi işlemleri

5 dizi işleminin üzerinden geçin:

styles adında bir dizi oluşturun. İçerisinde “Jazz” ve “Blues” elemanları olsun.
“Rock-n-Roll” elemanını sona ekleyin.
Ortada bulunan elemanı “Classics” ile değiştirin. Yazacağınız kod tek elemanlı değerler için çalışmalı. 1-3-5-7 gibi
Dizinin ilk değerini sil ve göster.
Dizinin başlangıcına Rap ve Reggae gibi elemanlar ekleyiniz.

İşlemler aşağıdaki gibi olmalıdır:

          Jazz, Blues
Jazz, Bues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll
        

let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alert( styles.shift() );
styles.unshift("Rap", "Reggae");

Dizinin içerisinden çağrı

Sonuç ne olur? Neden?

          let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // ?
        

Yazım olarak arr[2]() bilinen obje hali ile obj[method]() ile aynıdır. Buradaki obj yerine dizi ve method yerine ise 2 bulunur.

Bundan dolayı arr[2] this referansını alır ve bu referans arr’i gösterir. Bundan dolayı sonuç:

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // "a","b",function

Dizinin 3 değeri bulunmaktadır: Başlangıçta tanımlanan 2 tanesi ve üstüne eklenen bir fonksiyon.

Girilen değerleri toplama

sumInput() fonksiyonunu aşağıdaki şekilde yazınız:

prompt ile kullanıcının değer girmesini sağlayın.
Eğer kullanıcı boşluk karakteri girerse veya “İptal” tuşuna basar ise işlemi bitirin.
Tüm girilen değerlerin toplamını hesaplayın.

Not: 0 bir sayıdır, eğer giriş sıfır ise lütfen programı durdurmayın.

Demoyu çalıştır

Önemli bir detay ile başlamak gerekirse. prompt’tan alınan deger doğrudan sayıya çevirilmez. Çünkü deger = +deger gelen değerin boş karaktermi ( dur işareti ) yoksa 0 ( geçerli sayı ) olup olmadığını söyleyemez. Bu daha sonra yapılacaktır.

function sumInput() {

  let sayilar = [];

  while (true) {

    let deger = prompt("Lütfen bir sayı giriniz?", 0);

    // İptal edilmeli mi?
    if (deger === "" || deger === null || !isFinite(deger)) break;

    sayilar.push(+deger);
  }

  let toplam = 0;
  for (let sayi of sayilar) {
    toplam += sayi;
  }
  return toplam;
}

alert( sumInput() );

A maximal subarray

The input is an array of numbers, e.g. arr = [1, -2, 3, 4, -9, 6].

The task is: find the contiguous subarray of arr with the maximal sum of items.

Write the function getMaxSubSum(arr) that will return that sum.

For instance:

          getMaxSubSum([-1, 2, 3, -9]) = 5 (the sum of highlighted items)
getMaxSubSum([2, -1, 2, 3, -9]) = 6
getMaxSubSum([-1, 2, 3, -9, 11]) = 11
getMaxSubSum([-2, -1, 1, 2]) = 3
getMaxSubSum([100, -9, 2, -3, 5]) = 100
getMaxSubSum([1, 2, 3]) = 6 (take all)
        

If all items are negative, it means that we take none (the subarray is empty), so the sum is zero:

getMaxSubSum([-1, -2, -3]) = 0

Please try to think of a fast solution: O(n²) or even O(n) if you can.

Testler ile korunaklı olan aç.

Slow solution

We can calculate all possible subsums.

The simplest way is to take every element and calculate sums of all subarrays starting from it.

For instance, for [-1, 2, 3, -9, 11]:

          // Starting from -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Starting from 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Starting from 3:
3
3 + (-9)
3 + (-9) + 11

// Starting from -9
-9
-9 + 11

// Starting from 11
11
        

The code is actually a nested loop: the external loop over array elements, and the internal counts subsums starting with the current element.

function getMaxSubSum(arr) {
  let maxSum = 0; // if we take no elements, zero will be returned

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

The solution has a time complexety of O(n²). In other words, if we increase the array size 2 times, the algorithm will work 4 times longer.

For big arrays (1000, 10000 or more items) such algorithms can lead to a serious sluggishness.

Fast solution

Let’s walk the array and keep the current partial sum of elements in the variable s. If s becomes negative at some point, then assign s=0. The maximum of all such s will be the answer.

If the description is too vague, please see the code, it’s short enough:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // for each item of arr
    partialSum += item; // add it to partialSum
    maxSum = Math.max(maxSum, partialSum); // remember the maximum
    if (partialSum < 0) partialSum = 0; // zero if negative
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

The algorithm requires exactly 1 array pass, so the time complexity is O(n).

You can find more detail information about the algorithm here: Maximum subarray problem. If it’s still not obvious why that works, then please trace the algorithm on the examples above, see how it works, that’s better than any words.

Çözümü testler korunaklı alanda olacak şekilde aç.

Eğitim haritası

Yorumlar

yorum yapmadan önce lütfen okuyun...