Eindeutige Integerzahl

Hallo,
ich möchte eine string wie "123/112" in einer deutigen integer umwandeln so dass, wenn die string "123/112" nochmal kommt , kann ich sofort mit hilfe der integer sie als double kennzeichnen.
wie geht das?
Danke für eure Hilfe

Jochen Kalmbach

Geht nicht. Du musst schon die Strings vergleichen.
Oder Du machst aus den beiden Zahlen Eine:
"123/112" => "123 * 1000000 + 112"
Dies setzt natürlich vorraus, dass die Zahlen auch in die Zahl reinpasst.

Rhombicosidodecahedron

Wie wäre es mit Hash-Funktionen?

Jochen Kalmbach

Rhombicosidodecahedron schrieb:

Wie wäre es mit Hash-Funktionen?

Hash Funktionen sind nicht eindeutig und es kann somit Duplikate geben. Man könnte es höchstens als "ersten Versuch" nehmen, Ist der Hash ungleich dann ist auf jeden Fall der String auch ungleich.
Ist er hingegen gleich kann man nicht daraus schliessen, dass der String auch gleich ist!
Aber um den Hash zu erstellen, muss man auch den ganzen String durchgehen. Dann kann man den String auch sofort vergleichen...

Hallo,
meine Zahlen sind nicht immer so klein ich habe manchemal 12345678/123 .
wenn ich * 1000000 kriege ich so grosse Zahl die in longint mit minus kommt.
Ich habe versucht auch die / mit die zahl 11 zu berechnen an stelle mit 1000000
auch komme ich auf minus werte und bin mir nicht sicher ob es eindeutig oder nicht.
ist / = 11 eine gute lösung?
was von type kann ich verwenden um so grosse Zahlen zu empfangen?

ten

versuch mal das:

#include <stdlib.h>   // fuer atoX
#include <ctype.h>    // fuer isdigit

double to_number (char *str)
{
   char cp[256];
   int i;
   for (i=0;*str;str++)
      if (isdigit(*str))
         cp[i++] = *str;
   cp[i] = 0;
   return atof(cp);
}

oder so:

double to_number (char *str)
{
   double i=0.0;
   while (*str)
   {   
      if (isdigit(*str))
         i = 10.0 * i + *str - '0';
      str++;
   }
   return i;
}

geht mit etwa 16..18 stellen oder so, danach wird gerundet.
:xmas2:

aber das ist nicht was ich meine.
mit deiner funktion wird
123/12 = 12312 und
12/312 = 12312 also liefert die gleiche Zahl und nicht eindeutig.

CStoll

Da könntest du höchstens deinen String als Bruch x/y interpretieren und entweder das Paar (x,y) oder den Quotienten (double)x/y als Hash-Wert speichern (allerdings ist das erste kein einzelner int-Wert und das zweite auch nicht eindeutig).

Randfrage: Wozu brauchst du das eigentlich? Vermutlich ist es einfacher, einen doppelten Wert einfach hinzunehmen als krampfhaft zu versuchen, jeden Wert eindeutig zu machen.

ten

dokdok2 schrieb:

aber das ist nicht was ich meine.
mit deiner funktion wird
123/12 = 12312 und
12/312 = 12312 also liefert die gleiche Zahl und nicht eindeutig.

dann vielleicht so?

#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;
}

Es geht um Datenchecken bevor in einer DB eingefügt.
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.
Mit neuen Daten wird die textfile immer grösser.
die ids sind die P Schlüssel in der tbl .

CStoll

Eventuell wäre es da eine Lösung, dein Textfile gelegentlich wieder zu verkleinern (d.h. statt alle ankommenden IDs dort ohne Nachfrage reinzustopfen, solltest du lieber die duplikatfreie ID-Sammlung abspeichern).

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