JAVA reference

[ivan90BG]

Imam jedno pitanje iz Jave, nema veze sa prethodnim.

Pričao sam sa jednim profesorom na faksu i on kaže sledeće:

Kada se neki objekat prosledi kao argument nekoj metodi i ako se u toj metodi ta primljena referenca izjednači sa nekom drugom (sa nekim drugim objektom) ta promena će imati efekta na objekat (referencu) u metodi pozivaocu.

public void metoda(Object o)
{
	o = new Object();
}

a u nekom drugom bloku koda

Object m = NULL;
metoda(m);

Dakle tvrdnja je da ovim m više neće biti NULL, to jest pozivom metode "o i m se uparuju" i sve što se radi sa o se prenosi na m.

Da li je ovo tačno. Iskreno ne verujem, al ne škodi pitati.

 

[mister Mrva]

U pravu je posto se radi o referentnom tipu.

 

[Bahati [SiD]]

hmmmm... preformulisano: da li metod ima referencu ili interno referencu na referencu?

najlakse je to proveriti, ali zabavno je i pogadjati. ja pogadjam da je ovo prvo jer bi u suprotnom za svaki poziv metoda sa argumentima moralo da se odvoji mesto za reference argumenata u memoriji, da se tamo upisu reference, da se onda proslede reference na ta nova mesta metodu... previse posla da se radi po defult-u...

u prevodu mislim da je profa u pravu, s tim sto je zgodno imati u vidu za ubuduce da to nije znak jednakosti ("izjednacavanje") nego znak dodele.

 

[ivan90BG]

Pišem ovaj post iz amfiteatra. Evo vam jedan zanimljiv kod. Ubacivanje u BST stablo. Metoda je statička prima koren stabla.

public static void ubaci(CvorBStabla k, int podatak)
	{
		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}
		
		if (k.podatak < podatak)
		{
			if (k.desno != null)
				ubaci(k.desno, podatak);
			else
				k.desno = new CvorBStabla(podatak, null, null);
		}
		else
		{
			if (k.levo != null)
				ubaci(k.levo, podatak);
			else
				k.levo = new CvorBStabla(podatak, null, null);
		}
	}

Samo što se nisam posvađao sa asistentom oko ovoga. Prema prethodno utvrđenom pravili iz Jave, provere (k.desno != null) i (k.levo != null) su redundante. A ako pravilo ne važi onda je prvi if budalaština. Jel to OK.

Asistent mi je čak i objašnjavao da ako metoda primi koren onda prvi if valja, ali u ostalim rekurzivnim pozivima moramo da proveravamo pre poziva, jer u suprotnom gubimo kreirani objekat. A ako je metoda pozvana sa korenom kao argumentom objekat se prenosi u referencu metode koja je pozvala.

 

[SINTER]

Dobar je kod. Prvi if se koristi ako koren jos ne postoji (stablo je prazno).

Sto se tice prvog pitanja, nema tu nikakvog uparivanja. U javi se svi argumenti stavljaju na stek i prenose vrednosti (dakle, i reference se prenose preko vrednosti). Posle poziva metode ce m biti null, sto mozes da proveris sam veoma lako. Ista prica ti je kao da kazes:

Object m = new Integer(12);
Object k = m;
Object k = new Double(13.23);

Posle ovoga m ce biti i dalje Integer, a k Double.

 

[zeleni_zub]

public void metoda(Object o)
{
	o = new Object();
}

a u nekom drugom bloku koda

Object m = NULL;
metoda(m);

Dakle tvrdnja je da ovim m više neće biti NULL, to jest pozivom metode "o i m se uparuju" i sve što se radi sa o se prenosi na m.

Da li je ovo tačno. Iskreno ne verujem, al ne škodi pitati.

Nije tačno.

Object m = NULL;

Kreira se referenca m na Object i dodeljuje joj se vrednost null.

metoda(m);

Poziva se funkcija metoda(), referenca o na Object dobija vrednost reference m. Sada obe reference pokazuju na isti objekat.

o = new Object();

