import std.stdio;
import std.format;
import std.array;
class HızlıBağla
{
int[] bağ;
int kaçTane;
this(int N)
{
assert(N >= 0);
bağ = new int[N];
kaçTane = N;
for (int i = 0; i < N; ++i) {
bağ[i] = i;
}
}
int say()
{
return kaçTane;
}
int bul(int p)
{
while (p != bağ[p])
p = bağ[p];
return p;
}
bool bağlıMı(int p, int q)
{
return bul(p) == bul(q);
}
void bağla(int p, int q)
{
int i = bul(p);
int j = bul(q);
if (i == j) return;
bağ[i] = j;
kaçTane--;
}
}
void main()
{
HızlıBağla sayılar = new HızlıBağla(28);
sayılar.bağla(0, 1);
sayılar.bağla(1, 26);
write("bağ[] :");
for (int i = 0; i < 28; ++i) {
write(sayılar.bağ[i], " ");
}
writeln("\n0'ın kökü kaç : ", sayılar.bul(0));
}
İşte ağacın çalışma prensibini gösteren örnek bir program. HızlıBağla nesnesini oluşturduğumuz zaman içeriği şu oluyor.
'bağ[] :0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27'
Üstteki köke 26 alttaki köke 27 dedim. Şimdi sayıları bağlıyoruz. bağla(0, 1)
'bağ[] :'1' 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27'
Üstteki dizi'de 0. sırada bulunan elemanın 0'ın 1'i gösterdiğine dikkat.
1
/
0
Ağacımız oluşmaya başladı. Sonra en üstteki köke bağlıyorum. bağla(1, 26)
'
bağ[] :1 '26' 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27'
26
/
1
/
0
Bu şekilde ağacımız oluşmaya başlıyor. Dikkat edersen bul işlevi aslında ağacın kökünü veriyor. bul(0) bize 26 değerini verecek.
26 27
/ | \ /| \
1 2 3 21 22 23
/ \ / \
0 8 20 24
\ /
13 15
\
14
Ağacımız tamamlandıktan sonraki durum bu. Tabi eğer ağırlıklı hızlı bağla yöntemini kullansaydık ağacın derinliği bu kadar artmayacaktı. Ağacın derinliğinin artması fazladan işlem gücü demek.
Bu iki ağaç üzerinde hangi elemanları karşılaştırdığımızın önemi yok. Çünkü örneğin 0'ın kökü de 26, 8'in kökü de 26.
Algoritmaların performanslarını verdiğim github bağlantısında karşılaştırabilirsin. Veri miktarı az olduğunda bu çok farkedilmiyor. Ancak içerisinde 2 milyon kadar satır bulunan büyük.txt dosyasını kullandığında farkı görebilirsin.
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]
Permalink
Reply
