Unikalne łańcuchy znaków

2009-12-19 12:25

Okazjonalnie zachodzi potrzeba, aby do jakiegoś celu wygenerować niepowtarzalny ciąg znaków. Jednym z zastosowań może być tutaj nadanie plikowi nazwy gwarantującej brak kolizji z jakąkolwiek inną nazwą pliku w systemie albo chociaż w aktualnym katalogu. W przypadku gdy ów plik ma istnieć tylko przez chwilę – a więc być plikiem tymczasowym (tempfile), sprawa jest prosta i sprowadza się do wywołania GetTempFileName jako funkcji WinAPI lub metody klasy System.IO.Path z .NET.

Stworzona w ten sposób nazwa jest z definicji “krótko żyjąca”. Na drugim biegunie w zakresie unikalności znajdują się tzw. UUID-y, czyli specjalnie ustandaryzowane 128-bitowe identyfikatory konstruowane tak, by zapewnić, że prawdopodobieństwo wygenerowania duplikatów jest mikroskopijnie małe. Każdy, kto grzebał trochę w Rejestrze Windows lub miał do czynienia z technologią COM, zna na pewno ich kuzynów, czyli GUID-y, opartych w gruncie rzeczy na podobnych zasadach.
Ponieważ tworzenie nowych GUID-ów/UUID-ów jest proste, można je wykorzystać w celu uzyskania niepowtarzalnych ciągów znaków. W czystym Windows API unikalny string oparty na UUID-zie można otrzymać np. tak:

  1. #include <rpc.h>
  2. #pragma comment(lib, "rpcrt4.lib")
  3. string RandomStringViaUUID()
  4. {
  5.     UUID uuid;
  6.     if (UuidCreate(&uuid) != RPC_S_OK) return string();
  7.  
  8.     char* uuidStr;
  9.     if (UuidToStringA(&uuid, (unsigned char**)&uuidStr) != RPC_S_OK)
  10.         return string();
  11.     string res(uuidStr);
  12.     RpcStringFree (&uuidStr);
  13.     return res;
  14. }

Z kolei w .NET istnieje wyspecjalizowana klasa System.Guid, którą można wykorzystać w podobnym celu. W wyniku otrzymamy oczywiście teksty w stylu:

0DF44EAA-FF21-4412-828E-260A8728E7F1

co w wielu zastosowaniach może być strzelaniem z armaty do komara. Nie zawsze potrzebujemy przecież aż tak wielkiej unikalności, a UUID-y w formie tekstowej są długie i nieporęczne.

Są więc i inne rozwiązania, stosowalne jeśli nasz losowy ciąg musi być unikalny tylko przez stosunkowo niedługi czas, np. podczas jednego uruchomienia programu. W takim wypadku możemy użyć chociażby:

  • wartości zwracanych przez GetTickCount/QueryPerformanceCounter lub asemblerową instrukcję rdtsc. Jest to czas (lub liczba cykli procesora) od momentu rozruchu systemu, więc z definicji wartość taka nie powtórzy się w trakcie działania aplikacji. Warto wiedzieć aczkolwiek, że używanie rdtsc jest generalnie niezalecane.
  • aktualnego systemowego czasu – pobranego przez GetSystemTime z Windows API czy System.DateTime.Now z .NET – przekonwertowanego na string. Wadą jest tutaj wynikowa długość łańcucha i zbyt oczywisty format; prawdopodobnie więc należałoby jeszcze poddać go jakiemuś post-processingowi.
  • zwykłego ciągu losowych znaków. W zależności od jakości generatora liczb losowych oraz losowości początkowego ziarna seed, możemy otrzymać nawet całkiem dobre wyniki. Metoda jest dobra zwłaszcza wtedy, gdy generowanych identyfikatorów jest na tyle mało, że możemy je efektywnie przechowywać i po prostu sprawdzać, czy nowy string jeszcze nie wystąpił (przykładem mogą być uchwyty w menedżerze zasobów w silniku gry).

Najważniejsze jest to, aby właściwie dobrać metodę do sytuacji, w której potrzebujemy unikalnego łańcucha znaków. Często wystarczy coś w stylu:

  1. string s;
  2. while (rand() % MAX_LENGTH - s.length() > 0)
  3.     s += rand() % ('Z' - 'a') + 'a';

Nie myślmy nawet jednak, żeby tak stworzonego stringa używać do jakiejkolwiek formy komunikacji przez sieć. W takich przypadkach trzeba w zasadzie użyć UUID-ów.

Tags: , ,
Author: Xion, posted under Programming »


One comment for post “Unikalne łańcuchy znaków”.
  1. Aithne:
    December 19th, 2009 o 17:36

    Używanie rdtsc jest niezalecane do celów mierzenia czasu, ale do zdobywania bezsensownych liczb jest dobrym rozwiązaniem.

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.