Scala's TreeSet - Java'nın TreeSet'i - anket?

Java'nın TreeSet numaralı sürümünde en yüksek girişi log(n) zamanında kaldırmak istiyorsam, treeSet.pollFirst() kullanıyorum - Scala'nın mutable.TreeSet sınıfının karşılığı nedir?Scala's TreeSet - Java'nın TreeSet'i - anket?

Her neyse, gerçekten istediğim, logaritmik zamanda removeMax, add ve updatePriority sağlayan bir yığın benzeri öncelikli sıra yapısı yapısıdır. Scala koleksiyon kütüphanesine baktım ve kafam karıştı - mutable.PriorityQueue, logaritmik zamanda deque (yani removeMax) izin verirken - günlükte önceliği güncellemenin bir yolunu sağlamaz (hacimce öğeyi taramak ve kaldırmak zorundayım. doğrusal zaman). Benzer şekilde, mutable.TreeSet, logaritmik zamanda önceliği güncellememe izin verir (hacizce silip yeniden ekleyerek) ancak removeMax (yani pollFirst) işlemine sahip değildir. Hangi koleksiyonları kullanmalıyım? Lütfen beni dış bağımlılıklara yönlendirmeyin.

kaynak

2013-04-04 pathikrit

"updatePriority" nin Java'nın TreeSet ile çalışacağını nasıl düşünüyorsunuz? – sharakan

Kolay (TreeSet'i anonim bir sınıfla geçersiz kılarak bir dış karşılaştırıcı tanımladığınız varsayılarak). Sadece düğümü silip ekleyin. Örneğime bak. 19. satır ve 33-36 numaralı hatlara bakın: https://github.com/pathikrit/scalgos/blob/master/temp/SandBox/AStar.java – pathikrit

Doğru, mantıklı. Güncellemeden önce düğümü kaldırmalısınız. – sharakan

olan immutable.TreeSet adresindeki head ve last yöntemlerini kullanabilirsiniz. Aynı yöntemler mutable.TreeSet'da bulunur, ancak daha iyi verimlilik ve amortize edilmiş zaman sağlamak için geçersiz kılınmamıştır (Scala 2.10'da). head yöntemi, logaritmik olacak, ancak bunu yaparken bir yineleyici başlatabilir. last yöntemi, aslında doğrusal karmaşıklığa sahip olarak, onu geçecek. İyi haber şu ki, özel bir Ordering ile en küçük veya en büyük olanı kontrol edebilir ve Ordering.reverse numaralı telefonu arayarak mevcut bir Ordering'dan kolayca edinebilirsiniz.

Bu öğeyi kaldırmanız gerekiyorsa, -='u kullanın. Ağaç kümesinde pollFirst yöntemini geri yüklemek için kendi örtülü değer sınıfınızı oluşturabilirsiniz.

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
}

kaynak

2013-04-04 12:26:02 axel22

Baş ve son "peekFirst" ve "peekLast" öğelerine eşdeğerdir - istediğim ** ** ankettir ** – pathikrit

Bir TreeSet öğesindeki herhangi bir öğeyi tanımladıktan sonra bunu kaldırmak için önemsizdir - - ''. – axel22

Ah, tamam, ama bu basit 'pollLast'den çok çirkin. – pathikrit

Sorumun cevabı değil, sadece bir öneri JVM :) için derlemek eğer Java'nın TreeSet sizin için çalışıyorsa, onu kullanın böylece, iyi (scala Java kütüphaneleri erişebilirsiniz unutmayın :) :)

Ayrıca gereksinimlerinizi netleştirebilirsiniz; updatePriority yönteminizin parametreleri ne olurdu? kimin önceliğini güncellemeye çalışıyorsun?

kaynak

2013-04-04 12:55:16 okaram

Scala's TreeSet - Java'nın TreeSet'i - anket?

cevap

İlgili konular