1. Koleksiyon listesi
Hatırlayacağınız gibi, Java'nın aynı türden nesneleri depolamak için kullanışlı bir araç olan koleksiyonları vardır.
Koleksiyonla ilgili ana arayüzleri hatırlamaya çalışalım:
Liste , Küme , Harita ve Sıra .
Her zaman olduğu gibi, araçlar mutlaka iyi ya da kötü değildir - önemli olan onları amaçlarına uygun kullanıp kullanmadığınızdır. Ve bunu yapmak için, hangi koleksiyonun ne zaman kullanılacağını bilmek için belirli özelliklerini iyice anlamalıyız.
1. Liste
En çok kullanılan koleksiyonla başlayalım.
Düz bir eski diziye mümkün olduğunca yakın listeleyin .
Bu koleksiyon, bir dizi kullanıyor olsaydık zorunda kalacağımız gibi, koleksiyonun kendisinin boyutu hakkında endişelenmeden aynı türdeki nesnelerin bir listesini uygun bir şekilde saklamamızı sağlar. Koleksiyonun öğelerine index ile erişilir. Bir nesnenin tam olarak nerede olduğunu biliyorsak ve sık sık öğe eklemeye veya kaldırmaya gerek kalmadan ona sık sık erişmemiz gerekiyorsa, bir Liste idealdir.
2. Ayarla
Set tamamen farklı bir yapıya sahiptir.
Set, benzersiz nesneleri saklamamız gerektiğinde en uygunudur. Örneğin, her yazarın benzersiz olduğu bir kitaplıktaki yazar grubu. Ancak gidip ondan herhangi bir belirli yazarı alamayız. Set, kitaplığımızda belirli bir yazarın olup olmadığını hızlı bir şekilde kontrol etmemizi sağlar, yani Set içinde benzersiz bir nesne olup olmadığını kontrol edebiliriz . Ayrıca, her öğeye erişerek tüm koleksiyonu yineleyebiliriz, ancak bunu yapmak optimal değildir.
Başka bir deyişle, kitaplığımız için bir Küme , herhangi bir yazarın mevcut olup olmadığını hızlı bir şekilde kontrol etmek için tüm benzersiz yazarların koleksiyonunu temsil edebilir.
3. Harita
Harita daha çok, her dosyanın imzalandığı ve tek tek nesneleri veya tüm yapıları saklayabildiği bir dosya dolabı gibidir. Harita, bir değerden diğerine eşlemeyi sürdürmemiz gereken durumlarda kullanılmalıdır.
Map için bu ilişkilere anahtar/değer çiftleri denir.
Anahtar olarak yazar nesnelerini, değer olarak kitapların listelerini ( List nesneleri) kullanarak bu yapıyı kütüphanemizde kullanabiliriz . Böylece, kitaplıkta bir yazar nesnesinin olup olmadığını görmek için bir Kümeyi kontrol ettikten sonra, aynı yazar nesnesini bir Haritadan kitaplarının Listesini almak için kullanabiliriz .
4. Kuyruk
Queue bir koleksiyondur - sürpriz! — bir kuyruğun davranışını uygular. Sıra, LIFO (Son Giren İlk Çıkar) veya FIFO (İlk Giren İlk Çıkar)olabilirDahası, sıra çift yönlü veya "çift uçlu" olabilir.
Bu yapı, sınıfa eklenen nesnelerin alındıkları sırayla kullanılması gerektiğinde yardımcı olur. Örneğin, kütüphanemizi ele alalım.
Yeni gelen ziyaretçileri bir Kuyruğa ekleyebilir ve sırayla geldikleri kitapları yayınlayarak onlara hizmet verebiliriz.
Gördüğümüz gibi, bu yapıların her biri, amacına uygun kullanıldığında iyidir. Ve tek bir kitaplık örneğinde dört tür koleksiyonun tümü için iyi kullanımlar bulduk.
2. Karmaşıklık
Daha önce de belirttiğimiz gibi, yukarıda ele aldığımız koleksiyonlar arayüzlerdir, yani onları kullanabilmemiz için uygulamalarının olması gerekir.
Mikroskopla çivi çakmak nasıl en iyi fikir değilse, koleksiyonun her uygulaması da her duruma uygun değildir.
Bir iş için doğru aleti seçerken genellikle 2 özelliğe bakarız:
- Alet işe ne kadar uyuyor?
- İşi ne kadar hızlı bitirecek?
Bir iş için uygun aleti nasıl seçeceğimizi bulmak için biraz zaman harcadık, ancak hızı yeni bir şey.
Hesaplamada, bir aracın hızı genellikle zaman karmaşıklığı cinsinden ifade edilir ve büyük O harfiyle gösterilir.
Zaman karmaşıklığı nedir ki?
Basit bir ifadeyle, zaman karmaşıklığı, koleksiyondaki bir algoritmanın belirli bir eylemi (bir öğe ekleme/çıkarma, bir öğe arama) gerçekleştirmesi için gereken süreyi gösterir.
ArrayList ve LinkedList
Buna List arabiriminin iki uygulamasını kullanarak bakalım — ArrayList ve LinkedList .
Dış görünüş için bu koleksiyonlarla çalışmak benzerdir:
List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
List<String> linkedList = new LinkedList<>();
linkedList.add(String);
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
Gördüğünüz gibi, her iki koleksiyon türü için de öğe eklemek, almak ve kaldırmak aynı görünüyor. Bunun nedeni, bunların aynı arabirimdeki uygulamalar olmasıdır. Ancak benzerliklerin bittiği yer burasıdır.
Liste arayüzünün farklı uygulamaları nedeniyle , bu iki yapı farklı eylemleri diğerlerinden daha verimli gerçekleştirir.
Bir öğeyi kaldırmayı ve eklemeyi düşünün.
Bir ArrayList öğesinin ortasından bir öğeyi kaldırmamız gerekirse , listenin kaldırdığımız öğeyi takip eden kısmının üzerine yazmamız gerekir.
Diyelim ki 5 öğeden oluşan bir listemiz var ve 3. öğeyi kaldırmak istiyoruz.
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
Bu durumda, çıkarma bir hücreyi serbest bırakır, bu nedenle 3. öğenin olduğu yere 4. öğeyi ve 4. öğenin olduğu yere 5. öğeyi yazmamız gerekir.
Bu oldukça verimsizdir.
Listenin ortasına bir öğe eklerken de aynı şey olur.
LinkedList farklı yapılandırılmıştır. Öğeleri eklemek veya çıkarmak hızlıdır, çünkü yalnızca önceki ve sonraki öğelerdeki referansları değiştirmemiz gerekir, böylece öğe zincirinden çıkardığımız nesneyi hariç tutarız.
Aynı 5 elemanlı liste örneğine dönersek, 3. elemanı çıkardıktan sonra tek yapmamız gereken 2. elemanın referansını bir sonraki elemana ve 4. elemanın referansını bir öncekine değiştirmek.
Listeye bir öğe eklendiğinde, aynı işlem tersine gerçekleşir.
ArrayList'e kıyasla LinkedList'te ne kadar az iş yapmamız gerektiğine dikkat edin . Ve bu sadece 5 element. Listemizde 100 veya daha fazla öğe olsaydı, LinkedList'in üstünlüğü daha da belirginleşirdi.
Ancak bir öğeye dizine göre erişirsek durum nasıl değişir?
Burada her şey tam tersi.
ArrayList sıradan bir dizi olarak yapılandırıldığı için herhangi bir elemanı indeksine göre almak bizim için çok kolay olacaktır. İşaretçiyi belirli bir yere hareket ettiririz ve ilgili hücreden öğeyi alırız.
Ancak bir LinkedList bu şekilde çalışmaz. Belirli bir dizine sahip öğeyi bulmak için listenin tüm öğelerini gözden geçirmeliyiz.
Tüm bunları büyük O cinsinden ifade etmeye çalışalım mı?
Bir öğeye dizine göre erişerek başlayalım.
Bir ArrayList'te bu , öğenin listede nerede bulunduğundan bağımsız olarak tek adımda gerçekleşir. İster sonunda ister başında.
Bu durumda, zaman karmaşıklığı O(1) olacaktır .
Bir LinkedList'te , ihtiyacımız olan dizinin değerine eşit sayıda öğeyi yinelememiz gerekir.
Böyle bir eylem için zaman karmaşıklığı O(n)' dir , burada n ihtiyacımız olan öğenin indeksidir.
Burada büyük O parantez içine koyduğumuz sayının gerçekleştirilen işlem sayısına karşılık geldiğini görüyorsunuz.
Çıkarmaya ve eklemeye geri dönelim mi?
LinkedList ile başlayalım.
Bir eleman eklemek veya çıkarmak için çok sayıda işlem yapmamız gerekmediğinden ve bu işlemin hızı hiçbir şekilde elemanın bulunduğu yere bağlı olmadığından, karmaşıklığı O(1) olarak ifade edilir ve denir . sürekli olmak
ArrayList için bu işlemin zaman karmaşıklığı da lineer karmaşıklık dediğimiz O(n) şeklindedir.
Doğrusal karmaşıklığa sahip algoritmalarda, çalışma süresi doğrudan işlenecek öğe sayısına bağlıdır. Listenin başında mı yoksa sonunda mı olduğu, öğenin konumuna da bağlı olabilir.
Zaman karmaşıklığı da logaritmik olabilir. Bu, O(log n) olarak ifade edilir .
Örnek olarak, 10 sayıdan oluşan sıralanmış bir TreeSet düşünün. 2 sayısını bulmak istiyoruz.
Liste sıralı olduğundan ve tekrar içermediğinden, onu ikiye bölebilir ve hangi yarısında istenen sayının bulunacağını kontrol edebilir, ilgisiz kısmı atabilir ve ardından istenen öğeye ulaşana kadar bu işlemi tekrarlayabiliriz. En sonunda, log(n) eleman sayısını işledikten sonra sayıyı bulacağız (ya da bulamayacağız).
İşte koleksiyonların geri kalanının zaman karmaşıklığını özetleyen bir tablo.
dizine göre | anahtara göre | Aramak | sonunda ekleme | Sonunda ekleme | Kaldırma | |
---|---|---|---|---|---|---|
Dizi Listesi | O(1) | Yok | Açık) | O(1) | Açık) | Açık) |
Bağlantılı liste | Açık) | Yok | Açık) | O(1) | O(1) | O(1) |
HashSet | Yok | O(1) | O(1) | Yok | O(1) | O(1) |
Ağaç Kümesi | Yok | O(1) | O(günlük n) | Yok | O(günlük n) | O(günlük n) |
HashMap | Yok | O(1) | O(1) | Yok | O(1) | O(1) |
Ağaç Haritası | Yok | O(1) | O(günlük n) | Yok | O(günlük n) | O(günlük n) |
DiziDeque | Yok | Yok | Açık) | O(1) | O(1) | O(1) |
Artık popüler koleksiyonların zaman karmaşıklığını gösteren bir tablomuz olduğuna göre, neden bu kadar çok koleksiyon arasından en çok ArrayList , HashSet ve HashMap kullandığımız sorusunu yanıtlayabiliriz .
Basitçe, çoğu görev için en verimli olanlardır :)
GO TO FULL VERSION