Re: Performance: approach of reducing loops

t.lehmann@rtsgroup.net wrote:


Hi t!


I get:

$ g++ --version
g++ (GCC) 3.4.4 (cygming special) (gdc 0.12, using dmd 0.125)
Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.

$ g++ -O0 pairs.cc -o pairs.exe && pairs.exe
1999000 1999000
gen1: 5890
gen2: 5844

$ g++ -O1 pairs.cc -o pairs.exe && pairs.exe
1999000 1999000
gen1: 3438
gen2: 3421

$ g++ -O2 pairs.cc -o pairs.exe && pairs.exe
1999000 1999000
gen1: 2421
gen2: 2345

$ g++ -O3 pairs.cc -o pairs.exe && pairs.exe
1999000 1999000
gen1: 2422
gen2: 2390

(i also get very similar results with g++ 4.1.0 on linux)

With the following code (its yours with only the timing code added):

-----------------------------------------------------------
#include <iostream>
#include <set>
#include <time.h>

typedef std::pair<int, int> Pair;
typedef std::set<Pair> PairSet;

struct PairIterator
{
    PairIterator(const int limit)
        : _limit(limit), _pair(1,1) /*_a(1), _b(1)*/ {}

    inline operator bool () {
        if (_pair.second == _limit) { //_b == _limit)
            ++_pair.first; //++_a;
            _pair.second = _pair.first + 1; //_b = _a + 1;
        }
        else ++_pair.second; //++_b;
        return _pair.second <= _limit; //_b <= _limit;
    }

    inline const Pair& key() const { return _pair; }

    int _limit;
    Pair _pair; // int _a; int _b;
};

void gen1(PairSet& pairs, const int limit) {
    int a, b;
    for (a = 1; a <= limit; ++a)
        for (b = a+1; b <= limit; ++b)
            pairs.insert(std::make_pair(a,b));
}

void gen2(PairSet& pairs, const int limit) {
    PairIterator it(limit);
    while (it) pairs.insert(it.key());
}

int main() {
  int limit = 2000;
  PairSet p1, p2;

  clock_t t1 = clock();
  gen1(p1, limit);
  clock_t t2 = clock();
  gen2(p2, limit);
  clock_t t3 = clock();

  std::cout << p1.size() << " " << p2.size() << std::endl;
  std::cout << "gen1: " << (t2 - t1) << std::endl;
  std::cout << "gen2: " << (t3 - t2) << std::endl;

  return 0;
}
-----------------------------------------------------------

cheers, first post by the way :)

Simon

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]