Hi,

Denk an die frühen Assemblersprachen wo man vor jeder Operation erstmal die Werte in ein Register laden mußte,

Das gilt doch auch noch für die modernen Assemblersprachen?
Aua, aua, doch nich' gleich hauen!

ähm, bereits der 68000 kannte Speicheradressierungen für ADD und CMP, bei den Inteldinger kenn ich mich nicht aus (will es auch nicht :)

ja da habe ich was falsch abgeschrieben, Pidgeonsort schau ich mir gerne bald mal an :)

Ich putze mir gearde angelegentlich meine Sehhilfe, wenn Du zufällig gerade mit Telegraphenmasten winken solltest sehe ich das nicht.

Welcher Mast? Kein Mast!

Allerdings konnte ich zu Pidgeonsort nix googlen.

Obwohl ich in diesem Fall auch Bloomfilter spannend fände.

Ist in Arbeit, aber da es nun auch in Javascript funktionieren muß, ist das leider nicht ganz so einfach, wie das bischen Bitschuppserei in C.

Momentmal 1: Du versuchst bereits einen "Durchschnitt von n Listen" Algo mit Bloom Filtern zu realisieren?

Momentmal 2: Was geht in JS nicht? http://de.selfhtml.org/javascript/sprache/operatoren.htm#bits

Zudem wird der Bitstring, der den Bloomfilter darstellt verdammt lang. Bei 4 Hashfunktionen und den irgendwann einmal geschätzten 400 Einträgen bräuchte man

Oder sprichst du wieder vom Caching von Queries?

... für eine Fehlerrate von einem Promille 8172 Bits für den Bloomfilter. Das ist also ziemlich genau ein MiB (hier gesetzt: Byte == Oktet).

8172 Bits= 1MB??? Haben wir jetzt wieder ne Inflation wie in den 20ern ;)

Es ist zwar durch Kompression eine theoretische Ersparnis von rund 30% möglich, aber das ist erstens kompliziert und zweitens: Dekompression in Javascript?

Lauflängenkodierung oder so? Also in JS würd ich mir da keine Gedanken machen, wie willst du BTW einen 1 KB Bitstring im Quelltext verlustfrei in einem KB codieren?

Bitstream geht ja schlecht; bleibt nur Text! Und den würd ich sowieso gzippt ausliefern.

Entscheidungshilfe. BestCase hier oben ist ja schließlich O(1)!

Bitte? Ne, dazu müßte eine Liste einelementig sein!

Nein, unter unseren Voraussetzungen wie gezeigt nicht.

??? Gib mir mal bitte nen Algo der bei 2 Listen mit jeweils mehr als  1 Element den Durchschnitt ermittelt (Bestcase bitte angeben) und selbst bei einem Worstcase nur O(n) braucht.

In diesem Fall tritt BestCase ein falls S_1 != S_2, es ist nur noch ein Vergleich nötig. Gut, dazu müßte der generische Algorithmus etwas geändert werden, aber das schlägt sich nicht auf die Komplexität nieder.

Also du hattest früher sowas geschrieben wie

Worst Case:
S_1 = {a,b,c}
S_2 = {x,y,z}

...

Dadurch, das auch noch die Länge bekannt ist _und_ das zugrundeliegende Alphabet:

ax

??? wieso brauche ich nicht noch bx und cx zu prüfen, was hat das mit bekannter Länge und Alphabet zu tun???

[Rolfs sorgfältige Erklärung]

Ah, danke, das hat geholfen!

Hoffe ich zumindest, aber das würde dann ja wieder an mir selber liegen, nicht an Deiner Erklärung.

Ironie? ;)

Tschau
 rolf

PS: Notationen: Ich bin Anhänger der alten Schule für die 1 KB=1024 Bytes und ein kg=1000 Gramm, abhängig davon ob K groß/kleingeschrieben wurde.