Kreira se novi objekat tipa Object i referenca o sada pokazuje na novi objekat. Referenca m i dalje pokazuje na stari objekat.

Po izlasku iz funkcije, vrednost reference o se gubi, garbage collector briše taj objekat, a referenca m i dalje ima vrednost null.

 

[ivan90BG]

Ajd još da obrazložim.

Metoda "ubaci" je rekurzivna. Prima neki čvor drveta binarnog pretraživanja (mislim da u ovom slučaju nije bitno da li je samo BST ili je i balansirno).

Logično metoda uvek treba da proveri da li je primljeni objekat/referenca (više ni sam ne znam šta je) jednak(a) NULL. Meni bi bilo logično da tu bacim Exception jer znam da je to bio prvi poziv te metode, zato što se dalje u metodi proverava da li se sledećem rekurzivnom pozivu prosleđuje NULL. Dakle, ako dobije NULL onda je sigurno da je prosleđen NULL koren, i ja bi zato tu stavio Exception (naučen logici iz C/C++/Obj-C, koja kaže da ako ja promenim neki argument metode (vrednost nekog primitivnog tipa ili vrednost samog pointera), to se ne prenosi na pozivaoca).

Ali on tom NULL objektu/referenci dodeljuje novi objekat koji ovde kreiran sa new. Ovo ispada sasvim OK pošto sada znam da se objekti u Javi ponašaju kao statički objekti u C++-u (ali nisu) a da se u metode prenosi referenca (kao C++ referenca) i da ja u stvari nemam pointer na objekat nego vrednost (kao da je lokalan statički).

E sad tu dolazi NULL. U C/C++/Obj-C NULL je samo makro za nulu, to jest vrednost pointera je 0. Ali ako ja u Javi mogu objektu da dodelim NULL, to se kosi sa prethodno utvrđenim Javinim pravilom (ako prihvatimo da NULL znači referencu koja ne pokazuje ni našta, iliti na nulu). U C++ se ne može statičkom objektu dodeliti 0 jer nije tog tipa.


Ovo dovodi do zaključka da u Javi NULL nije običan makro koji znači null pointer. Nego da kada se NULL dodeli objektu/referenci zapravo Java kreira objekat u memoriji tog tipa i nekako ga označi da još nije inicijalizovan (konstruisan, kreiran...), a ako ga ja dobijem kao argument u metodi i konstruišem ga, pozivaoc će imati konstruisan objekat bez potrebe da mu moja metoda nešto vraća.

U tom slučaju je u rekurzivnoj metodi "ubaci" redundantno proveravati da li su levo ili desno dete trenutnog čvora jednaki NULL i kreirati objekat ako jeste, zato što će se ta provera uraditi u sledećem rekurzivnom pozivu i k.levo ili k.desno kao posledica tog poziva neće više NULL već će postati novokreirani objekat (opet po Javinom pravilu da se objekti ponašaju statički (da se i kreiraju u memoriji po samoj deklaraciji), da su pass by reference i da je NULL označavanje samog objekta da je neinicijalizovan).



Uh. Jesam li ovo sve izveo dobrom logikom.

Aj da još pojasnim šta mi objašnjavao asistent. Reko je da mi moramo da proveravamo da li su k.desno ili k.levo == NULL jer ako mi u sledećem rekurzivnom pozivu kreiramo objekat i dodelimo ga primljenoj referenci taj objekat se gubi po završetku metode i zato proveravamo i objekat kreiramo tu. (ko da mi je objasnio C/C++ pointere)

A onda kaže da prvi IF u metodi valja jer mi tu ako primimo NULL to znači da smo primli NULL koren i samo treba da napravimo novi objekat i da izvršimo dodelu, lupimo return i to će NULL objekat koji je pozivaoc prosledio postati taj novi objekat.

To je OK, ali su onda one donje provere redundantne. Znači da asistent "meri po dvostrukim aršinima". (jel mi i ovo dobra logika )

 

[zeleni_zub]

Ovo dovodi do zaključka da u Javi NULL nije običan makro koji znači null pointer. Nego da kada se NULL dodeli objektu/referenci zapravo Java kreira objekat u memoriji tog tipa i nekako ga označi da još nije inicijalizovan (konstruisan, kreiran...).

Ne kreira se objekat u memoriji, nego jednostavno imaš referencu koja ne pokazuje na objekat, baš kao i što null pointer ne pokazuje na neku memorijsku lokaciju.

Što se tiče koda...

		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}

Ako kao argument dobiješ null kao parrent čvor to znači da si stigao do kraja te grane drveta i možeš da kreiraš čvor.


Pošto već postoji ta provera, ovaj else je višak. Uštedeće dodatno pozivanje funckcije, ali će sve ispravno raditi i bez njega.

		if (k.podatak < podatak)
		{
			if (k.desno != null)
				ubaci(k.desno, podatak);
			[B]else
				k.desno = new CvorBStabla(podatak, null, null);[/B]
		}

znači kod bi mogao ovako da izgleda:

public static void ubaci(CvorBStabla k, int podatak)
	{
		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}
		
		if (k.podatak < podatak)
				ubaci(k.desno, podatak);
		else
				ubaci(k.levo, podatak);
			
	}

 

[ivan90BG]

Da, da, znači one dve donje provere su nepotrebne.


I onda, jel to znači da su objekti u Javi kao pointeri koji se u metode prenose po referenci (kao C++ reference), (znači ne prenosi se objekat po referenci nego pointer po referenci) i da u pozvanoj metodi ja pristupam vrednosti tog pointera (adresi na koju pokazuje), i da se stoga dodele koje radim nad tim pointerom prenose na pointer koji ima pozivaoc


Ali od drugih članova dobijam oprečne informacije.

 

[Bahati [SiD]]

preformulisano: da li metod ima referencu ili interno referencu na referencu?

zasto sam sve lepo razlozio i dosao do pogresnog zakljucka nemam pojma. klasican brain fart. mislim da sam istripovao da je u GC jezicima referenca nesto posebno (tj. ima povratnu vezu) i da runtime nekako zna sta da radi...

u pravu je sinter, a probao sam sad i u C# i isto se ponasa. ako se napravi metod sa ref keywordom pravi se "referenca na referencu" koju sam pominjao i lepo zakljucio da je glupo raditi to po default-u... :d onda se menja originalna referenca tj. referenca van metoda vise nije null nego gadja novi objekat kreiran u metodu.

 

[this_pointer]

(znači ne prenosi se objekat po referenci nego pointer po referenci)

ne prenosi se referenca po referenci nego po vrednosti, zato i nema bocni efekat.

 

[ivan90BG]

Evo smilovao sam se i probao.

I otkrio sam da objekat(referenca) u Javi radi kao običan pointer. Deklarisao sam objekat da bude null, prosledio ga u metodu koja kreira novi i pogodite šta se desilo, i posle poziva je objekat(referenca) ostao null.

Znači da profesor nije bio u pravu, a ni asistent jer dodela u prvom IF-u drugog primera koji sam postavio (pisanog na tabli ) ne radi ništa osim što kreira objekat i dodeljuje ga lokalnoj referenci, to jest u pozivaocu se ništa ne menja.

SID: E to u stvari tvrdi profesor, a i asistent za prvi IF u svom zadatku. A li kao što napisah, probao sam upravo i to je nije tačno.

U sunce ti dokle je došlo naše obrazovanje kad predavači na fakultetima ne znaju da li je isprano ono što predaju. Ne znam šta je sa drugim fakultetima ali FON je postao prava Java škola http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html


EDIT: ček malo, pa sinter je kontradiktovao samog sebe. Reče da je sa prvim IF-om sve u redu, a onda da nema uparivanja i da se prenosi vrednost reference. Ako je ovo drugo tačno onda prvi IF ne radi ništa. Ne može istovremeno da bude dobar i da ne radi ništa.

 

[SINTER]

public static void ubaci(CvorBStabla k, int podatak)
	{
		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}
		
		if (k.podatak < podatak)
				ubaci(k.desno, podatak);
		else
				ubaci(k.levo, podatak);
			
	}

