Gibt es eine Möglichkeit, ein Element einer unsortierten Liste in unter O(n) zu finden?

algorithmen

#1

Hab eine csv, und in dieser liegen Systeme mit Namen, aber leider unsortiert. Der gesuchte System-Name kann am Anfang, ende oder mitten drin sein. Gibts da ne Möglichkeit, den Systemnamen zu finden, ohne die komplette csv durchzulaufen, also durchschnittlich *nicht* in O(n) oder n/2? Bei mir dauert das über 1 Min. und es werden nur 0,25 % (Faktor 0,0025) der csv gebraucht. Tipps?

java:

class Sys {
    long id, modified;
    String name;
    float x, y, z;
}

class Model {
    static LinkedHashMap<Long, Sys> systems = new LinkedHashMap<>();
}

abstract class TaskRead implements Runnable {
    abstract String getSystemName();
    abstract float getDeltaToSystem();

    @Override
    public void run() {
        /* ... read Systems from csv ... */
        GUI.println(Model.systems.size());
        Sys deltaSys = null;
        for (Sys s : Model.systems.values()) {
            if (s.name.equals(getSystemName()) || s.name.toLowerCase().equals(getSystemName().toLowerCase())) {
                deltaSys = s;
                GUI.println(s.name);
                break;
            }
        }
        if (deltaSys != null) {
            float x = deltaSys.x, y = deltaSys.y, z = deltaSys.z;
            for (Iterator<Sys> iterator = Model.systems.values().iterator(); iterator.hasNext();) {
                Sys s = iterator.next();
                float d = (x - s.x) * (x - s.x) + (y - s.y) * (y - s.y) + (z - s.z) * (z - s.z);
                if (d > getDeltaToSystem()) {
                    iterator.remove();
                }
            }
        }
        GUI.println(Model.systems.size());
    }
}

java Aufruf:

        new Thread(new TaskRead() {
            @Override
            float getDeltaToSystem() {
                return 30625;
            }

            @Override
            String getSystemName() {
                return "Mokoi";
            }
        }).start();
        GUI.println(Model.systems.size());

#2

Also ohne Sortierung wirst du keinen Algo finden außer Iteration. Wenn du die Liste also unsortiert lassen willst, kannst du nur noch mit Indexlisten über Suchkriterien arbeiten. Dann sortierst du die Indizes, wendest deinen Suchalgo drauf an und hast im Ergebnis dann die Datensatznummer des gesuchten Eintrags. Nannte sich zu C64-Zeiten noch Index-Sequentielle Datenspeicherung.

Die Gute hier erklärt das ganz lieb…


#3

Kurze Antwort: Nein.

Lange Antwort: Neeeeeiiiiinnnnn…

Wenn das sowieso schon in einem Thread läuft, könnte man zwar überlegen, ob man die Dinger in einer Liste speichert, und dann numProcessors threads auf jeweils ca. list.size()/numProcessors+1 loszulassen, aber erstens hast du keine List sondern eine Map (warum auch immer), zweitens würde das an der asymptotischen Laufzeit von O(n) nichts ändern, und drittens würde man, bevor man mit dem geposteten Code irgendwas macht, den erstmal vernünftig schreiben.


#4

RAF und Zufall vielleicht? => Laufzeit nur noch n/2?
Ich kam noch nicht dazu, das über Speicherung mir anzugucken.

Edit: Was hättest du konkret am Code auszusetzen, was wäre falsch? Danke.


#5

O(n/2)=O(n).


#6

Ja ihr habt recht. :wink: Danke sehr allen.

[ Und Spacerat, das ist eigentlich gut erklärt in dem Vid. ]


#7

*seufz*

  • Nie einen static Zustand verwenden
  • Gegen’s interface programmieren, d.h. nicht LinkedHashMap<Long, Sys> systems = ... sondern Map<Long, Sys> systems = ...
  • Ein break ist oft ein Warnsignal. Lager’ die Suche in eine Methode aus.
  • Es gibt String#equalsIgnoreCase
  • Das ganze x,y,z-Gefrickel durch ein Sys#distanceTo(Sys other) oder eine “Distanzfunktion” rausziehen
  • Warum schreib’ ich das überhaupt? Morgen kommt eine neue Frage, mit ähnlichem Murxcode…

#8

Und wie ohne static?


#9

Indem man das Model einmal instanziert und nicht in einem statischen Kontext vorhält. Hier wäre also angebracht beim Start des Programms “new Model()” zu machen und dieses dann über geeignete Maßnahmen (mangels DI, via Referenzen) weitergeben.

Viel “schlimmer” als das finde ich den Verstoß gegen das Geheimnisprinzip. Und überhaupt die mangelnde Angabe der Zugriffmodifikatoren. Glaube nicht, dass das hier absichtlich passiert ist.


#10

Doch. :wink:


Das mit ohne static ist etwas dran. Werde ich dran denken. Danke.


#11

Kannst ja bei Gelegenheit näher erläutern ;D


#12

Mal noch eine Frage. Oben hatte ich eine Klasse für Systeme als Struktur. Das dauerte (das lesen der Systeme) etwa 1 Min.

Jetzt nutze ich mal testweise eine Datenbank in-memory…

eine Tabelle erstellen:

        stmt.execute("create table if not exists sys (\n"
                + "  id long primary key,\n"
                + "  modified long,\n"
                + "  x float,\n"
                + "  y float,\n"
                + "  z float,\n"
                + "  name varchar(255))");

daten da rein:

stmt.execute("insert or ignore into sys values (" + id + "," + modified + "," + x + "," + y + "," + z + ",'" + name + "')");

Bis dahin funktionierts, aber s dauert etwa 5 Min. jetzt, und etwa 15 Mio. Rows:

println(stmt.executeQuery("select count(*) from sys").getLong(1));

Jetzt möchte ich alle Rows in einer query entfernen, die zu getSystemName() mehr als getDeltaToSystem() entfernt liegen:

stmt.executeQuery("delete from sys s1 where exists ( select * from sys s2 where s2.name = '" + getSystemName() + "' and (s1.x - s2.x) * (s1.x - s2.x) + (s1.y - s2.y) * (s1.y - s2.y) + (s1.z - s2.z) * (s1.z - s2.z) > " + getDeltaToSystem() + " )");

Funktioniert aber nicht (syntax error near s1 or…), wer weiß wieso?

Und dann gleich zweite Frage… Später soll ja so ein Art Rundreise berechnet werden - wäre dabei Datenbank überhaupt sinnvoll?


#13

Ne


#14

das lesen der Systeme dauert 4mal so lange… aber das schrieb ich schon mal.

Ok, kein syntax error:

stmt.executeQuery("delete from sys where exists ( select * from sys s2 where s2.name = '" + getSystemName() + "' and (sys.x - s2.x) * (sys.x - s2.x) + (sys.y - s2.y) * (sys.y - s2.y) + (sys.z - s2.z) * (sys.z - s2.z) > " + getDeltaToSystem() + " )");

Allerdings hält es jetzt nicht mehr an. liegt an dem subquery/subselect/(“inner”) “join”. :frowning:

Abgesehen davon… … … ist es überhaupt ‘richtig’?


#15

Du erstellt mit deiner Query eine Potenzmenge sys x sys. Daher dauert das etwas länger.

Ich würde so vorgehen: Das System finden, um welches es geht. (Das machst du ja per Name)

Dann die Werte des Referenz-Systems als Skalare in der Query angeben.

Gruß,

Martin


#16

@Landei : Gibt es eine Möglichkeit mit Streams/Lambdas/functional programming ohne immensen Aufwand in “einer Zeile” aus einer DS alle Systeme zu entfernen, die zu einem System mit Namen x in der DS weiter als y entfernt liegen, ohne das System mit Namen x *“vorher”* separat aus der DS herauszufischen (und ohne das kartesische Produkt zu bestimmen)?

@Marcinek : Hab ich verstanden. Wenn ich es richtig verstanden hab, dann wird zuerst ein Join(*) mit 15 Mio.^2 bestimmt mit 225 Billionen, und dass dann nicht mehr “anhält”.

(*): Relationenalgebra: R x S, SQL: SELECT * FROM R, S;.


#17

Ach, fck, die nächstkleinere Schranke wäre O(1). Wenn nicht, belehrt mich eines Besseren. Und es kann keine Row gefunden werden, wenigstens alle Rows zu durchlaufen, ohne weitere Informationen dazu vorher zu bestimmen.

:thinking: Der Satz war grausig, aber ihr wisst, was ich meine. Wenn ein Kartenspieler 100 Karten hat (verdeckt), und man darf GENAU EINE Karte ziehen, dann kann man nicht genau jene ziehen, welche man sucht…

(Also nicht ohne Telepathie…)


#18

Zwischen O(n) und O(1) liegen noch unendlich viele weitere Schranken. Gängig beispielsweise O(log(n)), diese Komplexitätsklasse gilt z. B. für die Suche in einer sortierten Liste.


#19

Schranke für dich != Komplexitätsklasse, oder?

I-wie verwirrt mich das etwas, aber z. B. durch log log log … log log log n gibt es unendlich viele weitere Schranken zwischen o n und o 1 oder?

Aber auch o n^3 ist eine andere Schranke/Komplexitätsklasse als o n^4 oder?

Aber O(n/2) = O(n) ?? Da haste dich vertan… o n^2/2 = o n^2 ja…

Edit: Ich hab mich vertut. :smile: (Wollte schon den engl. Wikipedia Artikel in zweifel ziehen. :wink: )