Arraysuche schneller ausführen?

[gnui]

Hallo,
ich habe ein Problem mit der Laufzeit meines Programms.

Und zwar habe ich ein Programm welches 6 stellige Nummern mit dazugehörigen Preis einliest. Das können bis zu eine Million Nummern sein. Nun soll das einlesen allerdings so sein, dass wenn die Nummer schon vorhanden ist nur der Preis aktualisiert wird.
Ich habe das ganze im Moment mit einem 2 dimensionalen Array gelöst. Und zwar Feld[][] wobei die erste dimension einfach die Anzahl der Nummern sind und in der 2. Dimension bei 0 die eigentliche Nummer gespeichert ist und bei 1 dann der dazugehörige Preis.

Mein Problem ist nun, dass ich bevor ich eine weitere Nummer zu dem Array hinzufüge erst das bisherige Array komplett durchlaufen muss um zu prüfen ob die Nummer schon vorkommt.
Bei 300000 gespeicherten Nummern denen weitere 10 hinzugefügt werden sollen wären das dann 10*300000 durchläufe in etwa was einfach viel zu lange dauert.

Ich habe es auch schon versucht mit sortieren der Elemente um dann schneller nach doppelten suchen zu können, aber das sortieren von so vielen Elementen dauert dann auch schon sehr lange so dass ich da eher einen negativen Effekt empfunden habe.

Hätte jemand eventuell eine Lösung für dieses Problem? Eventuell eine andere Form des Array..wobei ich da nun schon einige Varianten ausprobiert habe. Das Programm muss ja nicht innerhalb einer Sekunde eine so große Elementzahl handhaben können, aber im Moment braucht mein Programm locker eine halbe Stunde für die Aufgabe.

Danke schonmal im Vorraus

 

[Ebenius]

Das Feld sortiert zu halten ist eine Möglichkeit. Dann kannst Du mit Arrays.binarySearch() suchen. Oder Du hältst Deine Daten in einer TreeMap. Oder ...

Ebenius

 

[gnui]

Oder? Ist dieses Array.binarySearch nicht nur für eindimensionale Arrays? Ich müsste dann ja schaun ob eine Nummer in Feld[0] vorkommt wobei i so lang ist wie die bisherige Anzahl der Elemente.

Und wegen sortieren, du meinst also wenn ich das sortieren lieber nach jedem neuen Element machen sollte? Welches Verfahren wäre da denn gut? Habe zur Zeit erstmal nur Bubblesort realisiert zum Test und weil es auch am einfachsten war aber damit wäre es wohl dann wieder sehr lange.

Das mit der Treemap denke ich wäre nicht so vorteilhaft für mich, da ich mich da nicht so auskenne und außerdem das ganze per Arrays realisiert werden soll.

 

[Ebenius]

Wenn Du an dem zweidimensionalen Feld festhalten willst: Du kannst alle eindimensionalen Felder immer sortiert halten. Dann kannst Du mit Array.binarySearch (nachdem Du die erste ebene herausgefunden hast) herausfinden, ob diese Nummer schon im Feld ist. Wenn dem so ist, aktualisierst Du die Daten. Wenn nicht, bekommst Du mit Array.binarySearch die Position an der Du einfügen musst. Das bedeutet, dass Du die Felder eigentlich nie sortieren musst.

Oder eben gleich alles in TreeSet oder TreeMap halten.

Ebenius

 

[gnui]

Danke für die schnelle Antwort.

Wie meinst du "wenn ich die erste Ebene herausgefunden habe" ? Die erste Ebene sagt ja eigentlich nix über den Inhalt aus sondern ist nur eine durchnummerierung der 2 Elemente der 2. Ebene dann. Versteh da nicht ganz wie ich mit meinem zweidimensionalen Feld dennoch das nutzen könnte bzw was ich dort herausfinden könnte, selbst wenn das Feld sortiert ist sagt der Index der ersten Ebene ja nicht weiter etwas aus.
Wobei so gesehen steht die 2. Ebene ja schon fest, es soll immer Feld[0] verglichen werden, was ja quasi schon einem eindimensionalen Array recht ähnlich kommt.
Und warum bekomme ich die Position an der ich einfügen muss wenn das ganze noch nicht vorhanden ist? Heißt das die Funktion gibt mir dann aus an welcher Position das neue Element der sortierung entsprechend passend wäre? Dann müsste ich ja dann alle Elemente ab dort um eins nach hinten rücken lassen.

Ansonsten meinst du wäre es eventuell einfacher 2 einzelne Felder zu machen? Dann könnte man ja scheinbar diese Arrays. Funktionen benutzen.

Und wegen dem Treeset, die Aufgabe soll mit Arrays gelöst werden, ansonsten wäre das wohl auch eine gute Idee auch wenn ich mich mit diesen Sachen garnicht auskenne.

 

[Ebenius]

Okay... dan hab ich das mit dem zweidimensionalen Feld fehlinterpretiert. In dem Fall sortierst Du natürlich das Feld in der ersten Ebene und baust Du Dir einen einen Comparator. Das sieht in etwa so aus:

class MyComparator implements Comparator<Feld[]> {
  public int compare(Feld[] f1, Feld[] f1) {
    return ( wenn f1 kleiner ) ? -1 : ( wenn gleich ) ? 0 : 1;
  }
}

Und diesen Comparator benutzt Du immer, wenn Du sortierst oder suchst.

Heißt das die Funktion gibt mir dann aus an welcher Position das neue Element der sortierung entsprechend passend wäre? Dann müsste ich ja dann alle Elemente ab dort um eins nach hinten rücken lassen.

Das heißt es, ja. Wenn der Rückgabewert von Arrays.binarySearch(T[], T, Comparator<? super T>) größer oder gleich 0 ist, dann wurde das gesuchte Element gefunden. Ist der Rückgabewert kleiner als 0, dann gibt der Wert (-(insertion point) - 1). Sieht in etwa so aus:

final int suchErgebnis = Arrays.binarySearch(felder, gesuchtesFeld, comparator);
if(suchErgebnis < 0) {
  // need to insert the new field
  final int hierEinfuegen = -suchErgebnis + 1;
  final Feld[][] neueFelder = Feld[felder.length + 1];
  System.arraycopy(felder, hierEinfuegen, neueFelder, hierEinfuegen + 1, felder.length - hierEinfuegen);
  felder[insertAt] = gesuchtesFeld;
  felder = neueFelder;
} else {
  // die Daten in felder[suchErgebnis] aktualisieren
}

(Code im Browser getippt. Ist bestimmt was falsch)

Ebenius

 

[gnui]

Leider ist laut Aufgabe nur eine Klasse zulässig, also die Klasse zum verwalten dieser Elemente weshalb das mit dem Comperator dann wohl leider nicht so klappt.

Wären denn 2 eindimensionale Felder einfacher? Dann könnte ich ja direkt dieses binarySearch anwenden oder?
Und zum Daten aktualisieren. Gibt binarySearch bei gefunden Element auch die Position dessen noch irgendwie an oder wie könnt ich das dann aktualisieren?

 

[Ebenius]

Leider ist laut Aufgabe nur eine Klasse zulässig, also die Klasse zum verwalten dieser Elemente weshalb das mit dem Comperator dann wohl leider nicht so klappt.

Das muss kein Problem sein. Du wirst sicher sowas dürfen, oder?

public class MyOneAndOnlyClass {
  private Comparator<Object[]> arrayComparator = new Comparator<Object[]>() {
    ....
  };

  // Rest Deiner Klasse
}

Wären denn 2 eindimensionale Felder einfacher? Dann könnte ich ja direkt dieses binarySearch anwenden oder?
Und zum Daten aktualisieren. Gibt binarySearch bei gefunden Element auch die Position dessen noch irgendwie an oder wie könnt ich das dann aktualisieren?

Es gibt immer die Position an, wenn es was findet und den Insertion Point (wie oben beschrieben), wenn es nix findet. Wie ist denn Dein Feld deklariert?

Mit zwei eindimensionalen Feldern zu arbeiten ist sicher auch möglich. Du musst eben, nachdem Du die Position gefunden hast, immer beide Felder modifizieren.

Ebenius

 

[gnui]

Danke nochmal für die sehr schnelle Antwort.

Mein feld ist zur zeit noch als int[][] feld = new feld[900000]][1] deklariert, wobei ich bis jetzt die Anzahl der gespeicherten Sachen noch in einer Variable habe und so nicht das ganze Feld durchsuchen muss sondern nur soviel wie nötig, was oft trotzdem zu viel ist.

Ja und private Dinge in der Klasse dürfen wir verwenden ja, wir müssen uns nur an ein Interface halten aber private-Sachen dürften davon ja nicht betroffen sein.
Nur leider habe ich deinen Comparator nicht ganz verstanden. Du übegibst immer ein Object[] oder Feld[], aber das schaut ja alles eher nach eindimensionalen Feldern aus bzw setzt du da auch ein zweidimensionales mit einem eindimensionalen Feld gleich, geht soetwas? Wasdu mit der arraycoppy Funktion machst ist mir auch noch nicht ganz klar, ich dachte binary Search suchen und dann einfügen da man die Position kennt würde reichen.
Außerdem rückst du in deinem Beispiel beim einfügen nicht alle darauffolgenden Elemente um eins hinter, macht das die Funktion automatisch beim einfügen eines Elementes in ein Array?

Und naja auf Grund dieser vielen Fragen, bei 2 eindimensionalen Feldern..würden da in deinem Beispiel die vielen Extrafelder nicht wegfallen? Dann müsst ich ja nur das Nummernfeld immer vergleichen auf doppelte, dann dort einfügen und das mit dem selben Index im Preisfeld tun, siehst du da einen Nachteil? Für mich klingt das erstmal einfacher weil es scheinbar doch einiges an Programmierung noch benötigt ein 2 dimensionales Feld zu vergleichen.

 

[Ebenius]

Danke nochmal für die sehr schnelle Antwort.

Mein feld ist zur zeit noch als int[][] feld = new feld[900000]][1] deklariert, wobei ich bis jetzt die Anzahl der gespeicherten Sachen noch in einer Variable habe

Bestimmt meinst Du int[][] feld = new int[900000][2], oder?

Ich schlage vor, Du mühst Dich nicht mit dem Comparator ab, sondern machst wirklich zwei Felder, in etwa:

public class MyOneAndOnlyClass {
  private static final int FELD_LAENGE = 900000;
  private int[] artikelNummern = new int[FELD_LAENGE];
  private int[] preise = new int[FELD_LAENGE];
  private int anzahlArtikel = 0;

  // ...
}

Wenn Du einen Artikel eintragen oder aktualisieren willst, dann machst Du sowas da:

int suchErgebnis = Arrays.binarySearch(artikelNummern, 0, anzahlArtikel, artikelNummer);
if (suchErgebnis > -1) {
  // Diesen Artikel gibt es schon; suchErgebnis ist der Index im Feld
  preise[suchErgebnis] = preis;
} else {
  // Dieser Artikel ist neu, wird hinzugefügt
  int hierEinfuegen = -suchErgebnis + 1;

  // Inhalte der Felder ab Index hierEinfuegen nach rechts verschieben
  System.arraycopy(artikelNummern, hierEinfuegen, artikelNummern,
        hierEinfuegen + 1, anzahlArtikel - hierEinfuegen);
  System.arraycopy(preise, hierEinfuegen, preise, hierEinfuegen + 1,
        anzahlArtikel - hierEinfuegen);
  
  // Neuen Artikel im Feld speichern
  artikelNummern[hierEinfuegen] = artikelNummer;
  preise[hierEinfuegen] = preis;

  // Anzahl der Artikel inkrementieren
  anzahlArtikel ++;
}

Wasdu mit der arraycoppy Funktion machst ist mir auch noch nicht ganz klar, ich dachte binary Search suchen und dann einfügen da man die Position kennt würde reichen. Außerdem rückst du in deinem Beispiel beim einfügen nicht alle darauffolgenden Elemente um eins hinter, macht das die Funktion automatisch beim einfügen eines Elementes in ein Array?

ArrayCopy kopiert aus einem Feld in ein anderes (oder das gleiche). Genau damit mache ich die Verschiebung. Schau Dir dazu mal die API-Doc an.

Hilft Dir das?

[edit] Nur um es hervorzuheben: BinarySearch funktioniert nur, wenn das Feld auch sortiert ist. Also dann nirgends das Feld modifizieren, ohne auf die Sortierreihenfolge zu achten!

Ebenius

 

[Marco13]

EDIT: Ein bißchen verändert...

Zwei einzelne Felder wären noch häßlicher, als ein int[][] feld = new feld[900000]][1], und aus Software-Entwurfs-Sicht IMHO gröbster Unfug. Die Anforderung "Nur eine Klasse" zu verwenden, verstehe ich (aus Sicht des Aufgabenstellers) aber das KANN sich IMHO nicht auf innere Klassen beziehen, solange sie der äußeren Klasse helfen, die voregebene Schnittstelle zu erfüllen. Du solltest also sowas machen können wie

class HauptklasseFürAufgabe1
{
    private static class Entry
    {
        ... siehe oben ...
    }
}

und diese Entry-Klasse kannst du dann in der Hauptklasse ganz normal verwenden.

Du solltest ggf. mal die genaue Aufgabenstellung posten (bzw. die Schnittstelle, die erfüllt werden muss). Es kann nämlich gut sein, dass es günstiger wäre, keine
private List<Entry> list = new ArrayList<Entry>();
zu verwenden, sondern eine
private Map<Integer, Entry> map = new HashMap<Integer, Entry>();
(das muss dann ggf. nichtmal eine sortiere Map sein...)

EDIT:

Im Moment klingt es aber, als würde es schon eine
private Map<Integer, Integer> mapNummerAufPreis = new HashMap<Integer, Integer>();
tun...

 

[Ebenius]

[...]Im Moment klingt es aber, als würde es schon eine
private Map<Integer, Integer> mapNummerAufPreis = new HashMap<Integer, Integer>();
tun...

Lies mal oben: Sie sollen's mit Feldern lösen und sie sollen nur eine Klasse machen. Sonst würde ich das nie so vorschlagen!

Ebenius

 

[Marco13]

Hm - dass das unbedingt mit Arrays gemacht werden MUSS (und nicht mit einer Map gemacht werden DARF) konnte ich jetzt nirgendwo herauslesen - aber ich habe ja schon nach der genauen Aufgabenstellung gefragt....

 

[Ebenius]

Hm - dass das unbedingt mit Arrays gemacht werden MUSS (und nicht mit einer Map gemacht werden DARF) konnte ich jetzt nirgendwo herauslesen

Und wegen dem Treeset, die Aufgabe soll mit Arrays gelöst werden, ansonsten wäre das wohl auch eine gute Idee auch wenn ich mich mit diesen Sachen garnicht auskenne.

@gnui: Wenn man innere Klassen benutzen darf, dann würde ich natürlich auch eine eigene datenhaltende Klasse benutzen...

Ebenius

 

[Marco13]

class MainClass
{
    // Here's the requested array:
    private Object array[] = new Object[0];

    // Real stuff starts here:
    private Map<Integer, Data> map;
    ...
}

:lol: