Best Practice Wie große "Tabellen" effizient durchsuchen und Daten händeln?

[Greeco-K]

Hallo zusammen!

In meinem Projekt muss ich sehr große Tabellen erzeugen und vielfach durchsuchen. Ich würde gern wissen wie man das am effizientesten anstellt?

Ein typisches Beispiel wären Punkte die im Raum verteilt sind. Jeder Punkt hat eine Nummer / ID und jeweils X,Y,Z Koordinaten. Jetzt würde ich z.B. gerne wissen welche Koordinaten der Punkt mit der ID 123456 hat. Dazu habe ich bisher 2D Arrays genutzt und so etwas gemacht:

for (int i=0 ; i<punktArray.length ; i++) {
     if (punktArray[i][0] == punktID) {
            punkt.set_x = punktArray[i][1];
            punkt.set_x = punktArray[i][2];
            punkt.set_x = punktArray[i][3];
            return;
       }
}

Ich habe eine Klasse "Punkt" erzeugt die als Eigenschaften u.a. X,Y,Z Koordinaten hat. Ich erzeuge ein Objekt von der Klasse, durchsuche das Array nach der gewünschten ID, wenn ich diese gefunden habe weise ich die gefundenen Werte meinem Objekt zu und arbeite mit dem Objekt dann weiter.

Ich erzeuge teilweise sehr viele Objekte und durchsuche das Array durchaus auch einige 10.000 oder einige 100.000 Male. Es ist also wichtig, dass dies möglichst effizient passiert.

Jetzt zu meinen Fragen ... 🙂
Ich möchte gerne auf ArrayList umsteigen. Gibt es hier performance einbußen beim durchsuchen? Oder wäre etwas gänzlich anderes sinnvoller?

Ich habe zwei Initialisierungmöglichkeiten gesehen.

ArrayList[][] table = new ArrayList[10][10];
table[0][0].add(); // add object to that ArrayList

und

List<List<String>> listOfLists = new ArrayList<List<String>>(size);

Wo ist hier der Unterschied?

Ist die Sache mit dem "Punkt" Objekt erzeugen kritisch?

Sooo viele Fragen! 🙂
Ich freue mich auf eure Ratschläge!
Liebe Grüße

 

[Thallius]

Ich würde das nicht selber machen sondern jemandem überlassen der sich mit sowas auskennt. Derjenige heißt Datenbank. Nimm eine SQLite DB und erstelle eine sauber indizierte Tabelle. Dann kannst du der DB einfach die gewünschte Anfrage stellen und bekommst deine Ergebnisse. Schneller wirst du es selbstgemacht bestimmt nicht hinbekomme.

Gruß

Claus

 

[fhoffmann]

Wenn du die Daten im Speicher halten willst, könntest du auch eine Map (z.B. HashMap) benutzen.

 

[mrBrown]

Nimm eine SQLite DB und erstelle eine sauber indizierte Tabelle. Dann kannst du der DB einfach die gewünschte Anfrage stellen und bekommst deine Ergebnisse. Schneller wirst du es selbstgemacht bestimmt nicht hinbekomme.

SQLite ist aber so ziemliche die langsamte Datenbank, die man mit Java nutzen kann, das wird eher das genaue Gegenteil von schneller sein 😛

In zumindest in dem UseCase wird es höchstwahrscheinlich mit einfachen HashMaps schneller gehen

Ich habe zwei Initialisierungmöglichkeiten gesehen.

ArrayList[][] table = new ArrayList[10][10];
table[0][0].add(); // add object to that ArrayList

und

List<List<String>> listOfLists = new ArrayList<List<String>>(size);

Wo ist hier der Unterschied?

Die erste Variante ist Unsinn, da wird ein Array von Arrays von ArrayListen erzeugt, btw mit falscher Syntax.
Im Zweiten Fall eine Liste von Listen von Strings.
Ist dir der Unterschied von Arrays und Listen geläufig?

Ist die Sache mit dem "Punkt" Objekt erzeugen kritisch?

Wahrscheinlich nicht - kommt aber auf den UseCase an.

 

