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());
}
}
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.
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.
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.
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:
@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)?
@martin123 : 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;.
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.
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…
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.
Danke sehr allen.
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…
(Wollte schon den engl. Wikipedia Artikel in zweifel ziehen.