Unsortiertes Array durchsuchen

[DirkHo]

Hallo,

ich würde gerne ein unsortiertes Array durchsuchen.
Folgendes Szenario habe ich: 2 CSV-Dateien die in vier Spalten enthalten, 3 davon sind Beschreibungen, die diesen Wert eindeutig machen und die vierte Spalte ist der Wert, mit dem auch gerechnet werden soll.

Eine Datei könnte so in der Art aussehen (eigentlich sind es Daten aus dem Geschäft, die ich sicherheitshalber mal anders dargestellt habe):

Ort | PLZ | Strasse | Wert
Musterstadt | 12345 | Musterstr | 0.87
Musterstadt | 12345 | Abcstr | 0.63
Musterstadt | 12346 | Teststr | 0.93
Musterhausen | 23439 | Abcstr | 0.77
Musterhausen 23439 | Teststr | 0.38

Man sieht, es können z.B. Ort und PLZ gleich sein, die Straße ist dann jedoch anders und die Kombination der 3 Werte (Ort, PLZ, Straße) macht den Wert (Spalte "Wert") eindeutig.

Jetzt habe ich in einer CSV-Datei stehen

bla.blubb.ort_0 = Musterstadt
bla.blubb.ort_1 = Musterhausen
bla.blubb.plz_0 = 12345
bla.blubb.str_1 = Musterstr
...

Diese lese ich aus der Properties aus und habe dann entsprechend 3 Arrays ort[], plz[] und strasse[]. Index 0 bei ort wäre dann eben Musterstadt, 1 Musterhausen,...

Wenn ich nun die CSV einlese möchte ich das ja Zeilenweise tun und wenn ich dann z.B. auf Musterstadt stoße will ich einfach das Array ort[] durchsuchen, welchen Index Musterstadt hat, dann die nächste Spalte, welchen Index z.B. 12345 (in plz[]) hat und dann, welchen Index Musterstr (in strasse[]) hat.

Anhand dieser Indexe fülle ich dann ein Array wert[][][].

Bei mir würde das z.B. dann ergeben
wert[0][0][1] = new Double(0.87);

Wenn nun jemand ein Formular absendet, in dem er per Dropdown die entsprechenden Felder ausgewählt hat muss ich mir die übermittelten Werte (values des Dropdown-Feldes sind dann logischerweise die Indexe) als Index in das Array eintragen und kann dann damit rechnen.

Mein Problem ist jetzt nur, dass ich über Arrays.binarySearch() nur sortierte Arrays durchsuchen kann (was sicher auch sinnvoll ist, nur in meinem Fall weiß ich das nicht so recht). Wenn ich mein Array nun aber sortiere passen später die Indexe mit den Values aus den Dropdown-Felder nicht mehr überein.

Gibt es also eine fertige Funktion, die dies ermöglicht? Was haltet ihr ansonsten in Sachen Performance von meiner vorgehensweise? Ich müsste die CSV-Dateien halt ständig neu einlesen, da sich die Werte ständig ändern.

Vielen Dank und viele Grüße,

Dirk

 

[miffi]

Howdie.

Ich hab da grad noch ein Verständnis-Problem:
Was ist das Problem, die Arrays zu sortieren, BEVOR du sie in ein DropDown-Menü schreibst? Wenn nur Strings drin stehen, musst du nicht mal ein Comparable- bzw. Comparator-Interface implementieren: Strings beinhalten das Comparable-Interface bereits und werden nach ihrer natürlichen Ordnung (alphabetisch) sortiert, wenn du die Sortierungs-Methode aufrufst.

Ergo: Unter der Voraussetzung, dass du nur Strings oder numerische Datentypen in den Arrays hast, kannst du (bevor die DropDown-Menüs gefüllt werden) jedes Array mit Arrays.sort(meinArray) ohne Comparator sortieren, was bedeutet, dass du die Suchfunktion ebenfalls ohne Comparator aufrufen kannst: Arrays.binarySearch(meinArray, "musterstraße").

Vielleicht hab ich aber auch das Problem nicht wirklich verstanden...

Gruß
miffi

//////// Edit:
Falls es allerdings so ist, dass die Indizes des Arrays mit denen in den Properties auch nach dem Auslesen weiterhin übereinstimmen müssen, noch ein anderer Gedanke:
Du kannst ein unsortieres Array von vergleichbaren (Comparable-implementierenden) Elementen - wie in deinem Fall vermutlich Strings - auch ohne Sortierung durchsuchen. Da dein gesuchtes Element nur einmal vorkommt, könnte das sogar funktionieren... Allerdings ist das keine verfizierte Information - eine binäre Suche ohne Sortierung ist in so einem Fall zwar durchaus möglich, kann allerdings unvorhersehbare Ergebnisse liefern und wird daher nicht empfohlen.

 

[Anime-Otaku]

Ansonsten kannst du nichts anderes machen als jeden Wert in der Liste durchzugehen und zu vergleichen.

 

[Vereth]

*widersprech*
Ich glaube, du speicherst deine Daten am besten andersrum ab. Für die Tabellen ort[], plz[] und strasse[] verwendest du dann eine Hashtable. Als key verwendest du dann die Strings, z.B. 'Musterstadt', und als value den intern zu verwendenden Index. Dann kannst du z.B. schreiben:

int i = ort["Musterstadt"];
plz["12543"] = 5;

Wenn du die Dropdown-Felder mit den Strings füllen willst, iterierst du mit foreach über die Hashtable und liest den jeweiligen key-String aus.

 

[miffi]

