Pytanie Sortuj obiekty o rozmiarze dynamicznym


Problem

Załóżmy, że mam dużą liczbę bajtów (do 4 GB) zawierających pewne dane. Te bajty odpowiadają różnym obiektom w taki sposób, że każdy s bajty (myślę s do 32) będzie stanowić pojedynczy obiekt. Jednym ważnym faktem jest to, że ten rozmiar s jest taki sam dla wszystkich obiektów, nie jest przechowywany w samych obiektach i nie jest znany podczas kompilacji.

W tej chwili obiekty te są tylko obiektami logicznymi, a nie obiektami w języku programowania. Mam porównanie na tych obiektach, które składa się z leksykograficznego porównania większości danych obiektu, z nieco inną funkcjonalnością do zerwania więzi z wykorzystaniem pozostałych danych. Teraz chcę posortować te obiekty wydajnie (to naprawdę będzie wąskie gardło aplikacji).

Pomysły do ​​tej pory

Zastanawiałem się nad kilkoma możliwymi sposobami osiągnięcia tego, ale każdy z nich wydaje się mieć raczej niefortunne konsekwencje. Niekoniecznie musisz przeczytać wszystkie te. Próbowałem wydrukować główne pytanie każdego podejścia pogrubioną czcionką.  Gdyby zaproponujesz jedno z tych podejść, następnie Twoja odpowiedź powinna również odpowiadać na powiązane pytania.

1. C quicksort

Oczywiście algorytm C quicksort jest również dostępny w aplikacjach C ++. Jego podpis idealnie spełnia moje wymagania. Ale fakt, że użycie tej funkcji zabrania inline funkcji porównania, oznacza, że ​​każde porównanie przenosi wywołanie funkcji narzut. Miałem nadzieję, że uda mi się tego uniknąć. Dowolne doświadczenie dotyczące sposobu C qsort_r w porównaniu do STL pod względem wydajności byłoby bardzo mile widziane.

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

