Set
- Türkçe karşılığı
- küme
Günlük kullanımda iki ad da yaygın.
Kısaca
Set, her farklı değeri en fazla bir kez saklayan ve bir değerin içinde olup olmadığını çoğunlukla sabit sürede kontrol edebilen bir koleksiyondur.
Set veri yapısı nedir?
Set, birbirinden farklı değerlerden oluşan bir koleksiyondur: her değer en fazla bir kez bulunur ve zaten var olan bir değeri eklemek hiçbir şeyi değiştirmez. Dizi ya da listeden farklı olarak Set konumla değil üyelikle ilgilidir; yanıtladığı temel soru, verilen bir değerin içinde olup olmadığıdır. Fikir matematikten gelir; orada küme, belirli bir sırası olmayan farklı nesnelerin topluluğudur.
Çoğu Set uygulaması hash tablosu üzerine kuruludur. Bir değeri eklemek, bucket seçmek için onu hash'ler; üyelik kontrolü de onu yeniden hash'leyip yalnızca o bucket'a bakar. Böylece ekleme, silme ve içerme kontrolü, bir listenin gerektirdiği O(n) taramaya karşılık ortalamada O(1) sürer. Java'nın TreeSet yapısı gibi ağaç tabanlı sürümler değerleri dengeli bir ağaçta sıralı tutar ve işlem başına O(log n) sürer. Setler ayrıca klasik matematiksel işlemleri de destekler: birleşim (ikisinden birindeki değerler), kesişim (ikisinde de olan değerler) ve fark (birincide olup ikincide olmayan değerler).
Kapıdaki bir davetli listesi iyi bir resimdir: ev sahibi yalnızca bir ismin listede olup olmadığına bakar ve bir ismi iki kez yazmak o misafirin iki kez girmesini sağlamaz. Setler yinelenenleri kaldırmak, BFS ve DFS gibi çizge aramalarında ziyaret edilen düğümleri izlemek, etiketleri ve izinleri hızla kontrol etmek ve hesap açıp hiç giriş yapmamış kullanıcıları bulmak gibi iki grubu karşılaştırmak için kullanılır. JavaScript'in Set ve Java'nın HashSet yapıları tipik yerleşik sürümlerdir; [...new Set(items)] ise bir dizideki yinelenenleri kaldırmak için kullanılan olağan JavaScript kalıbıdır.
Set sıklıkla liste ve map ile karşılaştırılır. Liste öğeleri sıralı tutar ve yinelenenlere izin verirken hash tabanlı bir Set yinelenenleri reddeder ve birçok dilde belirli bir sıra vaat etmez; ancak JavaScript'in Set yapısı ekleme sırasını korur. Sözlük ya da hash tablosu olarak da bilinen map her anahtar için bir değer saklar; Set ise yalnızca anahtarları saklar ve birçok dil onu içeride tam olarak böyle uygular. Üyelik ayrıca dilin değerleri nasıl karşılaştırdığına bağlıdır: JavaScript nesneleri kimliğine göre karşılaştırır, dolayısıyla [1, 2] içeren iki ayrı dizi iki farklı üye sayılır.
Önemli noktalar
- Set her farklı değeri yalnızca bir kez saklar, bu yüzden yinelenenler yok sayılır.
- Hash tabanlı setler ekleme, silme ve üyelik kontrolünü ortalamada O(1) sürede yapar.
- Java'nın
TreeSetyapısı gibi ağaç tabanlı setler değerleri işlem başına O(log n) maliyetle sıralı tutar. - Setler birleşim, kesişim ve fark işlemlerini destekler.
- Python'ın
set, JavaScript'inSetve Java'nınHashSetyapıları yaygın yerleşik uygulamalardır.
Örnek
tags = ["python", "web", "python", "api", "web"]
unique = set(tags) # duplicates disappear
print(len(unique)) # 3
print("api" in unique) # True, in O(1) on average instead of scanning a list
signed_up = {"ana", "ben", "cy", "dee"}
logged_in = {"ben", "dee", "eve"}
print(signed_up & logged_in) # intersection: ben and dee
print(signed_up | logged_in) # union: all five names
print(signed_up - logged_in) # difference: ana and cy never logged inSık sorulan sorular
Set ile liste arasındaki fark nedir?
Liste öğeleri sıralı tutar, yinelenenlere izin verir ve bir değeri içerip içermediğini kontrol etmek O(n) sürer. Hash tabanlı bir set ise her değeri bir kez saklar, genellikle sıra vaat etmez ve üyeliği ortalamada O(1)'de kontrol eder.
Setler sıralı mıdır?
Dile ve uygulamaya bağlıdır. Python'ın set gibi hash tabanlı setler sıra garantisi vermez, JavaScript'in Set yapısı ekleme sırasıyla dolaşılır ve Java'nın TreeSet gibi ağaç tabanlı setler değerleri sıralı tutar.
JavaScript'te bir dizideki yinelenenleri nasıl kaldırırım?
Diziyi bir Set'e verin ve tekrar diziye yayın: [...new Set(items)]. Bu, her değerin ilk geçtiği yeri korur ve O(n) sürede çalışır.
İlgili sayfalar
- Hash TablosuVeri Yapıları, s. 18Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- Bloom FilterVeri Yapıları, s. 5Bloom filter, çok az bellek kullanarak bir öğenin kümede kesinlikle olmadığını ya da büyük olasılıkla olduğunu söyleyen kompakt, olasılıksal bir veri yapısıdır.
- Dengeli AğaçVeri Yapıları, s. 9Dengeli ağaç, her değişiklikten sonra dengelenerek yüksekliğini log n civarında tutan ağaçtır; arama, ekleme ve silme en kötü durumda bile O(log n) kalır.
- HashingGüvenlik, s. 12Hashing, bir girdiyi tek yönlü bir fonksiyonla sabit uzunlukta bir değere dönüştürmektir; veri bütünlüğünü doğrulamaya ve parolaları güvenle saklamaya yarar.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin