Run Time'da Array Size arttırmaca (Java)

[Bittus]

Encapsulation ile ilgili ufak bir ödevim var. ödev set union ile filan ilgili.

encapsulation amacıyla SetOfIntegers adlı classda array'e eleman ekleyen ya da set union yapan methodlar içinde array size'ı arttırmam gerekiyor.

eleman eklemeye çalışınca OutOfBoundsException alıyorum. şimdi, run timeda array size'ı arrtırmak için bir şey yapabilir miyim?

bu arada neden hali hazırdaki set operation ile ilgili libraryi kullanmıyorsun demeyin, ödevin amacı encapsulation olduğundan yasak kullanmak.

şimdiden teşekkürler.

kötü bir açıklama oldu biliyorum -.-'

[aquila]

neden array? neden arraylist değil? array kullanımını zorunlu mu şeetmiş.

[Bittus]

evet, the only viable implementation for you at this point seems to be plain arrays demiş...

[nameless]

boşver hacı sen arraylist yap eahaeh

[Penthesilea]

Array i neden zorunlu kildigini anlamadim hocanin. Arrayleri su sekilde kullanabilirsin ama:

Buffer.BlockCopy veya Array.Copy kullanip, yeni boyuttaki bir arraye gecirebilirsin.
Vectorlerin calisma prensibiyle, her seferinde size'i bir artirmazsin da 2 katina cikarirsin her doldugunda, boylece perfomans sorunu da yasamazsin.

int arrayi diye varsayiyorum:

	public int[] extendCapacity(int[] oldArray)

	{

	    int newSize = oldArray.length * 2;

	    int[] newArray = new int[newSize];

	    Buffer.BlockCopy(oldArray, 0, newArray, 0, newSize);

	    // fill array, from index, to index, value, sebebini anlaticam

	    Arrays.fill(newArray, oldArray.length, newSize-1, Integer.MIN_VALUE);

	    return newArray;

	}

	

problem, arrayin doldugunu nasil anlayacak olman. Mesela diyelim bu bir int arrayi, sen yarattiginda full 0 dolu olacak ici, nasil anlayacaksin bitip bitmedigini? Bunun icin de ya siradaki eklemen gereken indexi tutucaksin, yani iste siradaki elemani 5. yere sokucam gibi, sonra da bunun length e esit olup olmadigini cekiceksin, ya da boyle bi imkanin yoksa suna benzer bisi yapicaksin: arrayi yarattiktan sonra bos olan kisimlari Integer.MIN_VALUE ile doldurman.

bir de dolu mu bos mu fonksiyonu yazarsin, son elemani kontrol etsen yeter

	public bool isFull(int[] array)

	{

	    return (array[array.length -1] != Integer.MIN_VALUE)

	}

	

sonra da iste insert icin bi fonksiyon yaz:

	public void insert(int[] array, int value)

	{

	    if(isFull(array))

	    {

	        array = extendCapacity(array);

	    }

	    array[ArrayUtils.indexOf(array, Integer.MIN_VALUE)] = value;

	}

	

array utils kullanmamizin sebebi ilk min_value bulunan, yani ilk bos yeri bulmak, elimizde nereye sokacagimizin infosu olmadigindan.

dedigim gibi, isfull ve insert methodlarini yazarken herhangi bir sebeple elinde siradaki indexin bilgisinin olmadigini var saydim, bu olsa da olmasa da calisacak bir kod, arraylist calisma mantiginda birsey yani. eger elinde bu imkan olacaksa, isfull icin length'e esit mi degil mi ona bakarsin, insert icin de direk o indexe koyarsin.

[Borastus]

Hoca arrayList vector gibi veri yapılarının çalışma mantığını, neler içerdiğini göstermek için böyle bir ödev vermiştir mantıksız bir ödev değil bence.

Değildiği gibi array için bir size birde maximum_size degiskenleri tutarsın. Mesela ilk başta maximumSize 10, size 0 olur ve eleman ekledikçe size e arttırırsın size maksimumSize ile eşit olduğu zaman maximumSize i 2 kat büyük olan yeni bir array yaratıp ona transfer edersin.

[aquila]

off algoritm dersi geldi aklıma, kötü oldum.

[Bittus]

ya şimdi encapsulation yapmam gerektiği için arrayleri constructor ile oluşturuyorum. yazdığım constructorlardan biri null yani empty set oluşturuyor diğeri ise bir string(set name) bir de int(size) alarak array oluşturuyor.

penthesileanın verdiği kodlar sorunu çözer diye düşünüyorum da birkaç sorum olacak.

said:

public int[] extendCapacity(int[] oldArray)
{
int newSize = oldArray.length * 2;
int[] newArray = new int[newSize];
Buffer.BlockCopy(oldArray, 0, newArray, 0, newSize);
// fill array, from index, to index, value, sebebini anlaticam
Arrays.fill(newArray, oldArray.length, newSize-1, Integer.MIN_VALUE);
return newArray;
}

mesela bu kodu set union için kullanabilirim de, sadece yeni bir eleman eklemek için kullanmak istediğimde
int newSize = oldArray.length * 2; yerine:

int newSize = oldArray.length + 1;

desem olur değil mi? çünkü direk o şekilde kullanırsam arrayde bulunmaması gereken arraysize - element number kadar sıfır olacak gibi.

[aquila]

encapsulation dediğin için class yapsan olmuyo mu sadece.

[Bittus]

ya evet class yapıyorsun da hem constructor hem de methodları yazıp onları mainde invoke ediyorsun.

zaten mainde oluşturabilseydim arrayi hiç böyle bir sorunum olmayacaktı.

[Mirage]

Bittus, Penth onu performans açısından söylemiş.

Dediğin gibi yapabilirsin. Ama o zaman add metodunu her kullandığında yeni bir array oluşturup tüm elemanları kopyalamış oluyorsun. Kopyalama işlemi de, özellikle büyük array'ler için, pahalı bir işlem. Penth'in dediği şekilde yaparsan bu kopyalama işleminin çok daha seyrek gerçekleşmesi gerekiyor.

Bence ilk önce söylediğin gibi yap. Yazdığın kod hocanın istediğini yapsın yani. Daha sonra Penth'in dediği şekilde performansı arttırmanı tavsiye ederim. Hem senin için çok iyi bir egzersiz olur, hem de hocanın hoşuna gider. Tabi hoca sorarsa nasıl çalıştığını anlatabilmen gerekecek. ;)

[aquila]

doldurucaksın arrayi, sonra bakıcan az yer kalmış, hop daha büyük array yapıp oraya kopyalıcan, dersimi çalışmış olsam time complexityni de yazardım hangi durumda ne kadar arttırsan iyi olur filan, tabi bi de bunun arrayi küçültmesi var sildikçe.

[Mirage]

Eleman silmek için metod yazması gerekmiyormuş ama ilk yazdığına bakılırsa. Küçültme kısmıyla uğraşması gerekmiyor yani. :)

[Bittus]

hehe aslında yazmam gerekiyor. çünkü A U B kümesi içinde ortak eleman varsa yani A(kesişim)B elemanlarını silmem gerekiyor.

tabi bunu metodu basit düşünerek söyledim. yani direk iki arrayi birleştirip sonra ortak elemanları silmeyi düşünüyordum.

gerçi if(a[j] == b[j]) diyip remove etsem daha mı kolay olur?

ahah if'in içinde arrayin index numberına i yazınca italik oldu sadfasd

[aquila]

hmmpffss disjoint sets.

[Bittus]

Penth, Eclipse Buffer ve ArrayUtils için cannot be resolved dedi. import yapınca da BlockCopy ve indexOf için undefined dedi. ne yapmam gerekiyor?

[Mirage]

Penth ya pseodocode yazmıştır ya da .NET ile Java'yı karıştırmıştır. Standard Java API'sinde ArrayUtils diye bir şey yok. Buffer var ama o da alakasız bir şey. Arrays işine yarar. API'ye bak: http://download.oracle.com/docs/cd/E17409_01/javase/6/docs/api/java/util/Arrays.html

