|
hi, I made a little test program, to check the performance of a map compared with a vector.
i'm not sure if the method i've used here for key value pairs using a vector is what you meant ? but using a vector for key value look-ups the way i have is much slower than using a map. Here's the test app :
If you know of a way I could improve the performance, i'd be greatful to know ?, thanks
#include "hr_time.h"
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
struct Object
{
int value;
Object()
{
value = 1;
};
~Object(){};
};
map<int, Object> m;
vector<int> ids;
vector<Object> v;
int main()
{
CStopWatch s;
double time;
int i, value;
for(i = 0; i < 10000; i++)
m.insert(make_pair(i,Object()));
s.startTimer();
for(i = 0; i < 10000; i++)
value = m[i].value;
s.stopTimer();
time = s.getElapsedTime();
for(i = 0; i < 9999; i++)
{
ids.push_back(i);
v.push_back(Object());
}
ids.push_back(20000);
v.push_back(Object());
sort(ids.begin(), ids.end());
int pos;
s.startTimer();
for(i = 0; i < 9999; i++)
{
pos = (int)(lower_bound(ids.begin(), ids.end(), i) - ids.begin());
value = v[pos].value;
}
pos = (int)(lower_bound(ids.begin(), ids.end(), 20000) - ids.begin());
value = v[pos].value;
s.stopTimer();
time = s.getElapsedTime();
return 0;
}
|
|
|
|
|
I meant use a single vector - instead of std::map<KeyType, ValueType> , use std::vector<std::pair<KeyType, ValueType> >
Yes, you need to write special comparison functions to just look at the key, but then you don't need to do any indexing - you can just use the iterators returned by lower_bound.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
I don't understand how to use lower_bound on a vector< pair<keytype, valuetype=""> > ?
if i write lower_bound(v.begin(), v.end(), key) for example what would the key be ?
i'm a bit confused about what you mean by comparison functions to look at the key ?
just so i know we're on the same wavelength, the result i'm looking for is to be able to retrieve a value (object) in an array by using the key associated with that value. so in a pseudo sort of way i'd be able to do this : value = getValueFromVector(key). ?
|
|
|
|
|
Here's a sample program
#include <vector>
#include <algorithm>
#include <iostream>
template <class Key, class Value>
bool CompareKeys(std::pair<Key, Value> const& left,
std::pair<Key, Value> const& right)
{
return left.first < right.first;
}
template <class Key, class Value>
typename std::vector<std::pair<Key, Value> >::const_iterator
Find(std::vector<std::pair<Key, Value> > const& vec, Key const& key)
{
typename std::vector<std::pair<Key, Value> >::const_iterator
found = std::lower_bound(vec.begin(), vec.end(),
std::make_pair(key, Value()),
&CompareKeys<Key, Value>);
if (found != vec.end() && found->first != key) return vec.end();
return found;
}
int main (int argc, char const *argv[])
{
typedef std::pair<std::string, int> MyPair;
std::vector<MyPair> associativeVector;
associativeVector.push_back(std::make_pair("Value", 40));
associativeVector.push_back(std::make_pair("Hello", 10));
associativeVector.push_back(std::make_pair("Test", 30));
associativeVector.push_back(std::make_pair("Goodbye", 20));
std::sort(associativeVector.begin(), associativeVector.end(),
&CompareKeys<std::string, int>);
std::vector<MyPair>::const_iterator found = Find(associativeVector, std::string("Test"));
if (found != associativeVector.end())
{
std::cout << found->first << " = " << found->second << std::endl;
}
else std::cout << "Test not found \n";
found = Find(associativeVector, std::string("NotThere"));
if (found != associativeVector.end())
{
std::cout << found->first << std::endl;
std::cout << found->second << std::endl;
}
else std::cout << "NotThere not found \n";
return 0;
}
The function CompareKeys is a generic key-ordering function, while Find can be used for any sorted vector (so long as the type Value can be default constructed).
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
Thanks very much for posting this.
unfortunatly the performance isn't as fast as using a map.
for getting the values of 10000 elements using associativeVector with int keys, the time taken was in the range of 0.7 - 0.8 seconds compared with 0.06 seconds using a map.
i don't know how the implementation of a map works but it seems to be the fastest method for doing key lookups.
thanks again. Seeing the associative vector method was very useful.
|
|
|
|
|
Mmmm - that seems strange - I moved to that implementation from a std::map purely because its measured performance was better
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
i can't spot any problems with my test code. did you test the performance yourself ?
|
|
|
|
|
In the application where I used an associative vector in place of a map, yes. It gave me a significant improvement.
I'll maybe have a closer look tomorrow
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
cool, if you decide to investigate, i'd like to know what you find.
|
|
|
|
|
For this example, map is faster. But are you using Debug mode for your timings? I got a factor of 12 difference in debug mode, 3 in release mode.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
i forgot switching to release mode might make a difference. Though the map stills performs faster with all speed optimazations enabled in release mode. I tested for a million elements and ten thousand, the speed difference of a vector and map seems more marginal when retrieving the values of a million elements but the map performs faster in both cases.
Here's what I got for ten thousand :
vector map
0.00141 0.00093
0.00139 0.00085
0.00156 0.00085
seconds
|
|
|
|
|
I suspect the other thing that can affect the performance is the key type.
All I know is that for my particular application, maps were slower
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
I guess it's useful to know both methods then.
i'll use a map for the project i'm doing at the moment.
thanks for your help
|
|
|
|
|
This program runs fine except when I try to delete/remove/erase an item as indicated below. No matter what I've tried with erasethe program crashes.
Could someone please help here.
Thanks
Alan Kurlansky
PS. When I cut and pasted some characters got changed. I hope I fixed alll of them.
// MultiMap.cpp : Defines the entry point for the console application.
//
#include <windows.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
using namespace std;
void testmultimap();
#include <tchar.h>
struct ASK {
int ival;
string key;
};
multimap<string, ASK *> mymm2;
multimap<string, ASK *>::iterator iter;
pair<multimap<string, ASK> ::iterator,multimap<string, ASK *>::iterator> ret;
int _tmain(int argc, _TCHAR* argv[])
{
testmultimap();
return 0;
}
//----------------------------------------------------------------------------------------------------------------
void testmultimap()
{
string key;
key.clear();
key.append("a");
ASK * Iptr = new ASK;
Iptr->ival = 10;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("a");
Iptr = new ASK;
Iptr->ival = 20;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("b");
Iptr = new ASK;
Iptr->ival = 30;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("a");
ret = mymm2.equal_range(key);
int cnt(0);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
// delete this single entry
// mymm2.erase(????);
}
printf("\n");
printf("2nd pass after 'a' erase\n");
ret = mymm2.equal_range(key);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
}
printf("\n");
key.clear();
key.append("b");
ret = mymm2.equal_range(key);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
}
printf("\n");
}
//----------------------------------------------------------------------------------------------------------------
|
|
|
|
|
When you modify the contents of a container, the iterators become invalid.
I believe that is what is happening here.
|
|
|
|
|
Thanks! I made a change that reflects what you said and all seems to be working now.
|
|
|
|
|
Hi,
I've run into a problem with the TransparentBlt function.
When I use TransparentBlt with a 24-bit bitmap it correctly masks the specified transparent color, but when I call it for a 4-bit or 8-bit bitmap, it doesn't make that color transparent.
For example, if I have a bitmap with a large rectangle of MAGENTA color and give RGB(255,0,255) as the last parameter in the function, the magenta is still there with a 4-bit bitmap, but it's masked with the 32-bit one.
This problem might be because 256-color/16-color bitmaps don't use RGB values. May be they use palettes somehow.
Can anyone help with that.
There is sufficient light for those who desire to see, and there is sufficient darkness for those of a contrary disposition.
Blaise Pascal
|
|
|
|
|
sashoalm wrote: This problem might be because 256-color/16-color bitmaps don't use RGB values. May be they use palettes somehow.
You are correct, obviously you cannot put RGB(R, G, B) into 4 or 8 bits. The early bitmap types could select a subset of the RGB spectrum and did so by first selecting a palette of colours and then using the color value as an index into the palette set. So the bottom line is that you cannot use all the new functionality with the old 16/256-colour bitmaps.
|
|
|
|
|
Richard MacCutchan wrote: You are correct, obviously you cannot put RGB(R, G, B) into 4 or 8 bits. The early bitmap types could select a subset of the RGB spectrum and did so by first selecting a palette of colours and then using the color value as an index into the palette set. So the bottom line is that you cannot use all the new functionality with the old 16/256-colour bitmaps.
Yes, we can!
|
|
|
|
|
Rozis wrote: Yes, we can!
How?
|
|
|
|
|
Richard MacCutchan wrote: The early bitmap types could select a subset of the RGB spectrum and did so by first selecting a palette of colours and then using the color value as an index into the palette set.
Can you give an example for using a palette?
How do I construct one, and do I select it into the DC with SelectObject?
There is sufficient light for those who desire to see, and there is sufficient darkness for those of a contrary disposition.
Blaise Pascal
|
|
|
|
|
sashoalm wrote: Can you give an example for using a palette?
I'm afraid I have not used this functionality for years so can only vaguely remember how it all fits together. You can probably find some information via Google, or Rozis has made a suggestion below as to how to convert to 24-bit.
|
|
|
|
|
The book Programming windows of charles Petzhold explains it pretty well
|
|
|
|
|
Rozis wrote: The book Programming windows of charles Petzhold explains it pretty well
I agree, all his books are really good. The version I had was Programming windows 3.1, which is a bit old now!
|
|
|
|
|
Maybe i can help you...
sashoalm wrote: This problem might be because 256-color/16-color bitmaps don't use RGB values. May be they use palettes somehow.
Only 24-bit bitmaps use no colortable, each pixel is 3 bytes in memory being 8 bits for red, 8 for green and 8 for blue. Transparency is implemented as an extension on this: instead of 3 bytes it uses 4 bytes for a pixel (8 bits for transparency level called 'Alpha'). 256- and 16-color bitmaps use a colortable.
TransparentBlt() has 2 levels of transparency: global and per pixel. Global transparency will make all your pixels - for example - 50% transparent. This only works for 24- and 32-bits bitmaps.
Per pixel transparency uses the setting of the alpha. So a 32-bitmap is required. With this you can set the transparency per pixel. One thing to know is that pixel-transparency expects your values for RGB are 'pre-multified', meaning:
alpha:=.. // alpha holds the alpha of the pixel
factor:=alpha/255
r:=r*factor
g:=g*factor
b:=b*factor
I'm not sure what your problem exactly is but i bet the solution is to 'transform' the bitmaps to a 24-bit version. With CreatecDIbitmap() you can do this...
Rozis
|
|
|
|
|