RSS Feed

String Interning

Czytając blog Ayende Rahien-a natknąłem się na dość ciekawą technikę przetrzymywania stringów w pamięci. “String Interning”.

Stringi wrzuca się do tablicy. Jeżeli dany string znajduje się już w tablicy przekazujemy tylko wskaźnik do istniejącego stringa jeżeli nie istnieje wrzucamy go do pamięci i przekazujemy wskaźnik.

Technika ta pozwala zaoszczędzić pamięć i przyspiesza porównywanie stringów [Sprowadza porównywanie do porownywania zwyklych referencji a nie obiektów. Jak wiemy porownywanie stringów to operacja o zlozonosci obliczeniowej O(n) natomiast porównywanie wskaźników to O(1).

Java i .Net stosuje ten mechanizm automatycznie w momencie tworzenia literałów.Python składuje tak małe stringi.

   12             int i = 1;

   13             int j = 1;

   14 

   15             String s = "jakis string";

   16             String a = "jakis string";

   17 

   18 

   19             Console.WriteLine((Object)s == (Object)a);

   20 

   21             Console.WriteLine((Object)i == (Object)j);

W przykładzie tym 1 porównanie zwróci wartość true. Oznacza to że oba obiekty wskazują w to samo miejsce.
W momencie tworzenia stringa s została przeszukana tablica stringów. Jako że nie było w niej stringu “jakiś string” została ona wrzucona do tej tablicy i został przekazany wskaźnik. Stringowi a natomiast został przypisany wskaźnik do miejsca na stercie na które wskazuje s ponieważ ta wartość już jest w tablicy. [Tak to działa w znacznym uproszczeniu].

Rzutowanie na Object jest wykonane po to by odwołać się do przeciążenia operatora w klasie bazowej (==) który porównuje referencję.

2 porównanie zwraca wartość false. Przykład ten jest tylko po to by ukazać że interning nie jest stosowane dla np intów. A to dlatego że są one w przeciwieństwie do literałów obiektami immutable [zmiennymi]

Advertisements

One Comment on “String Interning”


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s