Benutzer-Werkzeuge

Webseiten-Werkzeuge


playground:code:containers

Containers

Geschwindigkeitstest verschiedener Container der C++-Standardbibliothek.

Programmcode

/* cspeed.cpp: container speed test
 *
 * Copyright (C) 2007  Alexander Heinlein
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License  
 * as published by the Free Software Foundation; either version 3
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
 * USA
*/
 
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <iterator>
#include <ctime>
#include <sstream>
 
bool get_line(int& line)
{
 static std::ifstream file("input.txt", std::ios::in);
 
 if (file.eof())
 {
    file.clear(); 
    file.seekg(0);
 }
 
 if (!file)
 {
    std::cerr << "input file \"input.txt\" not found!" << std::endl;
    return false;
 }
 
 std::string str;
 getline(file, str);
 
 if (!file.eof())
 {
    line = atoi(str.c_str());
    return true;
 }
 
 return false;
}
 
void test_deque()
{
    std::deque<int> deq;
    int i;
 
    std::cout << "filling double ended queue" << std::endl;
    while (get_line(i))
    {
        deq.push_back(i);
    }
 
    std::cout << "removing elements" << std::endl;
    while (deq.size() > 0)
    {
        i = rand() % deq.size();
        deq.erase(deq.begin() + i);
    }
}
 
void test_list()
{
    std::list<int> list;
    int i;
 
    std::cout << "filling list" << std::endl;
    while (get_line(i))
    {
        list.push_back(i);
    }
 
    std::cout << "removing elements" << std::endl;
    std::list<int>::iterator it;
    while (list.size() > 0)
    {
        /* std::list has no random access iterator,
           we have to use std::advance instead */
        it = list.begin();
        i = rand() % list.size();
        std::advance(it, i);
        list.erase(it);
    }
}
 
void test_set()
{
    std::set<int> set;
    int i;
 
    std::cout << "filling set" << std::endl;
    while (get_line(i))
    {
        set.insert(i);
    }
 
    std::cout << "removing elements" << std::endl;
    std::set<int>::iterator it;
    while (set.size() > 0)
    {
        it = set.begin();
        i = rand() % set.size();
        std::advance(it, i);
        set.erase(it);
    }
}
 
void test_multiset()
{
    std::multiset<int> mset;
    int i;
 
    std::cout << "filling multiset" << std::endl;
    while (get_line(i))
    {
        mset.insert(i);
    }
 
    std::cout << "removing elements" << std::endl;
    std::multiset<int>::iterator it;
    while (mset.size() > 0)
    {
        it = mset.begin();
        i = rand() % mset.size();
        std::advance(it, i);
        mset.erase(it);
    }
}
 
void test_vector()
{
    std::vector<int> vec;
    int i;
 
    std::cout << "filling vector" << std::endl;
    while (get_line(i))
    {
        vec.push_back(i);
    }
 
    std::cout << "removing elements" << std::endl;
    while (vec.size() > 0)
    {
        i = rand() % vec.size();
        vec.erase(vec.begin() + i);
    }
}
 
void usage(char* cmd)
{
 std::cout << "Usage: " << cmd << " [OPTION]\n"
           << " " << cmd << " will fill the specified container type"
           << " with elements from\n"
           << " `input.txt' and remove them randomly\n\n"
           << " available containers:\n"
           << "  -d   double ended queue\n"
           << "  -l   list\n"
           << "  -m   multiset\n"
           << "  -s   set\n"
           << "  -v   vector\n";
}
 
int main (int argc, char* argv[])
{
 srand(time(NULL));
 
 if (argc != 2)
 {
    usage(argv[0]);
    return 1;
 }
 
 std::istringstream stream(argv[1]);
 std::string str = stream.str();
 
 if      (str == "-d")
    test_deque();
 else if (str == "-l")
    test_list();
 else if (str == "-m")
    test_multiset();
 else if (str == "-s")
    test_set();
 else if (str == "-v")
    test_vector();
 else
    usage(argv[0]);
 
 return 0;
}

Download

Erklärung

Getestet werden die fünf Container set, multiset, vector, dequeu und list. Dafür werden diese zu erst mit 100.000 Elementen vom Typ Integer gefüllt (aus der Datei input.txt) und anschließend solange zufällig gewählte Elemente gelöscht, bis die Container wieder leer sind.

Containertypen

deque

deque steht für double ended queue, also eine Warteschlange, bei der man sowohl am Anfang als auch am Ende Elemente entfernen und hinzufügen kann.

list

list stellt eine doppelt verkettete Liste dar.

set

Ein set ist eine Menge an sortierten Schlüsseln. Jeder Schlüssel kann dabei nur einmal vorkommen.

multiset

Ein multiset ist ein set, erlaubt aber mehrere identische Schlüssel.

vector

vector ist ein dynamisches Array.

Testergebnisse

System

Compiler

  • g++ (GCC) 4.1.3 20070718 (prerelease) (Debian 4.1.2-14)

CPU

  • AMD Athlon™ XP 1800+

Laufzeiten

Container Test #1 Test #2 Test #3 Durchschnitt
std::set 0m04.933s 0m04.973s 0m05.026s 0m04.977s
std::vector 0m07.093s 0m06.646s 0m06.950s 0m06.896s
std::deque 1m12.909s 1m12.152s 1m12.209s 1m12.423s
std::multiset 9m25.066s 9m24.926s 9m23.543s 9m24.512s
std::list 11m02.923s 11m03.570s 11m05.120s 11m03.871s
playground/code/containers.txt · Zuletzt geändert: 2014/03/01 17:13 (Externe Bearbeitung)