Najszybszy kod C / C++ do wyboru mediany w zestawie 27 wartości zmiennoprzecinkowych

Algorytm wyboru to czas liniowy (O (n)). Ze względu na złożoność nie można zrobić lepiej niż czas liniowy, ponieważ odczyt wszystkich danych wymaga czasu liniowego. Więc nie można było zrobić czegoś, co jest szybsze złożoności. Być może masz coś, co jest stałym czynnikiem szybszym na niektórych wejściach? Wątpię, żeby to coś zmieniło.

C++ zawiera już algorytm wyboru czasu liniowego. Dlaczego go nie użyjesz?

std::vector<YourType>::iterator first = yourContainer.begin();
std::vector<YourType>::iterator last = yourContainer.end();
std::vector<YourType>::iterator middle = first + (last - first) / 2;
std::nth_element(first, middle, last); // can specify comparator as optional 4th arg
YourType median = *middle;

Edit: technicznie rzecz biorąc, to tylko mediana dla pojemnika o nieparzystej długości. Dla jednego z parzystej długości, otrzyma" górną " medianę. Jeśli chcesz tradycyjną definicję mediany dla parzystej długości, być może będziesz musiał uruchomić ją dwa razy, raz dla każdego z dwóch "średnich" w first + (last - first) / 2 i first + (last - first) / 2 - 1, a następnie je średnią lub coś w tym stylu.

EDIT: muszę przeprosić. Poniższy kod był błędny. Mam stały kod, ale muszę znaleźć kompilator icc , aby powtórzyć pomiary.

Wyniki benchmarku algorytmów rozważanych do tej pory

Protokół i krótki opis algorytmów znajdują się poniżej. Pierwsza wartość to średni czas (sekundy) ponad 200 różnych sekwencji, a druga wartość to stdDev.

HeapSort     : 2.287 0.2097
QuickSort    : 2.297 0.2713
QuickMedian1 : 0.967 0.3487
HeapMedian1  : 0.858 0.0908
NthElement   : 0.616 0.1866
QuickMedian2 : 1.178 0.4067
HeapMedian2  : 0.597 0.1050
HeapMedian3  : 0.015 0.0049 <-- best

Protokół: generowanie 27 losowych pływaków za pomocą losowych bitów uzyskanych z rand (). Zastosuj każdy algorytm 5 milionów razy z rzędu (w tym wcześniejszą kopię tablicy) i Oblicz średnią i stdDev ponad 200 losowych sekwencji. Kod C++ skompilowany z icc-S - O3 i uruchomiony na Intel E8400 z 8GB DDR3.

Algorytmy:

HeapSort : pełne sortowanie sekwencji za pomocą sortowania i wybierania średniej wartości sterty. Naiwna implementacja korzystająca z dostępu do indeksu.

QuickSort: pełny rodzaj sekwencji za pomocą szybkiego sortowania i wybierania średniej wartości. Naiwna implementacja korzystająca z dostępu do indeksu.

QuickMedian1: algorytm szybkiego wyboru z zamianą. Naiwna implementacja korzystająca z dostępu do indeksu.

HeapMedian1: w miejsce metody zbalansowanej heap z uprzednim zamianą. Naiwna implementacja korzystająca z dostępu do indeksu.

NthElement: używa algorytmu STL nth_element. Dane są kopiowane do wektora za pomocą memcpy (vct.data (), rndVal, ... );

QuickMedian2: używa algorytmu quick select ze wskaźnikami i kopiuje w dwóch buforach, aby uniknąć zamiany. Na podstawie propozycji MSalters.

HeapMedian2: wariant mojego wymyślonego algorytmu wykorzystującego podwójne stosy ze wspólnymi głowami. Lewa sterta ma największą wartość jako head, prawa ma najmniejszą wartość jako head. Initialize z pierwszą wartością jako common head i pierwszą średnią domyślną wartością. Dodaj kolejne wartości do sterty lewej, jeśli jest mniejsza niż head, w przeciwnym razie do sterty prawej, aż jedna ze sterty będzie pełna. Jest pełna, gdy zawiera 14 wartości. Następnie rozważ tylko pełną stertę. Jeśli jest to właściwa sterta, dla wszystkich wartości większych niż głowa, pop head i wstaw wartość. Ignoruj wszystkie inne wartości. Jeśli jest to lewa sterta, dla wszystkich wartości mniejszych niż Głowica, pop head i włóż ją do sterty. Ignoruj wszystkie inne wartości. Gdy wszystkie wartości są kontynuowane, wspólna głowica jest wartością medianą. Używa indeksu integer do tablicy. Wersja wykorzystująca wskaźniki (64bit) wydawała się być prawie dwa razy wolniejsza (~1s).

HeapMedian3: ten sam algorytm co HeapMedian2, ale zoptymalizowany. Używa indeksu unsigned char, unika zamiany wartości i różnych innych małych rzeczy. Wartości średnie i stdDev są obliczane ponad 1000 losowych sekwencji. Dla nth_element mierzyłem 0.508 s i stddev 0.159537 z tymi samymi 1000 losowymi sekwencjami. HeapMedian3 jest zatem 33 razy szybszy od funkcji nth_element stl. Każda zwrócona wartość mediana jest sprawdzana z wartością mediana zwróconą przez heapSort i wszystkie są zgodne. Wątpię, żeby metoda wykorzystująca hash była znacznie szybsza.

EDIT 1: algorytm ten można dodatkowo zoptymalizować. Pierwsza faza, w której elementy są wysyłane w stercie lewej lub prawej na podstawie wyniku porównania nie wymagają sterty. Wystarczy po prostu dołączyć elementy do dwóch nieuporządkowanych sekwencji. Faza pierwsza zatrzymuje się, gdy tylko jedna sekwencja jest pełna, co oznacza, że zawiera 14 elementów (w tym wartość mediana). Druga faza rozpoczyna się od nagromadzenia pełnej sekwencji, a następnie przebiega zgodnie z opisem w algorytmie HeapMedian3. Jak najszybciej podam nowy kod i benchmark.

EDIT 2: zaimplementowałem i porównał zoptymalizowany algorytm. Ale nie ma znaczącej różnicy w wydajności w porównaniu do heapMedian3. Średnio jest nawet nieco wolniejszy. Pokazane wyniki są potwierdzone. Może być z dużo większymi zestawami. Zauważ również, że po prostu wybrać pierwszą wartość jako początkową medianę zgadywania. Jak sugerowano, można skorzystać z faktu, że szukamy wartości mediany w "nakładających się" zestawach wartości. Użycie algorytmu mediana mediany pomogłoby wybrać znacznie lepszą początkową wartość mediany Zgadnij.

Kod źródłowy HeapMedian3

// return the median value in a vector of 27 floats pointed to by a
float heapMedian3( float *a )
{
   float left[14], right[14], median, *p;
   unsigned char nLeft, nRight;

   // pick first value as median candidate
   p = a;
   median = *p++;
   nLeft = nRight = 1;

   for(;;)
   {
       // get next value
       float val = *p++;

       // if value is smaller than median, append to left heap
       if( val < median )
       {
           // move biggest value to the heap top
           unsigned char child = nLeft++, parent = (child - 1) / 2;
           while( parent && val > left[parent] )
           {
               left[child] = left[parent];
               child = parent;
               parent = (parent - 1) / 2;
           }
           left[child] = val;

           // if left heap is full
           if( nLeft == 14 )
           {
               // for each remaining value
               for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
               {
                   // get next value
                   val = *p++;

                   // if value is to be inserted in the left heap
                   if( val < median )
                   {
                       child = left[2] > left[1] ? 2 : 1;
                       if( val >= left[child] )
                           median = val;
                       else
                       {
                           median = left[child];
                           parent = child;
                           child = parent*2 + 1;
                           while( child < 14 )
                           {
                               if( child < 13 && left[child+1] > left[child] )
                                   ++child;
                               if( val >= left[child] )
                                   break;
                               left[parent] = left[child];
                               parent = child;
                               child = parent*2 + 1;
                           }
                           left[parent] = val;
                       }
                   }
               }
               return median;
           }
       }

       // else append to right heap
       else
       {
           // move smallest value to the heap top
           unsigned char child = nRight++, parent = (child - 1) / 2;
           while( parent && val < right[parent] )
           {
               right[child] = right[parent];
               child = parent;
               parent = (parent - 1) / 2;
           }
           right[child] = val;

           // if right heap is full
           if( nRight == 14 )
           {
               // for each remaining value
               for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
               {
                   // get next value
                   val = *p++;

                   // if value is to be inserted in the right heap
                   if( val > median )
                   {
                       child = right[2] < right[1] ? 2 : 1;
                       if( val <= right[child] )
                           median = val;
                       else
                       {
                           median = right[child];
                           parent = child;
                           child = parent*2 + 1;
                           while( child < 14 )
                           {
                               if( child < 13 && right[child+1] < right[child] )
                                   ++child;
                               if( val <= right[child] )
                                   break;
                               right[parent] = right[child];
                               parent = child;
                               child = parent*2 + 1;
                           }
                           right[parent] = val;
                       }
                   }
               }
               return median;
           }
       }
   }
} 

