Hi,

Allerdings konnte ich zu Pidgeonsort nix googlen.

Warun das denn ... argh!
Das heißt natürlich Pigeonsort (Taubensortierung -> eine Taube pro Verschlag, jede weiß genau in welchen Verschlag)

Mensch, was peinlich wieder! Sorry.

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?

Nein, da keine Fehler genehmigt worden sind. Wäre aber bei unsortierten Listen eine gute Möglichkeit, wenn geringe Fehler erlaubt sind oder nur danach gesucht wird, ob _keine_ Schnittmenge existiert.

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

Ja, soviel geht natürlich (sonst hätte ich diese Idee auch sofort verworfen), aber es läßt sich von C aus nicht ganz 1:1 übersetzen. Mit ein wenig Mühe geht es aber doch und das meinte ich damit. Es sollte nach Möglichkeit jedesmal der gleiche Code sein, damit das Managment nicht ausufert.

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?

Ja. Kam nicht ganz raus? Sorry, keine Absicht. Manchmal verklemm ich mir einfach zuviel Platzverbrauch.

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

Tut mir leid, aber da _konnte_ ich jetzt einfach nicht wiederstehen ;-)

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?

Nein, nur theoretische Kompresssion.

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?

Indem ich etwas über einen KiB Bitstring in etwas unter eine KiB Bitstring komprimiere.
http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/cbf.pdf

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

Ja, Base64-Codiert muß der natürlich werden, klar.

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.

Das habe ich weiter unten angegeben, das ich von eienr verkehrten Voraussetzung ausgegangen bin. Das heißt aber natürlich auch, das es genau diesen einen Fall auch tatsächlich gibt und mehr brauche ich ja für BestCase nicht.

Also du hattest früher sowas geschrieben wie

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

Es liegt in dem, was durch die Ellipsis ersetzt wurde. Auf diesem langem Wege bin ich nämlcih dazu gekommen, dsa ich falsch lag und habe meine Meinung revidiert. Das das trotzdem ein Irrtum war, ich mir selebr ein Bein gestellt hatte, habe ich leider erst später erkannt.

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???

Wenn ich die Länge der Listen und des Alphabets kenne (und die veschlampte Bedingung, das alle Elemente auch Elemente aus dem Alphabet sein müssen und _nur_ das, also einzelne Buchstaben. Hätte ich die Beispiel anders gewählt, hätte ich den Fehler auch sofort bemerken können), kann ich aus dem erstem Vergleich 'ax' schon sehen, das nach x kein a mehr kommt. Da ich die Länge der Listen kenne und die Länge des Alphabets kann ich bei Länge drei feststellen, das nach a kein x mehr kommen kann. Auha, noch ein Fehler: ich müßte in dem Fall auch den letzten kontrollieren, klar. Also Mindestmaß sind zwei Vergleiche.
Da aber die Elemente natürlich nicht den Elementen im Alphabet entsprechen, sondern viel schlimmer Zeichenketten mit variablen Längen sind, die in variabler Zusammensetzung aus dem Alphabet gesetzt sind, stimmt das natürlich alles vorn und hinten nicht.
Bitet entschuldige meinen Betonkopf, aber am Ende hast Du ihn ja doch weich bekommen.

[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? ;)

Nein, ganz und gar nicht!
Du hast das ganze in einer leicht andern Sichtweise dargestellt, als ich das kannte. Das hat mir dreidimensionale Sicht ermöglicht.
Da Du das ja kaum C&P von irgendwoher geklaut hast, hast Du da Arbeit reingesteckt, dafür muß ich mich doch bedanken, oder nicht?

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.

Naja, mir gefällt das alles auch nicht immer, aber es ist numal so festgelegt vom OSI, ob's einem nun schmeckt oder nicht.
Aber man gewöhnt sich mit der Zeit daran ;-)

so short

Christoph Zurnieden