Składowanie dużych elementów do posortowania

Hej,

ostatnio zastanawiałem się nad tym jak najlepiej poskładować duże elementy, które następnie będą posortowane. Gdy usłyszałem te pytanie od razu powiedziałem, że w liście, by sortować jedynie iteratory a elementy tak naprawdę pozostawić w spokoju. Jednak nie zakładałem, że jeżeli tych elementów jest dużo, porównywalnie do powiedzmy rozmiaru tych danych, to wtedy czas potrzebny na przejście między wskaźnikami będzie na tyle duży, że kopiowanie dużych struktur wcale nie byłoby gorsze.

Obecnie myślę o gromadzeniu w wektorze [bo ciągłość pamięci więc i mocna optymalizacja dostępu] małych elementów prostej klasy która posiada wskaźnik na dany duży element, oraz przeładowanie operatora < w którym te małe obiekty odnoszą się do określonych wartości pod wskaźnikiem - w celu możliwego działania w sort() [chyba ten operator wystarczy]. Dzięki temu uzyskamy zarówno szybki dostęp do elementów jak i ciągłość w pamięci. Co myślicie?

Jakie są wasze typy?
Dobrze myślę, że przy sortowaniu listy dochodzi tylko do sortowania iteratorów i zmian w tym który na co wskazuje, czy nie?

http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html
Przez to, że czas dostępu do elementów listy nie wynosi O(1) część algorytmów jest wykluczona, jak np. quicksort.

OOOooooo Dzięki!

Od C++11 masz semantykę przenoszenia, więc jeśli Twoja klasa to wspiera to wektor nie będzie elementów kopiować tylko przenosić podczas sortowania, co jest mniej więcej tak kosztowne jak kopiowanie wskaźników (w dużym uproszczeniu).

Faktycznie, w ogóle nie myślałem o move.
Rozumiem, że wszystkie typy wbudowane wspierają tę semantykę.
Nie wiem jednak czy funkcje np sort() opierają się na move, a nie na zwykłym kopiowaniu?
@twonek mógłbyś napisać coś bardziej szczegółowo?

Przydałyby się jakieś testy. Póki co z arta wrzuconego przez @spartanPAGE wynika jasno, ze do sortowania duzych elementów jednak lepiej nadaje się lista-> dotarcie do elementu jest mniej czasochłonne niż 3 kopiowania elementu
wektora.

Gdybym jednak miał pewność, że zamiast kopiowania dojdzie do przesunięcia, są spore szanse, że wektor zmiażdży listę nawet przy elementach wielkości 1KB.

Ciekawe bo ten art jest otagowany jako c++11, wynikałoby, ze sort zwyczajnie nie korzysta z move.

Noo i z tego co patrzę głebiej, swap zakłada podmianę dwóch elementów, move podobnie.
Cięzko mówić o podmianie adresów w wektorze który ma być posortowany skoro kolejność ustawienia w nim pamięci jest istotna, więc wydaje mi się, że nie możemy przy sortowaniu w ogóle mówić o move.

Natomiast w takim razie, wracam do pomysłu:
W wektorze przechowujemy iteratory na duże elementy. Zmiana kolejności==swap wskaźników z iteratorów, a przy tym mamy szybki dostęp do iteratorów. Nie. To bez sensu. Bo i tak trzeba sprawdzać wartość danej zmiennej w innym obszarze pamięci więc cache się opóźni do poziomu listy.

Jakieś pomysły? Czy jednak lista do dużych elementów i tyle?

http://thbecker.net/articles/rvalue_references/section_04.html

For those types that implement move semantics, many standard algorithms and operations will use move semantics and thus experience a potentially significant performance gain. An important example is inplace sorting: inplace sorting algorithms do hardly anything else but swap elements, and this swapping will now take advantage of move semantics for all types that provide it.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Foo
{
	Foo(int bar) : bar(bar) { cout << "Constructor " << bar << endl; }
	Foo(const Foo& rhs) { cout << "Copy constructor" << endl; bar = rhs.bar; }
	Foo(Foo&& rhs) { bar = rhs.bar; cout << "Move constructor " << bar << endl; }
	Foo& operator=(const Foo& rhs) { cout << "copy operator=" << endl; bar = rhs.bar; }
	Foo& operator=(Foo&& rhs) { bar = rhs.bar; cout << "move operator= " << bar << endl;  }
	
	int bar;	
};

int main() 
{
	vector<Foo> v = { 5, -1, 49, 29, -13, 4 };
	cout << "SORTING: " << endl;
	sort(begin(v), end(v), [](const Foo& a, const Foo& b) { return a.bar < b.bar; });
	for (const auto& i : v) 
	    cout << i.bar << " ";
	
	return 0;
}

http://ideone.com/H1vpWR

Możesz również zakomentować przenoszący konstruktor i operator=, wtedy sort będzie kopiować elementy.

Hm ciekawi mnie w jaki sposób obiekt jest przenoszony?
W wektorze przecież musi zostać zachowana ciągłość pamięci.
Mamy więc w adresie 00001: 0101 (Tak tylko dla przykładu!)
A w adresie 00004: 0011 (No i wychodzi, ze dalszy adres ma wieksza wartosc wiec chcemy je zamienić)
No i chcemy je swap. Wiesz może jak to się odbywa, by nie doszło do zwyczajnego skopiowania?
Jak ten mechanizm je zamienia? Jak to działa tam na niskim poziomie?

PS
Dzięki za informacje!

Dla typów prostych przenoszenie = kopiowanie. Znacząca różnica jest dopiero gdy masz dynamicznie zaalokowaną pamięć, wtedy zamiast kopiować tę całą pamięć po prostu kopiujesz wskaźnik wskazujący na nią. Czyli tak jakby ją zabierasz. Wolno zabierać tę dynamiczną pamięć ponieważ przenoszenie oznacza, że poprzedni właściciel tej pamięci już nie będzie z niej korzystać (a właściwie nie wolno mu, bo jak będzie to program może się sypnąć).

