Efektivita iterátorů – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Efektivita iterátorů – C / C++ – Fórum – Programujte.comEfektivita iterátorů – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
vdolek0
Newbie
30. 4. 2010   #1
-
0
-

Dřív jsem se někde dočetl, že práce s kontejnery (stl) pomocí iterátorů je rychlejší, než pomocí indexů. Bral jsem to jako fakt, ale teď jsem měl za úkol napsat straight selection sort arlgoritmus, a tak jsem ho napsal jak na základě iterátorů, tak i indexů. Když ale měřím časy obou verzí, je vždy rychlejší ta, která pracuje s indexy (přibližně 2 krát).
Zajíalo by mě, jak to tedy je s efektivitou těch iterátorů, jestli v tom třeba není nějaký fígl.

Nahlásit jako SPAM
IP: 84.42.206.–
Reklama
Reklama
AdamHlavatovic0
Stálý člen
1. 5. 2010   #2
-
0
-

> ... Zajíalo by mě, jak to tedy je s efektivitou těch iterátorů, jestli v tom třeba není nějaký fígl.
V idealnom pripade budu rovnako rychle ako priame indexovanie (za predpokladu, ze danny kontajner takyto pristup k prvkom podporuje).

Nahlásit jako SPAM
IP: 94.229.32.–
vdolek0
Newbie
1. 5. 2010   #3
-
0
-

To AdamHlavatovic : Ok, díky za odpověď. Mi to bylo divný, protože jsem bral za fakt, že iterátory jsou rychlejší.

Nahlásit jako SPAM
IP: 84.42.206.–
Quiark0
Věrný člen
1. 5. 2010   #4
-
0
-

To je takové divné tvrzení, protože neobsahuje dostatečně specifické informace. Především o jaký kontejner se jedná? Jsou v překladači zapnuté optimalizace? Jde o sekvenční procházení nebo random access?

Nahlásit jako SPAM
IP: 90.178.173.–
vdolek0
Newbie
2. 5. 2010   #5
-
0
-

No, porovnával jsem rychlost těchto dvou algoritmů (jak pro std::vector, tak i pro klasické pole), pro oba případy byl rychlejší ten druhý (indexový).

template <typename T>

void straightSelectionSort(T begin, T end)
{
// i je ukazatel na první položku nesetříděné části
for (T i = begin; i != end - 1; ++i)
{
T min = i;
// je je ukazatel na položku, se kterou se porovnává
for (T j = i + 1; j != end; ++j)
if (*j < *min)
min = j;

if (*min != *i)
swap(*min, *i);
}
}

template <typename T>
void straightSelectionSortIndex(T &container, int size)
{
for (int i = 0; i != size - 1; ++i)
{
int min = i;

for (int j = i + 1; j != size; ++j)
if (container[j] < container[min])
min = j;

if (container[min] != container[i])
swap(container[i], container[min]);
}
}

Nahlásit jako SPAM
IP: 84.42.206.–
ondra.holub+1
Stálý člen
6. 5. 2010   #6
-
0
-

Ono také záleží na tom, jak se to použití iterátorů napíše. Např. po výměně std::swap za std::iter_swap už to v mém případě (na std::vector<int>) běží rychleji s iterátory:

template <typename T>

void straightSelectionSort2(const T& begin, const T& end)
{
if (begin == end)
return;

// i je ukazatel na první položku nesetříděné části
for (T i = begin; i != end - 1; ++i)
{
T min = i;
// je je ukazatel na položku, se kterou se porovnává
for (T j = i + 1; j != end; ++j)
if (*j < *min)
min = j;

if (*min != *i)
std::iter_swap(min, i);
}
}
Ale stejně bych to napsal takto:
#include <algorithm>


template <typename T>
void straightSelectionSort3(const T& begin, const T& end)
{
if (begin == end)
return;

// i je ukazatel na první položku nesetříděné části
for (T i = begin; i != end - 1; ++i)
{
std::iter_swap(i, std::min_element(i, end));
}
}
Při rozhodování o tom, jestli udělat tu výměnu vždy nebo tam nechat tu podmínku může záležet i na tom, co je obsahem kontejneru. Někdy je lepší tam nechat tu podmínku a někdy to prohodit vždy bez podmínky.

Nahlásit jako SPAM
IP: 194.138.12.–
vdolek0
Newbie
7. 5. 2010   #7
-
0
-

No, tak u mě to rychlejší není, ať tam dám std::swap, std::iter_swap nebo svůj swap, tak se rychlost nezmění. U mě je to přes ty iterátory pomalejší (VS2008). Je to jedno, jen mě to zajímalo.

Nahlásit jako SPAM
IP: 84.42.206.–
ondra.holub+1
Stálý člen
7. 5. 2010   #8
-
0
-

To vdolek : Tak to asi bude zrovna slabé místo implementace STL od Microsoftu. Nechtělo se mi tomu věřit, tak jsem zkusil tento program:

#include <algorithm>

#include <cstdlib>
#include <vector>

template <typename T>
void straightSelectionSort2(const T& begin, const T& end)
{
if (begin == end)
return;

for (T i = begin; i != end - 1; ++i)
{
T min = i;
// je je ukazatel na položku, se kterou se porovnává
for (T j = i + 1; j != end; ++j)
if (*j < *min)
min = j;

if (*min != *i)
std::iter_swap(min, i);
}
}

template <typename T>
void straightSelectionSortIndex(T &container, int size)
{
for (int i = 0; i != size - 1; ++i)
{
int min = i;

for (int j = i + 1; j != size; ++j)
if (container[j] < container[min])
min = j;

if (container[min] != container[i])
std::swap(container[i], container[min]);
}
}

template <typename T>
void straightSelectionSort3(const T& begin, const T& end)
{
if (begin == end)
return;

// i je ukazatel na první položku nesetříděné části
for (T i = begin; i != end - 1; ++i)
{
std::iter_swap(i, std::min_element(i, end));
}
}

int main()
{
const size_t SIZE = 100000;

std::vector<int> v;
v.reserve(SIZE);

srand(1);

for (size_t i = 0; i < SIZE; ++i)
v.push_back(rand());

// straightSelectionSortIndex(v, v.size()); // varianta index
// straightSelectionSort2(v.begin(), v.end()); // varianta sort2
straightSelectionSort3(v.begin(), v.end()); // varianta sort3
}
Přeložil jsem to vždy jenom s jednou variantou řazení (jeden z poslednách tří řádků těla main). Výsledky gcc [g++.exe (TDM-2 mingw32) 4.4.1] (Přeloženo s -O3):

index .... cca 24s
straightSelectionSort2 ... cca 15.4s
straightSelectionSort3 ... cca 9.7s

Visual studio 2008 Express (přeloženo s /O2):

index ... cca 30s
straightSelectionSort2 ... cca 1m28s
straightSelectionSort3 ... cca 15.3s

Visual studio 2010 Express (přeloženo s/O2):

index ... cca 30s
straightSelectionSort2 ... cca 1m28s
straightSelectionSort3 ... cca 15.4s

Takže obě verze Visual Studia generují v tomto případě rovnocenný kód. Ovšem zdržení ve variantě straightSelectionSort2 je fascinující. Z tohoto jediného izolovaného příkladu nejde sice vyvodit závěr, že Visual Studio generuje horší kód, než gcc, ale je vidět, že s implementací STL Microsoft pořád bojuje. (Svědčí o tom i množství warningů, pokud použiju jakýkoliv header z STL - ty warningy jsou přímo na jejich kód.)

Takže na původní otázku, jestli iterátory jsou rychlejší než indexy lze asi dát jenom jednu odpověď: Jak kdy a jak ve kterém překladači.

Nahlásit jako SPAM
IP: 89.203.160.–
Quiark0
Věrný člen
8. 5. 2010   #9
-
0
-

Netuším sice, jak se ti tam podařilo dostat ty warningy, ale jinak mi časy ve MSVC 2008 Express vyšly podobně.

Použil jsem tento kód: http://gist.github.com/394469 který rovnou spustí všechny tři variany a změří čas

MSVC++ 2008 Express
standardní Release konfigurace
38.61
101.344
15.641

GCC 3.4.4 v cygwinu
g++ speed.cpp -o speed -O3
18.031
17.922
17.766

Nahlásit jako SPAM
IP: 90.178.173.–
vdolek0
Newbie
9. 5. 2010   #10
-
0
-

Tak to je zajímavé, vždy jsem si myslel, že nejideálnější kompilátor pro windows je Visual Studio, ale asi to není vždy tak úplně pravda. Jinak časy mi vyšly taky podobně.

Nahlásit jako SPAM
IP: 84.42.206.–
Jura
~ Anonymní uživatel
634 příspěvků
10. 5. 2010   #11
-
0
-

Zdravím,

vzhledem k tomu, že mě překvapily ty časy, tak jsem si příklad od Quiarka vyzkoušel na různých verzích visual studia. A musím říct, že mě docela překvapuje rozdíl mezi VSTS 2008 a VS 2010 Professional. Zde jsou výsledky(všechno release s /O2):

VC++ 6.0 Introductury Edition:
110.969
23.828
22.531

VSTS 2008:
26
69.578
6.172

VS 2010 Professional
11.875
6.125
6.156

Nahlásit jako SPAM
IP: 85.207.192.–
KIIV+42
God of flame
10. 5. 2010   #12
-
0
-

tak sem zkusil taktez.. jen pomoci g++ na linuxu ve virtualnim pc:)

$ g++ -O3 -o test test.cpp

$ ./test
11.95
11.59
5.93
$ g++ -O2 -o test test.cpp
$ ./test
7.64
7.25
5.88
$ g++ -O1 -o test test.cpp
$ ./test
14.71
12.74
12.83
$ g++ -O0 -o test test.cpp
$ ./test
50.57
80.13
78.36
$ g++ --version
g++ (Ubuntu 4.4.1-4ubuntu9) 4.4.1

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
vdolek0
Newbie
11. 5. 2010   #13
-
0
-

Tak u mě jsou časy:

VS 2008:
20.482
57.039
4.039
VS 2010
9.648
4.825
4.887

Vypadá to, že na tom Microsoft zapracoval.

g++ -O3 -o:
12.19
5.79
6.36

g++ -O2 -o:
8.19
7.72
6.22

Nahlásit jako SPAM
IP: 85.161.40.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 67 hostů

Podobná vlákna

Efektivita mysql — založil spartan13

Efektivita práce — založil Šťouchal

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý