İçeriğe atla

Dinamik dizi

Bellek tahsisi yaparken geometrik artırma yöntemi kullanılarak dinamik dizinin sonuna eleman ekleniyor. Boş kutular uzatılmış belleği ifade ediyor. Eklemeler sabit zamanlı (Θ(1)) ancak ekleme kapasitenin sonuna denk geldiğinde yeniden bellek tahsisi gerektirdiğinden yavaş (Θ(n) zaman) kalıyor (kaplumbağa ile gösterilmiştir). Dizinin boyu (logical size) ve kapasitesi (capacity) sonda gösterilmiştir.

Dinamik dizi, tutabileceği eleman sayısının derleme zamanında bilinmesine gerek olmayan dizidir. Dinamik dizi tanımlandığında, kapasitesini belirten bir bellek tahsis edilir ve kullanımda kapasiteye erişildiğinde yeniden bir dinamik bellek tahsisi yapılır. Dinamik diziye elemanlar eklenebilir, diziden elemanlar silinebilir; dizinin boyutu azaltılabilir ve arttırılabilir. Bazı programlama dillerinde vektör adıyla anılan bu yapıyı birçok modern programlama dili kendi kütüphaneleriyle sunmaktadır.

Diziler ve sabit boyutun dezavantajları

İdeal veri yapılarının ortak özelliği değiştirilebilir ve esnek olmasıdır. İyi bir kullanıcının kullanacağı veri yapısı da bu özellikleri sağlamalıdır. Programlamanın temel veri yapısı olan diziler sabit boyutlu olmaları nedeniyle bu yeterliliğe erişememektedir. Bu sebeple programlama dillerinin gelişmesiyle paralel olarak farklı özelliklere ve esnekliklere sahip veri yapıları ortaya sunulmuş, kullanılmıştır.

Bazı kod dizilerinde sabit boyutlu bir dizi ihtiyacı karşılasa da bazı durumlarda yetersiz kalmaktadır. Kullanılacak veri sayısının belirsiz olması ya da önceden saptanamaması bu noktadaki temel problemdir. Bu probleme çözüm olarak klasik fakat verimsiz bir çözüm yolu sunulmaktadır. Bu çözüm yolu, ihtiyaç duyulandan daha fazla ya da anormal büyük boyutta bir dizi tanımlamaktır. Kimi zaman çözüm yolu olarak seçilen bu yöntem dizilerin yetersiz olması durumunu değiştirmemektedir. Çünkü, sabit boyuttaki bir dizinin bu boyutuna sığmayacak sayıda veri içermesi gerekliliği hiçbir zaman önceden saptanamaz. Diğer bir taraftan da bu çözüm yolu kod dizisinin çalışmak için ihtiyaç duyacağı hafıza miktarını arttıracaktır. Bu da kod dizisini hantallaştırmakla beraber çalışabilirliğini de düşürmektedir.

Çalışma şekli

Dinamik dizilerdeki ekleme ve silme işlemlerinin temel mantığı dizilerdeki gibidir. Aradaki farklılık sabit boyutlu bir dizinin kapasitesi dolduğunda yeni veri ekleme işleminin hata ile sonuçlanması, dinamik dizilerde ise aynı işlemin yeni bellek tahsisi kullanılarak başarılı olmasıdır.

En basit dinamik dizi yapısında arka planda çalışan iki dizi kullanılmaktadır. Bunlardan ilki veriyi tutmaktadır, ikincisi ise tampon bölge olarak görev yapmaktadır. Birinci bölge oluşturulduğunda dizi yeni oluşturulan daha büyük boyutlu bir diziye kopyalanarak ilk dizi silinmektedir.

Sınır durumdaki ekleme işlemi hakkında bir irdeleme yapılmalı ve dinamik dizinin ne zaman genişletilmesi gerektiğine çok iyi karar verilmelidir. Çünkü genişletme, eklemeye göre daha masraflı bir işlemdir. Birkaç elemandan oluşan dizilerde bu masraf göz ardı edilebilecek kadar düşük bir maliyette olsa da dizinin eleman sayısı arttıkça bu maliyette artmaktadır.

Performans

OperasyonBağlı listeDiziDinamik dizi
Erişim ve güncelleme Θ(n) Θ(1) Θ(1)
Ekleme Θ(1) Θ(1) Θ(1)
Genişleme gerektiren ekleme Θ(1) - Θ(n)
Gereksiz hafıza kullanımı 0 Θ(n) Θ(n)

Dinamik diziler performans olarak dizilere benzer performans gösterseler de genişleme durumlarındaki eklemelerde maliyet üst seviyelere varmaktadır.

  • Dizi içindeki bir elemana ulaşma ya da elemanı değiştirme performansı sabittir (Θ(1)).
  • Ekleme işlemi de aynı performanstadır ve sabittir (Θ(1)).
  • Genişleme gerektiren ekleme ise dizi içerisindeki eleman sayısına bağlı olarak artan bir performansa sahiptir (Θ(n)).
  • Gereksiz hafıza kullanımı genişlemeden önceki durumda minimumdur, diğer durumlarda yüksektir.

Dizilere bakarak erişim, güncelleme, ekleme açısından aynı performanstadır. Genişleme gerektiren ekleme yüksek maliyete sahiptir.

Bağlı listelerle kıyaslandığında ise erişim ve güncelleme daha hızlıdır. Genişleme gerektiren ekleme daha yüksek bi maliyete sahiptir. Bağlı listelerde sıfır olan gereksiz hafıza kullanımı dinamik dizilerde yüksektir.

Diller ve dinamik diziler

  • C ve pascal dilinde dinamik dizi sağlanmamaktadır. Fakat kullanıcı bunu simüle edebilir.
  • C++ dilindeki std::vector dinamik dizi implementasyonu sağlar.
  • C# dilinde List<> sınıfı dizi kullanımı sağlar.
  • Delphi ve D dilleri dinamik dizi kullanımı sağlamaktadır.
  • Java dilinde dinamik diziler, java.util paketinde bulunan Vector ve ArrayList sınıfları tarafından sağlanır.
  • Python list yapısını sağlar.
  • Rust std::vec::Vec yapısını sağlar.

Kaynakça

  • Veri Yapıları ve Algoritma, M.Ümit Karakaş, Beta Basım Yayın, 2000
  • Algoritma Geliştirme ve Veri Yapıları, Bülent Çobanoğlu, Pusula Yayıncılık, 2008
  • Data Structures and Algorithms, Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft, Addison-Wesley, 2005

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">C (programlama dili)</span> programlama dili

C, yapısal bir programlama dilidir. Bell Laboratuvarları'nda, Ken Thompson ve Dennis Ritchie tarafından UNIX işletim sistemini geliştirebilmek amacıyla B dilinden türetilmiştir. Geliştirilme tarihi 1972 olmasına rağmen yaygınlaşması Brian Kernighan ve Dennis M. Ritchie tarafından yayımlanan "C Programlama Dili" kitabından sonra hızlanmıştır. Günümüzde neredeyse tüm işletim sistemlerinin yapımında %95'lere varan oranda kullanılmış, hâlen daha sistem, sürücü yazılımı, işletim sistemi modülleri ve hız gereken her yerde kullanılan oldukça yaygın ve sınırları belirsiz oldukça keskin bir dildir. Keskinliği, programcıya sonsuz özgürlüğün yanında çok büyük hatalar yapabilme olanağı sağlamasıdır. Programlamanın gelişim süreciyle beraber programlamanın karmaşıklaşması, gereksinimlerin artması ile uygulama programlarında nesne yönelimliliğin ortaya çıkmasından sonra C programcıları büyük ölçüde nesne yönelimliliği destekleyen C++ diline geçmişlerdir.

Komut kümesi mimarisi, CPU'nun yazılım tarafından nasıl kontrol edileceğini tanımlayan bilgisayar soyut modelinin bir parçasıdır. ISA, işlemcinin ne yapabileceğini ve bunu nasıl yapacağını belirterek donanım ve yazılım arasında bir arayüz gibi davranır.

<span class="mw-page-title-main">RAM</span> herhangi bir sırada okunabilen ve değiştirilebilen bir tür geçici veri deposu

Rastgele erişimli hafıza veya rastgele erişimli bellek mikroişlemcili sistemlerde kullanılan, genellikle çalışma verileriyle birlikte makine kodunu depolamak için kullanılan herhangi bir sırada okunabilen ve değiştirilebilen bir tür geçici veri deposudur. Buna karşın diğer hafıza aygıtları saklama ortamındaki verilere önceden belirlenen bir sırada ulaşabilmektedir, çünkü mekanik tasarımları ancak buna izin vermektedir.

<span class="mw-page-title-main">Bellek yönetimi</span>

Ana belleğin işlemler arasında paylaştırılmasına ana bellek yönetimi ya da bellek yönetimi adı verilir. İşletim sisteminin bu amaçla oluşturulan kesimine de bellek yöneticisi adı verilir.

Paralel hesaplama ya da Koşut hesaplama, aynı görevin, sonuçları daha hızlı elde etmek için çoklu işlemcilerde eş zamanlı olarak işletilmesidir. Bu fikir, problemlerin çözümünün ufak görev parçalarına bölünmesi ve bunların eş zamanlı olarak koordine edilmesine dayanır. Paralel hesaplama ile performans artar, büyük sorunlar daha az sürede çözülür ve bilimdeki gelişmeler paralel hesaplamaya gereksinim duyar.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

<span class="mw-page-title-main">Assembly</span> uygulanan işlemlerle programlama dilinin birbirine çok yakın olduğu düşük seviye programlama dilleri

Assembly dili, bir işlemcinin komut kümesi üzerine tanımlanmış alt seviye bir dildir. Assembly dili kolay hatırlanabilir semboller tanımlar ve böylece işlemcinin makina koduna karşılık gelen sayı dizilerinin bilinmesine gerek kalmaz. Assembly dili, platformdan bağımsız yüksek seviyeli programlama dillerinin aksine, işlemci mimarisine bağımlıdır. Tipik uygulamaları; cihaz sürücüleri, alt seviyeli dahili (embedded) ve gerçek zamanlı sistemlerdir. Bır assembly programı assembler kullanılarak makine koduna çevrilir.

<span class="mw-page-title-main">Bilgisayar mimarisi</span>

Bilgisayar mimarisi, en küçüğe ve en başarılıya ulaşmayı hedeflerken aynı zamanda maliyeti de göz önünde bulundurduğu için sanat ve bilimin ortak buluştuğu nokta olarak da tanımlanır. Bilgisayar Mimarisi, bilgisayar parçalarının iç yapıları ve aralarındaki haberleşme bağlantıları ile ilgilidir.

<span class="mw-page-title-main">Sıralama algoritması</span>

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.

Bağlı liste, her elemanın bir değerinin yanında bir de referans içerdiği veri yapısıdır.

Programlama paradigmaları, programlama dillerini özelliklerine göre sınıflandırmanın bir yoludur. Diller birden fazla paradigma içinde sınıflandırılabilir.

<span class="mw-page-title-main">OpenCL</span>

OpenCL,, Apple tarafından 2008 yılında kâr amacı gütmeyen teknoloji şirketleri birliği Khronos Group'a önerilen, kabul gördükten sonra spesifikasyonu pek çok şirketin katkılarıyla hazırlanan heterojen hesaplama platformudur. OpenCL; destekli grafik işlemcileri, genel amaçlı işlemciler ve FPGA ler gibi farklı platformlarda hesaplama yapılmasına olanak sağlar. OpenCL AMD, Intel, NVIDIA ve ARM tarafından desteklenmektedir. Ayrıca OpenCL kullanılarak Sony Playstation cihazlarında kullanılan Cell işlemcilerde de hesaplama yapılabilmektedir.

<span class="mw-page-title-main">Öznitelik çıkarımı</span>

Makine öğrenimi, örüntü tanıma ve görüntü işleme alanlarında kullanılan öznitelik çıkarımı, girdi olarak verilen ölçülmüş verileri kullanarak türetilmiş değerler (öznitelikler) oluşturur. Türetilen değerlerin bilgilendirici ve artıksız olması, öğrenme sürecini kolaylaştırıcı olması ve bazı durumlarda insan uzmanlar tarafından daha iyi anlaşılabilir (yorumlanabilir) olması amaçlanır. Öznitelik çıkarımı, boyut indirgeme konusuyla ilişkilidir.

<span class="mw-page-title-main">Ayrıştırıcı (yazılım)</span>

Ayrıştırıcı, girdi verilerini alır ve girdinin yapısal bir temsilini vererek, süreçte doğru sözdizimini kontrol eden bir veri yapısı oluşturan bir yazılım bileşenidir. Ayrıştırma öncesinde veya sonrasında başka adımlar izlenebilir veya bunlar tek bir adımda birleştirilebilir. Ayrıştırıcı, genelde girilen karakter dizisinden belirteçler oluşturan ayrı bir sözcük tabanlı analiz motorunu takip eder. Ayrıştırıcılar elle programlanabilir veya bir ayrıştırıcı üreteci tarafından otomatik olarak veya yarı otomatik olarak oluşturulabilir. Ayrıştırma, biçimlendirilmiş çıktı üretimlerini tek bir şablonda tamamlama görevi görür. Bunlar, farklı etki alanlarına uygulanabilir, ancak bir derleyicinin girdi ve çıktı aşamaları gibi genellikle bir arada sunulur.

Programlama deyimi veya kod deyimi, bir veya daha fazla programlama dili içinde yinelenen bir yapının özel bir özelliğini ifade eder. Geliştiriciler programlama deyimlerini bir veya daha fazla kod parçasını ilişkilendirerek ve anlam vererek tanır. Deyim, uygulamada bitişik veya dağınık kod parçaları ile temsil edilen, koddaki bir örüntünün altında yatan bir kavram olarak görülebilir. Bu parçalar çeşitli programlama dillerinde, iskelet ve hatta kütüphanelerde mevcuttur. Genel olarak konuşursak, bir programlama deyimi, kullanılan programlama dilinde yerleşik bir özellik olmayan basit bir görevin algoritma veya veri yapısının doğal bir dil ifadesidir. Bir programlama diline yerleştirilmiş alışılmadık veya dikkate değer bir özellik. Ayrıca terim, uygulama algoritmalarının uygulanması ve ihmal edilmesi açısından karmaşık algoritmalara veya tasarım örüntülerine atıfta bulunmak için daha geniş bir şekilde kullanılabilir.

<span class="mw-page-title-main">Dize (bilgisayar bilimi)</span> karakter dizisi, veri türü

Bilgisayar programlamada dize, karakterlerden oluşan dizidir. Dizeyi oluşturan karakterler değişmez (sabit) veya değişken olabilir. İkincisi, elemanlarının mutasyona uğramasına ve uzunluğunun değiştirilmesine izin verebilir veya sabitlenebilir. Bir dize genellikle veri tipi olarak kabul edilir ve genellikle bayt dizi veri yapısı olarak uygulanır. Bazı karakterleri, genellikle karakterleri, bir dizi karakter kodlaması kullanarak saklar. Dize ayrıca daha genel dizileri veya diğer dizileri veri türlerini ve yapılarını gösterebilir.

C dinamik bellek yönetimi ve tahsisi, C standart kütüphanesinde mevcut bulunan birtakım hazır metotları kullanarak, kullanılacak olan program için bellekte sanal bir alan oluşturulmasını sağlar. C programlama dilinde dinamik bellek tahsisi için malloc, realloc, calloc ve free metotları kullanılmaktadır. malloc metodu kullanılarak bellekte bulunan kullanılmaya uygun bir alan, kullanıcı için tahsis edilir. Benzer şekilde calloc da bellekte kullanılmaya uygun bir hafıza alanını kullanıcının kullanımına açar fakat calloc hazırlanan bellek alanının içindeki verileri de sıfırlar. realloc metodu ise önceden calloc veya malloc kullanılarak oluşturulan bellek alanının büyüklüğünü dinamik zamanda (run-time'da) değiştirmek için kullanılır. free ise diğer dinamik bellek tahsisi metotları ile oluşturulan ve kullanılan bellek alanlarını temizlemek için kullanılır.

Bilgisayar biliminde dizi programlama, işlemlerin bir kerede tüm değerler kümesine uygulanmasına izin veren çözümleri ifade eder. Bu tür çözümler, bilimsel ve mühendislik ortamlarında yaygın olarak kullanılmaktadır.

MicroScript, hafif ve optimize edilmiş bir programlama dili ve işletim sistemidir. Gömülü sistemlerde kullanılmak üzere tasarlanmıştır ve sensörler, mikrokontrolcüler ve diğer kaynak sınırlı cihazlarda etkili bir şekilde çalışır.

C++ Standard Kütüphanesi, C++ programlama dilinde ve C++ ISO Standard'ıyla yazılmış sınıfların ve fonksiyonların koleksiyonudur.