Effizienter Suchalgorithmus gesucht

[banshee]

Hallo,

hat jemand eine Idee, wie man folgendes möglichst effizient umsetzen kann:

1) Ich habe einen JTable, der ganz normal mit Daten gefüllt ist.
2) Ich habe eine Liste, wo Filterausdrücke drinstehen.

Beispiel: Der Header des JTables ist so aufgebaut: A B1 ... BN C D1 ... DN und Filterausdrücke sind dann z.B. sowas wie A > 10, B1 like "Hallo", C between 0 and 10 usw.

Problem Nr. 1) Da die Form des Headers immer so aussieht, macht es da Sinn, die Liste mit den Filterausdrücken vorzusortieren?

Problem Nr. 2) Wie durchlaufe ich den table dann? Im Prinzip muss ich dann ja jede Zelle einmal betrachten. Ich hatte mir das so gedacht, den filter einfach in ein String-Array zu splitten, dann mit dem Header der betrachteten Spalte zu verleichen und dann das Filterkriterium zu überprüfen.

Problem Nr. 3) Wie kann ich den Operator als String möglichst effizient in einen Ausdruck parsen?

 

[banshee]

Mittlerweile bin ich zu dem Schluss gekommen, dass folgendes am besten sein müsste:

Man sucht erst ein Paar (Spaltentitel aus dem Header, Spaltentitel aus einem Filter), überprüft anschließend die Bedingung, markiert alle Zeilen der Tabelle, für die die Bedingung zutrifft. Dann macht man mit dem nächsten Filter weiter und muss nur noch die markierten Zeilen untersuchen.

 

[Paddelpirat]

Hi,

wie füllst du denn überhaupt deine JTable? Sind die Daten irgendwie mit einer Datenbank verknüpft? Wenn du die Daten z.B. aus MySQL laden würdest, bräuchtest du ja nur noch geeignete SQL-Statements um die passenden Datensätze zu suchen/rauszufiltern.

Edit: Ist aber auch eine Frage des Programms, ob sich obige Möglichkeit anbietet. Wenn es sich um ein Client-Server Programm handelt könnte es wohl eher problematisch sein die Datensätze immer wieder aus der Datenbank auszulesen. Dann wäre es wohl sinnvoll die Filterkriterien nach und nach abzuklappern, wie du es oben gepostet hast.

 

[banshee]

Sie werden aus einer Datei eingelesen. Ich denke auch, dass das die beste oder zumindest eine annehmbare Lösung ist.

Ich bin nur noch auf der Suche, den Operator effizient zu parsen, d.h. von einem String möglichst einfach zu einem Ausdruck zu kommen, um sich die vielen if's zu sparen:

if(operator == ">")
  tableZelle > operand;
else if(operator == "<"
  tableZelle < operand;
usw.

 

[Paddelpirat]

Sie werden aus einer Datei eingelesen. Ich denke auch, dass das die beste oder zumindest eine annehmbare Lösung ist.

Ich bin nur noch auf der Suche, den Operator effizient zu parsen, d.h. von einem String möglichst einfach zu einem Ausdruck zu kommen, um sich die vielen if's zu sparen:

Hmm ich weiß ja nicht wie umfangreich die Daten sind, aber evtl. solltest du doch mal über eine Datenbank nachdenken, weil dir diese das parsen zu einem großen Teil abnehmen kann. Du müsstest dann deinen Filter-String in ein SQL-Statement umwandeln und die Datenbank erledigt den Rest.

Ansonsten bleibt dir wahrscheinlich nicht viel anderes übrig als einige if-else-Abfragen abzuarbeiten.

 

[JohannisderKaeufer]

Das Project apche commons collection definiert eine kleine Predicate-Api.

Predicate (Commons Collections 3.2.1 API)

Ziel ist es ein Predicate zu erstellen, bzw. zu konfigurieren.

Dem Predicat kann dann ein Objekt übergeben werden das evaluiert wird was dann true oder false zurückliefert.

Damit lassen sich dann recht gut Filter erstellen, die auch sehr komplex sein können. Im package functor bieten sich bereits vorgefertigte Geschichten, Wie das AllPredicate, ect.

class BiggerPredicate implements Predicate{ 
  private Object operand
  public BiggerPredicate(Object operand){
  this.operand = operand; 
  }
  public boolean evaluate(Object o){
    return operand < o
  }
}

class FooPredicate implements Predicate{ 
  private Object operator, operand
  public BiggerPredicate(Object operand, Object operator){
  this.operand = operand; 
  this.operator = operator;
  }
  public boolean evaluate(Object o){
    Predicate p;
    if(operator == ">")
      predicate = new BiggerOperator(operand);
   if(operator == "<")
     predicate = new LowerOperator(operand);
  return p.evaluate(o);
  }
}

 

[Loki]

operator == ">"

Ich kann mir nicht vorstellen, wie das funktionieren soll.

 

[banshee]

Eine Frage noch, ob sich der Aufwand für folgende Optimierung lohnt:

Zuerst durchlaufe ich den Header, schaue nach, welche Filterbedingung zu welchem Spaltenindex gehört und speichere dann das Paar (Index, Filterbedingung) in einer Collection. Diese wird anschließend aufsteigend nach den Keys sortiert und dadurch kann ich mir dann - vorausgesetzt es gibt nicht für jede Spalte eine Bedingung - zahlreiche Zellenvergleiche sparen.

Die Frage ist nur, ob der Aufwand für das Collection-Gedöns nicht größer ist, als die überflüssigen Bedingungen zu testen. Ich weiß auch nicht, welche Collection man da nimmt. Offensichtlich muss es ja eine Art Map sein, aber die erlauben ja alle keine doppelten keys und diese dann noch mit verketteten Listen zu verschachteln...ich denke da wird mir der Aufwand dann doch zu groß.

 

[Marco13]

Collection die dann sortiert wird?.... Schau dir mal TreeMap an, die ist von vornherien sortiert (ist aber Uhrzeitbedingt nur ins Blaue geraten, weiß nicht ob das für dich passt...)

 

[banshee]

Daran hab ich auch als erstes gedacht, aber wenn ich dann zwei values unter dem gleichen key speichern will (was ja durchaus vorkommen kann, wenn ich zwei Filter auf die selbe Spalte anwende) wird der erste überschrieben.

 

[Landei]

Nö, mach eine TreeMap, die auf eine Liste von Filtern zeigt. Oder schau unter google-collections, die haben sicher die richtige Datenstruktur für dich dabei...