Was ist eine einfache C-Bibliothek für eine Menge von Integer-Mengen?

Question

Ich muss ein C-Programm ändern und ich muss eine Reihe von unsigned Integer-Sets enthalten. Das heißt, ich habe Millionen von Mengen von ganzen Zahlen (jeder dieser Integer-Sätze enthält zwischen 3 und 100 ganze Zahlen), und ich muss diese in irgendeiner Struktur speichern, wir können es das Verzeichnis nennen, das in logarithmischer Zeit mir sagen kann, ob ein gegeben ist Ganzzahlsatz ist bereits im Verzeichnis vorhanden. Die einzigen Operationen, die für das Verzeichnis definiert werden müssen, sind Suchen und Einfügen.

Dies wäre leicht in Sprachen mit integrierter Unterstützung für nützliche Datenstrukturen, aber ich bin ein Ausländer zu C und die Suche auf Google hat (überraschend) meine Frage nicht zufriedenstellend beantwortet. Dieses Projekt sieht ungefähr richtig:

http://uthash.sourceforge.net/

aber ich würde mit meinem eigenen Hash-Schlüssel-Generator zu kommen braucht.

Dies ist ein einfaches Standardproblem, also hoffe ich, dass es eine standardmäßige und einfache Lösung gibt.

Answer 1

Es hängt davon ab, was Sie mit den Daten tun werden. Aber vielleicht tsearch macht schon was du willst. Sie können für jedes Set auch ein sortiertes Array erstellen und die Werte mit bsearch nachschlagen, obwohl die Leistung während des Einfügens leiden könnte.

EDIT: Wenn Sie eine (externe) Bibliothek suchen, finden Sie einen Vergleich einiger C und C++ Hash-Tabelle Implementierung here. Der Autor des Artikels hat eine generische Header-Implementierung namens khash geschrieben. So haben Sie kompilierte binäre keine zusätzlichen Abhängigkeiten.

Answer 2

Implementieren Sie eine einfache Hash-Tabelle selbst. Es wird Sie zu einem besseren Programmierer machen, wenn Sie wissen, wie Sie einen selbst implementieren können.

http://en.wikipedia.org/wiki/Hash_table

Answer 3

EDIT: sorry, ich begann zu beantworten, wie es C ist ++ und C nicht Ja, dann sollten Sie Ihre Hash-Funktion und Code, es selbst finden .. da Sie bereits die durchschnittliche Dimension eines Satzes kennen es ist nicht so schwierig, wählen Sie einfach eine gute Hash-Funktion! Sie müssen jedoch ein ganzes Set in einer einzigen Nummer kodifizieren, wenn Sie prüfen möchten, ob bereits ein Verzeichnis vorhanden ist.

können Sie versuchen, indem iterativ die einzelnen Zahlen des Satzes Hashing:

int hashcode = initvalue 
for (int i = 0; i < 0; ++i) 
    hashcode = calc_code(hashcode, number_set[i], i); 

in einer Weise, dass die Hashfunktion auf den vorherigen Wert abhängig ist, die aktuelle Nummer und den aktuellen Index.

Was ist mit STL-Sets?

#include <set> 

int nums[6] = {1,6,34,2,67,41}; 
set<int> numbers; 

for(int i = 0; i < 6; ++i) numbers.insert(nums[i]); 

for(set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter) 
    cout << *iter << ' '; 

Mit dieser Datenstruktur, die Sie leicht alle Ihre Sets speichern können, aber Sie müssen auch einen Weg, um zu überprüfen, ob ein Satz bereits im Verzeichnis enthalten ist. Es ist nicht klar: Möchten Sie wissen, ob ein Satz mit allen SAME-Elementen bereits im Verzeichnis existiert?

Sie es alle Elemente manuell tun können, indem überprüft, aber da man Millionen von ihnen haben Sie eine Möglichkeit, die Elemente des Satzes in einer eindeutigen Nummer und verwenden, um eine Karte von Sätzen zu Hash .. Wenn

Answer 4

finden sollten Ich verstehe Sie richtig, Sie wollen eine Reihe von Mengen von Ganzzahl darstellen, die ich nicht für besonders trivial halte.

Der erste Punkt besteht darin, eine Menge von ganzen Zahlen darzustellen. Der einfachste Weg, eine variable Größe Array wie folgt verwenden würde:

typedef struct { 
    int size; 
    int elems[1]; 
} intset; 

, als Sie einen neuen Satz (mit einer festen Anzahl von Elementen) erstellen können mit

intset *newset(int size) 
{ 
    intset *set; 
    set = malloc(sizeof(intset) + sizeof(int)*(size-1)); 
    if (set) set->size = size; 
    return set; 
} 

und speichern Sie die Elemente mit set->elems[0]=i1; ....Eine andere Option wäre, Bit-Arrays zu verwenden, aber die Implementierung hängt von der Art der zu speichernden Ganzzahlen ab (z. B. liegen sie innerhalb eines festen Bereichs? Erscheint sie normalerweise in Gruppen in einer Gruppe?).

Sobald Sie Ihre Menge von ganzen Zahlen haben, benötigen Sie eine Vergleichsfunktion (um zu bestimmen, ob zwei Sätze die gleichen Elemente haben). Wenn Sie sich für ein Array entschieden haben, das eine Menge darstellt, und Sie das Array sortiert halten, können Sie ganz einfach prüfen, ob zwei Mengen identisch sind. Wenn es sich um eine Bitmap handelt, hängt es davon ab, wie Sie es implementiert haben.

Jetzt können Sie für die Menge der Sätze einen (sortierten) Vektor auswählen, den Sie von Zeit zu Zeit anpassen müssen, wenn Sie Elemente einfügen, oder eine Hash-Tabelle. Im letzteren Fall müssen Sie eine Hash-Funktion für Ihre Integer-Sätze schreiben (möglicherweise unter Verwendung bestehender Funktionen!).

Wie gesagt, es scheint mir nicht trivial, ich bin nicht überrascht, dass Google nicht geholfen hat.

Es ist nicht sehr kompliziert, aber Sie müssen nur einige Entscheidungen treffen, bevor Sie fortfahren.