Na to pytanie nie można łatwo odpowiedzieć z tego prostego powodu, że wydajność jednego algorytmu w stosunku do drugiego zależy tak samo od kombinacji kompilatora / procesora / struktury danych, jak od samego algorytmu, jak na pewno wiesz]}

Dlatego Twoje podejście do wypróbowania kilku z nich wydaje się wystarczająco dobre. I tak, quicksort powinien być dość szybki. Jeśli tego nie zrobiłeś, możesz spróbować insertionsort, który często działa lepiej na małych zestawach danych. To powiedziane, po prostu ustatkuj na sortującym algo, który wykonuje zadanie wystarczająco szybko. Zazwyczaj nie dostaniesz 10 razy szybciej, po prostu wybierając" prawo " algo.

Aby uzyskać znaczne przyspieszenie, lepszym sposobem często jest użycie większej struktury. Niektóre pomysły, które działały dla mnie w przeszłości z problemami na dużą skalę: {]}

• Czy można efektywnie wstępnie obliczyć podczas tworzenia voxeli i przechowywać 28 zamiast 27 pływaków?

• Czy przybliżone rozwiązanie wystarczy? Jeśli Zobacz też mediana, powiedzmy 9 wartości, ponieważ " ogólnie można oczekuje się, że wartości są stosunkowo blisko."Lub można go zastąpić średnia, o ile wartości są stosunkowo blisko.

• Czy naprawdę potrzebujesz mediany dla wszystkich miliardy voxeli? Może masz łatwy test, czy potrzebujesz mediana, a następnie można obliczyć tylko dla odpowiedniego podzbioru.

• Jeśli nic innego nie pomoże: spójrz na kod asm generowany przez kompilator. Możesz napisać asm kod, który jest znacznie szybciej (np. wykonując wszystkie kalkulatory wykorzystujące rejestry).

Edit: jeśli to coś warte, załączyłem (częściowy) kod wstawki wymieniony w komentarzu poniżej (całkowicie niesprawdzony). Jeśli numbers[] jest tablicą o rozmiarze N i chcesz posortować najmniejsze pływaki P na początku tablicy, wywołaj partial_insertionsort<N, P, float>(numbers);. Stąd Jeśli zadzwonisz partial_insertionsort<27, 13, float>(numbers);, numbers[13] będzie zawierać medianę. Aby uzyskać dodatkową prędkość, musisz również rozwinąć pętlę while. Jako omówione powyżej, aby uzyskać naprawdę szybko, trzeba wykorzystać swoją wiedzę na temat danych (np. czy dane są już częściowo posortowane? Czy znasz właściwości rozkładu danych? Chyba rozumiesz dryf).

template <long i> class Tag{};

template<long i, long N, long P, typename T>
inline void partial_insertionsort_for(T a[], Tag<N>, Tag<i>)
{   long j = i <= P+1 ? i : P+1;  // partial sort
    T temp = a[i];
    a[i] = a[j];       // compiler should optimize this away where possible
    while(temp < a[j - 1] && j > 0)
    { a[j] = a[j - 1];
      j--;}
    a[j] = temp;
    partial_insertionsort_for<i+1,N,P,T>(a,Tag<N>(),Tag<i+1>());}

template<long i, long N, long P, typename T>
inline void partial_insertionsort_for(T a[], Tag<N>, Tag<N>){}

template <long N, long P, typename T>
inline void partial_insertionsort(T a[])
 {partial_insertionsort_for<0,N,P,T>(a, Tag<N>(), Tag<0>());}

Najbardziej prawdopodobnym algorytmem do użycia w pierwszej próbie jest po prostu nth_element; to prawie daje to, co chcesz bezpośrednio. Poproś o 14 element.

Przy drugiej próbie, celem jest wykorzystanie stałej wielkości danych. Nie musisz przydzielać żadnej pamięci w ogóle ze względu na algorytm. Skopiuj wartości voxel do wstępnie przydzielonej tablicy 27 elementów. Wybierz pivot i skopiuj go na środek tablicy 53 elementów. Skopiuj pozostałe wartości po obu stronach pivot. Tutaj masz dwa wskaźniki (float* left = base+25, *right=base+27). Są teraz trzy możliwości: lewa strona jest większa, prawa strona jest większa, lub obie mają 12 elementów. Ostatni przypadek jest trywialny; Twój pivot to mediana. W przeciwnym razie wywołaj nth_element po lewej lub prawej stronie. Dokładna wartość Nth zależy od tego, ile wartości było większych lub mniejszych niż pivot. Na przykład, jeśli dzielenie wynosi 12/14, potrzebny jest najmniejszy element większy od przegubu, więc Nth=0, a jeśli dzielenie było 14/12, trzeba największy element mniejszy pivot, więc Nth=13. Najgorsze przypadki to 26/0 i 0/26, kiedy twój pivot był skrajny, ale zdarzają się tylko w 2/27 wszystkich przypadków.

Trzecie ulepszenie (lub pierwsze, jeśli musisz użyć C i nie masz nth_element) zastępuje całkowicie nth_element. Nadal masz tablicę 53 elementów, ale tym razem wypełniasz ją bezpośrednio z wartości voxel (zapisując kopię tymczasową do float[27]). Pivot w tej pierwszej iteracji jest po prostu voxel[0][0][0]. Dla kolejnych iteracji, używasz drugiej wstępnie przydzielonej float[53] (łatwiej, jeśli obie mają ten sam rozmiar) i kopiuj pływaki między nimi. Podstawowy etap iteracji jest nadal: skopiuj pivot do środka, posortuj resztę w lewo i w prawo. Na końcu każdego kroku dowiesz się, czy mediana jest mniejsza czy większa od bieżącego obrotu, więc możesz odrzucić pływaki większe lub mniejsze od tego obrotu. Na iterację, eliminuje to od 1 do 12 elementów, ze średnią z 25% pozostałych.

Ostateczna iteracja, jeśli nadal potrzebujesz większej prędkości, opiera się na obserwacji, że większość twoich wokseli znacznie się pokrywa. Wstępnie obliczasz dla każdego plastra 3x3x1 wartość mediany. Następnie, gdy potrzebujesz początkowego obrotu dla kostki voxel 3x3x3, bierzesz medianę z trzech. Wiesz a priori, że jest 9 voxeli mniejszych i 9 voxeli większych niż mediana medianów (4+4+1). Tak więc, po pierwszym obrotowym kroku, najgorsze przypadki to 9/17 i Rozdwojona 17/9. Tak więc, trzeba tylko znaleźć 4. lub 13. element w float[17], zamiast 12. lub 14. elementu w float[26].

Background: idea skopiowania najpierw Pivota, a następnie reszty float[N] do float[2N-1], używając lewego i prawego wskaźnika polega na wypełnieniu podprzestrzeni float[N] wokół Pivota, z wszystkimi elementami mniejszymi niż pivot po lewej stronie (dolny indeks) i wyższymi po prawej (wyższy indeks). Teraz, jeśli chcesz element Mth, może znajdziesz sobie szczęście i miej elementy M-1 mniejsze niż pivot, w którym to przypadku pivot jest elementem, którego potrzebujesz. Jeśli jest więcej niż (M-1) elementów mniejszych niż pivot, element Mth jest wśród nich, więc możesz odrzucić pivot i wszystko większe niż pivot, i seacrh dla elementu Mth we wszystkich niższych wartościach. Jeśli istnieje mniej niż (M-1) elementów mniejszych niż pivot, szukasz wartości wyższej niż pivot. Więc odrzucisz pivot i wszystko mniejsze od niego. Niech liczba elementów mniej niż pivot, tzn. na lewo od pivot być L. w następnej iteracji, chcesz (M-L-1)Ten element (N-L-1)pływaków, które są większe niż pivot.

