Die Laufzeit ist zu lang :-(

Hallo :wave: ,

lässt sich hier etwas vereinfachen was ich aber bislang nicht sehe?:

/* .... */
f.addLine("Parse Systems");
long counter1 = 0;
long counter2 = 0;
long counter3 = 0;
long counter4 = 0;
try (BufferedReader r = new BufferedReader(new FileReader("a.csv"))) {
    String[] h = r.readLine().split(",");
    String l;
    a : while ((l = r.readLine()) != null) {
        counter4++;
        String[] ar = l.split(",", h.length);
        if (ar.length != h.length) {
            throw new IllegalArgumentException(l);
        }
        HashMap<String, Object> m = new HashMap<>();
        for (int i = 0; i < h.length; i++) {
            if (ar[i].isEmpty()) {
                counter1++;
                ar[i] = "-1";
            }
            if (i >= 3 && i <= 5) {
                Object o = parseN(ar[i], 1, true);
                if (o == null) {
                    counter2++;
                    f.addLine(l);
                    continue a;
                }
                m.put(h[i], o);
            } else {
                m.put(h[i], parseN(ar[i], 2, false));
            }
        }
        if (distToSol(m) > 150) {
            counter3++;
            continue;
        }
        systems.put((Long) m.get("id"), m);
    }
} catch (IOException ex) {
    f.addLine(ex.getMessage());
}
f.addLine("Counter: " + counter1 + ", " + counter2 + ", " + counter3 + "= " + counter4);
f.addLine("Systems: " + systems.size());
/* .... */

Object parseN(String s, int min, boolean failFast) {
    switch (min) {
        case 3:
            try {
                return Integer.parseInt(s);
            } catch (NumberFormatException e1) {
                try {
                    return Long.parseLong(s);
                } catch (NumberFormatException e2) {
                    try {
                        return Float.parseFloat(s);
                    } catch (NumberFormatException e3) {
                        if (failFast) {
                            return null;
                        }
                        return s;
                    }
                }
            }
        case 2:
            try {
                return Long.parseLong(s);
            } catch (NumberFormatException e2) {
                try {
                    return Float.parseFloat(s);
                } catch (NumberFormatException e3) {
                    if (failFast) {
                        return null;
                    }
                    return s;
                }
            }
        default:
            try {
                return Float.parseFloat(s);
            } catch (NumberFormatException e3) {
                if (failFast) {
                    return null;
                }
                return s;
            }
    }
}

float distToSol(HashMap<String, Object> m) {
    return (float) Math.sqrt((Float) m.get("x") * (Float) m.get("x") + (Float) m.get("y") * (Float) m.get("y") + (Float) m.get("z") * (Float) m.get("z"));
}

    LinkedHashMap<Long, HashMap<String, Object>> systems = new LinkedHashMap<>();

Ein paar Werte:
Es gibt 22967572 Systeme, davon sind 25641 gesucht, 22941930 nicht gesucht und 1 ungültig.
Ich brauche also 0,11 % der Systeme.

Das Problem ist, dass das parsen 7,5 Minuten dauert!!!

Wenn ich bei einem Code-Review (egal ob von einem Kollegen, Studenten oder sonstwem) solchen Code sehen würde, würde ich denjenigen fragen, ob er mich verarschen will.

Es gibt im wesentlichen zwei Möglichkeiten:

  1. Entweder du hast dir, als du das geschrieben hast, keine Mühe gegeben, es vernünftig zu schreiben. Dann müßte ich fragen: Warum sollte sich das jemand durchlesen und versuchen, das besser zu machen?
  2. Du hast dir dabei Mühe gegeben. Dann wird das, was man dazu sagen könnte, etwas unbequem.

Poste nochmal “richtigen” Code, am besten compilierbar und testbar, und am besten mit einem kleinen Beispiel-CSV (vielleicht 50 Zeilen), damit man eine Chance hat, zu erahnen, worum es da geht.

5 „Gefällt mir“

Hallo Marco,
Danke für Deine Antwort. Es ist so, dass es, um es vernüftig zu machen, wahrscheinlich Commons CSV braucht… Was allerdings noch langsamer wäre!!!

Es geht darum, eine 3-gb-CSV zu parsen, in der Strings, floats, ints und longs stehen vorkommen, zu parsen!

HashMap<String, Object> könnte man ja durch eine Klasse ersetzen, aber weiß nicht, ob eine HashMap erstellen viel Platz braucht und langsam ist - oder es am ExceptionHandling liegt…

Ich kann mich Marko nur anschließen.

Da du ja anscheinend ein bestimmtes Format im CSV erwartest, könntest du einer Zeile eine eigene Klasse spendieren, mit primitiven Typen, so dass das ganze Boxing schon mal wegfällt.

Und warum ziehst du die Wurzen in distToSol? Vergleiche doch einfach mit 150*150.

Was das “wenn ich es richtig schreibe, wird es noch langsamer” angeht: Viele Optimierungen sieht man erst, wenn man auf verständlichen Code schaut. Selbst wenn du z.B. am Ende die Commons CSV nicht nimmst, hilft dir diese einfachere Variante, Struktur in diesen Haufen zu bekommen. Und wenn du dann optimierst, dann nicht frei Schnauze, sondern nachdem du gemessen hast, wo es wirklich klemmt.

3 „Gefällt mir“

Hier sind einfach mal 20 zufällig gewählte CSV-Zeilen:

[id, edsm_id, name, x, y, z, population, is_populated, government_id, government, allegiance_id, allegiance, state_id, state, security_id, security, primary_economy_id, primary_economy, power, power_state, power_state_id, needs_permit, updated_at, simbad_ref, controlling_minor_faction_id, controlling_minor_faction, reserve_type_id, reserve_type]
....
7104,9790,"HIP 21776",46.75,-131.53125,-300.65625,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1543522071,"HIP 21776",,,1,Pristine
9626,14372,"Hyades Sector HW-W d1-63",126.1875,-29.625,-141.46875,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1540251275,,,,,
22879,26367,"Blanco 1 Sector WE-Y c1-2",-28.53125,-712.125,12.6875,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1513648221,,,,,
23485,27298,"Praea Euq UV-O b6-2",544.53125,111.5625,362.53125,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116422,,,,,
23486,27372,"Praea Euq XM-C b13-1",561.4375,95.1875,495.53125,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116422,,,,,
23698,27811,"LTT 8201",-28.21875,-46.0625,60.9375,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1543187784,"LTT 8201",,,,
25440,32888,"Col 285 Sector FC-T b17-2",-122.90625,-213.09375,25.1875,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1537681985,,,,,
26615,34662,"Wredguia YN-E c26-0",-920.65625,406.71875,90.8125,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1508706196,,,,,
27965,21108,"Crucis Sector MD-S b4-2",68.71875,35.28125,88.21875,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1543440958,,,,,
28107,37791,"NGC 3590 CLA 15",4986.75,-17.03125,1934.8125,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1541004043,,,,1,Pristine
28792,47641,"Col 285 Sector WV-C c13-18",-42.625,50.5625,181.0625,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1540718409,,,,,
29062,46413,"HIP 117922",33.09375,-272.625,81.1875,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1526325003,"HIP 117922",,,,
32591,58659,"Praea Euq GS-M b48-5",148.6875,21.28125,1274.78125,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116443,,,,,
33670,59164,"Col 70 Sector ND-X a51-0",143.34375,-36.5625,-1047.84375,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116445,,,,,
35479,34737,"HIP 111916",-1627.125,-505.78125,-208.75,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116449,"HIP 111916",,,,
35614,42327,"Sharru Sector IH-V b2-5",15.0625,67.875,-16.09375,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1543537750,,,,,
35793,49318,"Hydrae Sector SD-T b3-3",97,54.53125,85.59375,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1543432617,,,,,
35944,59360,"Col 359 Sector VS-J c9-19",-142.59375,-120.5625,530.9375,0,0,176,None,5,None,80,None,64,Anarchy,10,None,,,,0,1517164581,,,,,
36104,69185,"Traikaae DU-G b14-0",-960.03125,740.9375,4359.84375,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116451,,,,,
36345,70523,"Traikaae ZS-O c20-11",-1128.46875,296.96875,4949.4375,0,0,176,None,5,None,80,None,16,Low,10,None,,,,0,1474116451,,,,,

Apache CSV ist tatsächlich langsam. Der Hauptgrund dafür ist, dass CSV-Dateien nach https://tools.ietf.org/html/rfc4180 auch recht kompliziert sein können. Die können verschiedene Delimiter haben, einen Header oder eben nicht, und sie haben “Quoting Characters”. Wenn in einer CSV-Datei sowas steht wie

123, "This is a string with a comma, and this will break", 456

dann wird es ihn bei einem line.split(",") komplett raushauen.

Wenn man viele Annahmen machen kann, kann man auch selbst schnell was runterhacken. Das hatte ich vor kurzem in https://github.com/javagl/Data/blob/master/data-io-csv/src/main/java/de/javagl/data/io/csv/CsvDataStreams.java gemacht. Aber dieser code wird jetzt nicht mehr verwendet. Stattdessen verwende ich Apache CSV, weil eben genau der o.g. Fall eingetreten ist, und ich eben einen “robusteren” Parser haben wollte. Sowas selbst schreiben wäre ein Krampf.

Das folgende ist aus o.g. Code extrahiert (mit List<String> statt Record). Da die Daten als Stream geliefert werden, kann man leicht filtern und was auch immer machen, und hier lokal hab’ ich damit auch schon auf 18 GB (!) großen CSV-Dateien rumgerödelt, ohne dass die JVM dabei jemals mehr als ein paar MB (!) Speicher belegt hat. Und schnell sollte es auch sein.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class QuickAndSimpleCsv
{
    public static void main(String[] args) throws IOException
    {
        try (InputStream inputStream = new FileInputStream("quickAndSimpleCsv.csv"))
        {
            read(inputStream)
                .map(QuickAndSimpleCsv::createEntry)
                .forEach(System.out::println);
        }
    }
    
    static class Entry
    {
        String name;
        double x;
        double y;
        double z;
        @Override
        public String toString()
        {
            return "Entry [name=" + name + ", x=" + x + ", y=" + y + ", z=" + z
                + "]";
        }
    }

    private static Entry createEntry(List<String> tokens)
    {
        Entry e = new Entry();
        e.name = tokens.get(2);
        e.x = tryParseDouble(tokens.get(3));
        e.y = tryParseDouble(tokens.get(4));
        e.z = tryParseDouble(tokens.get(5));
        return e;
    }
    
    private static double tryParseDouble(String s)
    {
        try
        {
            return Double.parseDouble(s);
        }
        catch (NumberFormatException e)
        {
            return Double.NaN;
        }
    }
    
    
    
    
    //=========================================================================
    
    static Stream<List<String>> read(InputStream inputStream) 
        throws IOException
    {
        char delimiter = ',';
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(inputStream));
        // Ignore header
        br.readLine();
        
        Iterator<List<String>> resultRecordsIterator = 
            new Iterator<List<String>>()
        {
            private List<String> next;
            
            // Initialize the first next record
            {
                prepareNext();
            }
            
            private void prepareNext()
            {
                next = null;
                try
                {
                    String line = br.readLine();
                    if (line != null)
                    {
                        next = split(line, delimiter);
                    }
                }
                catch (IOException e)
                {
                    System.err.println(
                        "IOException while reading stream: " + e.getMessage());
                }
                //System.out.println("Prepared next: "+next);
            }
            
            @Override
            public boolean hasNext()
            {
                return next != null;
            }

            @Override
            public List<String> next()
            {
                if (!hasNext())
                {
                    throw new NoSuchElementException("No more elements");
                }
                List<String> nextResult = next;
                prepareNext();
                return nextResult;
            }
        };
        
        Spliterator<List<String>> spliterator = 
            Spliterators.spliteratorUnknownSize(resultRecordsIterator, 0);
        Stream<List<String>> recordsStream = 
            StreamSupport.stream(spliterator, false);
        Runnable closeHandler = () -> 
        {
            try
            {
                inputStream.close();
            }
            catch (IOException e)
            {
                throw new UncheckedIOException(e);
            }
        };
        Stream<List<String>> closeableRecordsStream = 
            recordsStream.onClose(closeHandler);
        return closeableRecordsStream;
    }
    
    static List<String> split(String s, char delimiter)
    {
        List<String> tokens = new ArrayList<String>();
        int index = 0;
        for (int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            if (c == delimiter)
            {
                tokens.add(s.substring(index, i));
                index = i + 1;
            }
        }
        if (index < s.length())
        {
            tokens.add(s.substring(index, s.length()));
        }
        else 
        {
            char c = s.charAt(s.length()-1);
            if (c == delimiter)
            {
                tokens.add("");
            }
        }
        return tokens;
    }
    

}

