Teiler ermittlen - Array erweitern?

[S.T.O.R.M.]

Hallo zusammen,

ich versuche eine Java-Programm zu schreiben, das folgendes macht:
Es wird eine Zahl z initialisiert z.B. int z=24. Jetzt soll das Programm mir alle Teiler zwischen 1 und z ausgeben, den größten Teiler und die Anzahl aller Teiler.
Für die Teiler würde ich gerne ein Array deklarieren, aber mir fehlt ja am Anfang die Größe um es zu initialisieren.

Hier ist mein Ansatz:

public class Teiler
{
    public static void main(String[] args)  {
        int zahl=24;
        int j=0;
        int[] teiler;
        int anzahlTeiler=0;
        for (int i=2; i<zahl; i++)  {
            if(zahl%i==0)   {
                anzahlTeiler++;
                i=teiler[j];
                j++;
            }
        }
        System.out.println(teiler);
    }
}

Der Compiler meldet natürlich einen Fehler, da teiler nicht initialisiert wurde. Hat jemand eine Idee wie ich das mit dem Array hinbekomme ohne die Schleife doppelt durchlaufen zu müssen? :bahnhof:

Gruß,
Storm

 

[0x7F800000]

Hat jemand eine Idee wie ich das mit dem Array hinbekomme ohne die Schleife doppelt durchlaufen zu müssen?

Gar nicht. Nimm einfach LinkedList (Java Platform SE 6), und versuche auf Arrays zugunsten der Collections lieber ganz zu verzichten: in Java sind die Dinger irgendwie total alienmäßig :autsch:

 

[javimka]

Was ist an einem Array denn "alienmäßig"? Ist jedenfalls immer noch die allerschnellste Möglichkeit, mehrere Elemente eines Typs zu verwalten.

Aber im Beispiel hier, würde sich ArrayList/LinkedList sicherlich anbieten.

 

[S.T.O.R.M.]

Danke für die schnelle Antwort. So scheint es ja dann zu funktionieren:

import java.util.*;
public class Zwei
{
    public static void main(String[] args)  {
        int zahl=24;
        int j=0;
        LinkedList teiler=new LinkedList();
        int anzahlTeiler=0;
        for (int i=2; i<zahl; i++)  {
            if(zahl%i==0)   {
                anzahlTeiler++;
                teiler.add(i);
                j++;
            }
        }
        System.out.println(teiler);
    }
}

Wenn man solche Listen hat, wozu benutzt man dann eigentlich Arrays? Diese Listen sind doch viel flexibler!?

Edit: noch eine Frage: Gibt es eine Möglichkeit auf spezielle Elemente dieser Liste zuzugreifen wie bei einem Array mit z.B. array[3]? Oder müsste ich anstatt dessen mit Vektoren arbeiten?

 

[Murray]

Wenn man solche Listen hat, wozu benutzt man dann eigentlich Arrays? Diese Listen sind doch viel flexibler!?

Genauso könnte man fragen: warum verwendet man die primitiven Typen int,double etc, wo man doch auch mit den Wrapper-Typen Integer, Double etc. arbeiten könnte. In manchen Situationen möchte/muss man sich den Overhead, den die Listen gegenüber den Arrays haben, eben sparen.

Edit: noch eine Frage: Gibt es eine Möglichkeit auf spezielle Elemente dieser Liste zuzugreifen wie bei einem Array mit z.B. array[3]? Oder müsste ich anstatt dessen mit Vektoren arbeiten?

(Linked)List.get( int index);
Mit Vectoren sollte man nicht mehr arbeiten; das ist ein Relikt aus den Anfangszeiten von Java und nur noch aus Kompatibilitätsgründen vorhanden.

 

[Landei]

Besser:

List<Integer> teiler=new ArrayList<Integer>();

Dann funktioniert auch int x = List.get(index); ohne Casts.
LinkedList ist dann gut, wenn viel am Anfang oder der Mitte eingefügt oder gelöscht wird, und wenn man keinen Zugriff über index braucht (die ganze Liste durchgehen ist OK). ArrayList ist gut, wenn nur am Ende eingefügt oder gelöscht wird, wenn man die Endgröße schon schätzen kann und wenn man Zugriff über Index benötigt.

 

[bygones]

Was ist an einem Array denn "alienmäßig"?

sie sind keine eigene Klassen und somit muss ziemlich viel aufwand betrieben werden sie dementsprechend hinzubiegen

Ist jedenfalls immer noch die allerschnellste Möglichkeit, mehrere Elemente eines Typs zu verwalten.

sorry aber das ist einfach nur Unsinn !

 

[faetzminator]

Ein Array bietet sich grundsätzlich kann, wenn man eine Datenmenge hat, welche bereits im Vorherein bekannt ist und sich nicht ändert ("ich habe 5 Elemente, und das hab ich immer, solang ich das Array brauch").
Ansonsten nimmt man meistens eine List, z.B. eine ArrayList arbeitet intern sowieso mit einem Array des jeweiligen Datentyps.

 

[Landei]

sie sind keine eigene Klassen und somit muss ziemlich viel aufwand betrieben werden sie dementsprechend hinzubiegen

Da kann ich nur zustimmen. Java ist eben nur eingeschränkt objektorientiert, sonst dürfte es primitive Typen, Arrays und - meiner Meinung nach - null nicht geben (dafür fehlt ein ordentlicher void-Typ). Immer wenn es um diese Sachen geht, kommen dann auch prompt unschöne Ecken und Kanten zum Vorschein. Arrays "können" z.B. nicht richtig mit Generics, und beherbergen Java's größtes Typ-Loch:

