Üst düğüm algoritması - Top-nodes algorithm

üst düğüm algoritması bir algoritma kaynak ayırma takvimini yönetmek için. Algoritma ilk olarak 2003 yılında yayınlandı,[1] ve 2009'da iyileştirildi.[2] Bir kaynak birçok kullanıcı arasında paylaşıldığında kullanılır (örneğin Bant genişliği içinde telekomünikasyon bağlantı veya disk kapasitesi büyük bir veri merkezi ).

Algoritma, kullanıcıların şunları yapmasına olanak tanır:

  • bir miktar olup olmadığını kontrol edin kaynak belirli bir süre boyunca mevcuttur,
  • belirli bir süre için bir miktar kaynak ayırmak,
  • önceki bir rezervasyonu sil
  • takvimi ileri hareket ettirin (takvim belirli bir süreyi kapsar ve zaman geçtikçe ilerletilmesi gerekir).

Prensip

Takvim, bir ikili ağaç yapraklar temel zaman dönemlerini temsil eder. Diğer düğümler, tüm torunları tarafından kapsanan süreyi temsil eder.

Yedi saatlik takvim örneği (bir saatlik temel dönemler)
Yedi saatlik takvim örneği (bir saatlik temel dönemler)

Bir rezervasyonun kapsadığı süre, bir dizi "üst düğüm" ile temsil edilir. Bu küme, rezervasyon süresini tam olarak kapsayan minimum düğüm kümesidir.

Bir düğüm ikili ağaç belirli bir rezervasyon için "üst düğüm" ise

  • tüm torunları rezervasyon süresinin içindedir ve
  • kök düğümdür veya ebeveyn düğümün en az bir soyundan gelen, rezervasyon süresinin dışındadır.
1: 00'dan 5: 59'a kadar rezervasyon için en üst düğümler
1: 00'dan 5: 59'a kadar rezervasyon için en üst düğümler

Her düğümde aşağıdaki değer saklanır:

q (düğüm) = maks (q (sol çocuk), q (sağ çocuk)) + bu düğüme "üst düğüm" olarak sahip tüm rezervasyonlar için toplam ayrılmış kaynak miktarı

(için kod optimizasyonu, bu meblağın iki kısmı genellikle ayrı olarak depolanır.)

Verim

Bu algoritmanın avantajı, yeni bir kaynak ayırma kaydetme süresinin yalnızca takvim boyutuna bağlı olmasıdır (toplam rezervasyon sayısına bağlı değildir).

İzin Vermek n takvimdeki ilk dönemlerin sayısı.

Belirli bir rezervasyon için maksimum "üst düğüm" sayısı 2.log n'dir.

  • belirli bir süre boyunca bir miktar kaynak olup olmadığını kontrol etmek için: Ö(günlük n)
  • belirli bir süre için bir miktar kaynak ayırmak için: Ö(günlük n)
  • önceki bir rezervasyonu silmek için: Ö(günlük n)
  • takvimi ileriye taşımak için: Ö(günlük n + M.log n)

nerede M eklenen takvim dönemlerinde aktif olan rezervasyonların sayısıdır.

(M = 0 takvimin bitiminden sonra rezervasyonlara izin verilmiyorsa.)

Referanslar

  1. ^ İlgili ABD patenti (algoritma 2008'den beri kamu malıdır)
  2. ^ İyileştirilmiş üst düğüm algoritması

Dış bağlantılar