[Thallius]

SQLite ist aber so ziemliche die langsamte Datenbank, die man mit Java nutzen kann, das wird eher das genaue Gegenteil von schneller sein 😛

In zumindest in dem UseCase wird es höchstwahrscheinlich mit einfachen HashMaps schneller gehen
.

Ein richtig konfiguriertes SQLite wird in dem Fall komplett im RAM gehalten. Und ich glaube nicht, dass irgendein Java Code und sei er noch so optimal programmiert an die Geschwindigkeit einer jahrelang optimierten compilierten Anwendung wie SQLite heran kommt.

 

[Xyz1]

An dem Punkt mit SQLite inmemory schnell, ist etwas dran, Thallius liegt damit nicht falsch.
Wie fhoffmann schreibt, erreicht man das in Java damit, dass man zwei HashMap's verwendet.
Eine mappt die Nummer/ID auf Punkte, die andere mappt die Punkte (also drei Hashwerte kombi) auf Nummer/ID.
Dann ist es für jeden UseCase, wie mrBrown schrieb, schnell.
999'999 Arrays der Länge 3 halten ist auch "unproblematisch".
Kann das gerne vorführen.

 

[mrBrown]

Ein richtig konfiguriertes SQLite wird in dem Fall komplett im RAM gehalten. Und ich glaube nicht, dass irgendein Java Code und sei er noch so optimal programmiert an die Geschwindigkeit einer jahrelang optimierten compilierten Anwendung wie SQLite heran kommt.

Ich wette für diesen UseCase dagegen 😉
Glaubst du wirklich, das ein einfaches get auf einer HashMap langsamer ist, als der Umweg über SQL?

Bei entsprechenden IDs kann man das hierbei sogar im wesentlichen auf *1* Arrayzugriff optimieren, da braucht vermutlich allein das Bauen des Strings für die Query länger...

 

[Flown]

Ich muss hier @mrBrown zustimmen. Wenn es so einfache Abfragen sind wie das Mapping ID -> Koordinaten, dann ist das auf jedenfall schneller als über JDBC Driver -> DB -> Query -> Result -> ....
Wenn dann Joins ins Spiel kommen und mehr als eine Tabelle verwendet wird, dann wird eine DB erst interessant.

 

[mrBrown]

So wirklich interessant aber erst, wenns Persistent oder sogar über mehrere Anwendungen hinweg sein muss.
Besser optimieren lassen wird sich tendenziell immer direkt im Programm, im Zweifel mit den gleichen Möglichkeiten, die die DB nutzt. Einerseits weil der gesamte Overhead weg fällt, andererseits, weil genau für die entsprechenden Daten optimiert werden kann.

 

[Greeco-K]

Vielen Dank für die vielen tollen Antworten!

Ich denke ich versuche mal die Hashmap Variante, da sie für mich als Laien auch einfach am leichtesten umzusetzen ist denke ich. Ich habe dazu mal ein Probierbeispiel gemacht.

import java.util.*;

public class TestClass {
    public static void main(String[] args) {
     
        // Hashmap und einige Parameter erzeugen
        HashMap <Integer, double []> map = new HashMap <Integer, double[]>();
        int n = 3;
        double x=11, y=22, z=33;
     
        // Hashmap befüllen!
        map.put(n, new double[] {x,y,z});
        map.put(4, new double[] {44.0,55.0,66.0});
        map.put(5, new double[] {77.0,88.0,99.0});
     
        // in den meisten Fällen würde  ich mit get() einen Key übergeben und mir den dazugehörigen Value holen
        System.out.println(map.get(n)[0] + " " +map.get(n)[1]+ " " +map.get(n)[2]+ " ");
        System.out.println(map.get(4)[0] + " " +map.get(4)[1]+ " " +map.get(4)[2]+ " ");
     
        // in seltenen(!) Fällen müsste es andersherum laufen...
        for (Map.Entry<Integer, double[]> i : map.entrySet()) {
            int k = i.getKey();
            double [] v = i.getValue();

            double [] compare = new double [] {77.0 , 88.0 , 99.0};
         
            if (Arrays.equals(v, compare)) {
                System.out.println("Correct! - " + k);
            }
            else {System.out.println("Wrong! - " + v[0] +" "+ v[1] +" "+ v[2]);}
        }
    }
}

