Problem

Przypuśćmy, że mam dużą tablicę bajtów (myśl do 4 GB) zawierającą pewne dane. Te bajty odpowiadają różnym obiektom w taki sposób, że każdys bajty (pomyśls do 32) będzie stanowić pojedynczy obiekt. Ważnym faktem jest to, że ten rozmiars jest taki sam dla wszystkich obiektów, nie jest przechowywany w samych obiektach i nie jest znany w czasie kompilacji.

W tej chwili obiekty te są tylko jednostkami logicznymi, a nie obiektami w języku programowania. Mam porównanie tych obiektów, które składa się z leksykograficznego porównania większości danych obiektu, z odrobiną innej funkcjonalności, aby złamać powiązania przy użyciu pozostałych danych. Teraz chcę posortować te obiektywydajnie (to naprawdę będzie wąskie gardło aplikacji).

Dotychczasowe pomysły

Pomyślałem o kilku możliwych sposobach osiągnięcia tego, ale każdy z nich wydaje się mieć pewne niefortunne konsekwencje. Nie musisz koniecznie czytać tych wszystkich.Próbowałem wydrukować główne pytanie każdego podejścia pogrubioną czcionką. Jeśli zaproponujesz jedno z tych podejść,następnie Twoja odpowiedź powinna również odpowiadać na powiązane pytania.

1. C quicksort

Oczywiście algorytm quicksort C jest również dostępny w aplikacjach C ++. Jego podpis prawie idealnie pasuje do moich wymagań. Ale fakt, że użycie tej funkcji uniemożliwi wstawianie funkcji porównania, oznacza, że ​​każde porównanie niesie na siebie narzut wywołania funkcji. Miałem nadzieję, że uda mi się tego uniknąć.Wszelkie doświadczenia na temat tego, jak Cqsort_r porównanie do STL pod względem wydajności byłoby mile widziane.

2. Kierunek za pomocą obiektów wskazujących na dane

Łatwo byłoby napisać kilka obiektów zawierających wskaźniki do odpowiednich danych. Wtedy można je posortować. Należy wziąć pod uwagę dwa aspekty. Z jednej strony, poruszanie się po wskaźnikach zamiast wszystkich danych oznaczałoby mniej operacji pamięci. Z drugiej strony, nieprzenoszenie obiektów prawdopodobnie złamałoby lokację pamięci, a tym samym wydajność pamięci podręcznej. Prawdopodobieństwo, że głębsze poziomy rekursji quicksort będą mogły uzyskać dostęp do wszystkich danych z kilku stron z pamięci podręcznej, zniknie prawie całkowicie. Zamiast tego każda strona pamięci podręcznej przyniosłaby tylko kilka użytecznych elementów danych przed ich wymianą.Gdyby ktoś mógł przedstawić jakieś doświadczenie na temat kompromisu między kopiowaniem a lokalizacją pamięci, byłbym bardzo zadowolony.

3. Niestandardowe obiekty iteracyjne, odniesienia i wartości

Napisałem klasę, która służy jako iterator w zakresie pamięci. Dereferencjonowanie tego iteratora nie daje referencji, ale nowo skonstruowany obiekt, aby trzymać wskaźnik do danych i rozmiarus który jest podany przy budowie iteratora. Obiekty te można więc porównywać, a nawet mam ich implementacjęstd::swap dla tych. Niestety wygląda na to, żestd::swap nie wystarczystd::sort. W niektórych częściach procesu moja implementacja gcc używa sortowania wstawek (tak jak zaimplementowano w__insertion_sort w plikustl_alog.h), która przenosi wartość z sekwencji, przesuwa liczbę elementów o jeden krok, a następnie przenosi pierwszą wartość z powrotem do sekwencji w odpowiedniej pozycji:

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

Czy wiesz o standardowej implementacji sortowania, która nie wymaga typu wartości, ale może działać tylko przy zamianie?

Więc nie tylko potrzebuję mojej klasy, która służy jako odniesienie, ale potrzebowałbym także klasy, która utrzymywałaby tymczasową wartość. A ponieważ rozmiar moich obiektów jest dynamiczny, musiałbym przydzielić to na stercie, co oznacza alokacje pamięci na samych liściach drzewa rekusji. Być może jedną alternatywą byłby typ vaue o wielkości statycznej, która powinna być wystarczająco duża, aby pomieścić obiekty o rozmiarach, które obecnie zamierzam obsługiwać. Ale to oznaczałoby, że w związku międzyreference_type ivalue_type klasy iteratora. I oznaczałoby to, że musiałbym zaktualizować ten rozmiar, aby moja aplikacja mogła pewnego dnia obsługiwać większe obiekty. Brzydki.

Jeśli możesz wymyślić czysty sposób na uzyskanie powyższego kodu do manipulowania moimi danymi bez konieczności dynamicznego przydzielania pamięci, byłoby to świetne rozwiązanie. Używam już funkcji C ++ 11, więc używanie semantyki ruchu lub podobnego nie będzie problemem.

4. Sortowanie niestandardowe

Zastanawiałem się nawet nad ponownym wprowadzeniem całego quicksortu. Być może mógłbym wykorzystać fakt, że moje porównanie jest głównie porównaniem leksykograficznym, tj. Mógłbym posortować sekwencje według pierwszego bajtu i przełączyć się na następny bajt, gdy pierwszy bajt jest taki sam dla wszystkich elementów. Nie opracowałem jeszcze szczegółów na ten temat, alejeśli ktoś może zasugerować odniesienie, implementację, a nawet kanoniczną nazwę, która ma zostać użyta jako słowo kluczowe do sortowania leksykograficznego według bajtów, byłbym bardzo szczęśliwy. Nadal nie jestem przekonany, że przy rozsądnym wysiłku z mojej strony mogę pokonać wydajność implementacji szablonu STL.

5. Całkowicie inny algorytm

Wiem, że sąwiele wiele rodzaje algorytmów sortowania. Niektóre z nich mogą lepiej pasować do mojego problemu.Sortuj Radix przychodzi mi na myśl, ale jeszcze tak naprawdę nie myślałem.Jeśli możesz zasugerować algorytm sortowania bardziej odpowiedni do mojego problemu, zrób to. Najlepiej z implementacją, ale nawet bez.

Pytanie

Więc zasadniczo moje pytanie brzmi:
„Jak skutecznie sortowałbyś obiekty o rozmiarze dynamicznym w pamięci sterty?”

Każda odpowiedź na to pytanie odnoszące się do mojej sytuacji jest dobra, bez względu na to, czy jest to związane z moimi własnymi pomysłami, czy nie. Przydatne byłyby również odpowiedzi na poszczególne pytania zaznaczone pogrubioną czcionką lub jakiekolwiek inne spostrzeżenia, które mogłyby pomóc mi w wyborze między moimi alternatywami, zwłaszcza jeśli nie pojawi się żadna konkretna odpowiedź na jedno podejście.