Autocomplete und Bitoperatoren - Experte gesucht

[Jense]

Guten Abend allerseits,
heute mal eine Frage an die wahren Insider - folgende Aufgabenstellung:
Grundsätzlich geht es erstmal um eine Autocomplete-Version. Soll wie immer kurz und kanckig sein. Habe im netz auch was nettes gefunden:

function binSuche(elem)
{
   var links = -1;
       var rechts = this.length;
       var mitte;

while(rechts - links > 1)
   {
      mitte = (links + rechts) >>> 1;
      if(this[mitte] < elem)
         links = mitte;
      else
         rechts = mitte;
   }

if(this[rechts] != elem)
      return -(rechts + 1);

return rechts;
}

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe

Tolle Sache! Gibt bei nicht vorhandenem Element die Stelle an der es eingefügt werden muss als negative Zahl an, wobei bei 1 angefangen wird zu zählen. Ist das Element dagegen in der Menge vorhanden, dann wird bei Null angefangen zu zählen und die positive Zahl gibt die entsprechende Stelle im Feld an. (Nur der vollständigkeithalber: das Feld muss bereits vollständig vorsortiert sein, denn es geht hier nur um das Einsortieren...) Soweit sogut, funktioniert super, und ich vermute ohne das ich es getestet habe, dass es auch relativ schnell geht, da Bit-Operatoren benutzt werden. Jetzt kommen wir zu meinem Problem: Ich habe im Prinzip keine Ahnung wie und warum die Prozedur funktioniert was mich in diesem Fall auch nur deshalb stört da meine Anforderungen etwas abweichen, ich aber das Ding nicht anpassen kann. Wie gesagt keine Ahnung welche Einsen und Nullen sich da wo, wie und warum verschieben. Bin ja selber eine Null...
Ich habe ein zweidimensionales Feld. Es gibt immer Paare von ID's und dazugehörigen Bezeichnern, also z.B.: [[0,"a"],[1,"b"],...]
Also nichts ungewöhnliches aber eben anders als hier ursprünglich vorgesehen. Sortiert werden soll übrigens nach dem Bezeichner (wie gesagt: autocomplete), aber ich brauch eben auch die Nummer.
Jetzt bin ich gespannt wer von euch sich als echter Spezi outet und mir das Ding hinbiegt. Tausend Dank schonmal vorab!!!

Jense

[Struppi]

Grundsätzlich geht es erstmal um eine Autocomplete-Version. Soll wie immer kurz und kanckig sein. Habe im netz auch was nettes gefunden:

Was ist Autocomplete?

function binSuche(elem)
{
   var links = -1;
       var rechts = this.length;

Was ist this hier?
Du hast nirgends ein Objekt, dann ist this == window.

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe

Fehler: [["a"], ["b"], ["d"]].binSuche is not a function
Quelldatei: test.html
Zeile: 54

Vielleicht sagst du uns noch um was es konkret geht?

Struppi.

[Cheatah]

Hi,

ich bin gerade auf dem Sprung, kann mich um das eigentliche Problem gerade mal nicht kümmern, aber:

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe
Fehler: [["a"], ["b"], ["d"]].binSuche is not a function

Array.prototype.binSuche = binSuche;

Danach sollte es gehen.

Cheatah

[Struppi]

ich bin gerade auf dem Sprung, kann mich um das eigentliche Problem gerade mal nicht kümmern, aber:

Ich auch ;-)

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe
Fehler: [["a"], ["b"], ["d"]].binSuche is not a function

Array.prototype.binSuche = binSuche;

Danach sollte es gehen.

Mir ist das klar, aber warum kriegen wir nur ein kastriertes Beispiel?
Und warum schreib man nicht gleich:

Array.prototype.binSuche = fucntion() {  
}  

Wie auch immer, wenn es nur um die Bitoperatoren geht, hier im Forum müßte ein aktiver Thread sein, in dem darauf hingewiesen wurde, dass diese unter JS nicht schneller sind als normale Rechneoperationen - hab ich aber noch nie getestet.

Struppi.

[steckl]

Hi,

Wie auch immer, wenn es nur um die Bitoperatoren geht, hier im Forum müßte ein aktiver Thread sein, in dem darauf hingewiesen wurde, dass diese unter JS nicht schneller sind als normale Rechneoperationen.

