Eindeutige Integerzahl

das hast du vollkommenrech.
die 9000 000 sind alle eindeutige ids und sind die PK in der Tabelle

ten schrieb

#include <ctype.h> 
double to_number (char *str) 
{ 
   double i=0.0; 
   while (*str) 
   {   
      i = 10.0 * i; 
      if (isdigit(*str)) 
          i = i + *str - '0'; 
      str++; 
   } 
   return i; 
}

das auch nicht
123/012 = 1230012 auch
1230/12 = 1230012

deswegen anstelle 0 habe ich 11 benutzt.
123/12 = 124112 --> 123/ = 1230+11
12/312 = 131312 --> 12/ = 120 +11
meine Frage war ist das eindeutig wenn ich / in 11

CStoll

Ich würde lieber nicht davon ausgehen (außer du berechnest deine Zahl im 11er System)

12/123 = 131123
130/23 = 131123

Mal ein möglicher Ansatz (Achtung, der arbeitet nicht mit int's):

pair<int,int> to_key(const string& str)
{
  size_t p=str.find('/');
  return make_pair(atoi(str.substr(0,p-1).c_str()),atoi(str.substr(p+1).c_str()));
}

Alternativ kannst du dir einen int-Wert auch auf Binär-Ebene ansehen und bitweise in zwei Teile zerlegen, die den beiden Teilen des Eingabestrings entsprechen (aber das wird eklig).

PS: Auch wenn ein Hash nicht immer eindeutige Ergebnisse liefert, könntest du ihn doch als Ausgangsbasis für die weitere Suche nutzen - schließlich mußt du den Wert nur noch mit den gespeicherten Werten vergleichen, die den selben Hash-Wert zurückgegeben haben (und das sollte nur ein geringer Teil deiner Eingabedaten sein).

danke,
ich hätte beinahe auf die 11 verlassen.

wo gibt es über Hash zum lesen? natürlich nicht hashish.
noch eine Frage .
wie kann ich Set container benutzen mit multidemintionswerte.

anstelle SET[10,11,12] eine demention.
SET[(10,1),(10,2),(10,3),(11,1),(11,2),(11,3)] was ähnlisch wie vector vom type struktur

noch eine Frage .
Wie wird 123/12 in digital form mit lauter null und eines?
wir wiessen das alle daten werden mit null und eins übertragen.

also wenn ich 123/12 in z.b 1110101110101010 umwandele und lege diese werte als integer in meinem container.ich denke es wird auch funktionieren oder?

Th

Es ist klar, daß ein Zahlenvergleich schneller als ein String-Vergleich ist, aber um diese Strings eindeutig zu hashen ist evtl. wieder mehr Aufwand nötig.
Du könntest statt dem Stringvergleich die C-Funktion "memcmp" benutzen (diese ist optimiert für schnelleren Vergleich, anstatt Zeichen für Zeichen zu vergleichen wird bei größeren Speicherblöcken die max. Prozessorwortbreite verglichen (also bei 32-Bit Prozessoren 4 Byte gleichzeitig).

vielleicht longintger wird auch nicht reichen für die länge

ich weiss nicht wie ich das vergleichen mit der funktion memcmp mache.
mit set geht es einfach .

if(idlist.find(neuer_ID)==idlist.end())
{
 doubleid= false;
}	
else
{
doubleid= true;
}

CStoll

set verwendet normalerweise < für den Vergleich zweier Elemente, aber du kannst ihm auch einen eigenen Funktor übergeben, der den Vergleich durchführt:

struct mem_checker : public binary_function<string,string,bool>
{
  bool operator()(const string& l,constr string& r)
  {
    size_t len=min(l.length(),r.length())+1;
    return memcpy(l.c_str(),r.c_str(),l)<0);
  }
};

set<string,mem_checker> idlist;

(oder du suchst dir einen Hash-Container (neuere MSVC-Versionen haben afaik hash_set und Kollegen), in den du deine IDs einsortierst)

Babbage

Beim Programmstart lade ich von Textfile 9000000 strings(IDs)in einem container -->SET und tue double check.
Es dauert jedesmal 15 Min bis die strings oder IDS hochgeladen im Programm und Auch verbraucht zuviel Arbeitsspeicer.
mit integers Dauert 30% von Zeit und Arbeitsspeicher.

Also beides wird nicht gehen Schneller Rechnen und weniger Arbeitsspeicher ist bei solchen Algorithmen meist nicht drin, zumal Du mit dem Integer noch einen Informationsverlust hast.

Da Du bisher ein Set (ist als Binänbaum abgelegt) mit 9Mio Werten ca. (ln(9000000)~16) 16 Vergleiche pro Zugriff verwendest und große set's auch beim Einfügen neuer Werte oft ne Menge arbeiten müssen, wär vielleicht eine 2-stufigen Lösung möglich?

Als erste Ebene ein Hash mit vielleicht 50000 Werten.
Hinter jedem dieser Hashwerte steht ein Set wie Du es bisher auch verwendest.
Nur kommt jetzt in jedes Set nur ca (9Mio/50000) 180 Werte.
d.h. Du hast pro Zugriff nur einen Hashzugriff und einen Set Zugriff mit (ln(180)) 5 Vergleichen anstatt 16 Vergleiche.

Das könnte deine Zugriffszeiten beschleunigen aber auch deinen Speicherbedarf erhöhen.

An dem Hashwert kann man dann drehen und ein Optimum (irgendwas zwischen 100 und 8000000) von Speicherbedarf und Geschwindigkeit ermitteln.

Babbage

ich habe was gefunden -->map
dadurch kann ich meine strings
123/12 in 2 Teile beide integer teilen.

ich weiss nicht , ob map zuverlässig?
kann map höhe zahl von werte laden.Wieviel? und auch wieviel kann set laden als maximum?
wenn ich ein set von type (123/12) string und ein map von type(123,12) (int,int )
wer von beiden schneller .
über hash habe was gelesen und werde mich demnäscht rumschauen.

CStoll

Die maximale Größe von map<> und set<> ist jeweils nur vom verfügbaren Speicherplatz abhängig, also kannst du im Extremfall deinen RAM mit einer einzigen map<> vollschaufeln, wenn du es drauf anlegst. Und die Suche in map's ist auch vergleichbar mit set's (die arbeiten intern auf der selben Datenstruktur, nur daß map noch einen zusätzlichen Wert zu jedem Schlüssel mitschleppt).

ABER: Die Elemente der map werden nur nach ihrem Schlüssel verglichen (das kann von Vorteil sein, aber es gefährdet die Eindeutigkeit deiner IDs noch stärker als die bisher vorgeschlagenen Hash-Funktionen - für die map sind die Elemente (123/13) und (123/47) identisch). Als Kompromiss wäre es auch möglich, ein set<pair<int,int> > zu verwenden - das dürfte schneller vergleichen als set<string> und im Gegensatz zu deiner map berücksichtigt es den kompletten Schlüssel.

danke du hast mir viele zeit erspart.
kannst du vielleicht ein kleines Beispiel tippen um zu zeigen
1-wie definiere ich set<pair<int,int> >
2-wie füge ich paar elemente
3-wie kann ich ein wert raus finden ob vorhanden oder nicht
brauch ich extra includs als # include <set>

CStoll

1. genauso wie's da steht: set<pair<int,int> > daten;
2./3. wie bei einem normalen set<int> auch (nur daß du statt einzelnen Zahlen mit Zahlenpaaren arbeiten mußt) - aus zwei Zahlen kannst du per make_pair() ein Paar erzeugen - und daraus über p.first und p.second wieder die einzelnen Werte auslesen
4. Du brauchst noch #include <utility> für das pair<>

Babbage

Muß denn zwischen
123/12
und
0123/12
unterscheiden werden?

Ein set<pair<int,int> > macht die Opration nur um den Faktor schneller, den ein Integervergleich schneller ist als ein Stringvergleich (und schnellere Kopieraktionen)
Aber die Anzahl der Vergleiche bleibt, ebenso wie die Verwaltungsarbeit des großen Binärbaums (egal ob set oder map)
Da ein Stringvergleich bei unterscheidlichen ersten Zeichen ziemlich schnell ist glaube ich nicht das der Effekt riesig groß sein wird.

Babbage

Hab die ganze Sache mal mit nem Hash-Table realisiert und 10Mio Strings reingeschrieben.
Die Sache geht solange gut (bis ca. 3-5 Mio) bis eine Temp-Datei auf die Festplatte ausgelagert wird und nix geht mehr.

Ohne dies Problem würde die Aktion wohl bei mir in ner Minute durchlaufen.

Babbage

Hast Du das Problem immer noch oder ist die Sache abgechlossen?
Ich brauch mit Quicksort inzwischen ca. 20sek für 10Mio strings.

Babbage