Suchaufwand

[Christoph Zurnieden]

Hi,

na, da habe ich alles schön aufgeschrieben und muß hier gerade vor dem Abschicken feststellen: ich bin einfach zu langsam! ;-)
wahsaga hat's zwar schon sehr schön erklärt, aber bevor ich hier für den Orkus sprich /dev/null schreibe schick ich's trotzdem ab.

Ich habe folgende Daten die ich in einem Array (Javascript) speichere:

Domain                       Wildcards          Eigenschaft X
-------                      ---------          -------------
domain.com                   True               B
mail.domain.com              False              C
scanner.mail.domain.com      True               A
anderedomain.de              False              A

Ich gehe mal von folgender Arraystruktur aus (ist aber auch nur für die Details wichtig):

  
[["domain.com"],[true],["B"]],  
[["mail.domain.com"],[false],["C"]],  
...  

Jetzt schreibe ich eine Funktion, welche anhand der Domain die ich übergebe, die Entsprechende Eigenschaft zurückgeben soll, etwa in der Form:

function GetEigenschaftX(domain) {
  return EigenschaftX;
}

Wird nun eine Domain übergeben, die nicht im Array ist (z.B. web.domain.com), jedoch irgend ein übergeordneter Level der Domain die Eigenschaft Wildcard "True" besitzt, dann soll die Eigenschaft X dieser Domain zurückgegeben werden (z.B. "B"). Für die Domain "mail.domain.com" soll aber obwohl "domain.com" die Eigenschaft Wildcards "True" besitzt, der Wert "D"

(Das soll wohl "C" heißen?)

zurückgegeben werden. Wird gar keine Entsprechung gefunden, dann wird immer "E" zurückgegeben.

Dann schreib's Dir doch mal in Pseudocode auf (Variableninhalt der Einfachheit halber aufgelöst):

if(myArray.find("mail.domain.com"))
  // der vollständige String ist im Array
  return myArray[2];
else{
  splitArray = splitAtPointsExceptTheLastOne("web.domain.com");
  for(i = splitArray.length()-1;i>=0;i--){
    var part = makeStringFromArrayItoArrayEnd(i);
    if(myArray.find(part) && myArray.find(part)[1]==true){
      // setzt voraus, das keine Doubletten vorhanden sind
      return myArray.find(part)[2];
    }
  }
}
return "E";

Naja, viel Pseudo ist jetzt nicht mehr im Pseudocode ;-)

Die Frage ist nun wie ich die Funktion GetEigenschaftX() am besten realisiere. Insbesondere spielt die Performance eine wichtige Rolle (Das Array kann z.B. auch die Länge von 100 haben).

Bei gerade mal 100 Stück? Soll das etwa auf 'nem Handy laufen?

Ich hab mir überlegt ob es mit Javascript möglich ist und es sich lohnt eine Baumstruktur aufzubauen?

Es ist möglich, klar.
Da Du die Domainnamen von hinten durchsuchen mußt würde sich ein Suffixtree eignen (Javascriptimplementation gibt's im Netz. Da mußt Du aber Google fragen, ich habe leider kein Bookmark)

Wie durchsuche ich am schnellsten?

Solltest Du nicht erstmal etwas funktionierendes haben, bevor Du optimierst? Wenn es dann überhaupt noch nötig ist?

Wenn Du magst, kannst Du das Array nach den Domainnamen sortieren und dann darauf eine binäre Suche anwenden. (Die ich hier jetzt aber nicht nochmal poste, such' bitte im hiesigem Archiv danach.) Aber ob das bei 100 Stück viel bringt wage ich ernsthaft zu bezweifeln.

so short

Christoph Zurnieden