Suchaufwand

[Marco]

Hallo

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

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" zurückgegeben werden. Wird gar keine Entsprechung gefunden, dann wird immer "E" zurückgegeben.

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).

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

Wie würdet ihr das realisieren?

Gruss Marco

[Gunnar Bittersmann]

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

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").

Marco,
Das überdenk nochmal genauer. Für foo.scanner.mail.domain.com sind sowohl scanner.mail.domain.com als auch domain.com übergeordnet mit Wildcard="True". Willst du es dem Zufall überlassen, ob A oder B zurückgegeben wird?

(Das Array kann z.B. auch die Länge von 100 haben).
Ich hab mir überlegt ob es mit Javascript möglich ist

Du willst also die ganze Liste zum Client übertragen und dort auswerten? Mal von evtl. nicht vorhandenem JavaScript abgesehen, wäre eine serverseitige Lösung nicht sinnvoller?

Live long and prosper,
Gunnar

[wahsaga]

hi,

Das überdenk nochmal genauer. Für foo.scanner.mail.domain.com sind sowohl scanner.mail.domain.com als auch domain.com übergeordnet mit Wildcard="True". Willst du es dem Zufall überlassen, ob A oder B zurückgegeben wird?

dass in so einem falle der "treffer" scanner.mail.domain.com höhere priorität hat, weil er "näher dran" (bzw. "genauer") ist als mail.domain.com, würde ich mal annehmen.

aber genau kann das natürlich nur Marco selber definieren.

gruß,
wahsaga

[Marco]

hi,

dass in so einem falle der "treffer" scanner.mail.domain.com höhere priorität hat, weil er "näher dran" (bzw. "genauer") ist als mail.domain.com, würde ich mal annehmen.

Genau, weils eben "genauer" ist:-)

Gruss Marco

[Marco]

Hallo

Du willst also die ganze Liste zum Client übertragen und dort auswerten? Mal von evtl. nicht vorhandenem JavaScript abgesehen, wäre eine serverseitige Lösung nicht sinnvoller?

Javascript ist auf allen Clients vorhanden. Serverseitige Lösung ist leider nicht möglich.

Gruss Marco

[wahsaga]

hi,

Für die Domain "mail.domain.com" soll aber obwohl "domain.com" die Eigenschaft Wildcards "True" besitzt, der Wert "D" zurückgegeben werden.

das verstehe ich nicht - in deiner beispiel-tabelle steht doch bei mail.domain.com ein _C_? tippfehler?

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

binärer suchbaum mit alphabetischer ordnung ...?
lohnt sich m.E. für so ein szenario nicht.

Wie würdet ihr das realisieren?

mein erster gedanke: mit einem mehrdimensionalen assoziativen array.

die "wertetabelle"
domain.com                   True               B
mail.domain.com              False              C
scanner.mail.domain.com      True               A
anderedomain.de              False              A

wird umgesetzt als:

(werte["com"]["flag"] = false;)
werte["com"]["domain"]["flag"] = true;
werte["com"]["domain"]["eigenschaft"] = "B";
werte["com"]["domain"]["mail"]["flag"] = false;
werte["com"]["domain"]["mail"]["eigenschaft"] = "C";
werte["com"]["domain"]["mail"]["scanner"]["flag"] = false;
werte["com"]["domain"]["mail"]["scanner"]["eigenschaft"] = "C";
(werte["de"]["flag"] = false;)
werte["de"]["anderedomain"]["flag"] = false;
werte["de"]["anderedomain"]["eigenschaft"] = "A";

die ebenen in klammern nur für den fall, dass du sie beim durchgehen brauchst. wenn du jeweils erst ab der zweiten ebene an zu suchen fangen willst, kannst du sie ggf. weglassen.)

dann den zu suchenden term mit split() am punkt zerlegen, und von hinten durchgehen:

mail.domain.com -> "com", "domain", "mail"
existiert werte["com"]? ja
existiert werte["com"]["domain"]? ja
existiert werte["com"]["domain"]["mail"]? ja -> eigenschaft hat dort den wert "C"

gibtsnich.domain.com -> "com", "domain", "gibtsnich"
existiert werte["com"]? ja
existiert werte["com"]["domain"]? ja
existiert werte["com"]["domain"]["gibtsnich"]? nein
hat werte["com"]["domain"]["flag"] den wert true? ja
-> wert für gibtsnich.domain.com ist werte["com"]["domain"]["eigenschaft"] = "B"

auchnich.anderedomain.de -> "de", "anderedomain", "auchnich"
existiert werte["de"]? ja
existiert werte["de"]["anderedomain"]? ja
existiert werte["de"]["anderedomain"]["auchnich"]? nein
hat werte["de"]["anderedomain"]["flag"] den wert true? nein
(hat werte["de"]["flag"] den wert true? nein)
-> es wird "E" zurückgegeben

am einfachsten zu machen, wenn du dir, sobald du auf einer ebene einen treffer gefunden hast, dessen wildcard-flag true ist, immer dessen wert schon mal als ergebnis merkst - und ggf. in der nächsten ebene überschreibst, wenn dort auch noch ein treffer gefunden werden sollte.
(und auf "nullter" ebene natürlich mit ergebnis ="E" starten, als fallback für die fälle, für die es überhaupt keinen treffer gibt.)

gruß,
wahsaga

[Marco]

Hallo Wahsaga

Deine Idee die Werte so abzuspeichern fand ich ja ganz gut:

(werte["com"]["flag"] = false;)
werte["com"]["domain"]["flag"] = true;
werte["com"]["domain"]["eigenschaft"] = "B";
werte["com"]["domain"]["mail"]["flag"] = false;
werte["com"]["domain"]["mail"]["eigenschaft"] = "C";
werte["com"]["domain"]["mail"]["scanner"]["flag"] = false;
werte["com"]["domain"]["mail"]["scanner"]["eigenschaft"] = "C";
(werte["de"]["flag"] = false;)
werte["de"]["anderedomain"]["flag"] = false;
werte["de"]["anderedomain"]["eigenschaft"] = "A";

Problematisch find ich die Implementierung. Wie kann ich prüfen ob auch eine Domain existiert?

var domains = new Array();
domains["com"]["domain"]["mail"]["EIGENSCHAFT"] = "";

function FindDomain("mail.domain.com") {
   // IMPLEMENTIERUNG?
}

[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

[Marco]

Hallo

Vielen Dank für den Post!

Wie durchsuche ich am schnellsten?

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

Vielleicht. Problem ist eben, dass in den meisten Fällen, "E" zurückgegeben werden soll, d.h. es wird keine Übereinstimmung geben. Es sollten also möglichst wenige Vergleiche gemacht werden, d.h. bereits ein erster Vergleich sollte wenn möglich entscheiden ob weitere Vergleiche überhaupt nötig sind.

Gruss Marco

[Christoph Zurnieden]

Hi,

Wie durchsuche ich am schnellsten?

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

Vielleicht.

Das war ja eigentlich eine rhetorische Frage ;-)

Problem ist eben, dass in den meisten Fällen, "E" zurückgegeben werden soll,

Ist nicht erstmal das Problem, das Du ein Skript benötigst, das die Funktion erfüllt? Oder hast Du das schon?

d.h. es wird keine Übereinstimmung geben. Es sollten also möglichst wenige Vergleiche gemacht werden, d.h. bereits ein erster Vergleich sollte wenn möglich entscheiden ob weitere Vergleiche überhaupt nötig sind.

Du kannst nichts optimieren, das nicht existiert. Obwohl manch einer sagen würde, das aus dem selbem Grund eine Optimierung nicht nötig ist, denn etwas nicht existierendes ist schon optimal, da es genau Null Schritte benötigt.

Aber Scherz beiseite: im Vornherein kannst Du auch optimieren und zwar durch Sortieren und Entfernen der Redundanzen.
Nach einigen der anderen Posts bin ich mir nicht mehr ganz so sicher, ob ich Dein Problem korrekt verstanden habe. Statt lästig zu werden und nachzufragen hier einfach mal noch ein Versuch:
Sortierung der umgedrehten Strings und Suche nach dem "längstem gemeinsamem Substring von Anfang an".

"gro.elpmaxe"
"moc.elpmaxe"
"moc.elpmaxe.liam"
"moc.elpmaxe.liam.rennacs"

"Längster gemeinsamem Substring von Anfang an" ist bei dem Beispiel oben "moc.elpmaxe".

Die Suche nach dem vollständigem String durch binäre Suche ist in O(log(n)) durchzuführen.
Die Suche nach dem "längstem gemeinsamem Substring von Anfang an" ist Average Case O(log(n)). (Aufgrund der Sortierung ist Best Case O(1) wenn schon der zweite Eintrag im erstem Buchstaben unterschiedlich ist. Wenn man in meinem Beispiel die beiden ersten Einträge gesondert nimmt ist das so ein Fall. Im schlimmsten Fall muß die ganze Liste abgeklappert werden. Nein, das stimmt nicht ganz, oder? Die ganze Liste muß ja dank der Sortierung und der Struktur der Domainnamen nie vollständig abgeklappert werden?)
Dazu kommen noch die einzelnen Stringvergleiche, die ohne Optimierung in O(n) ablaufen. (aber selbst mit kaum besser werden)

Insgesamt sollte Dein Algorithmus also flott ablaufen können, ich würde mir da keine großen Sorgen machen.

so short

Christoph Zurnieden