// Printout
// 11.0 22.0 33.0
// 44.0 55.0 66.0
// Wrong! - 11.0 22.0 33.0
// Wrong! - 44.0 55.0 66.0
// Correct! - 5

Wäre das soweit in Ordnung?
Ich hab gelesen, dass wenn die Hashmap korrekt implementiert ist, man konstante "Suchzeiten" hat egal wie groß Hashmap ist?! Stimmt das? Wäre natürlich super. Hätte ich hier alles korrekt implementiert?! 🙂

Vielen Dank und liebe Grüße

 

[mrBrown]

Ja, das kann man so machen. Ich würde aber statt einem Array eine sinnvolle Klasse nutzen.
Für den Rückweg könnte man auch eine Map nutzen, die von Punkt auf ID maped, kommt aber drauf an wie oft du das machen musst.



Das entspricht O(1), ja, aber in der Praxis steigt es natürlich schon mit der Größe, ist aber meistens nicht relevant

 

[Greeco-K]

Ja super! Mit der Klasse hätte ich es dann so probiert:

import java.util.*;

public class TestClass {
    public static void main(String[] args) {

        HashMap <Integer, Point> map = new HashMap <Integer, Point>();

        int n = 3;
        double x=11, y=22, z=33;

        Point p = new Point();
        p.set_x(x);
        map.put(n, p);

        System.out.println(map.get(3).get_x());

    }
}

class Point {

    //Empty Constructor
    public Point () {};
   
    //########### Get and Set Methods ###########
   
    private double x_coordinate;
   
    //----------- Node ID -------------

    public void set_x (double x) {
        x_coordinate = x;
    }

    public double get_x () {
        return x_coordinate;
    }
}

und dann eben entsprechend die Klasse weiter aufgebaut mit mehr Parametern und mehr get / set methoden usw.

War das so gemeint?

 

[mrBrown]

Ja, genau so.
Wobei ich die Punkte immutable machen würde und hashcode und equals überschrieben würde, ersteres ist allerdings Geschmacksache, letzteres aber nötig, falls sie in einer HashMap als Key genutzt werden sollen

 

[Greeco-K]

Ja, genau so.
Wobei ich die Punkte immutable machen würde und hashcode und equals überschrieben würde, ersteres ist allerdings Geschmacksache, letzteres aber nötig, falls sie in einer HashMap als Key genutzt werden sollen

Uff... das habe ich jetzt nicht verstanden. Kann du mir die Implementierung anhand meines Minibeispiels zeigen?

Hab ich es richtig verstanden, es geht darum anstatt ein Integer als Key (wie in meinem Beispiel) den neu eingeführten Datentyp "Punkt" als Key zu verwenden ...?

 

[mrBrown]

Uff... das habe ich jetzt nicht verstanden. Kann du mir die Implementierung anhand meines Minibeispiels zeigen?

Immutable heißt einfach nur, dass alle Variablen final sind. Das macht das arbeiten damit oftmals einfacher.

hashcode und equals müssen überschreiben werden, damit es überhaupt als Key genutzt werden kann, da reicht der Autogenerierte Teil der IDE.

Hab ich es richtig verstanden, es geht darum anstatt ein Integer als Key (wie in meinem Beispiel) den neu eingeführten Datentyp "Punkt" als Key zu verwenden ...?

Integer als Key passt schon, wenn du nach ID suchen willst 😉
Punkt als Key ist nur für andere UseCases interessant 😉

 

[DrZoidberg]

Mit etwas mehr Informationen könnten wir vielleicht noch bessere Tipps geben.
Wie viele Punkte sind es insgesamt? In welchem Bereich liegen die IDs? Wie viele Punkte kommen pro Sekunde dazu und wie oft pro Sekunde durchsuchst du die Liste?