1. Zuhause
  2. Frage und Antwort
  3. Effiziente Implementierung eines Bloom-Filters in C?

Effiziente Implementierung eines Bloom-Filters in C?

2012-06-13 9 views
11

Diese Frage wurde bereits früher gestellt, aber es gab zu dieser Zeit keine Antwort, also entschied ich mich, sie noch einmal zu stellen.Effiziente Implementierung eines Bloom-Filters in C?

Ich brauche eine effiziente Implementierung eines Bloom-Filters in C (nicht C++). Wenn es so etwas nicht gibt, würde ich nichts dagegen haben, wenn ich einen guten Hinweis bekomme, damit es nicht zu viel Zeit in Anspruch nimmt.

Ich möchte diese Datenstruktur für Einfügungen und Tests in einem Verhältnis (1: 20k) verwenden, also ist es in erster Linie testintensiv. Die zu testenden Daten sind 64-Bit-Ganzzahlen.

Quelle

2012-06-13 Aman Deep Gautam

+0

Es ist probabilistisch. Wenn Sie eine exakte Antwort wünschen, verwenden Sie Union Disjoint Set suchen. Suchen Sie nach diesem auf Topcoder, es sollte ein Tutorial für sie geben. – nhahtdh

+1

Wenn Sie C schreiben, ist dies nicht die Art von Sache, für die Sie eine allgemeine Bibliothek benötigen. Es sollte weniger als 100 Codezeilen umfassen und sollte weniger Zeit zum Schreiben benötigen als die Integration einer Drittanbieterbibliothek. Lesen Sie einfach Ihre Lieblingsbeschreibung des Algorithmus auf Wikipedia oder ähnliches. –

+1

@R schreiben es wird weniger Zeit dauern, die ich weiß, aber es effizient zu schreiben, so dass es gut skaliert ist ein Problem.Ich muss die Zugehörigkeit von Daten in der Größenordnung von 10^7 testen und diese Abfrage schneller machen als die count (*) Abfrage auf das Ergebnis eines Equi Joins. Ich kann es mir nicht leisten, auch nur eine ms in meiner Implementierung zu verlieren –

Antwort

1

Chromium ein in C hat ++

github link

Quelle

2012-06-13 02:40:15 eqzx

+0

Man, sie müssen wirklich Bob Jenkins 'Copyright für ihre Verwendung seiner (Public Domain) Hashing-Funktion enthalten ... – tbert

4

Nicht zu viel Eigenwerbung zu tun, aber ich habe ein Plugin für die Geany editor/IDE geschrieben, die doppelte Textzeilen herausfiltert, verwendet es einen Bloom-Filter.

Die Implementierung ist in C, und Sie können es right here on GitHub finden. Es ist GPL v3, also abhängig von Ihren genauen Bedürfnissen können Sie es oder möglicherweise nicht verwenden.

Einige Anmerkungen zu meiner Umsetzung:

  • Es fertigt Saiten zu filtern, tut und der Schlüsseltyp nicht abstrakt. Das bedeutet, dass Sie die Schlüsselbehandlung an Ihre Bedürfnisse anpassen müssen.
  • Es unterstützt uncharakteristische Semantik, Sie können es tatsächlich für völlig nicht-probabilistische Existenzprüfung verwenden, wenn Sie möchten (siehe BloomContains Callback-Funktionszeiger, der von bloom_filter_new() verwendet wird). Übergeben Sie einfach NULL, um einen "reinen" Filter zu erhalten.
  • Die String-Hash-Funktion ist MurmurHash2 von Austin Appleby. Ich bewertete das aktuellere Murmur Hash3, aber Version 2 war leichter zu handhaben.
  • Um in das Geany Eco System zu passen, verwendet dieser Code GLib Typen.

Es wurde nicht stark für die Leistung abgestimmt, sollte aber in Ordnung sein. Ich würde mich über jedes Feedback freuen, das Sie nach dem Testen haben, natürlich!

Quelle

2012-06-13 06:59:12 unwind

+0

Hey, danke, es kann wirklich sehr hilfreich sein. Ich werde es versuchen und Ihnen davon erzählen. –

+0

können Sie vorschlagen, können einige andere Bibliotheken für hohe Leistung als Glib –

+0

können Sie vorschlagen, ein bestimmtes Motiv der Verwendung von glib-Bibliothek mit Ausnahme von es macht Code tragbar. –

Verwandte Themen

 Verwandte Themen