Schneller Zugriff aus 2dim Elemente



  • Hallo,

    ich habe folgendes Problem:

    Ich habe eine große Matrix, in der Entfernungen zwischen Städten/Orten
    enthalten sind (Zeilen = Ausgangsorte, Spalten = Zielorte, wobei Ausgangsorte != Zielorte, also 2 verschiedenen Mengen).

    Nun möchte ich möglichst schnell und effizient auf ein Matrixelement zugreifen.

    Bisher habe ich mir ein kleines Klassenelement "Verbindung" geschrieben, welches aus 2 strings (Ausgangsort, Zielort) und 1 int (Entfernung zwischen den 2 Orten) besteht. Die Entfernungsmatrix habe ich dann mit einem Tool in eine Liste umgewandelt und dann als Textdatei gespeichert. Diese habe ich dann in C++ in einen vector<Verbindung> eingelesen.

    Wie kann ich nun gezielt auf Entfernungswerte zugreifen?

    Beispielsweise brauche ich in einer Funktion die Entfernung zwischen Stuttgart und Köln. Bisher bin ich dann immer mit mehreren for und if - Schleifen
    durch meinen vector gelaufen und habe Elemente miteinander verglichen (if Ausgangsort == Stuttgart && Zielort == Köln, dann gebe int Wert vom vector<Verbindung> zurück).

    Das funktioniert soweit, ist aber für meine riesige Matrix und der Vielzahl zur berechnenden Elemente sicherlich ineffizient 😉

    Gibt es in der STL (oder sonstwo) andere (bessere) Möglichkeiten?
    Ich habe mich bereits kurz mit "maps" beschäftigt. Dort bräuchte ich aber dann statt einem Schlüssel 2 Schlüssel (string, string). Cool wäre, wenn es sowas geben würde wie

    map Entfernung<string,string, int> mit 2 Schlüsseln, so dass man
    einfach durch aufruf von
    Entfernung[Stuttgart,Köln] den richtigen int-Wert ausgegeben bekommt. 😃

    Gibt es eine solche Möglichkeit mit 2 Schlüsseln in einer map bzw. gibt es
    andere / bessere Möglichkeiten, mein Problem effizient zu implementieren?

    Ich freue mich auf Antworten und Anregungen 🙂

    Besten Dank!
    Thomas


  • Mod

    map<string, size_t> welche zu einem gegebenen String die passende Zeile/Spalte in der Matrix kennt.



  • Ich vermute, dass eine unordered_map<string, size_t> besser geeignet wäre (gerade, wenn die Matrix sehr groß wird). Das hängt aber davon ab, woher die Bezeichner stammen -- mit Hashes macht man sich potentiell immer verwundbar, wenn die Daten aus einer nicht vertrauenswürdigen Quelle kommen.

    Besser noch wäre ein TST oder eine andere trie-artige Datenstruktur; diese ist aber in der Standardbibliothek nicht vorhanden. Es gibt in Boost.Spirit eine Klassenvorlage, die man dafür missbrauchen könnte: http://www.boost.org/doc/libs/1_51_0/libs/spirit/doc/html/spirit/qi/reference/string/symbols.html



  • Thomas1982 schrieb:

    Cool wäre, wenn es sowas geben würde wie

    map Entfernung<string,string, int> mit 2 Schlüsseln, so dass man
    einfach durch aufruf von
    Entfernung[Stuttgart,Köln] den richtigen int-Wert ausgegeben bekommt. 😃

    Gibt es eine solche Möglichkeit mit 2 Schlüsseln in einer map bzw. gibt es
    andere / bessere Möglichkeiten, mein Problem effizient zu implementieren?

    No, es gibt da z.B. std::pair .
    Also

    std::map<std::pair<std::string, std::string>, int> meineMap;
    // ...
    int entfernung = meineMap[std::make_pair("Stuttgart", "Köln")]; // Baum, alter
    


  • Neues Ziel für Heute: Ich bastle eine Trimap.



  • Sone schrieb:

    Neues Ziel für Heute: Ich bastle eine Trimap.

    Da bin ich mal gespannt 😋



  • out schrieb:

    Sone schrieb:

    Neues Ziel für Heute: Ich bastle eine Trimap.

    Da bin ich mal gespannt 😋

    Das dauert noch 😞
    Momentan bin ich bei equal_range/lower_bound/upper_bound



  • Ein Gerüst hab' ich schon: http://ideone.com/N58aM

    Jetzt muss das alles noch umgeschrieben werden.



  • Hallo,

    vielen Dank für die Antworten bisher:

    also die maps mit einem pair als Schlüssel habe ich glaub ich gebastelt bekommen:

    // map.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
    //

    #include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <fstream>

    using namespace std;

    int main()
    {
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    // maps mit <pair,int> (06.10.2012)
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    map<pair<string, string>, int> Verbindung;
    Verbindung.insert(make_pair(make_pair("Dortmund", "Hannover"), 123)); // manuell einlesen

    // - - - - - - - - - - - - - - - aus Textdatei einlesen - - - - - - - - - - - - - - - - - - - - - -
    fstream f("Testenternungen.txt");
    while (! f.eof())
    {
    string d1, d2;
    int d3;
    f >> d1 >> d2 >> d3;
    Verbindung.insert(make_pair(make_pair(d1,d2), d3));
    }

    // - - - - - - - - - - - - - - - alle Entfernungen ausgeben - - - - - - - - - - - - - - - - - - - -
    for (map<pair<string, string>,int>::const_iterator it=Verbindung.begin(); it!=Verbindung.end(); ++it)
    {
    cout << "[" << it->first.first << " , " << it->first.second << "] = " << it->second << endl;
    }

    // - - - - - - - - - - - - - - - auf ein Element zugreifen- - - - - - - - - - - - - - - - - - - - -

    string Ausgangsort = "Dortmund";
    string Zielort = "Hannover";

    map<pair<string, string>,int>::const_iterator it = Verbindung.find(make_pair(Ausgangsort,Zielort));
    cout << "Entfernung zwischen " << Ausgangsort << " und " << Zielort << " = " << it->second << endl;

    getchar();

    return 0;
    }

    Welche Vorteile hat den eine Trimap gegenüber einer map<pair<string,string>, int>?



  • Der Zugriff auf die anderen beiden Elemente eine Trios über die Suche nach einem der Element des Trios. Zumindest wenn ich das jetzt richtig deute.

    tri_map.insert( make_trio<A,B,C>( "a", "b", "c" ) );
    assert( tri_map.get<0>["a"] == make_pair<B,C>( "b", "c" ) );
    assert( tri_map.get<1>["b"] == make_pair<A,C>( "a", "c" ) );
    assert( tri_map.get<2>["c"] == make_pair<A,B>( "a", "b" ) );
    

    oder so ähnlich... mach das mal mit der map! 🙂



  • Decimad schrieb:

    Der Zugriff auf die anderen beiden Elemente eine Trios über die Suche nach einem der Element des Trios. Zumindest wenn ich das jetzt richtig deute.

    tri_map.insert( make_trio<A,B,C>( "a", "b", "c" ) );
    assert( tri_map.get<0>["a"] == make_pair<B,C>( "b", "c" ) );
    assert( tri_map.get<1>["b"] == make_pair<A,C>( "a", "c" ) );
    assert( tri_map.get<2>["c"] == make_pair<A,B>( "a", "b" ) );
    

    oder so ähnlich... mach das mal mit der map! 🙂

    Oh, ich hab das missverstanden! Ich hab die ganze map falsch gemacht 😞

    Edit: Aber jetzt hab' ich auch keinen Bock mehr.



  • Oje, es tut mir Leid! 😞



  • Decimad schrieb:

    Oje, es tut mir Leid! 😞

    Haha, entspann dich 😃
    Jetzt mach ich's richtig. Da hat sich aber wetten noch keiner rangetraut 😃


  • Mod

    Schnell mit multi_index_container zusammengeschrieben

    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/global_fun.hpp>
    #include <boost/multi_index/composite_key.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <iterator>
    #include <iostream>
    #include <string>
    
    using namespace boost::multi_index;
    
    struct distance_map
    {
    
        struct from_tag {};     typedef std::string from;
        struct to_tag {};       typedef std::string to;
        struct path_tag {};
        struct distance_tag {}; typedef int distance_type;
    
        typedef std::tuple<from, to, distance_type> tuple_type;
    
        struct value_type : tuple_type
        {
            value_type(from a, to b, distance_type c) : tuple_type{ a, b, c } {}
        };
    
        typedef boost::multi_index_container<value_type, indexed_by<
            ordered_non_unique<tag<from_tag>,     global_fun<const tuple_type&, const std::tuple_element<0, tuple_type>::type&, std::get<0>>>,
            ordered_non_unique<tag<to_tag>,       global_fun<const tuple_type&, const std::tuple_element<1, tuple_type>::type&, std::get<1>>>,
            ordered_non_unique<tag<distance_tag>, global_fun<const tuple_type&, const std::tuple_element<2, tuple_type>::type&, std::get<2>>>,
            ordered_unique<tag<path_tag>, composite_key<
                value_type,
                global_fun<const tuple_type&, const std::tuple_element<0, tuple_type>::type&, std::get<0>>,
                global_fun<const tuple_type&, const std::tuple_element<1, tuple_type>::type&, std::get<1>>
            >>
        >> type;
    };
    
    std::ostream& operator<<(std::ostream& s, const distance_map::value_type& v)
    {
        return s << std::get<0>(v) << '\t' << std::get<1>(v) << '\t' << std::get<2>(v);
    }
    
    int main()
    {
        distance_map::type m;
    
        m.insert(distance_map::value_type{ "A", "B", 10 });
        m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
        m.insert(distance_map::value_type{ "B", "A", 11 });
        m.insert(distance_map::value_type{ "A", "A", 0 });
    
        {
            std::cout << "from = A\n";
            auto range = m.get<distance_map::from_tag>().equal_range("A");
            std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
        }
        {
            std::cout << "to = A\n";
            auto range = m.get<distance_map::to_tag>().equal_range("A");
            std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
        }
        {
            std::cout << "distance = 10\n";
            auto range = m.get<distance_map::distance_tag>().equal_range(10);
            std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
        }
        {
            std::cout << "path = A...B\n";
            auto range = m.get<distance_map::path_tag>().equal_range(boost::make_tuple("A", "B"));
            std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
        }
    }
    


  • Zerstör' doch nicht den Spaß, camper 😞

    Ich seh's gerade vor mir, der Camper oben auf dem Dach mit seinem Spoilerrifle 😃



  • camper ist so ein Gott .

    Edit: Wo camper schon mal da ist, ich hab so angefangen:

    #include <tuple>
    #include <set>
    
    template<typename Type1,
             typename Type2,
             typename Type3,
             typename Compare = std::less<std::tuple<Type1,
                                                     Type2,
                                                     Type3>>,
             typename Allocator = std::allocator<std::tuple<Type1,
                                                            Type2,
                                                            Type3>>>
    class trimap
    {
    public:
    
            typedef Type1 key_type_1;
            typedef Type2 key_type_2;
            typedef Type3 key_type_3;
    
            typedef std::tuple<key_type_1,
                               key_type_2,
                               key_type_3> value_type;
    
    private:
    
            typedef std::set<value_type,
                             Compare,
                             Allocator> array_type;
            array_type mArray;
    
    public:
    
            typedef typename array_type::size_type size_type;
    
            typedef typename Allocator::pointer pointer;
            typedef typename Allocator::const_pointer const_pointer;
            typedef typename Allocator::reference reference;
            typedef typename Allocator::const_reference const_reference;
    
            typedef typename array_type::iterator iterator;
            typedef typename array_type::const_iterator const_iterator;
            typedef typename array_type::reverse_iterator reverse_iterator;
            typedef typename array_type::const_reverse_iterator const_reverse_iterator;
    
            typedef Allocator allocator_type;
            typedef Compare key_compare;
            typedef typename Allocator::difference_type difference_type;
    
            explicit trimap( const Compare& comp = Compare(),
                             const Allocator& alloc = Allocator() ):
                    mArray(comp, alloc) {}
    
            explicit trimap( const Allocator& alloc = Allocator() ):
                    mArray(alloc) {}
    
            template< class InputIt >
            trimap( InputIt first, InputIt last,
                    const Compare& comp = Compare(),
                    const Allocator& alloc = Allocator() ):
                    trimap(comp, alloc)
            {
                    insert(first, last);
            }
    
            trimap( const trimap& other, const Allocator& alloc ):
                    trimap(alloc)
            {
                    *this = other;
            }
    
            trimap(trimap&&) = default;
            trimap(trimap&& other, const Allocator& alloc ):
                    trimap(alloc)
            {
                    operator=(std::forward<trimap>(other));
            }
            trimap(trimap const&) = default;
    
            trimap( std::initializer_list<value_type> init,
                    const Compare& comp = Compare(),
                    const Allocator& alloc = Allocator() ):
                    trimap(comp, alloc)
            {
                    mArray = std::move(init);
            }
    
            trimap& operator=( trimap const& other ) = default;
            trimap& operator=( trimap&& other ) = default;
    
            void swap(trimap& other)
            {
                    mArray.swap(other.mArray);
            }
    
            allocator_type get_allocator() const {return mArray.get_allocator();}
            key_compare key_comp() const {return mArray.key_comp();}
    
            void clear(){mArray.clear();}
            bool empty() const { return mArray.empty();}
            size_type size() const { return mArray.size();}
            size_type max_size() const { return mArray.max_size();}
    
            iterator begin() {return mArray.begin();}
            const_iterator begin() const {return mArray.begin();}
            iterator end() {return mArray.end();}
            const_iterator end() const {return mArray.end();}
            reverse_iterator rbegin() {return mArray.rbegin();}
            const_reverse_iterator rbegin() const {return mArray.rbegin();}
            reverse_iterator rend() {return mArray.rend();}
            const_reverse_iterator rend() const {return mArray.rend();}
    
            const_iterator cbegin() const {return mArray.cbegin();}
            const_iterator cend() const {return mArray.cend();}
            const_reverse_iterator crbegin() const {return mArray.crbegin();}
            const_reverse_iterator crend() const {return mArray.crend();}
    };
    

    Hat's noch Sinn weiterzumachen? Oder gibt es von der Idee her noch was besseres (neben dem MultiIndex-Container)?



  • camper schrieb:

    distance_map::type m;
    
        m.insert(distance_map::value_type{ "A", "B", 10 });
        m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
        m.insert(distance_map::value_type{ "B", "A", 11 });
        m.insert(distance_map::value_type{ "A", "A", 0 });
    

    Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.


  • Mod

    hinundher schrieb:

    camper schrieb:

    distance_map::type m;
    
        m.insert(distance_map::value_type{ "A", "B", 10 });
        m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
        m.insert(distance_map::value_type{ "B", "A", 11 });
        m.insert(distance_map::value_type{ "A", "A", 0 });
    

    Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

    Aber andere Richtung.



  • hinundher schrieb:

    camper schrieb:

    distance_map::type m;
    
        m.insert(distance_map::value_type{ "A", "B", 10 });
        m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
        m.insert(distance_map::value_type{ "B", "A", 11 });
        m.insert(distance_map::value_type{ "A", "A", 0 });
    

    Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

    Genau das hab ich mit meiner Map zu lösen versucht (und geschafft).



  • camper schrieb:

    hinundher schrieb:

    camper schrieb:

    distance_map::type m;
    
        m.insert(distance_map::value_type{ "A", "B", 10 });
        m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
        m.insert(distance_map::value_type{ "B", "A", 11 });
        m.insert(distance_map::value_type{ "A", "A", 0 });
    

    Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

    Aber andere Richtung.

    Na und? Es zählt doch die Kombination.


Log in to reply