https://msdn.microsoft.com/en-us/library/dd293665.aspx

No tak, to rozumiem.
Jednak trzyma mi się to w głowie kupy w momencie gdy mamy klase która ma wskaźnik na początek jakiegoś obszaru na stercie.
Gdy dochodzi do swap'a wskaźniki te zostają podmienione (w move tylko jeden, a drugi zerowany)- ok Kumam i trzyma się to kupy.
Jezeli jednak mam wektor -> tak jak podałeś na tym przykładzie.
To w implementacji wektora masz jedynie wskaźnik na pierwszy element zaalokowanej pamięci (w skrócie mówiąc).
Pamięć jest ciągła, jak więc możemy zamienić wskaźniki na 5ty i 7my element skoro wektor ich w ogóle nie używa?

Rozumiem, że wtedy właśnie trzeba mieć taką klasę jak ta którą podałeś, która ma odnośnik w postaci wskaźnika na stertę i to tam jest nasza duża wartość. Wtedy ta klasa realnie sie nie rusza a jedynie dochodzi do swap tego wskaźnika. (Czyli zamiast int a, mamy DuzyObiekt * wsk_na_niego; )

Czyli hmm dochodzimy do koncepcji o której myślałem wcześniej- mamy jakby iteratory w wektorze które wskazują na duże zmienne? Bo gdyby te duże zawierały się w nich to musielibyśmy je zwyczajnie przepisać. Musimy mieć jedynie do nich wskaźnik.

Wiesz co mam problem ze zrozumieniem tego jakie w przykładzie który dałeś wskaźniki są przesuwane, skoro jedyny wskaźnik jakim operujemy to wskaźnik na początek sterty na wektorze.

Ty nie przenosisz wektora, tylko jego elementy. Czyli ten wewnętrzny wskaźnik wektora na dynamicznie zaalokowaną pamięć się nie zmienia.
Teraz pod tą pamięcią masz obiekty typu DuzyObiekt

wskaźnikWektora --> [DuzyObiekt1][DuzyObiekt2][DuzyObiekt3]

Każdy taki obiekt ma wskaźnik do jego własnej dynamicznie alokowanej pamięci. Teraz jeśli chcesz przenieść DuzyObiekt3 na miejsce DuzyObiekt1, to po prostu kopiujesz wskaźniki z DuzyObiekt3 do DuzyObiekt1.
Wskaźnik wektora na ten cały obszar pamięci (niezwiązany z pamięcią dynamiczną DuzychObiektów) się nie zmienia.

Mając wskaźnik na początek obszaru, łatwo możesz dostać wskaźnik na DuzyObiekt3

wsk += 2;

Ty nie przenosisz wektora, tylko jego elementy. Czyli ten wewnętrzny wskaźnik wektora na dynamicznie zaalokowaną pamięć się nie zmienia.

Wiem, chodzi mi o zamianę 3 z 5 elementem. To przecież nie są już wskaźniki tylko normalne elementy, więc move na nich wypada jak normalne skopiowanie (Jeżeli nie zawierają wskaźników na inne elementy)- tak?

Aby wyjaśnić: http://pastebin.com/ejF8HL0K
to w PUNKT 1 jak bym patrzył na wektor i pamięc jaką on zaalokował (pod wskaźnikiem który on przetrzymuje) to nie byłoby to zwyczajnie?:
Element- Element tej mojej klasy która składa się z 2 double
-> tutaj wskazuje wskaźnik w wektorze

Sterta:
->[Pierwszy Element][Drugi Element-][Trzeci Element]... co jest równoważne z
->[double-][-double-][double][double][double][double]..

Bo teraz zrozumiałem, po tym co napisałeś, że to wygląda bardziej tak:
->[wsk na 1element][wsk na 2 element][wsk na 3 element]
i wtedy faktycznie move byłoby efektywne ZAWSZE ale nigdy nie myślałem, by tak to wyglądało.

W drugim przypadku owszem, jeżeli dochodzi do zamiany kumam move.
W pierwszym przypadku musimy zwyczajnie skopiować zawartość w przypadku tej klasy.
Dopiero gdyby moja klasa miała wskaźnik jakiś na duży element move byłoby efektywne:
->[Pierwszy Element-][Drugi Element-----][Trzeci Element----]...
->[wsk_na_d][double][wsk_na_d][double][wsk_na_d][double]...
Bo dochodzi do przepisania double i zamiany wskaźników.

Chce mieć pewność, że dobrze Cię rozumiem.
Rozumiem, że poprawne jest ostatnie rozumowanie, czy się mylę?

Piwniczne napisał(a):

Wiem, chodzi mi o zamianę 3 z 5 elementem. To przecież nie są już wskaźniki tylko normalne elementy, więc move na nich wypada jak normalne skopiowanie (Jeżeli nie zawierają wskaźników na inne elementy)- tak?
Tak.

Sterta:
->[Pierwszy Element][Drugi Element-][Trzeci Element]... co jest równoważne z
->[double-][-double-][double][double][double][double]..
Tak (ideowo, nie wiem jak to naprawdę układa kompilator).

W pierwszym przypadku musimy zwyczajnie skopiować zawartość w przypadku tej klasy.
Dopiero gdyby moja klasa miała wskaźnik jakiś na duży element move byłoby efektywne:
...
Bo dochodzi do przepisania double i zamiany wskaźników.
Tak.

Ogólnie jeśli klasa na określoną, stałą ilość zmiennych typu prostego, to move = copy.

świetnie teraz Cię w pełni rozumiem, dzięki