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

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.

> ... 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).

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

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?

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]);

	}

}

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);

    }

}

#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));

    }

}

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.

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

}

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

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ě.

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

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

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