On Tue, 13 Jan 2004 14:26:01 +0100, Daniel Heiserer
<Daniel.Heiserer@bmw.de> wrote:
[color=blue]
>[color=green][color=darkred]
>> >I used a unique associative container such as:
>> >//---------------
>> >map<vector<int>,double> X;
>> >//---------------
>> >
>> >In general I fill X with millions of entries.[/color]
>>
>> What code do you use to add element? There may be a more efficient
>> way.[/color]
>
>vector<int> a;
>double b;
>X[a]=b;
>// or
>X[a]+=b;[/color]
Ok, first improvement is to insert using:
X.insert(mymaptype::value_type(a, b));
[color=blue]
>[color=green][color=darkred]
>> >Sorting plays no role for me. All I need is uniqueness
>> >of the keys and speed when inserting them.[/color]
>>
>> Why are you using vector<int> as your key? If there a fixed maximum
>> length of vector? How do you create the vector? You would probably get
>> an improvement from a custom key class.[/color]
>
>foreach of my maps the vectors have the same length, but I want to
>use different maps. e.g. one with vectors of size 3 others with
>longer or shorter ones. Before I "add" my element I "X.resize(length)"
>the vectors.
>map<vector<int>,double> X; // vector length 3
>map<vector<int>,double> Y; // vector lenght 5
>
>Of course this distinction has to be made during runtime.
>How much would a
>
>hash_map<int[3],double> X;
>
>speed that up? And how much memory would I save?[/color]
Well, the above is illegal (arrays aren't copyable), but you might try
this:
#include <cstddef>
#include <algorithm>
template <std::size_t Length>
class Key
{
int m_data[Length];
public:
static std::size_t const SIZE = Length;
Key()
{
//0 initialize
std::set(m_data, m_data + SIZE, 0);
}
int& operator[](std::size_t i)
{
assert(i < SIZE);
return m_data[i];
}
int const& operator[](std::size_t i) const
{
assert(i < Length);
return m_data[i];
}
friend bool operator<(Key const& lhs, Key const& rhs)
{
return std::lexicographical_compare(
lhs.m_data, lhs.m_data + SIZE,
rhs.m_data, rhs.m_data + SIZE);
}
friend bool operator==(Key const& lhs, Key const& rhs)
{
return std::equal_range(
lhs.m_data, lhs.m_data + SIZE,
rhs.m_data, rhs.m_data + SIZE);
}
//add anything required for convenience.
};
std::map<Key<3>, double> m;
That would add a pretty big speedup at insert time (in terms of
constant factor), and an even bigger memory saving. Key<3> takes up
12-16 bytes whereas std::vector<int> takes up 16 bytes before you even
consider the contents of the vector (another 16 at least, if not more
will allocation overhead). Using the above should roughly halve the
memory requirements and provide a major speed increase.
[color=blue]
>[color=green][color=darkred]
>> >At the end I retrieve them using iterators from the beginning
>> >to the end. Which should lead to constant complexity.
>> >
>> >Memory requirement is important but less then speed.
>> >
>> >Unfortunately the used "map" is too slow.
>> >I need a faster implementation.
>> >
>> >I found hash_map as an alterantive, but it does not work
>> >by simply replacing "map" with "hash_map".[/color]
>>
>> No, you need to provide a hashing function at least.[/color]
>
>How do I define one for vectors?[/color]
For your vectors you could have something like:
std::size_t hash(std::vector<int> const& v)
{
return std::accumulate(v.begin(), v.end(), std::size_t(0));
}
That's a bad hashing algorithm, so you may want to read up on hashing
algorithms.
[color=blue][color=green]
>> GCC comes with an implementation <ext/hash_map>. I don't know how good
>> it is. Docs are here:
>>
>>
http://gcc.gnu.org/onlinedocs/libstd...t/howto.html#1
>>
>> You might be able to make std::map fast enough if you optimize your
>> use of it...[/color]
>
>Well a suggestion might be useful ;-)
>Again: The time critical part is insertion and therefore checking
>for duplicate ones. In maybe 50% of the cases the next insertion
>"might" be "close" to the previous one so this might help to speed it
>up.
>After that I only retrieve all pairs from the beginning to the end
>which should be of complexity O(1) using the iterators.[/color]
Iteration over the whole container is O(n). Inserting n elements is
O(n log n).
[color=blue]
>I would appreciate if I could use as much of the standard container
>functions as possible and avoid writing new templates and classes.[/color]
The standard containers are building blocks and in many cases aren't
the optimal solution. If your problem definitely requires these
multi-int keys and performance isn't good enough using the standard
approach, then first trying the Key class and then trying the Key
class in a hash_map (writing a hash function for Key) is going to work
best.
Tom
C++ FAQ:
http://www.parashift.com/c++-faq-lite/
C FAQ:
http://www.eskimo.com/~scs/C-faq/top.html 