Łatwo byłoby napisać grupę obiektów zawierających wskaźniki do ich danych. Wtedy można je sortować. Należy wziąć pod uwagę dwa aspekty. Z jednej strony, samo poruszanie się wskaźnikami zamiast wszystkich danych oznaczałoby mniej operacji pamięciowych. Z drugiej strony, nie przemieszczanie obiektów prawdopodobnie spowodowałoby przerwę w pamięci, a tym samym wydajność pamięci podręcznej. Szanse, że głębsze poziomy rekursji quicksort rzeczywiście będą mogły uzyskać dostęp do wszystkich danych z kilku stron pamięci podręcznej, znikną prawie całkowicie. Zamiast tego, każda buforowana strona pamięci dawała tylko bardzo mało użytecznych elementów danych przed ich zastąpieniem. Gdyby ktokolwiek mógł przekazać pewne informacje na temat kompromisu między kopiowaniem a miejscem 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. Odwołanie tego iteratora nie daje odniesienia, ale nowo skonstruowany obiekt do przechowywania wskaźnika do danych i rozmiaru s który jest podany przy konstrukcji iteratora. Tak więc te obiekty można porównać, a nawet mam implementację std::swap dla tych. Niestety wydaje się, że std::swapnie wystarczy std::sort. W niektórych częściach procesu moja implementacja gcc używa sortowania wstawiania (zaimplementowanego w __insertion_sort w pliku stl_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 znasz standardową implementację sortowania, która nie wymaga typu wartości, ale może działać z samymi zamianiami?

Więc potrzebowałbym nie tylko mojej klasy, która służy jako punkt odniesienia, ale potrzebowałbym też klasy, która utrzymałaby tymczasową wartość. A ponieważ rozmiar moich obiektów jest dynamiczny, musiałbym przydzielić to na stercie, co oznacza przydziały pamięci na samych liściach drzewa recusrion. Być może alternatywą byłby typ vaue ze statycznym rozmiarem, który powinien być wystarczająco duży, aby pomieścić obiekty o rozmiarach, które obecnie zamierzam obsługiwać. Oznaczałoby to jednak, że w związku między reference_type i value_type z klasy iteratora. A to oznaczałoby, że będę musiał 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, aby powyższy kod mógł manipulować moimi danymi bez konieczności dynamicznej alokacji pamięci, byłoby to świetne rozwiązanie. Używam już funkcji C ++ 11, więc użycie semantyki move lub podobnej nie będzie problemem.

4. Niestandardowe sortowanie

Nawet rozważałem ponowne wprowadzenie wszystkich quicksort. Być może mógłbym skorzystać z faktu, że moje porównanie jest głównie porównaniem leksykograficznym, tzn. Mogę sortować sekwencje według pierwszego bajtu i przełączać się tylko na następny bajt, gdy bajt FT jest taki sam dla wszystkich elementów. Nie wyjaśniłem jeszcze szczegółów, ale jeśli ktokolwiek może zaproponować referencję, implementację lub nawet nazwę kanoniczną, która zostanie użyta jako słowo kluczowe do takiego bajtowego sortowania leksykograficznego, byłbym bardzo szczęśliwy. Nadal nie jestem przekonany, że przy rozsądnym wysiłku z mojej strony mogłem 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. Sortowanie Radix przychodzi mi na myśl w pierwszej kolejności, ale tak naprawdę nie przemyślałem tego jeszcze. Jeśli możesz zaproponować algorytm sortowania bardziej odpowiadający mojemu problemowi, zrób to. Korzystniej z wdrożeniem, ale nawet bez.

Pytanie

Więc zasadniczo moje pytanie brzmi:
"Jak skutecznie sortować obiekty o rozmiarze dynamicznym w pamięci sterty?"

Każda odpowiedź na to pytanie, która dotyczy mojej sytuacji, jest dobra, niezależnie od tego, czy jest ona związana z moimi własnymi pomysłami, czy nie. Odpowiedzi na poszczególne pytania zaznaczone pogrubioną czcionką lub inne informacje, które mogą mi pomóc w podjęciu decyzji między moimi alternatywami, również byłyby użyteczne, szczególnie, jeśli nie pojawia się jednoznaczna odpowiedź na pojedyncze podejście.


12
2017-07-19 13:38


pochodzenie




Odpowiedzi:


Ponieważ istnieje tylko 31 różnych odmian obiektu (od 1 do 32 bajtów), można łatwo utworzyć typ obiektu dla każdego i wybrać wywołanie do std::sortna podstawie instrukcji switch. Każde połączenie zostanie zainspirowane i zoptymalizowane.

Niektóre rozmiary obiektów mogą wymagać niestandardowego iteratora, ponieważ kompilator będzie nalegał na dopełnianie rodzimych obiektów, aby dopasować je do granic adresów. Wskaźniki mogą być używane jako iteratory w innych przypadkach, ponieważ wskaźnik ma wszystkie właściwości iteratora.


1
2017-07-19 18:18





Najbardziej praktycznym rozwiązaniem jest użycie stylu C. qsort o którym wspomniałeś.

template <unsigned S>
struct my_obj {
    enum { SIZE = S; };
    const void *p_;
    my_obj (const void *p) : p_(p) {}
    //...accessors to get data from pointer
    static int c_style_compare (const void *a, const void *b) {
        my_obj aa(a);
        my_obj bb(b);
        return (aa < bb) ? -1 : (bb < aa);
    }
};

template <unsigned N, typename OBJ>
void my_sort (const char (&large_array)[N], const OBJ &) {
    qsort(large_array, N/OBJ::SIZE, OBJ::SIZE, OBJ::c_style_compare);
}

(Możesz też zadzwonić qsort_r jeśli wolisz.) Od STL sort zwiększa liczbę porównań, możesz nie uzyskać najszybszego sortowania. Jeśli cały system wykonuje sortowanie, może warto dodać kod, aby zmusić niestandardowe iteratory do działania. Ale jeśli przez większość czasu twój system robi coś innego niż sortowanie, dodatkowy zysk, jaki otrzymujesz, może być po prostu hałasem dla całego systemu.


2
2017-07-19 16:23



Używanie parametru czasu kompilacji S oznacza, że ​​będę musiał utworzyć instancję dla każdego możliwego rozmiaru s. Chociaż jest to możliwe w przypadku problemów, które będę w stanie poradzić sobie w dającej się przewidzieć przyszłości, sądzę, że w tym przypadku wolałbym qsort_r tak, że mogę przekazać rozmiar jako parametr runtime. I tak, ta aplikacja odczyta dane wejściowe, posortuje je, wykona duplikaty obsługi i zapisu, więc sortowanie będzie stanowiło główną część operacji. - MvG
@MvG: Dobra uwaga. Edytowałem swoją odpowiedź, aby rozmiar był cechą obiektu, a nie wywołaniem my_sort. Pozwala to zaimplementować porównanie raz w szablonie, chociaż wiele wystąpień funkcji zostanie utworzonych. - jxh


Zgadzam się z std::sort używanie niestandardowego iteratora, odniesienia i typu wartości; w miarę możliwości najlepiej jest korzystać ze standardowej maszyny.

Martwisz się o alokację pamięci, ale nowoczesne alokatory pamięci są bardzo wydajne w rozdawaniu małych porcji pamięci, szczególnie gdy są wielokrotnie wykorzystywane. Możesz także rozważyć użycie własnego (stanowego) przydziału, przydzielając długość s Kawałki z małej sadzawki.


1
2017-07-19 14:20



Czy alokacja pamięci jest włączona? Jeśli nie, nadal martwię się nawet o obciążenie wywołane wywołaniem funkcji. Mechanizm alokacji niestandardowej wydaje się być dobrym pomysłem; Mogłem nawet umieścić stan w iteratorze i maszynie w odniesieniu do wartości operatora obsady, ponieważ wolałbym unikać zmiennych statycznych, a algorytm sortowania nie bierze obiektu przydziału. - MvG
@MvG Nie wierzę, że alokacja pamięci jest typowana typowo, ale procesor będzie mógł zastosować prognozę rozgałęzień pośrednich, co powinno zmniejszyć obciążenie. - ecatmur


Jeśli możesz nałożyć obiekt na bufor, możesz go użyć std::sort, o ile twój typ nakładki jest kopiowalny. (W tym przykładzie 4 liczby całkowite 64-bitowe). Z 4 GB daneBędziesz jednak potrzebował dużo pamięci.

Jak omówiono w komentarzach, możesz wybrać kilka możliwych rozmiarów w oparciu o pewną liczbę szablonów o stałym rozmiarze. Będziesz musiał wybrać od tych typów w czasie wykonywania (używając switch oświadczenie, na przykład). Oto przykład typu szablonu o różnych rozmiarach i przykład sortowania rozmiaru 64-bitowego.

Oto prosty przykład:

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>

template <int WIDTH>
struct variable_width
{
   unsigned char w_[WIDTH];
};

typedef variable_width<8> vw8;
typedef variable_width<16> vw16;
typedef variable_width<32> vw32;
typedef variable_width<64> vw64;
typedef variable_width<128> vw128;
typedef variable_width<256> vw256;
typedef variable_width<512> vw512;
typedef variable_width<1024> vw1024;

bool operator<(const vw64& l, const vw64& r)
{
   const __int64* l64 = reinterpret_cast<const __int64*>(l.w_);
   const __int64* r64 = reinterpret_cast<const __int64*>(r.w_);

   return *l64 < *r64;
}

std::ostream& operator<<(std::ostream& out, const vw64& w)
{
   const __int64* w64 = reinterpret_cast<const __int64*>(w.w_);
   std::cout << *w64;
   return out;
}

int main()
{
   srand(time(NULL));
   std::vector<unsigned char> buffer(10 * sizeof(vw64));
   vw64* w64_arr = reinterpret_cast<vw64*>(&buffer[0]);

   for(int x = 0; x < 10; ++x)
   {
      (*(__int64*)w64_arr[x].w_) = rand();
   }

   std::sort(
      w64_arr,
      w64_arr + 10);

   for(int x = 0; x < 10; ++x)
   {
      std::cout << w64_arr[x] << '\n';
   }

   std::cout << std::endl;

   return 0;
}

1
2017-07-19 13:57



W twoim podejściu rozmiar obiektu jest ustalany podczas kompilacji. Wystarczająco duże, aby pomieścić określoną ilość danych, ale w przypadku użycia z mniejszymi obiektami może nastąpić znaczna utrata pamięci, ponieważ w rzeczywistości wykorzystany zostanie tylko ułamek każdego przydzielonego obiektu. Musiałem ponownie skompilować aplikację i zmienić rozmiar klasy obiektu, jeśli chciałem w przyszłości obsługiwać większe elementy danych. Ogólnie: możliwe, ale bardzo statyczne podejście. - MvG
Ahh, nie zdawałem sobie sprawy, że rozmiary przedmiotów mogą się różnić w czasie wykonywania. Czy masz praktyczny zestaw rozmiarów, które można wykorzystać? Możesz zrobić to samo z zestawem zdefiniowanych template<int> klasy, które poradzą sobie w większości przypadków ... - Chad
Mam nieskończoną sekwencję możliwych rozmiarów, z których każda odpowiada większej klasie problemów niż poprzednio. Idealnie chciałbym rozwiązać którekolwiek z nich, ale praktycznie będę ograniczony do kilku pierwszych na dzisiejszym sprzęcie. Ale to, co dziś jest niewykonalne, może jutro stać się praktyczne, a ja nie chciałbym edytować kodu, żeby się do tego dostosować, nawet jeśli na pewno. - MvG
Jeśli edytujesz swoją odpowiedź na ten styl szablonu, to dam ci rozwiązanie: użycie 64-bitowych liczb całkowitych do przesłania danych wydaje się dobrym pomysłem, a przy tym mogę pokryć duży zakres możliwych rozmiarów przy pomocy kilku instancji szablonów . Sądzę, że to może zaspokoić przynajmniej kilka następnych lat. - MvG
Zaktualizowałem, mam nadzieję, że przynajmniej trochę pomoże. Wersja szablonu wymaga o wiele więcej rzutowania, więc nie jest tak ładna, aby patrzeć, ale nadal "działa". - Chad


Biorąc pod uwagę olbrzymi rozmiar (4 GB), poważnie zastanawiałbym się nad dynamicznym generowaniem kodu. Skompiluj sortowanie niestandardowe do biblioteki współużytkowanej i dynamicznie ją ładuj. Jedynym nieliniowanym połączeniem powinno być wywołanie do biblioteki.

W przypadku wstępnie skompilowanych nagłówków czasy kompilacji mogą nie być tak złe. Całość <algorithm> nagłówek nie zmienia się, ani logika opakowania. Wystarczy za każdym razem ponownie skompilować jeden predykat. A ponieważ jest to jedna funkcja, łączenie jest trywialne.


1
2017-07-19 16:33



Cóż, prawie wszystkie algorytmy sortowania, które znam, używają rekursji, a większość bibliotek implementuje to za pomocą rekursji funkcji. Ponieważ nie można wstawiać nazwanych rekurencyjnie funkcji, istnieje tam ograniczenie. Chyba, że ​​kompilator jest naprawdę sprytny lub sam zarządzasz stosem wywołań. Przez dynamiczne generowanie kodu masz na myśli generowanie kodu do rozmiaru, który będę potrzebować? Trochę się martwię o wymaganie pełnego kompilatora w czasie wykonywania. - MvG
Aby wyjaśnić, mam na myśli umieszczenie predykatu w samej funkcji sortowania. Samo rekurencyjne wywołanie raczej nie jest zbyt głębokie. Ale tak, tag [g ++] był powodem, by to zasugerować - możesz dystrybuować GCC. - MSalters


#define OBJECT_SIZE 32
struct structObject
{
    unsigned char* pObject;
    bool operator < (const structObject &n) const
    {
        for(int i=0; i<OBJECT_SIZE; i++)
        {
            if(*(pObject + i) != *(n.pObject + i))
                return (*(pObject + i) < *(n.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{       
    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * OBJECT_SIZE); // 10 Objects


    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*OBJECT_SIZE);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to check the sort
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end());


    free(pObjects);

Aby pominąć # definicję

struct structObject
{
    unsigned char* pObject; 
};

struct structObjectComparerAscending 
{
    int iSize;

    structObjectComparerAscending(int _iSize)
    {
        iSize = _iSize;
    }

    bool operator ()(structObject &stLeft, structObject &stRight)
    { 
        for(int i=0; i<iSize; i++)
        {
            if(*(stLeft.pObject + i) != *(stRight.pObject + i))
                return (*(stLeft.pObject + i) < *(stRight.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{   
    int iObjectSize = 32; // Read it from somewhere

    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * iObjectSize);

    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*iObjectSize);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to work with something...  
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end(), structObjectComparerAscending(iObjectSize));


    free(pObjects);

0
2017-07-19 15:12



Więc pójdziesz na moje podejście nr 2, sortując wskaźniki zamiast rzeczywistych bloków danych obiektów. Zdecydowanie najłatwiejsze rozwiązanie, więc wykorzystam to do prototypowania, czekając na więcej odpowiedzi, ale moje obawy dotyczące lokalizacji pamięci pozostaną, a ty nie rozwiązałeś ich. Zwróć też uwagę na ciągłą naturę Ciebie OBJECT_SIZEmakro nie oddaje dynamicznego aspektu mojego problemu. - MvG
@MvG edytowane do używania rozmiaru "dyamicznego" - João Augusto
@MvG, jeśli rozmiar danych obiektów jest mały, prawdopodobnie lepiej byłoby nie pracować ze wskaźnikami i robić kopie, ale twoje "jest" dynamiczne. Może powinieneś pomyśleć o użyciu MapReduce do rozwiązania twojego problemu. - João Augusto
Nie wiedziałem wcześniej o map-reduce, ale teraz, gdy na nią patrzę, wydaje mi się, że już mam taki układ kinf od razu i użyłbym tego sortowania tutaj jako jednego kroku w procesie. - MvG