Danke. Jetzt muss ich nur noch herausfinden, welches der signifikante Unterschied zwischen den beiden Codes ist. :blush:
Aber das mit der wichtigen „Modularität“ bleibt…

Sind das Daten aus Elite Dangerous? Wo hast die denn her? Kannst die mal verlinken?

Ich würde es mal mit 'nem StreamTokenizer versuchen. Damit spart man sich dieses ganze Object-Casting-In-Out-Boxing-Gedöns.

Ja. Ja, kann ich, aber ich hatte vor eineinhalb Jahren schonmal einen Link zu eddb io gepostet, und dieser wurde kommentarlos gelöscht…

Bitte nur über den Browser downloaden: Link.

Nur mal so gefragt. Exceptions sind ja relativ teuer, Stacktrace kopieren und so. Geht das nicht einfacher?

Wenn ich einen Blick auf Apache Commons StringUtils.isNumeric werfe, dann wird dort über die Character iteriert und über isDigit getestet. Das hört sich erstmals aufwändiger zu implementieren an, sollte aber im Endeffekt dem parseDouble Meilenweit davonlaufen.

http://commons.apache.org/proper/commons-lang/javadocs/api-release/src-html/org/apache/commons/lang3/StringUtils.html#line.7203

@ionutbaiu liest gar nicht, was wir schreiben. - Mit Commons CSV dauert es nicht 7 Minuten, sondern 'ne Viertelstunde, um dasselbe Ergebnis zu erreichen.


Edit: Upps - gar übersehen, dass du das gar nicht meintest. :smiley:

Die Methode macht was komplett anderes als die, die ich gepostet habe. Rauszufinden, ob ein String ein gültiger Java-double-String ist, ist schwierig bis umöglich. Seit langem habe ich die „Challenge“ am Laufen: Erstelle eine RegEx, die genau double oder float matcht. Noch hat sich niemand dran gewagt. (Abgesehen davon, dass die ersten Testfälle natürlich sowas wie -0256234567.e-332 (true) und -0256234567.e-333 (false) wären, wäre die RegEx sicher auch noch langsamer…)

Hier ging es ja nicht nur darum zu prüfen, ob das ein double-String ist, sondern tatsächlich den double-Wert auch rauszubekommen. Den String in Double#parseDouble zu werfen, und schauen, ob’s klappt, ist das einzig sinnvolle. Und die Exception sollte hier ja wirklich eine Ausnahme sein. Man geht schon davon aus, dass das alles „gutmütige“, „normale“ double-Strings sind.

Und solange man Exceptions wirklich nur für Ausnahmen verwendet, ist alles OK. Ansonsten kenne ich zur Performance von Exceptions nur eine ultimative Referenz: The Exceptional Performance of Lil' Exception . Und was ich mit „ultimativ“ meine, weiß jeder, der sich das wirklich komplett durchliest.