String[] strings = { "eins", "zwei" };
Object[] object = strings;
objects[0] = Integer.valueOf(1); //Bumm!!!

 

[0x7F800000]

@Landei: bitte, jetzt nicht schon wieder von vorne das ganze ;(
@javimka: siehe den Dinosaurier Thread, dort wurde das alles schon zehn mal durchgekaut...

Könnten wir das jetzt bitte lassen?

 

[Landei]

Ich hab' mich doch schon kurz gefasst

 

[javimka]

0x7F800000 zuliebe, schreibe ich nichts mehr zur Array/List Verwendung, aber den mit dem "sorry aber das ist einfach nur Unsinn ! " von bygones kann ich schon nicht kampflos so stehen lassen

Folgedes Beispiele erstellt ein Array und eine ArrayList mit n int/Integer und misst 3 Mal abwechslungsweise die benötigten Laufzeiten, um alle Zahlen in der Datenstruktur zu addieren.

import java.util.*;
import java.util.Random;

public class ArrayOrList {

	private int n;
	private int[] array;
	private ArrayList<Integer> arrayList;
	
	public ArrayOrList(int n) {
		this.n = n;
		this.array = new int[n];
		this.arrayList = new ArrayList<Integer>();
		Random rand = new Random();
		for (int i=0;i<n;i++) {
			int v = rand.nextInt(100);
			array[i] = v;
			arrayList.add(v);
		}
	}
	
	private void start() {
		testArray();
		testArrayList();
		
		testArray();
		testArrayList();
		
		testArray();
		testArrayList();
	}
	
	private void testArray() {
		int sum = 0;
		long t0 = System.nanoTime();
		for (int i=0;i<n;i++) {
			sum += array[i];
		}
		long dt = System.nanoTime()-t0;
		System.out.println("Array Test: "+dt/1000000+" ms");
	}
	
	private void testArrayList() {
		int sum = 0;
		long t0 = System.nanoTime();
		for (int i=0;i<n;i++) {
			sum += arrayList.get(i);
		}
		long dt = System.nanoTime()-t0;
		System.out.println("ArrayList Test: "+dt/1000000+" ms");
	}

	public static void main(String[] args) {
		ArrayOrList arrayOrList = new ArrayOrList(4000000);
		arrayOrList.start();
	}
}

Das Resultat auf meinem Computer (Windows 7, 64-Bit, Java 1.6.0_16, Core2 Duo 2.53GHz) sieht für n = 4 Mio Elemente folgendermassen aus:

Array Test: 9 ms
ArrayList Test: 49 ms
Array Test: 8 ms
ArrayList Test: 49 ms
Array Test: 8 ms
ArrayList Test: 35 ms

Es würde mich noch interessieren, ob das auf einem 32er System auch solche Unterschiede gibt. Vielleicht hat das ja gerade jemand eines parat

Die LinkedList ist für diese Aufgabe übrigens nicht im geringsten konkurrenzfähig. Für n = 100'000 Elemente dauert es über 8 Sekunden.

 

[Marco13]

Auch wenn Microbenchmarks immer heikel sind: Bei diesem wurden zumindest einige ""Grundregeln"" für's Microbenchmarking beachtet.
Trotzdem sagt das in dieser Form nicht viel aus: Etwas sinnvoller wäre, einen Integer array[] statt eines int array[] zu verwenden, weil man im Moment nicht weiß, wieviel Zeit für die Arrayzugriffe draufgeht, und wie viel für die Umwandlungen von Intger in int. Danach könnte man noch den "RANGE_CHECK" in der ArrayList ausschalten, und aus Neugier, und das ganze dann nochmal mit -server parameter starten... dann dürften sie sich schon etwas annähern. Interessanterweise können bei solchen Benchmarks schon solche Fragen einen Einfluss haben wie ob dort
[c]private ArrayList<Integer> list[/c]
oder
[c]private List<Integer>[/c]
steht, und ob es noch andere List-Implementierungen in diesem Programm gibt... Wie auch immer: Wenn es um den letzten Fitzel Performance geht, liegen Arrays praktisch immer vorne - aber ob man ein paar Prozent Geschwindigkeit gegen eine potentiell(!!!) unschönere Struktur tauschen will, muss man sich dann halt überlegen...

 

[javimka]

Ich habe hier ein int[] array verwendet, S.T.O.R.M eines verwendet hat. Hier habe ich es mit einem Interger[] array getestet:

Array Test: 10 ms
ArrayList Test: 49 ms
Array Test: 10 ms
ArrayList Test: 48 ms
Array Test: 10 ms
ArrayList Test: 35 ms

Und hier habe ich "private List" statt eine "private ArrayList" verwendet. (geht etwas langsamer)

Array Test: 10 ms
ArrayList Test: 55 ms
Array Test: 10 ms
ArrayList Test: 55 ms
Array Test: 9 ms
ArrayList Test: 48 ms

 

[0x7F800000]

In der "Praxis" habe ich aber in 99% der Fälle feststellen müssen, dass es wesentlich angenehmer ist, den faktor 5 in kauf zu nehmen, statt tagelang an einem Programm zu hocken, nur um dieses dann später wegzuwerfen... :bahnhof:

Wenn man mit solchen tests direkt an die Knochen rangeht, muss man auch im Hinterkopf behalten, dass solche Vorteile eh unter einer größeren Architektur vergraben werden könnten, dann hat man am ende eben Laufzeit von 510ms statt 550ms , und hat sich dafür dreimal so lange das Hirn zerbrochen... Und am Ende stellt sich auch noch heraus, dass diese ganzen Arrays auch draußen am Interface des Pakets zu sehen sind, und dann benutzt es kein Mensch^^