Ayrıca Penth bir yerde boş kısımları Integer.MIN_VALUE ile doldurmayı önermiş ama pek iyi bir çözüm değil. Integer.MIN_VALUE dediği -2^31 sayısı sonuçta. Birisi array'e bu sayıyı eklerse yanlış çalışacak.

Bence Penth'in ilk önerdiği gibi, en son elemanın indexini tutmak en mantıklısı.

Onun yerine illa boş elemanlara bir değer vermek gerekiyorsa null referans kullanabilirsin. Onun için de array'i primitive int yerine Integer nesnelerinden oluşturabilirsin. Metodlar parametre ve return değerleri için yine primitive int alır, böylece kullanıcı içerde Integer nesneleri kullandığını görmez. İlk null referansın indexini bularak son elemanın indexini bulabilirsin.

[Bittus]

Mirage said:

Arrays işine yarar. API'ye bak: http://download.oracle.com/docs/cd/E17409_01/javase/6/docs/api/java/util/Arrays.html

ben de buna bakıyordum şu anda. buradaki methodları nasıl kullanabilirim? body yazmak da gerekiyor mu bunlara?

[Mirage]

Hayır. Bunlar Java'nın standard kütüphanesinin sana sunduğu metodlar. En yukarda class'ın hangi pakette olduğu yazar.

Mesela Arrays için:

java.util
Class Arrays

yazıyor. Yani bu doküman java.util paketinde bulunan Arrays class'ını anlatıyor. Kullanmak için bu class'ı import etmen gerekecek. Kullanacağın yerde en yukarda şunu yazacaksın:

	import java.util.Arrays;

	

Arrays class'ı static metodlar içeren yardımcı bir class. Dolayısıyla Arrays türünden bir nesne üretmen gerekmiyor. Import ettikten sonra metodları şöyle kullanacaksın:

	Arrays.metodİsmi(argüman1, argüman2, ...);

	

[Bittus]

yardımlarınızla çoğu gitti azı kaldı. kodun son hali şöyle:

SetOfIntegers class

	import java.util.Arrays;

	

	public class SetOfIntegers {

	        

		public SetOfIntegers() { 

			aSet = new int[0];         //empty set

		}

		public SetOfIntegers(int element) { 

			aSet = new int[1]; 

			aSet[0] = element;         //singletone

		}

		public SetOfIntegers(int element,int size) {

	

			theSize = size;

			aSet = new int;   //a set with the first element

			aSet[0] = element;

		}

	

		private int theSize;

		private int aSet[];

	        

		public int getTheSize() {

			return theSize;

		}

		public void setTheSize(int setSize) {

			this.theSize = setSize;

		}

		public int[] getaSet() {

			return aSet;               //getters&setters

		}

		public void setaSet(int[] aSet) {

			this.aSet = aSet;

		}

		public void addElement(int index,int e) {

			aSet[index-1] = e;

		}

	

		public SetOfIntegers setCopy(SetOfIntegers otherSet) {

	

			otherSet.aSet = Arrays.copyOf(aSet.clone(), aSet.length);

			return otherSet;    

	

		}

		public SetOfIntegers setUnion(SetOfIntegers otherSet) {

			SetOfIntegers union = new SetOfIntegers();

			union.aSet = Arrays.copyOf(aSet.clone(),

	aSet.length+otherSet.theSize-1);

			for(int i=0; i<otherSet.theSize; i++){

				union.addElement(aSet.length+i, otherSet.aSet[j]

	(italik oluyor diye j ile degistirdim));

			}

			return union;

		}

		public String toString() {

			return   Arrays.toString(aSet) ;

		}

	

	}

	

	

	

<div class="spinfo">SetTest class(Main)</div>[code]
public class SetTest {


public static void main(String[] args ) {

SetOfIntegers A = new SetOfIntegers(1, 5);
A.addElement(2, 3);
A.addElement(3, 11);
A.addElement(4, 22);
A.addElement(5, 13);
SetOfIntegers B = new SetOfIntegers(5, 4);
B.addElement(2, 7);
B.addElement(3, 11);
B.addElement(4, 33);
SetOfIntegers C = new SetOfIntegers();
System.out.println(A);
System.out.println(B);
System.out.println(A.setUnion(B));
System.out.println(A.setCopy(C));

}


}

[/code]

Union ve Copy methodlarının dışında birkaç method daha yazmam gerekiyor. Subset-Superset karşılaştırması ve Equal mı değil mi onları yazmam gerekiyor.

yukarıdaki kodda geliştirebileceğim bir şey var mı peki? Garbage code filan varsa yani.

Ha bir de SetUnion methodunda aynı elemandan 2 tane varsa birini çıkartmam gerekiyor. orada bi iteration yazıp if ile check edip silsem iyi olur mu?

Mirage: Kodlara "code" tagı ekledim, okunmuyor öbür türlü. Bu tür kodları koyarken bu tagları eklersen herkes için daha rahat olur.

ah, code taginden bihaberdim. iyi oldu. birkaç comment ekledim bir de.

[fizban]

kimse şuna cevap vermemiş de; newsize = oldsize + 1 yapman tavsiye edilmez, çünkü daima bi memory taşıma durumu sözkonusu. düşün 10000 tane elemanın var, limit de 10000. 10 tane daha geldi. sen bu 10000'i alıp 10 kez baska yerlere tasican. yazık günah. onun yerine 20000 yap kurtul.

[Bittus]

@fizban

şu anda o kadar büyük bir size ile uğraşmadığım için çok sorun değil aslında. daha büyük olduğu zaman dikkate alırım bunu, teşekkür ederim.

[Mirage]

fizban, yapma etme abi iki kere söylendi zaten o dediğin. :)

Sanırım en büyük hata, encapsulation yapıyorum diyerek bu class'ı yapıp, encapsulate etmek istediğin kümeyi getter metodu ile dışarı vermen. O kullandığın aSet ve theSize adlı field'lar class içinde kullanacağın private alanlar. Onlar için getter ve setter yazmayacaksın yani. (belki theSize için getter yazılabilir, ama şart değil)

aSet için getter metodu yazmayacağın için setteki elemanlara tek tek ulaşamayacaksın. Kümeler için normali de budur zaten. Ama public boolean contains(int element) diye bir metod yazıp, verilen sayının küme içinde olup olmadığını döndüren bir metod yazabilirsin.

aSet ve theSize değişkenlerini constructor'lardan önce tanımlamanı tavsiye ederim. Demin iki dakka aradım durdum nerde bunlar diye. Hatta copy/paste hatası oldu çıkmadı falan sandım. :)

Değişken isimlerini daha anlaşılabilir koyabilirsin. aSet yerine set, theSize yerine de capacity kullanabilirsin mesela. Size ya da length isimleri genelde bir veri yapısının içinde kaç eleman olduğunu gösterir. Capacity ise veri yapısının boyutunu büyütmeye gerek kalmadan kaç eleman alabileceğidir. Burda senin theSize ile belirttiğin capacity yanı aslında.

Mesela new SetOfIntegers(0, 5) deyince setin içinde sadece tek eleman var (0 rakamı). yani size 1. Ama class içindeki array'inin uzunluğu 5, yani capacity 5.

Onun dışında addElement metodunda index kullanmaman lazım bence. Verilen eleman kümenin içinde var mı diye bakacaksın (yukarda bahsettiğim contains metodunu kullanabilirsin). Yoksa en sona ekleyeceksin, gerekiyorsa array boyunu arttıracaksın.

setCopy ve setUnion metodlarının isimlerinin başındaki set'leri sil.

union metodunda ilk önce bütün elemanları ekleyip, sonradan fazladan olanları silmek yerine şöyle yapabilirsin: Diyelim kümeler A ve B olsun. İlk önce A kümesinin kopyasını oluştur. Bu kopyaya C kümesi diyelim. Sonra B kümesindeki her elemanı addElement metoduyla C kümesine ekle. addElement metodu birden fazla elemanları zaten eklemeyeceği için silme işlemine falan gerek kalmamış olacak.

copy metodunda yeni bir küme oluşturup geri vermen gerekiyor. Sen argüman olarak verilen kümeyi değiştirmişsin. Orayı da düzeltmen lazım.

Bunları düzelt önce, daha geliştirilebilecek şeyler buluruz. :)

[Bittus]

Mirage said:

Sanırım en büyük hata, encapsulation yapıyorum diyerek bu class'ı yapıp, encapsulate etmek istediğin kümeyi getter metodu ile dışarı vermen. O kullandığın aSet ve theSize adlı field'lar class içinde kullanacağın private alanlar. Onlar için getter ve setter yazmayacaksın yani. (belki theSize için getter yazılabilir, ama şart değil)

evet haklısın. ben ilk başta constructorı tanımlarken elemanları da alıp yerleştirmek istemiştim ama her kümenin değişik sayıda elemanı olacağından hata vermemesi için sadece ilk elemanı alıp diğer elemanları addElement methodu ile almaya karar verdim. o yüzden aSet getter&setter yazmıştım(gerçi generate getters&setters diince onları da eklemişti hehe) o yüzden unutmuşum silmeyi. ama theSize için yazmam gerekiyor tabi.

Edit: yazmam gerekiyor demişim ama gerekmiyormuş evet =)

said:

aSet ve theSize değişkenlerini constructor'lardan önce tanımlamanı tavsiye ederim. Demin iki dakka aradım durdum nerde bunlar diye. Hatta copy/paste hatası oldu çıkmadı falan sandım.

bunu da üstteki sebepten alta yazmıştım. üste yazınca nedense size'ı 0 alıyordu. üstteki durum ortadan kalkınca da geri almayı unuttum. daha dikkatli olmam lazım bu konularda galiba =)

said:

Değişken isimlerini daha anlaşılabilir koyabilirsin. aSet yerine set, theSize yerine de capacity kullanabilirsin mesela. Size ya da length isimleri genelde bir veri yapısının içinde kaç eleman olduğunu gösterir. Capacity ise veri yapısının boyutunu büyütmeye gerek kalmadan kaç eleman alabileceğidir. Burda senin theSize ile belirttiğin capacity yanı aslında.

Variable name üretmek de pek sıkıntı ya. düzelttim onları da.
Eclipse de sağolsun, rename diyince hepsini değiştiriyor =)

said:

Onun dışında addElement metodunda index kullanmaman lazım bence. Verilen eleman kümenin içinde var mı diye bakacaksın (yukarda bahsettiğim contains metodunu kullanabilirsin). Yoksa en sona ekleyeceksin, gerekiyorsa array boyunu arttıracaksın.

setCopy ve setUnion metodlarının isimlerinin başındaki set'leri sil.

union metodunda ilk önce bütün elemanları ekleyip, sonradan fazladan olanları silmek yerine şöyle yapabilirsin: Diyelim kümeler A ve B olsun. İlk önce A kümesinin kopyasını oluştur. Bu kopyaya C kümesi diyelim. Sonra B kümesindeki her elemanı addElement metoduyla C kümesine ekle. addElement metodu birden fazla elemanları zaten eklemeyeceği için silme işlemine falan gerek kalmamış olacak.

bu gayet mantıklı ama beni biraz uğraştıracak gibi hehe. halledebilirsem çok daha iyi olur tabi.

said:

copy metodunda yeni bir küme oluşturup geri vermen gerekiyor. Sen argüman olarak verilen kümeyi değiştirmişsin. Orayı da düzeltmen lazım.

burada bir sorun yok ya. amaç zaten o. yani A=B yapmak olay.
SetOfIntegers C = new SetOfIntegers();
System.out.println(A.copy(C));
demişim zaten. aldığı küme boş küme yani.

[fizban]

Mirage said:

fizban, yapma etme abi iki kere söylendi zaten o dediğin.

senin ve aquila'nın mesajlarını şu an sadece adminlere ve gold üyelere açık oaln ignore özelliğiyle yoksaymışım, sori :P