Ich habe das mal getan. Hier mal nebenbei Dank an all die Steuerzahler, die meine Zeit damals finanziert haben :smiley:

Insofern hast du recht marco.

Meine Kritik bezog sich auch im Kontext auf den Ursprungspost. Dort wird nämlich über die Exception zuerst geschaut ob Integer, falls Exception ob Long, falls Exception ob Float ansonsten der String zurückgegeben. Also alles kaskadierend.

Und hier dürfte die Exception sehr oft fliegen, also keine Ausnahme darstellen.

Aber in deinem Beispiel marco, dürfte die Exception tatsächlich die Ausnahme darstellen. Sorry, wenn das etwas missverständlich war.

Zudem ist es auch immer die Frage, ob man Anhand der Datenlage auch auf solche Randbedingungen eingehen muss oder nicht. Dort scheinen die Zahlen auch nicht mit Exponenten versehen zu sein.

Joa, das ist natürlich Murx. Was anderes hatte ich in meiner ersten Antwort ja auch nicht gesagt.

(Den „spezifischsten“ Typ einer CSV-Spalte rauszufinden ist aber tatsächlich ziemlich tricky. Vor einiger Zeit hatte ich mal https://github.com/javagl/Data/blob/master/data-type-guessing/src/test/java/de/javagl/data/typeguessing/TypeGuessingTest.java gebastelt, aber das ist sehr vorläufig, und vieeele Fragen sind noch offen…)

Das Problem ist: HashMap<String, Object> m = new HashMap<>();.
Machst Du so.

class Sys {
    long id, edsm_id, updated_at;
    String name;
    float x, y, z, dts;
    ArrayList<Sta> stas = new ArrayList<>();
}


    f.addLine("Parse Systems");
    long counter1 = 0;
    long counter2 = 0;
    try (BufferedReader r = new BufferedReader(new FileReader("a.csv"))) {
        String[] h = r.readLine().split(",");
        String l;
        a: while ((l = r.readLine()) != null) {
            counter1++;
            String[] ar = l.split(",", h.length);
            if (ar[2].charAt(0) == '"' && ar[2].charAt(ar[2].length() - 1) != '"') {
                f.addLine("l = " + l);
                counter2++;
                continue;
            }
            Sys s = new Sys();
            s.x = Float.parseFloat(ar[3]);
            s.y = Float.parseFloat(ar[4]);
            s.z = Float.parseFloat(ar[5]);
            s.dts = distToSol(s);
            if (s.dts > 150) {
                counter2++;
                continue;
            }
            s.id = Long.parseLong(ar[0]);
            //s.edsm_id = Long.parseLong(ar[1]);
            s.updated_at = Long.parseLong(ar[22]);
            s.name = ar[2].charAt(0) == '"' ? ar[2].substring(1, ar[2].length() - 1) : ar[2];
            systems.put(s.id, s);
        }
    } catch (IOException ex) {
        f.addLine(ex.getMessage());
    }
    f.addLine("Counter: " + counter1 + ", " + counter2);
    f.addLine("Systems: " + systems.size());


float distToSol(Sys s) {
    return (float) Math.sqrt(s.x * s.x + s.y * s.y + s.z * s.z);
}

Dauert weniger 30 Sekunden.

Sorry, dieses Thema kann durch AObelix als gelöst betrachtet werden. Und willkommen zurück.

Ein Trick bei solchen Berechnungen ist, nicht mit Distanzen, sondern mit dem Quadrat der Distanzen zu arbeiten, und sich so das Wurzelziehen zu sparen. Aber keine Ahnung, ob das hier viel ausmacht.

Hallo Landei, das müsste ich mit einem Benchmark feststellen; wozu ich aber momentan einfach „nicht den Nerv habe“. Dennoch vielen Dank für deinen Einwand. :woozy_face: