Discovery: dictionaries load slow unless you have the right key/value pair in the right format

[RayLopez99]

Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.

I had this dictionary:

Dictionary<Point, Rectangle> aDictionary = new Dictionary<Point,
Rectangle>();

then later, inside of a massive (million iteration) loop, I had this:

aRectangle = new Rectangle (i,j);

aDictionary.Add(new point(i,j), aRectangle);

After several hundred iterations, the program slowed down dramatically
on a fast PC. But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).

That is, this worked fast: aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'

Anybody observe this? I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.

Or so it seems (to my mind's eye)

RL

[Family Tree Mike]

Post by RayLopez99
Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.
Dictionary<Point, Rectangle> aDictionary = new Dictionary<Point,
Rectangle>();
aRectangle = new Rectangle (i,j);
aDictionary.Add(new point(i,j), aRectangle);
After several hundred iterations, the program slowed down dramatically
on a fast PC. But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).
That is, this worked fast: aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'
Anybody observe this? I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.
Or so it seems (to my mind's eye)
RL

I think it is hard to tell why this might be without an understanding of the
Rectangle and Point definitions. Standard structures and classes that I
know with those names don't have any common constructors that would allow
(i, j) as arguments interchangably.

[RayLopez99]

Post by Family Tree Mike
I think it is hard to tell why this might be without an understanding of the
Rectangle and Point definitions.  Standard structures and classes that I
know with those names don't have any common constructors that would allow
(i, j) as arguments interchangably.

You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes, and take x,y (x being the horizontal axis from the top left
corner of your screen, y the vertical). Here i,j are also loop int
variables (two nested for loops).

But if this does not ring a bell, it might be also that I've
simplified it from the actual code, without IMO losing anything from
the actual code. If Jon Skeet was still around he would complain
"post the entire code!" LOL. RIP Jon Skeet, wherever you are.

RL

[Family Tree Mike]

Post by RayLopez99

Post by Family Tree Mike
I think it is hard to tell why this might be without an understanding of the
Rectangle and Point definitions. Standard structures and classes that I
know with those names don't have any common constructors that would allow
(i, j) as arguments interchangably.

You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes, and take x,y (x being the horizontal axis from the top left
corner of your screen, y the vertical). Here i,j are also loop int
variables (two nested for loops).
But if this does not ring a bell, it might be also that I've
simplified it from the actual code, without IMO losing anything from
the actual code. If Jon Skeet was still around he would complain
"post the entire code!" LOL. RIP Jon Skeet, wherever you are.
RL

Then, what constructor of a Rectangle (presumably System.Drawing.Rectangle)
takes an x and y as you just defined as the only parameters?

[Göran Andersson]

Post by RayLopez99

Post by Family Tree Mike
I think it is hard to tell why this might be without an understanding of the
Rectangle and Point definitions. Standard structures and classes that I
know with those names don't have any common constructors that would allow
(i, j) as arguments interchangably.

You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes,

There is a Rectangle class, but it doesn't have any constructor that
takes any parameters.

There is no Point class, only the Point structure in the System.Drawing
namespace.

Post by RayLopez99
and take x,y (x being the horizontal axis from the top left
corner of your screen, y the vertical). Here i,j are also loop int
variables (two nested for loops).
But if this does not ring a bell, it might be also that I've
simplified it from the actual code, without IMO losing anything from
the actual code. If Jon Skeet was still around he would complain
"post the entire code!" LOL.

Well, something is lost. Having a rectangle with only coordinates and no
size doesn't even make sense.

Post by RayLopez99
RIP Jon Skeet, wherever you are.

That's what you say about someone who died. That's now what you meant,
right?

[RayLopez99]

Post by Göran Andersson
Well, something is lost. Having a rectangle with only coordinates and no
size doesn't even make sense.

No, the size and location are the x,y, and (not shown) I have
an .Offset extension method that moves the rectangle around (Offsets
it from the original location, everytime the loop loops).

More general question: have you had problems with Dictionary keys?
(selecting them?) I recall reading something about how keys can be
hashed to speed up stuff, so I assume that they are O(n) something or
another when creating...maybe this is an example.

Post by Göran Andersson

Post by RayLopez99
RIP Jon Skeet, wherever you are.

That's what you say about someone who died. That's now what you meant,
right?

Yes. But I hope he's alive. I was only speaking metaphorically, like
he's dead in terms of posting here.

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
Well, something is lost. Having a rectangle with only coordinates and no
size doesn't even make sense.

No, the size and location are the x,y, and (not shown) I have
an .Offset extension method that moves the rectangle around (Offsets
it from the original location, everytime the loop loops).

So the code that you showed isn't the code that you use, and you don't
create new Rectangle object but change existing ones?

Post by RayLopez99
More general question: have you had problems with Dictionary keys?
(selecting them?) I recall reading something about how keys can be
hashed to speed up stuff,

The dictionary always uses hash codes.

If the key has a GetHashCode method that gives too little variation in
the hash codes, the Dictioary doesn't work properly, and it gets as slow
as using a regular list.

[Jeff Johnson]

Post by RayLopez99
You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes

No, they are structures, not classes, and they are in System.Drawing. Don't
use "class" as a catch-all. If you're trying to be generic, say "type."

[RayLopez99]

Post by Jeff Johnson

You don't deal with Forms do you FTM?  Rectangle and Point are Forms
classes

No, they are structures, not classes, and they are in System.Drawing. Don't
use "class" as a catch-all. If you're trying to be generic, say "type."

OK thanks. Another phrase used (introduced to me on this board by MVP
Jon Skeet) is to say "member" instead of "object".

Type not class is the generic type, noted.

RL

[Göran Andersson]

Post by RayLopez99

Post by Jeff Johnson

Post by RayLopez99
You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes

No, they are structures, not classes, and they are in System.Drawing. Don't
use "class" as a catch-all. If you're trying to be generic, say "type."

OK thanks. Another phrase used (introduced to me on this board by MVP
Jon Skeet) is to say "member" instead of "object".

No, a member is not the same thing as an object. A member is a variable,
property, constructor or method in a class or structure.

Post by RayLopez99
Type not class is the generic type, noted.
RL

[Jeff Johnson]

Post by Göran Andersson

Post by RayLopez99

Post by Jeff Johnson

Post by RayLopez99
You don't deal with Forms do you FTM? Rectangle and Point are Forms
classes

No, they are structures, not classes, and they are in System.Drawing. Don't
use "class" as a catch-all. If you're trying to be generic, say "type."

OK thanks. Another phrase used (introduced to me on this board by MVP
Jon Skeet) is to say "member" instead of "object".

No, a member is not the same thing as an object. A member is a variable,
property, constructor or method in a class or structure.

Right. A better synonym for "object" would be "instance."

[Göran Andersson]

Post by RayLopez99
Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.
Dictionary<Point, Rectangle> aDictionary = new Dictionary<Point,
Rectangle>();
aRectangle = new Rectangle (i,j);
aDictionary.Add(new point(i,j), aRectangle);
After several hundred iterations, the program slowed down dramatically
on a fast PC. But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).
That is, this worked fast: aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'
Anybody observe this? I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.
Or so it seems (to my mind's eye)
RL

I found a Point structure in the WINdowsBase assembly, I suppose that's
the one that you are using?

That Point structure implements GetHashCode and Equals, so it should be
usable as a dictionary key.

The Rectangle class has no implementation for GetHashCode or Equals that
uses the coordinates of the rectangle, so that's not suitable as a
dictionary key.

I don't know the exact reason for your performance problem, and it's
hard to tell with so little of the code, but it definitely has nothing
to do with creating a new Point value. The value is copied when the Add
method is called anyway, so if it's copied from a newly created value or
a value that existed before makes no difference at all.

[RayLopez99]

Post by Göran Andersson
I found a Point structure in the WINdowsBase assembly, I suppose that's
the one that you are using?
That Point structure implements GetHashCode and Equals, so it should be
usable as a dictionary key.
The Rectangle class has no implementation for GetHashCode or Equals that
uses the coordinates of the rectangle, so that's not suitable as a
dictionary key.

Goran--you are onto something very important. It's late now and I
have to go sleep. Below is what I was going to write before I saw
this post.

Any help appreciated.

Here is the important thing (I would say "key" or "point" but it's
confusing): apparently using the Rectangle as a key is fast--if you
are getting a "Point" as the value. But going the other way (using
the "Point" as the key, to get a Rectangle as a value) slows down the
algorithm (Dictionary) tremendously. I am not switching my terms:
what I say is true--going from Rectangle (as key) and Point (as value)
is fast, see the below, but the slow part is going the other way.

Can you figure it out?

Here is the code below.

Another thing: if you cannot figure out how to fix this, then the next
step is this: how to find a Rectangle (a key) given a point (that is
the value in a dictionary, see the below). Why do I ask? Because I
know the points (x,y) that are the logical coordinates (I have a 1000
by 1000 chessboard, so the middle of the chessboard is 500,500), but I
want to find what rectangle is associated with any logical coordinate,
like say 498,501 (also there is a zoom factor, as per Bob Powell's
matrix transform, so depending on the zoom the rectangles change) I am
using a grid that is a two -dimensional array of rectangles (an idea
from an old book--it works pretty well). But an old post by Jon Skeet
said that you cannot find a key from a value--if I could, I could just
use the first table (RectpointDict below)

Thank you.

RL

Question:
why is my dictionary so slow?

I have a 1 million cell collection of Rectangles to Points, stored in
RectpointDict, a dictionary. It takes no time at all to store
Rectangles as the key, and Points as the value. There is a one-to-one
correspondence between Rectangles and Points.

Yet, when I run the below (since I want to store Points as the key),
to create a new dictionary called PointRectangleDict, I get a long
wait (about 30 seconds) on a fast Core 2 Duo with lots of RAM. Any
ideas?

RL

PointRectangleDict = new Dictionary<Point, Rectangle>();

foreach (KeyValuePair<Rectangle, Point> kvp in RectpointDict)


{

PointRectangleDict.Add(kvp.Value, kvp.Key); //makes one dictionary's
key the other's value


}

//http://www.phase9studios.com/2008/01/08/DictionaryVSHashTable.aspx

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
I found a Point structure in the WINdowsBase assembly, I suppose that's
the one that you are using?
That Point structure implements GetHashCode and Equals, so it should be
usable as a dictionary key.
The Rectangle class has no implementation for GetHashCode or Equals that
uses the coordinates of the rectangle, so that's not suitable as a
dictionary key.

Goran--you are onto something very important. It's late now and I
have to go sleep. Below is what I was going to write before I saw
this post.
Any help appreciated.
Here is the important thing (I would say "key" or "point" but it's
confusing): apparently using the Rectangle as a key is fast--if you
are getting a "Point" as the value. But going the other way (using
the "Point" as the key, to get a Rectangle as a value) slows down the
what I say is true--going from Rectangle (as key) and Point (as value)
is fast, see the below, but the slow part is going the other way.
Can you figure it out?
Here is the code below.
Another thing: if you cannot figure out how to fix this, then the next
step is this: how to find a Rectangle (a key) given a point (that is
the value in a dictionary, see the below). Why do I ask? Because I
know the points (x,y) that are the logical coordinates (I have a 1000
by 1000 chessboard, so the middle of the chessboard is 500,500), but I
want to find what rectangle is associated with any logical coordinate,
like say 498,501 (also there is a zoom factor, as per Bob Powell's
matrix transform, so depending on the zoom the rectangles change) I am
using a grid that is a two -dimensional array of rectangles (an idea
from an old book--it works pretty well). But an old post by Jon Skeet
said that you cannot find a key from a value--if I could, I could just
use the first table (RectpointDict below)
Thank you.
RL
why is my dictionary so slow?
I have a 1 million cell collection of Rectangles to Points, stored in
RectpointDict, a dictionary. It takes no time at all to store
Rectangles as the key, and Points as the value. There is a one-to-one
correspondence between Rectangles and Points.
Yet, when I run the below (since I want to store Points as the key),
to create a new dictionary called PointRectangleDict, I get a long
wait (about 30 seconds) on a fast Core 2 Duo with lots of RAM. Any
ideas?
RL
PointRectangleDict = new Dictionary<Point, Rectangle>();
foreach (KeyValuePair<Rectangle, Point> kvp in RectpointDict)
{
PointRectangleDict.Add(kvp.Value, kvp.Key); //makes one dictionary's
key the other's value
}
//http://www.phase9studios.com/2008/01/08/DictionaryVSHashTable.aspx

It's most likely the coordinates that you use for the points that makes
it slow. If the x coordinate is the same as the y coordinate, all points
get the same hash code and the dictionary gets very slow.

I tried adding items to a dictionary with a Point as key, and using new
Point(i, i) I can add about 10000 items in a second. Using new Point(i,
0) I can add about 10000000 items in a second.

The GetHashCode method for the Point structures calculates the hash code
by doing an xor between the x and y coordinates. This means that if x
and y are equal, the hash code becomes zero.

If the x and y coordinates are the same in all your points, you should
create an EqualityComparer to use with the dictionary so that you can
implement the GetHashCode method differently.

But then again, if the x and y coordinates in your points are the same,
it's rather pointless (!) to use a Point as key...

[i***@gmail.com]

Post by Göran Andersson

Post by Göran Andersson
I found a Point structure in the WINdowsBase assembly, I suppose that's
the one that you are using?
That Point structure implements GetHashCode and Equals, so it should be
usable as a dictionary key.
The Rectangle class has no implementation for GetHashCode or Equals that
uses the coordinates of the rectangle, so that's not suitable as a
dictionary key.

Goran--you are onto something very important.  It's late now and I
have to go sleep.  Below is what I was going to write before I saw
this post.
Any help appreciated.
Here is the important thing (I would say "key" or "point" but it's
confusing):  apparently using the Rectangle as a key is fast--if you
are getting a "Point" as the value.  But going the other way (using
the "Point" as the key, to get a Rectangle as a value) slows down the
what I say is true--going from Rectangle (as key) and Point (as value)
is fast, see the below, but the slow part is going the other way.
Can you figure it out?
Here is the code below.
Another thing: if you cannot figure out how to fix this, then the next
step is this:  how to find a Rectangle (a key) given a point (that is
the value in a dictionary, see the below).  Why do I ask?  Because I
know the points (x,y) that are the logical coordinates (I have a 1000
by 1000 chessboard, so the middle of the chessboard is 500,500), but I
want to find what rectangle is associated with any logical coordinate,
like say 498,501 (also there is a zoom factor, as per Bob Powell's
matrix transform, so depending on the zoom the rectangles change) I am
using a grid that is a two -dimensional array of rectangles (an idea
from an old book--it works pretty well).  But an old post by Jon Skeet
said that you cannot find a key from a value--if I could, I could just
use the first table (RectpointDict below)
Thank you.
RL
why is my dictionary so slow?
I have a 1 million cell collection of Rectangles to Points, stored in
RectpointDict, a dictionary.  It takes no time at all to store
Rectangles as the key, and Points as the value.  There is a one-to-one
correspondence between Rectangles and Points.
Yet, when I run the below (since I want to store Points as the key),
to create a new dictionary called PointRectangleDict, I get a long
wait (about 30 seconds) on a fast Core 2 Duo with lots of RAM.  Any
ideas?
RL
PointRectangleDict = new Dictionary<Point, Rectangle>();
foreach (KeyValuePair<Rectangle, Point> kvp in RectpointDict)
{
PointRectangleDict.Add(kvp.Value, kvp.Key); //makes one dictionary's
key the other's value
}
//http://www.phase9studios.com/2008/01/08/DictionaryVSHashTable.aspx

It's most likely the coordinates that you use for the points that makes
it slow. If the x coordinate is the same as the y coordinate, all points
get the same hash code and the dictionary gets very slow.
I tried adding items to a dictionary with a Point as key, and using new
Point(i, i) I can add about 10000 items in a second. Using new Point(i,
0) I can add about 10000000 items in a second.
The GetHashCode method for the Point structures calculates the hash code
by doing an xor between the x and y coordinates. This means that if x
and y are equal, the hash code becomes zero.
If the x and y coordinates are the same in all your points, you should
create an EqualityComparer to use with the dictionary so that you can
implement the GetHashCode method differently.
But then again, if the x and y coordinates in your points are the same,
it's rather pointless (!) to use a Point as key...
--
Göran Andersson
_____http://www.guffa.com

There is nothing like making an operation to change one's gender, no
propsal, no go-to <<<<< I have in mind that!

[RayLopez99]

Goran you are a genius. Genius is sometimes defined as the ability to
see a problem and solve it based on limited information. You, unlike
some other posters in this thread (who were very helpful and very
smart to be sure), saw the solution based on the limited info I
provided. Comments below.

Post by Göran Andersson
It's most likely the coordinates that you use for the points that makes
it slow. If the x coordinate is the same as the y coordinate, all points
get the same hash code and the dictionary gets very slow.

Yes, this is likely the case. For example, I am traversing an array
defining a game board, that can be as high as 3000 x 3000. X,Y
(defined from the upper left corner of your screen), can be, for
example (0,2999), (1,2999), (2,2999), etc (in this case you are
traversing the last row of the board, horizontally, and moving left to
right across the bottom of the screen).

Post by Göran Andersson
I tried adding items to a dictionary with a Point as key, and using new
Point(i, i) I can add about 10000 items in a second. Using new Point(i,
0) I can add about 10000000 items in a second.
The GetHashCode method for the Point structures calculates the hash code
by doing an xor between the x and y coordinates. This means that if x
and y are equal, the hash code becomes zero.

Yes, again true. You have observed it seems the asymmetry I have
spoken about: using one element of the pair as key is faster than
using the other element of the pair.

Post by Göran Andersson
If the x and y coordinates are the same in all your points, you should
create an EqualityComparer to use with the dictionary so that you can
implement the GetHashCode method differently.

I would love, for my future reference, to learn what you mean by this
(in my mind's eye I know what you are saying, but I need a concrete
example). If you have a link or easy example please post, but I don't
want to waste your time, so please don't worry about it and go out of
your way--it's not important now. By the way, you have helped me a
lot in the past and now, in fact, I name (for keyword searching) all
interesting discoveries that you have pointed out before (such as
using a predicate logic boolean search function/method) as "GORAN" in
my notes, so I can find them easier!

Post by Göran Andersson
But then again, if the x and y coordinates in your points are the same,
it's rather pointless (!) to use a Point as key...

Aha! This is incredible that you deduced this, and very true. Below
is what I found right after I logged off this morning, as I just
posted to another here.

RL

PS--the good news, and it's funny, is that five minutes after I posted
this reply to Goran this morning, it struck me: the solution for this
particular problem of mine (has nothing to do with this post,
theoretically), is trivial--I have a 2D array of rectangles I call
"Board", having signature: Rectangle [,] Board. It turns out that the
i,j elements of the board are also identical for my Point (I am using
a solution offered by Jones in his Windows MFC book, on how to
construct a game board). Thus, for this particular program, here is
the solution:

public Rectangle ReturnBoardRectangle (Point P)
{
int x = P.X;
int y = P.Y;
return Board[x, y]; //done!
}

LOL, I can't believe I overlooked this. No need for a second
dictionary after all.

But, aside from this workarond, it was still educational for me to
post here about this theoretical problem.

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
If the x and y coordinates are the same in all your points, you should
create an EqualityComparer to use with the dictionary so that you can
implement the GetHashCode method differently.

I would love, for my future reference, to learn what you mean by this
(in my mind's eye I know what you are saying, but I need a concrete
example).

I wrote an article about using a custom class as key in a dictionary. In
the example the custom class contains the EqualityComparer class, but
you can create an EqualityComparer class by itself to use with an
already existing class as key.

http://www.codeproject.com/KB/cs/dictionary_customkey.aspx

[Jeff Johnson]

Post by Göran Andersson
http://www.codeproject.com/KB/cs/dictionary_customkey.aspx

Well, hello, "Guffa"!

Here are three excellent articles (kind of a series) I found about hash
keys. I learned a lot:

http://blog.roblevine.co.uk/?p=13
http://blog.roblevine.co.uk/?p=15
http://blog.roblevine.co.uk/?p=19

[RayLopez99]

Post by Göran Andersson
I wrote an article about using a custom class as key in a dictionary. In
the example the custom class contains the EqualityComparer class, but
you can create an EqualityComparer class by itself to use with an
already existing class as key.
http://www.codeproject.com/KB/cs/dictionary_customkey.aspx

Goran--your article above contains a typo I believe.

in your code for "ParkingSpaceKey" your method "GetHasCode" should
read: "GetHashCode". Note the extra 'h'. I think this is required
for the code to work. I might implement it later today and report
back, but I think this is a typo that should be corrected.

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
I wrote an article about using a custom class as key in a dictionary. In
the example the custom class contains the EqualityComparer class, but
you can create an EqualityComparer class by itself to use with an
already existing class as key.
http://www.codeproject.com/KB/cs/dictionary_customkey.aspx

Goran--your article above contains a typo I believe.
in your code for "ParkingSpaceKey" your method "GetHasCode" should
read: "GetHashCode". Note the extra 'h'. I think this is required
for the code to work. I might implement it later today and report
back, but I think this is a typo that should be corrected.
RL

If you look at the comments to the article, you see that the type has
already been discovered.

It's such a small and obvious error, that I haven't updated the article
just for that. If I make any other changes to the article, I will
correct that also.

[i***@gmail.com]

Post by RayLopez99
Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.
Dictionary<Point, Rectangle> aDictionary = new  Dictionary<Point,
Rectangle>();
aRectangle = new Rectangle (i,j);
aDictionary.Add(new point(i,j), aRectangle);
After several hundred iterations, the program slowed down dramatically
on a fast PC.  But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).
That is, this worked fast:  aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'
Anybody observe this?  I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.
Or so it seems (to my mind's eye)
RL

The title makes me imagine much, I have to tell you
I still believe noop matter what one says, it is just a freedom of
speech the result is unchanged

[Anthony Jones]

Post by RayLopez99
Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.
Dictionary<Point, Rectangle> aDictionary = new Dictionary<Point,
Rectangle>();
aRectangle = new Rectangle (i,j);
aDictionary.Add(new point(i,j), aRectangle);
After several hundred iterations, the program slowed down dramatically
on a fast PC. But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).
That is, this worked fast: aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'
Anybody observe this? I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.
Or so it seems (to my mind's eye)

I've read through this thread so far and what you are actually doing is as
clear as mud.

Please state exactly which namespace Point and Rectangle are from and
exactly what are the data types of i and j in the code above. Add some more
code to the sample if you feel it would make things more clear.

[RayLopez99]

Post by Anthony Jones
Please state exactly which namespace Point and Rectangle are from and
exactly what are the data types of i and j in the code above.  Add some more
code to the sample if you feel it would make things more clear.
--
Anthony Jones - MVP ASP/ASP.NET

Thanks for your help. I figured a workaround as per my other reply
here, but the theoretical problem remains: when chosing key and
value, you must have the value different sufficiently from the key so
that the 'behind the scenes' hashing/algorithm for the dictionary is
efficient. If not (if, as apparently here, the key is derived from
the value, thus the value cannot easily be used as the key in a
reverse dictionary, if you follow the drift) your dictionary creation
is painfully slow.

RL

[Frans Bouma [C# MVP]]

Post by RayLopez99
Recently I found that dictionaries cannot be used easily if a certain
format is not observed for the key rather than the value.
Dictionary<Point, Rectangle> aDictionary = new Dictionary<Point,
Rectangle>();
aRectangle = new Rectangle (i,j);
aDictionary.Add(new point(i,j), aRectangle);
After several hundred iterations, the program slowed down dramatically
on a fast PC. But, strangely, if I switched the value (here a
Rectangle type) and the key (here a Point), it worked fine (fast).
That is, this worked fast: aDictionary.Add(aRectangle, new point
(i,j)); //order reversed, and key is not created 'inline' or 'on the
fly'
Anybody observe this? I think it has to do with the fact a 'new' key
is being created everytime in the loop, rather than a 'new' value.
For some reason, because of the algorithm used for key pairs, keys
cannot easily be created 'behind the scenes'.
Or so it seems (to my mind's eye)

Which point/rectangle are you using, from System.Drawing?
These two use a hashcode which is based on both x and y (and for
rectangle also with and height) using XOR, which shouldn't lead to much
duplicates. Every duplicate will make things slower.

FB

[RayLopez99]

On Jan 8, 4:35 am, "Frans Bouma [C# MVP]"

        Which point/rectangle are you using, from System.Drawing?
        These two use a hashcode which is based on both x and y (and for
rectangle also with and height) using XOR, which shouldn't lead to much
duplicates. Every duplicate will make things slower.
                FB

Thanks FB--you are onto something. What I observed is for real, not a
coding phantom resulting from something else, IMO. I think because
the key and value are so close, there is not a clear distinction
between the two and thus it's slowing down the algorithm when using
Point to find Rectangle, rather than vice versa, since Rectangle is
constructed from Point. And yes they are part of System.Drawing.

PS--the good news, and it's funny, is that five minutes after I posted
this reply to Goran this morning, it struck me: the solution for this
particular problem of mine (has nothing to do with this post,
theoretically), is trivial--I have a 2D array of rectangles I call
"Board", having signature: Rectangle [,] Board. It turns out that the
i,j elements of the board are also identical for my Point (I am using
a solution offered by Jones in his Windows MFC book, on how to
construct a game board). Thus, for this particular program, here is
the solution:

public Rectangle ReturnBoardRectangle (Point P)
{
int x = P.X;
int y = P.Y;
return Board[x, y]; //done!
}

LOL, I can't believe I overlooked this. No need for a second
dictionary after all.

But, aside from this workarond, it was still educational for me to
post here about this theoretical problem.

RL

[Chris Dunaway]

Post by RayLopez99
public Rectangle ReturnBoardRectangle (Point P)
{
int x = P.X;
int y = P.Y;
return Board[x, y]; //done!
}

Firstly, no need to create the extra variables, just call

return Board[P.X, P.Y];

Secondly, why bother creating this method at all? You could just
reference the board array directly:

i.e. instead of this:

Rectangle r = ReturnBoardRectangle(somePoint);

why not just do this:

Rectangle r = Board[somePoint.X, somePoint.Y];

and eliminate the method? I suppose if your ReturnBoardRectangle does
more than just access the array, then it might be useful.

Chris

[RayLopez99]

         Rectangle r = Board[somePoint.X, somePoint.Y];
and eliminate the method?  I suppose if your ReturnBoardRectangle does
more than just access the array, then it might be useful.
Chris

Good point, thanks Chris. But in fact, I need to access Board from
outside the class it's in, because it's private. But I'll make it a
property and use your suggestion...wait, properties cannot use input
variables...so I'll just shorten the method as per your suggestion.

RL

[Göran Andersson]

Post by RayLopez99
I think because
the key and value are so close, there is not a clear distinction
between the two and thus it's slowing down the algorithm when using
Point to find Rectangle, rather than vice versa, since Rectangle is
constructed from Point.

Not at all. What type you use for value has nothing to do with how the
keys work.

[RayLopez99]

Post by Göran Andersson
Not at all. What type you use for value has nothing to do with how the
keys work.

No, but my point is what type you use for keys, including how closely
the key is related to the value, makes a difference.

Simple example:

key: a value: aa
key: b value: bb
key: c value: cc

Presumeably would index slower than:

key: asdfasf value: aa
key: aw341 value: bb
key: [random string here] value: cc

etc

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
Not at all. What type you use for value has nothing to do with how the
keys work.

No, but my point is what type you use for keys, including how closely
the key is related to the value, makes a difference.

Not at all, the only thing that matters is the key. Any relation between
the key and the dictionary is completely irrelevant for the dictionary.

[Göran Andersson]

Post by Göran Andersson

Post by RayLopez99

Post by Göran Andersson
Not at all. What type you use for value has nothing to do with how the
keys work.

No, but my point is what type you use for keys, including how closely
the key is related to the value, makes a difference.

Not at all, the only thing that matters is the key. Any relation between
the key and the dictionary is completely irrelevant for the dictionary.

That last should of course be:

Any relation between the key and the value is completely irrelevant for
the dictionary.

[RayLopez99]

Post by Göran Andersson
Any relation between the key and the value is completely irrelevant for
the dictionary.

Thanks; well that's basically what I said, with a twist. The choice
of key matters in how fast your dictionary works. If you have a key
that does not change much, as apparently is the case with my
particular use of "Point" (as discussed, the points were largely just
off by one number, i.e. (10,11), (10,12), etc...) as opposed to
Rectangle (which has other stuff in it presumeably) then your lookup
times would suffer. Kind of like using a mirror for the mouse pad in
an optical mouse--the hardware uses XOR of surface imperfections (the
key) and if the surface is too smooth and perfect then the mouse loses
track of its position.

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson
Any relation between the key and the value is completely irrelevant for
the dictionary.

Thanks; well that's basically what I said, with a twist.

No, it's not.

You said that it matters "how closely the key is related to the value",
which is the exact opposite of what I said.

Post by RayLopez99
The choice
of key matters in how fast your dictionary works. If you have a key
that does not change much, as apparently is the case with my
particular use of "Point" (as discussed, the points were largely just
off by one number, i.e. (10,11), (10,12), etc...) as opposed to
Rectangle (which has other stuff in it presumeably) then your lookup
times would suffer.

No, that is not correct. What matters is if the _hash_code_ changes
between the key values. A Point with the coordinates (10,11) has a
different hash code than a Point with the coordinates (10,12), so that
is just fine.

The problem with the hash code of the Point structure, is that a change
in the X coordinate can elliminate the change in the Y coordinate. The
coordinates (1,10) gives the same hash code as the coordinates (10,1).
The coordinates (1,1) gives the same hash code as the coordinates (2,2).

Post by RayLopez99
Kind of like using a mirror for the mouse pad in
an optical mouse--the hardware uses XOR of surface imperfections (the
key) and if the surface is too smooth and perfect then the mouse loses
track of its position.
RL

I think that you are too much looking for patterns that doesn't exist.
You should find out how it really works, instead of just looking at the
effects and try to invent a reason.

[RayLopez99]

Post by Göran Andersson

Post by RayLopez99
Thanks; well that's basically what I said, with a twist.

No, it's not.
You said that it matters "how closely the key is related to the value",
which is the exact opposite of what I said.

But the analogy was the same.

Post by Göran Andersson

Post by RayLopez99
The choice
of key matters in how fast your dictionary works.  If you have a key
that does not change much, as apparently is the case with my
particular use of "Point" (as discussed, the points were largely just
off by one number, i.e. (10,11), (10,12), etc...) as opposed to
Rectangle (which has other stuff in it presumeably) then your lookup
times would suffer.

No, that is not correct. What matters is if the _hash_code_ changes
between the key values. A Point with the coordinates (10,11) has a
different hash code than a Point with the coordinates (10,12), so that
is just fine.
The problem with the hash code of the Point structure, is that a change
in the X coordinate can elliminate the change in the Y coordinate. The
coordinates (1,10) gives the same hash code as the coordinates (10,1).
The coordinates (1,1) gives the same hash code as the coordinates (2,2).

You mispelled "eliminate". Also, I think you mean to say that
coordinates (1,2), have the same hash as (2,1).

Post by Göran Andersson

Post by RayLopez99
Kind of like using a mirror for the mouse pad in
an optical mouse--the hardware uses XOR of surface imperfections (the
key) and if the surface is too smooth and perfect then the mouse loses
track of its position.
RL

I think that you are too much looking for patterns that doesn't exist.
You should find out how it really works, instead of just looking at the
effects and try to invent a reason.

No, actually from a hardware point of view XOR is used just like in
software.

Thanks for your input, I learned something and hopefully you did too.

RL

[Göran Andersson]

Post by RayLopez99

Post by Göran Andersson

Post by RayLopez99
Thanks; well that's basically what I said, with a twist.

No, it's not.
You said that it matters "how closely the key is related to the value",
which is the exact opposite of what I said.

But the analogy was the same.

What analogy?

Post by RayLopez99

Post by Göran Andersson

Post by RayLopez99
The choice
of key matters in how fast your dictionary works. If you have a key
that does not change much, as apparently is the case with my
particular use of "Point" (as discussed, the points were largely just
off by one number, i.e. (10,11), (10,12), etc...) as opposed to
Rectangle (which has other stuff in it presumeably) then your lookup
times would suffer.

No, that is not correct. What matters is if the _hash_code_ changes
between the key values. A Point with the coordinates (10,11) has a
different hash code than a Point with the coordinates (10,12), so that
is just fine.
The problem with the hash code of the Point structure, is that a change
in the X coordinate can elliminate the change in the Y coordinate. The
coordinates (1,10) gives the same hash code as the coordinates (10,1).
The coordinates (1,1) gives the same hash code as the coordinates (2,2).

You mispelled "eliminate".

Yes, I did, but you misspelled misspelled. ;)

Post by RayLopez99
Also, I think you mean to say that
coordinates (1,2), have the same hash as (2,1).

No, I didn't. They do have the same hash code, but that is not what I
meant to say.

Post by RayLopez99

Post by Göran Andersson

Post by RayLopez99
Kind of like using a mirror for the mouse pad in
an optical mouse--the hardware uses XOR of surface imperfections (the
key) and if the surface is too smooth and perfect then the mouse loses
track of its position.
RL

I think that you are too much looking for patterns that doesn't exist.
You should find out how it really works, instead of just looking at the
effects and try to invent a reason.

No, actually from a hardware point of view XOR is used just like in
software.

Yes, but they are used in completely different ways in an optical mouse
and Point hash code. In the mouse it's used to recognise a pattern,
while in a hash code it's supposed to avoid patterns.

Besides, that wasn't what I was talking about. What I mean is that you
are trying to apply some theory to the dictionary based on something
that you think that you have observed, but as the observations are not
correct you come to the wrong conclusion.

[RayLopez99]

--

Goran,

OK, OK, you win. BTW I knew I misspelled misspell, but I didn't care.

Now, changing the subject, please tell me what worthy project I should
be working on to sharpen my C# skills, which as you know are "much
improved" over last summer (let's leave aside questions like
percentages).

For example, I am finishing up on my chess board game (very nice I
might add, though the engine, the hardest part, I stole from open
source) and my probability study (Poisson distribution), and I
employed databases using C# as the front end (and SQL Server 2005 as
the back end), but now I believe I am weak in the "internet" (ASP.NET)
space. However, since ASP is a scripting language that is not
strongly typed, I have a feeling it is going to be obsolete soon (does
Silverlight / WPF have an internet component? Does the next
generation of C# 2010? have?).

So please share your thoughts--what should I be learning next?
Remember, I do this for fun, not for money, so I'm trying to learn
something cool rather than simply make money (from what I can tell,
database management is where the money is at, but it seems boring to
me, once you set up the front end, the rest is tweaking the backend
during maintenance, which rapidly grows unstable since databases
cannot be easily changed 'on the fly' once set up).

RL

[Dathan]

Post by RayLopez99

--

Goran,
OK, OK, you win.  BTW I knew I misspelled misspell, but I didn't care.
Now, changing the subject, please tell me what worthy project I should
be working on to sharpen my C# skills, which as you know are "much
improved" over last summer (let's leave aside questions like
percentages).
For example, I am finishing up on my chess board game (very nice I
might add, though the engine, the hardest part, I stole from open
source) and my probability study (Poisson distribution), and I
employed databases using C# as the front end (and SQL Server 2005 as
the back end), but now I believe I am weak in the "internet" (ASP.NET)
space.  However, since ASP is a scripting language that is not
strongly typed, I have a feeling it is going to be obsolete soon (does
Silverlight / WPF have an internet component?  Does the next
generation of C# 2010? have?).
So please share your thoughts--what should I be learning next?
Remember, I do this for fun, not for money, so I'm trying to learn
something cool rather than simply make money (from what I can tell,
database management is where the money is at, but it seems boring to
me, once you set up the front end, the rest is tweaking the backend
during maintenance, which rapidly grows unstable since databases
cannot be easily changed 'on the fly' once set up).
RL

I'm not sure about ASP, as I have no experience prior to ASP.Net, but
ASP.Net isn't a scripting language, it's a framework. You use ASP.Net-
specific markup in your code, but most of the actual functionality is
programmed in C# or Visual Basic (does ASP.Net support other languages
for the code-behind?). I don't see ASP.Net going anywhere any time
soon -- it's got all the power of the .Net framework behind it, and
there's still lots of active development in it.

~Dathan

[Anthony Jones]

--

So please share your thoughts--what should I be learning next?
Remember, I do this for fun, not for money, so I'm trying to learn
something cool rather than simply make money (from what I can tell,
database management is where the money is at, but it seems boring to
me, once you set up the front end, the rest is tweaking the backend
during maintenance, which rapidly grows unstable since databases
cannot be easily changed 'on the fly' once set up).

<<<<<<<

It think you'll have the most fun with WPF/Silverlight. I don't think it
will replace Web UIs built in tools like ASP.NET any time soon though. So
if you want to learn more Web/Internet skills I would recommend you look
into ASP.NET-MVC.

[RayLopez99]

It think you'll have the most fun with WPF/Silverlight.  I don't think it
will replace Web UIs built in tools like ASP.NET any time soon though.  So
if you want to learn more Web/Internet skills I would recommend you look
into ASP.NET-MVC.
--
Anthony Jones - MVP ASP/ASP.NET

OK thanks. Please feel free to post a worthy WPF/Silverlight project,
if such a project is distinct from a regular Windows .Forms C# project
(I assume not), which is what I'm familiar with over the last 9
months. That is, if in fact 'porting' a C# .Forms project into WPF/
Silverlight is what the challenge is, I will assume this is what you
meant. For example, I understand the WPF framework is different than
C#. Forms (in the sense that code and data is distinctly seperated in
WPF, rather than having your code and data reside in events, as
in .Forms, for example), and perhaps this is the part that's
interesting: porting a regular C# project into WPF. Also the GUI
(from a video webcast I saw) seems different--more bells and whistles
specific to Vista for example (I'm assuming WPF only runs on Vista,
which is fine since that's what OS I have).

RL

[Anthony Jones]

It think you'll have the most fun with WPF/Silverlight. I don't think it
will replace Web UIs built in tools like ASP.NET any time soon though. So
if you want to learn more Web/Internet skills I would recommend you look
into ASP.NET-MVC.
--
Anthony Jones - MVP ASP/ASP.NET

OK thanks. Please feel free to post a worthy WPF/Silverlight project,
if such a project is distinct from a regular Windows .Forms C# project
(I assume not), which is what I'm familiar with over the last 9
months. That is, if in fact 'porting' a C# .Forms project into WPF/
Silverlight is what the challenge is, I will assume this is what you
meant. For example, I understand the WPF framework is different than
C#. Forms (in the sense that code and data is distinctly seperated in
WPF, rather than having your code and data reside in events, as
in .Forms, for example), and perhaps this is the part that's
interesting: porting a regular C# project into WPF. Also the GUI
(from a video webcast I saw) seems different--more bells and whistles
specific to Vista for example (I'm assuming WPF only runs on Vista,
which is fine since that's what OS I have).
I would suggest you port your Chess game to Sliverlight, look into
animations and visual effects to give it an engaging UI.

[RayLopez99]

Post by Anthony Jones
I would suggest you port your Chess game to Sliverlight, look into
animations and visual effects to give it an engaging UI.

This is key! Animations and visual effects--you need to hire a
graphics artist. It's as much work seems to me to do the artwork as
the code.

BTW a lot of people develop for the iPhone etc; it would be
interesting to see what language they are using, and whether you can
use C# on a PC to port to the iPhone or Android or other non-MSFT OS
PC platform.

RL

[Registered User]

On Tue, 13 Jan 2009 14:43:58 -0800 (PST), RayLopez99

Post by RayLopez99

Post by Anthony Jones
I would suggest you port your Chess game to Sliverlight, look into
animations and visual effects to give it an engaging UI.

This is key! Animations and visual effects--you need to hire a
graphics artist. It's as much work seems to me to do the artwork as
the code.

Depending upon what is desired, you might be your own graphic artist.
Although I am not a big fan of the 'Unleashed' texts I did find
"Silverlight 2 Unleashed" to do a pretty good job introducing the
tools and how to use them to create animations and visual effects.
That part of it can be a PIA but the degree of difficulty is not too
high.

regards
A.G.

[RayLopez99]

Post by Registered User
Depending upon what is desired, you might be your own graphic artist.
Although I am not a big fan of the 'Unleashed' texts I did find
"Silverlight 2 Unleashed" to do a pretty good job introducing the
tools and how to use them to create animations and visual effects.
That part of it can be a PIA but the degree of difficulty is not too

Tx I'll check them out. I'm actually a pretty good graphics artist
(in high school I won some prizes) but it's time consuming to do it
right, unless, like you imply, Silverlight has some nice cut and paste
type tools.

RL

[RayLopez99]

Post by Registered User
On Tue, 13 Jan 2009 14:43:58 -0800 (PST), RayLopez99
"Silverlight 2 Unleashed" to do a pretty good job introducing the
tools and how to use them to create animations and visual effects.
That part of it can be a PIA but the degree of difficulty is not too
high.

Well this review says this book sucks...and I'm leary of shelling out
money for these first to market books so maybe I'll pass for now.

RL

Amazon.com

Disappointing - Too basic, for the most part, October 29, 2008 By
whatever (san jose, ca) - See all my reviews

I'm a developer who is intimiately familiar with C# and the .NET
platform in general. I've also been playing with Silverlight 1.1-2
betas/rc's and was hoping that this book would fill in the gaps that
I'd gotten through just playing with it.

But in general, the book seems to be pitched toward a less technical
audience- for example, he spends a paragraph telling us how to comment
out XML, another area explains how to install Expression Blend, page
68 explains to us why we've got F's in our numbers (it's hex, duh),
the diff between raster and vector graphics (this was necessary?)

Chapter -8- finally gets us into some code, and it's JavaScript- but
the whole point of V2 was to get us out of JS and let us use other
langs for more complex apps than just adding Flash-like abilities to
our .NET sites.

Even THEN, we get told that, "JavaScript ... and other C-based
languages are case sensitive!", and apparently (in the next para),
"...JavaScript uses -variables- (text has it in italics) to store
data." Oh my!

Chapter -9- is "Understanding .NET" and finally gets into VStudio.

At page 488, you get 10 pages on calling WCF servers.

If you're a .NET developer with some familiarity with WPF/XAML and a
little WCF, you're probably better off waiting for other books. This
should have really been called something similar to "Beginning
Silverlight 2, mostly with Javascript".

If there were any other reasonable books specifically on 2.0, I'd send
it back, but there aren't yet.

[Registered User]

On Wed, 14 Jan 2009 22:23:59 -0800 (PST), RayLopez99

Post by RayLopez99

Post by Registered User
On Tue, 13 Jan 2009 14:43:58 -0800 (PST), RayLopez99
"Silverlight 2 Unleashed" to do a pretty good job introducing the
tools and how to use them to create animations and visual effects.
That part of it can be a PIA but the degree of difficulty is not too
high.

Well this review says this book sucks...and I'm leary of shelling out
money for these first to market books so maybe I'll pass for now.

The review's author had some previous experience with SL which makes
his POV quite valid. Someone with very limited (done a couple demos)
or no SL/WPF experience the text can't be considered too basic. I
found the documentation on how to use Expression Blend most valuable.

- quote clipped from review -

Post by RayLopez99
If you're a .NET developer with some familiarity with WPF/XAML and a
little WCF, you're probably better off waiting for other books. This
should have really been called something similar to "Beginning
Silverlight 2, mostly with Javascript".
If there were any other reasonable books specifically on 2.0, I'd send
it back, but there aren't yet.

- end quote -

All quite true even if 'some' and 'a little' are vague terms. For a
relative beginner the text is a starting point. I believe some WROX
texts on the subject(s) will be published this spring. I couldn't
wait.

regards
A.G.

[Anthony Jones]

Post by Anthony Jones
I would suggest you port your Chess game to Sliverlight, look into
animations and visual effects to give it an engaging UI.

This is key! Animations and visual effects--you need to hire a
graphics artist. It's as much work seems to me to do the artwork as
the code.

BTW a lot of people develop for the iPhone etc; it would be
interesting to see what language they are using, and whether you can
use C# on a PC to port to the iPhone or Android or other non-MSFT OS
PC platform.
<<<<<<<<<<<<<<<

Apart from Windows Mobile there is currently no support for .NET languages
on mobile phones. .NET is just to hungry for power.

objective-c is the language of choice for the iPhone and I doubt that'll
change quickly.