I sta ti ovo radi? Poenta cele setnje kroz stablo je da si taj novi cvor uveze u ostatak stabla.

Ova metoda je verovatno zamisljena da se ovako koristi:

CvorBStabla root = null;
ubaci(root, 12);
ubaci(root, 7);
ubaci(root, x);
ubaci(root, ...);

Sa tvojim kodom bi stablo vecno imalo samo jedan cvor. Cak i da postoji celo stablo, samo bi se prosetalo kroz njega i onda referencirao cvor od kog se krenulo.

Kod koji ti je asistent dao je pravilno ubacivanje u binary tree (btw, ime klase CvorBStabla je pogresno posto su B-trees nesto sasvim drugo). Pametna optimizacija sa zaista velika stabla bi bila da postoji samo public metoda ubaci koja proverava da li je pocetni cvor null i koja potom poziva rekurzivnu privatnu metodu koja radi ostatak posla jer je proveru k == null potrebno samo jednom izvrsiti.

@ivan
Ne pravi java nista u memoriji (na heap-u) dok se ne pozove konstruktor. Mozes null u javi da posmatras na isti nacin kao null u C-u/C++/cemu vec hoces. To je neka rezervisana vrednost koja govori da ta adresa nije validna.

Nisam shvatio sta te tacno zbunjuje. Napisi isti ovaj kod u C++ ako njega znas bolje i videces da nema nekih bitnih razlika. Baratas sa dosta termina koji, verujem, zbunjuju i tebe i nas.


@offtopic
Mislim da ovaj topic hijacking nije dobra praksa i da bi moderatori mogli da razdvoje ove dve teme. Ionako je ovo jedan od retkih subforuma koji je jos uvek normalan (verovtno zato sto ga posecuje 20 ljudi ), pa ne bi bilo lose da ostane 'uredan'.

 

[ivan90BG]

Sad mi tek nije jasno šta svako od vas misli.

if (k == null)
{
    k = new CvorBStabla(podatak, null, null);
    return;
}

i ako ja pozovem ovu metodu ovako:

CvorBStabla root = null;
ubaci(root, 1024);

hoćete li da kažete da posle poziva "ubaci" root više neće biti NULL. Probao sam to i ne radi.

 

[zeleni_zub]

Ustvari ni jedan ni drugi algoritam ne rade.

Treća sreća:

public static void ubaci(ref CvorBStabla k, int podatak)
	{
		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}
		
		if (k.podatak < podatak)
				ubaci(k.desno, podatak);
		else
				ubaci(k.levo, podatak);
			
	}

I sta ti ovo radi? Poenta cele setnje kroz stablo je da si taj novi cvor uveze u ostatak stabla.

Zaboravio sam samo da dopišem ref:
public static void ubaci(ref CvorBStabla k, int podatak)


Ovako će funkcija rekurzijom stići do kraja grane drveta i umesto null reference na to mesto ubaciti novi čvor.

 

[ivan90BG]

Pa jel u Javi postoji keyword ref. Eclipse se opasno buni kad to otkucam.

 

[Bahati [SiD]]

Mislim da ovaj topic hijacking nije dobra praksa i da bi moderatori mogli da razdvoje ove dve teme. Ionako je ovo jedan od retkih subforuma koji je jos uvek normalan (verovtno zato sto ga posecuje 20 ljudi ), pa ne bi bilo lose da ostane 'uredan'.

pade mi odmah napamet, al' tad me mrzelo i nisam mislio da ce ovoliko da se rasplamsa. :d

 

[Bahati [SiD]]

SID: E to u stvari tvrdi profesor, a i asistent za prvi IF u svom zadatku. A li kao što napisah, probao sam upravo i to je nije tačno.

ma skapirao sam i sam u medjuvremenu...

 

[zeleni_zub]

Pa jel u Javi postoji keyword ref. Eclipse se opasno buni kad to otkucam.

Ne postoji. Ne programiram u Javi tako da sam to smetnuo sa uma. Znači da bi ovo radilo u Javi mora malo da se promeni koncept.

 

[ivan90BG]

Istraživao sam malo, i postoji više mogućnosti.

1. Metod mora umesto void da vraća nazad kreiran koren
2. Ja bih ovo razdvojio na dve metode, jednu vrhovnu koja radi proveru i vraća cvor liste (za sličaj da primi null), i jednu void rekurzivnu koja radi posao.
3. Staviti referencu u niz kapaciteta 1 i prosledeiti to
4. Definisati novu klasu Ref<T> koja drži referncu na objekat i proslediti to (u metodu se prosleđuje vrednost reference na Ref<T>, a Ref<T> ispada nešto kao smart pointer (C++))

Iskreno čini mi se da ovakvi problemi u stvari i ne mogu da iskrsnu u praksi.

 

[SINTER]

Ma mi besmisleno sve komplikujemo
Obicno bi se ovo radilo tako sto bi se pravila klasa BinaryTree sa privatnim poljem root. Java malo previse forsira OOP, pa je ideja da metoda moze da dira samo ono sto pripada klasi u kojoj se nalazi. Ako se ostane pri odluci da je 'ubaci' staticka metoda onda je vracanje korena OK taktika.

Ustvari ni jedan ni drugi algoritam ne rade.

Treća sreća:

public static void ubaci(ref CvorBStabla k, int podatak)
	{
		if (k == null)
		{
			k = new CvorBStabla(podatak, null, null);
			return;
		}
		
		if (k.podatak < podatak)
				ubaci(k.desno, podatak);
		else
				ubaci(k.levo, podatak);
			
	}

Zaboravio sam samo da dopišem ref:
public static void ubaci(ref CvorBStabla k, int podatak)


Ovako će funkcija rekurzijom stići do kraja grane drveta i umesto null reference na to mesto ubaciti novi čvor.

Glavna stvar kod ubacivanje je trenutak:
k.levo/desno = new Cvor();
Gde cvor postaje sin odgovarajuceg roditelja i ulancava se u ostatak stabla.
Ti se samo spustis kroz stablo i napravis novi cvor bez ulancavnja sa ostatkom stabla.

 

[zeleni_zub]

Evo ga ispravan kod (da eliminišem zabunu koju sam napravio):

class TreeNode
{
    public double data; 
    
    public TreeNode leftBranch, rightBranch;
    
    TreeNode(double p_data)
    {
        leftBranch = null;
        rightBranch = null;
        data = p_data;
        
        return;
    }
}

class BinaryTree
{
    TreeNode rootNode;
    
    BalancedTree()
    {
        rootNode = null;
    }
    
    public void AddNode(double data)
    {
        if(rootNode == null)
            rootNode = new TreeNode(data);
        else
            RecAddNode(rootNode, data);
            
        return;
    }
    
    protected void RecAddNode(TreeNode parrentNode, double data)
    {
        if(parrentNode.data >= data)
        {
            if(parrentNode.leftBranch == null)
                parrentNode.leftBranch = new TreeNode(data);
            else
                RecAddNode(parrentNode.leftBranch, data);
        }
        else
        {
            if(parrentNode.rightBranch == null)
                parrentNode.rightBranch = new TreeNode(data);
            else
                RecAddNode(parrentNode.rightBranch, data);
        }
    
    }
}

public class JavaTest 
{

    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        
        tree.AddNode(100.0);
        tree.AddNode(50.0);
        tree.AddNode(20.0);
        tree.AddNode(150.0);
        tree.AddNode(250.0);
                
    }
}

 

[SINTER]

Yep, to je to
Jedina sitnica je sto ovo nije balanced tree, ali kao obican binary tree radi ko bombona

 

[zeleni_zub]

Ispravljeno. Mada bio bi balanced ako imamo dobru distribuciju brojeva.

 

[SINTER]

Haha
good point

 

[xphreak]

Nije balanced tree. Balanced tree je npr. Red-Black tree, AA, AVL... svaki od ovih ima rotacije...