Vereth hat natürlich recht, die sauberste Methode - bei der du außerdem sämtliche Werte nach deinem Gutdünken vergeben kannst - wäre eine Map wie Hashtable.
Mein Vorschlag mit der Vorsortierung wäre nur dann angebracht, wenn du aus Design-Gründen deine Arrays beibehalten willst bzw. musst.

Gruß
miffi

 

[Sentoo]

Vorab, ich habe nicht heraus gelesen, dass Du bei dem mehrdimensionalen Array bleiben musst ... ?

Dann würde ich, wie die anderen meinten eine HashMap vorschlagen oder ein sortiertes Array ...

Zunächst die Klasse, die die Attribute kapselt. Interessant ist da eigentlich nur die vergleichsmethode "compareTo(AdressSatz aAndereAdresse)".

package de.tutorials.collections;

public class AdressSatz implements Comparable<AdressSatz> {
    private String ort;
    private Integer plz;
    private String strasse;
    private Float wert;
    
    public AdressSatz(String aOrt, Integer aPlz, String aStrasse) {
        super();
        ort = aOrt;
        plz = aPlz;
        strasse = aStrasse;
    }

    public Float getWert() {
        return wert;
    }

    public void setWert(Float aWert) {
        wert = aWert;
    }

    @Override
    public int compareTo(AdressSatz aAndereAdresse) {
        // Die einzelnen Attribute mit einem Faktor gewichten.
        // Es kann sein, dass der Faktor noch angepasst werden muss.
        int tmpCompareWert = plz.compareTo(aAndereAdresse.plz) * 100;
        tmpCompareWert += ort.compareTo(aAndereAdresse.ort) * 10;
        tmpCompareWert += strasse.compareTo(aAndereAdresse.strasse);
        return tmpCompareWert;
    }

    @Override
    public String toString() {
        return plz + " | " + ort + " | " + strasse;
    }

    @Override
    public int hashCode() {
        // 1) Von Eclipse generieren lassen.
        // 2) Die gleichen Faktoren bei den HashCodes vermerken, wie beim
        //    #compareTo( .. ).
        final int prime = 31;
        int result = 1;
        result = prime * result + ((ort == null) ? 0 : ort.hashCode() * 10);
        result = prime * result + ((plz == null) ? 0 : plz.hashCode() * 100);
        result = prime * result + ((strasse == null) ? 0 : strasse.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        // Von Eclipse generieren lassen.
        // ... weg gelassen, ist etwas lang.
    }    
}

Durch das Comparable interface kannst Du die Arrays.sort Methode verwenden. Wenn Du hashCode ordentlich implementierst kannst Du statt dessen auch einfach eine HashMap<AdressSatz, AdressSatz> verwenden. Kannst Du in den Tests nachvollziehen.

package de.tutorials.collections;

import static org.junit.Assert.assertSame;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class AdressSatzTest {

    private AdressSatz[] adressArray;
    private AdressSatz bruel;
    private AdressSatz elsdorf;
    private AdressSatz bedburg;
    private AdressSatz elsdorf2;
    private HashMap<AdressSatz, AdressSatz> adressMap;
    
    @Before
    public void setUp() throws Exception {
        adressArray = new AdressSatz[4];
        
        bruel = new AdressSatz("Brühl", 50321, "Comesstrasse");
        bruel.setWert(0.42F);
        adressArray[2] = bruel;
        
        elsdorf = new AdressSatz("Elsdorf", 50189, "Gladbacherstrasse");
        elsdorf.setWert(0.89F);
        adressArray[0] = elsdorf;
        
        bedburg = new AdressSatz("Bedburg", 50181, "Hauptstrasse");
        bedburg.setWert(0.89F);
        adressArray[1] = bedburg;
        
        elsdorf2 = new AdressSatz("Elsdorf", 50189, "Mausweg");
        elsdorf2.setWert(0.23F);
        adressArray[3] = elsdorf2;
        
        Arrays.sort(adressArray);
        
        adressMap = new HashMap<AdressSatz, AdressSatz>();
        for(AdressSatz tmpSatz : adressArray) {
            adressMap.put(tmpSatz, tmpSatz);
        }
    }

    @Test
    public void testCollectionsSort() {
        assertSame(bedburg, adressArray[0]);
        assertSame(elsdorf, adressArray[1]);
        assertSame(elsdorf2, adressArray[2]);
        assertSame(bruel, adressArray[3]);
    }

    @Test
    public void testCollectionsFind() {
        AdressSatz tmpSatz = new AdressSatz(
                "Elsdorf", 50189, "Gladbacherstrasse");
        int tmpIndex = Arrays.binarySearch(adressArray, tmpSatz);
        Float tmpWert = adressArray[tmpIndex].getWert();
        assertSame(elsdorf.getWert(), tmpWert);
    }

    @Test
    public void testHashMap() {
        AdressSatz tmpSatz = new AdressSatz(
                "Elsdorf", 50189, "Gladbacherstrasse");
        Float tmpWert = adressMap.get(tmpSatz).getWert();
        assertSame(elsdorf.getWert(), tmpWert);
    }
    
    @After
    public void tearDown() throws Exception {
        adressArray = null;
        bruel = null;
        bedburg = null;
        elsdorf = null;
    }
}

 

[DirkHo]

Hallo zusammen,

erst einmal vielen Dank für eure vielen Antworten! Ich werde die Vorschläge am Montag direkt noch mal durchlesen und dann mal testweise verwenden.

VIelen Dank und viele Grüße,

Dirk