3. Generierung von kurzen IDs

Generierung von kurzen IDs

  • S

    Hiho Leute,

    Ich bräuchte ein (neues) Verfahren zum Generieren von möglichst kurzen IDs.

    Historisch bedingt lief die ID-Generierung in diesem SWP nach dem folgenden Muster ab (Pseudocode):

    int ListeVonAObjekten[100000];

int GenerateID(){

   GenListAObjekte();

   for (z=0; z<100000; z++){
      if(!ListeVonAObjekten[z]) return z;
   }
   return 0;
}

void GenListAObjekte(){

   vector<AlleObjekttypen> Liste;

   for(y=0; y<Liste.size(); y++){
      if(Liste.at(y).Typ==AObjekt) ListeVonAObjekten[y]=1;
   }
}

    ListeVonObjekten ist ein Array der Größe 100000 und wird für jede ID-Genierung neu erstellt und mit IDs aus einem Vektor von Objekten gefüllt, je nachdem ob die Objekte den richtigen Typ haben.

    Optimal ist was anderes, aber es war für die bisherigen Anforderungen tragbar. Dank einem neuen Feature, was nun auf einem Schlag 85000 neue Objekte erstellt, geht der Rehner natürlich ziemlich in die Knie.

    Eine standard ID-Generierung kommt leider nicht in Frage, weil mit den IDs manuell gearbeitet werden muss, also müssen sie möglichst kurz sein.

    Jemand einen kreativen Vorschlag?
    Hab leider in diesem Bereich null Erfahrung.

    0
  • V
     

    int GenerateID(){
   int z;
   do
      z=rand()%122000;
   while(Liste.at(y).Typ!=AObjekt);
   return z;
}

    int main(){//WinMain/FormLoad...
   srand(time(0));
...
    0
  • ?

    Halt dir die höchste noch nicht benutzte Zahl an irgendeiner Stelle vor. Halte dir außerdem eine Queue der IDs vor, die einem Objekt zugewiesen wurden, das nich mehr existiert (wenn ein Objekt verloren geht, pushe seine ID da rein). Wenn du eine neue ID brauchst, kuck nach, ob etwas in der Queue ist, ggf. nimm es da raus. Andernfalls nimm die nächsthöhere, bislang unbenutzte Zahl und erhöhe den entsprechenden Zähler.

    Sofern du sicher bist, dass du nie mehr als 4,3 Milliarden Objekte während eines Programmlauf kriegst (das ist nichts für Serverprozesse!), kannst du auch einfach einen uint32_t hochzählen. Oder einen uin64_t, damit langt das für 264 Objekte.

    0
  • S

    Random kam mir auch schon in den Sinn, wollen die User aber nicht da sie solange wie möglich mit kurzen Zahlen arbeiten wollen.

    Hochzählen und Ids vorhalten... ja klar, aber gibts da nicht was geschickteres?

    0
  • V

    du kannst dir auch ne hashfunktion basteln, die ID in deiner gewünschten länge erstellt.

    0
  • M

    Hochzählen erzeugt bereits jeweils die minimal kürzeste ID...

    Was Du machen kannst ist das Zahlensystem wechseln - d.h. Du verwendest ein 36er-System mit den Ziffern 0..9A..Z. Eine ID Z8 entspricht dann der Zahl 35*16+8.

    Mit 4 Ziffern kannst Du bereits 1.6Mio Werte darstellen, größte Zahl in diesem System wäre dann ZZZZ.

    Intern nimmst Du weiterhin einfach die mit Zählen generierte ID, nur bei Eingabe/Ausgabe konvertierst Du in das andere Zahlensystem.

    0
Anmelden zum Antworten