Hier ist er.

mfG,
steckl

[Jense]

Hallo nochmal,

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe
Fehler: [["a"], ["b"], ["d"]].binSuche is not a function

Array.prototype.binSuche = binSuche;

Danach sollte es gehen.

Ein Experte!!! OK ich habe das Array.prototype. weggenommen. Nicht zum Spass, sondern weil mein Skript plötzlich an einer ganz anderen Stelle nicht mehr lief als ich die Version mit Array.prototype. eingefügt habe (ohne das ich die Funktion schon benutzt hätte!?!). Da ich wie gesagt von dieser Programmierebene keinen blassen schimmer habe, bin ich nach der trial and error methode vorgegangen. Bei mir funktioniert es so auch. Keine Fehler, auch der Rest des Scriptes läuft wie zuvor reibungslos). Werde jetzt aber nochmal ein bisschen rumprobieren...

Mir ist das klar, aber warum kriegen wir nur ein kastriertes Beispiel?

Das Beispiel ist nicht kastriert sondern entspricht genau meinen Vorgaben und Ansprüchen irgendwelches drumherum würde mein Anliegen nur (noch?) unverständlicher machen

Und warum schreib man nicht gleich:

Array.prototype.binSuche = fucntion() {

}

>   
> Wie auch immer, wenn es nur um die Bitoperatoren geht, hier im Forum müßte ein aktiver Thread sein, in dem darauf hingewiesen wurde, dass diese unter JS nicht schneller sind als normale Rechneoperationen - hab ich aber noch nie getestet.  
>   

Wie gesagt ich auch nicht...es ist aber auch einfach eine elegante Methode - da wenig Code, deshalb würde ich die Funktion gerne nutzen - abgeändert natürlich.  
Vielleicht könnt Ihr euch die Tage darüber nochmal auslassen, denn ich glaube Ihr habt das grundsätzlich drauf...  
  
Gruss Jense

[Jense]

Nabend Struppi,

Was ist Autocomplete?

'AutoVervollständigen' heisst die Option z.B. im IE - dass Du danach fragst wundert mich!
Es ist dieselbe Funktion die man von 'zu Hause' kennt, wobei ja eigentlich nicht automatisch vervollständigt wird (gibt es ja auch) sondern die Liste mit bereits mal eingegebenen oder vorhandenen Daten nur entsprechend mitläuft, bzw. eingegrenzt wird.

function binSuche(elem)
{
   var links = -1;
       var rechts = this.length;

Was ist this hier?

Das war doch meine Frage :)

Du hast nirgends ein Objekt, dann ist this == window.

Wo steht das denn?

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe

Fehler: [["a"], ["b"], ["d"]].binSuche is not a function
Quelldatei: test.html
Zeile: 54

Also bei mir funktioniert es tadellos...

Vielleicht sagst du uns noch um was es konkret geht?

Konkret nochmal anders formuliert: Ich habe ein zweidimensionales Feld wie beschrieben mit Paaren von ID und Bezeichnern. Jetzt brauche ich eine Funktion die mir die die Stelle des Arrays (indem die Einträge alphabetisch nach den Bezeichnern vorsortiert sind) angibt wo eine beliebige Eingabe einsortiert werden müsste, sofern diese noch nicht im array vorhanden ist, bzw an welcher Stelle des arrays die Eingabe schon existiert. Wie gesagt sortiert und eingefügt wird alphabetisch nach den Bezeichnern. Die ID's müssten halt mitsortiert werden. Ich hoffe es ist jetzt etwas klarer geworden. Wenn nicht... bitte fragen.

Gruss Jense

[Struppi]

Was ist Autocomplete?

'AutoVervollständigen' heisst die Option z.B. im IE - dass Du danach fragst wundert mich!

Ich weiß was eine Autocomplete Funktion ist, aber was zeigst du uns da?

function binSuche(elem)
{
   var links = -1;
       var rechts = this.length;

Was ist this hier?
Das war doch meine Frage :)

Ok, so wie du es geschrieben hast ist this = window, vermutlich nicht das was du willst.

Du hast nirgends ein Objekt, dann ist this == window.
Wo steht das denn?

Das ist so, this ist immer der Kontext  in dem eine Funktion aufgerufen wird und da hier kein Objekt existiert ist this gleich window

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe

Fehler: [["a"], ["b"], ["d"]].binSuche is not a function
Quelldatei: test.html
Zeile: 54

Also bei mir funktioniert es tadellos...

Dann zeigst du uns nicht alles.

Vielleicht sagst du uns noch um was es konkret geht?

Konkret nochmal anders formuliert: Ich habe ein zweidimensionales Feld wie beschrieben mit Paaren von ID und Bezeichnern. Jetzt brauche ich eine Funktion die mir die die Stelle des Arrays (indem die Einträge alphabetisch nach den Bezeichnern vorsortiert sind) angibt wo eine beliebige Eingabe einsortiert werden müsste, sofern diese noch nicht im array vorhanden ist, bzw an welcher Stelle des arrays die Eingabe schon existiert. Wie gesagt sortiert und eingefügt wird alphabetisch nach den Bezeichnern. Die ID's müssten halt mitsortiert werden. Ich hoffe es ist jetzt etwas klarer geworden. Wenn nicht... bitte fragen.

Das klingt so trivial, dass ich nicht vermute das ich verstanden habe worum es geht.

for(var i = 0; i < array.length; i++ ){  
if( array[i] > eintrag ) alert('hier:' + i);  
}  

Struppi.

[Jense]

alert([["a"],["b"],["d"]].binSuche("c"));  // Testausgabe

Fehler: [["a"], ["b"], ["d"]].binSuche is not a function
Quelldatei: test.html
Zeile: 54

Also bei mir funktioniert es tadellos...

Dann zeigst du uns nicht alles.

doch, klar die script tags oder wie die heissen hab ich weggelasen - die Frage läuft ja unter js....

Das klingt so trivial, dass ich nicht vermute das ich verstanden habe worum es geht.

trivial - kann man so sehen. Es ist halt grundsätzlich ein Einfügeproblem in eine bereits sortierte Menge

for(var i = 0; i < array.length; i++ ){

if( array[i] > eintrag ) alert('hier:' + i);
}

>   

Das ist natürlich auch eine Lösung - also Du weisst um was es geht!  
Ich möchte allerdings die sogenannte 'Binäre Suche' in einer Funktion umgesetzt haben, da diese bei grösseren Feldern klare Performancevorteile hat.  
  
Jense  

[molily]

Hallo,

Sortieren kannst du so einen Array mit einer eigenen Vergleichsfunktion:

arr.sort(function (a, b) {
  if (a[1] < b[1])
    return -1;
  if (a[1] > b[1])
    return 1;
  return 0;
});

Sinniger wäre es, dass die Arrayelemente Objekte sind:
[ { id : "...", bezeichner : "..." }, ... ]

Dann kannst du statt a[0] a.id und statt a[1] a.bezeichner schreiben. Dementsprechend:

arr.sort(function (a, b) {
  if (a.bezeichner < b.bezeichner)
    return -1;
  if (a.bezeichner > b.bezeichner)
    return 1;
  return 0;
});

Wenn du jetzt eine Binäre Suche über diesen Array mit Objects machen willst, schreibst du die Funktion entsprechend um. Der Zugriff auf das maßgebende Element verläuft nicht über this[index], sondern über this[index].bezeichner. Ist eigentlich simpel.

http://molily.de/temp/binaere-suche.html

Aber was hat das Ganze konkret mit AutoComplete zu tun? AutoComplete verstehe ich so, dass man einen Teil eines Begriffes eingibt und automatisch alle zuvor eingegebenen Begriffe angezeigt werden, die mit diesem Teil beginnen.
Was hast du eigentlich genau vor? Mir kommt dieses Konstrukt dermaßen umständlich vor, dass es sicher eine einfachere Lösung gibt. Was genau willst du? Willst du in den Array etwas einsortieren (warum?) oder einfach schauen, ob ein Wert drinsteht?
Willst du die ID zu einem Bezeichner extrahieren? Dann kannst du auch einfach ein Object nehmen, in der die Abbildung von Bezeichner auf ID gespeichert ist und du kannst dir die ganze Sortierung und Binäre Suche sparen.

Mathias