[Algorytmy] Mieszanie dużych tablic

Question

Witam,

 

Chciałbym wymieszać bardzo szybko i bardzo dokładnie tablice wielu elementów mowa tu dokładnie o wektorze, którego rozmiar może być w zakresie (1000000 - 10000000).

Jakieś pomysły/rady :/.

 

Z góry dziękuje za każdą pomoc.

Comments

Bardzo dokładnie, czyli jak?

---

To znaczy tak aby posortowana tablica stala sie bardzo nieposortowanai quicksort sobie swietnie z nia radzil :)

Answer 1

Skorzystaj z std::shuffle.

Comments

for (int& x: foo) std::cout << ' ' << x;

co oznacza ten zapis ? czy da sie skrocic petle for ? czy obowiazuje on w obecnym standardzie ?

---

 czy da sie skrocic petle for ? czy obowiazuje on w obecnym standardzie ?

Tak.

Znaczy to dosłownie: każdy element z foo przypisz do x i wykonaj na nim operacje wyszczególnione w ciele pętli.

---

czym sie rozni taka tablica od zwyklej ?

---

Hm. Przede wszystkim każdy element przypisujesz najpierw do tego iksa i tak operujesz na elementach kontenera zamiast bezpośrednio za pomocą iteratorów/operatora[]. Tutaj masz referencje więc praktycznie nie robi to różnicy. Już pomijając optymalizacje kompilatora który jeszcze bardziej zmniejsza różnice między taką pętlą a "klasyczną". Być może i ostatecznie nie różnią się niczym, ale nie wiem. Poza tym, tylko zapisem.

Answer 2

Ja to bym zrobił na liście. Szybciej niż na liście się i tak chyba nie da.