Ten rodzaj algorytmu nth_element jest dość wydajny, ponieważ większość pracy poświęca się kopiowaniu pływaków między dwiema małymi tablicami, z których obie będą w pamięci podręcznej, a także dlatego, że twój stan jest przez większość czasu reprezentowany przez 3 wskaźniki (wskaźnik źródła, wskaźnik lewego miejsca docelowego, prawy miejsca docelowego pointer).

Aby pokazać Podstawowy kod:

float in[27], out[53];
float pivot = out[26] = in[0];     // pivot
float* left = out+25, right = out+27
for(int i = 1; i != 27; ++1)
if((in[i]<pivot)) *left-- = in[i] else *right++ = in[i];
// Post-condition: The range (left+1, right) is initialized.
// There are 25-(left-out) floats <pivot and (right-out)-27 floats >pivot

Sieć sortująca wygenerowana przy użyciu algorytmu Bose-Nelson znajdzie medianę bezpośrednio bez pętli / rekurencji przy użyciu 173 porównań. Jeśli masz możliwość wykonywania porównań równolegle, takich jak użycie instrukcji wektorowo-arytmetycznych, możesz być w stanie zgrupować porównania do zaledwie 28 operacji równoległych.

Jeśli jesteś pewien, że pływaki są znormalizowane, a nie (qs) NaN, możesz użyć operacji integer do porównania pływaków IEEE-754, które mogą wykonać bardziej korzystnie na niektórych procesorach.

Bezpośrednia konwersja tej sieci sortującej do C (gcc 4.2) daje najgorszy przypadek 388 cykli zegara na moim Core i7.

Sortowanie Sieci

Przypuszczam, że najlepiej będzie użyć istniejącego algorytmu sortowania i spróbować dowiedzieć się, czy można go dostosować tak, aby zbiór nie musiał być w pełni sortowany. Aby określić medianę, potrzebujesz co najwyżej połowy posortowanych wartości, albo niższa lub wyższa połowa wystarczy:

original:              | 5 | 1 | 9 | 3 | 3 |
sorted:                | 1 | 3 | 3 | 5 | 9 |
lower half sorted:     | 1 | 3 | 3 | 9 | 5 |
higher half sorted:    | 3 | 1 | 3 | 5 | 9 |

Druga połowa byłaby zbiorem niesortowanych wartości, które po prostu mają tę właściwość, że są większe/mniejsze lub równe największej / najmniejszej posortowanej wartości.

Ale nie mam gotowego algorytm do tego, to tylko pomysł, jak możesz wziąć skrót w sortowaniu.

Nowa książka Alexa Stepanova Elements of Programming mówi w pewnym sensie o znajdowaniu statystyk zamówień przy użyciu minimalnej liczby średnich porównań przy minimalizacji kosztów czasu pracy. Niestety, spora ilość kodu jest potrzebna tylko do obliczenia mediany elementów 5, a nawet wtedy daje jako projekt znalezienie alternatywnego rozwiązania, które wykorzystuje ułamek porównania mniej średnio, więc nie marzyłbym o rozszerzeniu tego frameworka do znalezienia mediany 27 żywioły. A książka będzie dostępna dopiero 15 czerwca 2009. Chodzi o to, że ponieważ jest to problem o stałej wielkości, istnieje metoda bezpośredniego porównania, która jest udowodniona.

Istnieje również fakt, że algorytm ten nie jest uruchamiany raz w izolacji, ale raczej wiele razy, a między większością uruchomień zmieni się tylko 9 z 27 wartości. Oznacza to, że w teorii część pracy jest już wykonana. Nie słyszałem jednak o żadnych algorytmach filtrowania mediany w przetwarzaniu obrazów że wykorzystać ten fakt.

+ 1 dla każdego, kto wspomniał o nth_element, ale ten rodzaj kodu jest tam, gdzie ręcznie napisany algorytm jest lepszy niż STL, ponieważ chcesz wygenerować najbardziej efektywny kod dla tego jednego kompilatora działającego na jednym CPU z określonym zestawem danych. Na przykład, dla niektórych kombinacji CPU/kompilatora std:: swap (int, int) może wolniejszy niż ręcznie napisany swap przy użyciu XOR (zanim odpowiesz, wiem, że to prawdopodobnie prawda 20 lat temu, ale już nie). Czasami wydajność uzyskuje się przez ręczne pisanie montażu kod specyficzny dla Twojego procesora. Jeśli planujesz skorzystać z procesorów strumieniowych GPU, być może będziesz musiał odpowiednio zaprojektować swój algorytm.

Wspomniałeś używając 2 stosów i śledź medianę podczas wstawiania. To właśnie zrobiłem jakiś czas temu w projekcie. Zmieniłem tablicę w miejscu i użyłem tylko jednej sterty. Nie mogłem wymyślić żadnego szybszego algorytmu, ale chciałbym ostrzec Cię o zużyciu pamięci, w szczególności pamięci cache CPU. Chcesz być ostrożny z dostępem do pamięci. Pamięć podręczna procesora jest zamieniane na strony, więc chcesz, aby twój algorytm dotykał pamięci, które są blisko siebie, aby zminimalizować brak pamięci podręcznej procesora.

Gdy mamy powiedzmy milion różnych wartości, od których potrzebujesz mediany. Czy można oprzeć swoją medianę na podzbiorze tych milionów, powiedzmy 10%. Tak, że mediana jest blisko n-tego elementu, który dzieli wartości w 2 równe (lub prawie równe) podzbiory? W związku z tym, aby znaleźć medianę trzeba mniej niż O (n)-razy (w tym przypadku O (1/10n) i tym samym zbliżyć się do optymalnego sortowania z quicksort w O(nlogn)?

Jeśli chcesz zobaczyć algorytmy zajrzyj do książek Donalda E. Knutha.

PS. Jeśli uważasz, że wymyśliłeś coś lepszego, powinieneś być w stanie pokazać, że złożoność jest podobna lub lepsza do złożoności znanych algorytmów. Który dla wariacji opartych na bucket i radix jest O (n) Z drugiej strony quick-sort jest tylko o(N. log(N)). Metoda, która jest o 20% szybsza jest nadal O(N. log (n)) dopóki nie pokażesz algorytmu: -)

Założę się, że można je obliczyć za zerowy koszt - w osobnym wątku podczas ładowania z dysku (lub jak są generowane).

Tak naprawdę mówię ,że 'prędkość' nie będzie wynikać z BiT twidling, ponieważ 27 wartości nie wystarczy, aby notacja Big O była prawdziwym czynnikiem.

Możesz rzucić okiem na ćwiczenie Knutha 5.3.3.13. Opisuje algorytm z powodu Floyda, który znajduje medianę N elementów za pomocą porównań(3/2)n+O(n^(2/3) log n), A stała ukryta W O (·) wydaje się w praktyce nie być zbyt duża.

Jeśli są 3x3x3 = 27 możliwych wartości (jeśli tak to dlaczego pływaki?), czy można utworzyć tablicę 27 elementów i policzyć każdą możliwość w jednym przejściu przez dane?

Mój super szybki algorytm obliczania mediany zbioru danych 1-D wykonuje zadanie w trzech przebiegach i nie musi sortować (!!!) zbiór danych.

Bardzo ogólny opis jest następujący:

• Pass 1: skanuje zestaw danych 1-D i zbiera pewne informacje statystyczne z zestawu danych
• Pass 2: wykorzystuje informacje statystyczne zbioru danych i stosuje eksplorację danych do tworzenia pośredniej (pomocniczej) tablicy
• Pass 3: Scans the intermediate (helper ) tablica w celu znalezienia mediany

Algorytm jest przeznaczony do znajdowania nośników bardzo dużych zbiorów danych 1-D większych niż 8GE ( giga elements ) wartości zmiennoprzecinkowych o pojedynczej precyzji ( w systemie stacjonarnym z 32GB pamięci fizycznej i 128GB pamięci wirtualnej), lub do znajdowania nośników małych zbiorów danych w twardym środowisku czasu rzeczywistego.

Algorytm jest następujący:

• szybciej niż klasyczny algorytm, oparty na algorytmie sortowania sterty lub scalania, w ~60 - ~75 razy
• zaimplementowane w czystym języku C
• nie używa żadnych funkcji Intel intrinsics
• nie używa żadnych wbudowanych instrukcji asemblera
W 2007 roku firma Microsoft ogłosiła, że będzie miała 100 000 klientów, a w 2009 roku 10 000 000 klientów.]}
• absolutnie przenośne między platformami

Pozdrawiam, Sergey Kostrov