Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Rose]

This may just be my current migraine talking, but what about hashing a string made by concatenating the two integers?  Eg. if your pair contains 45 and -67, hash "45-67"?

If you use the sign of the second number as the separator between the first and the second, I'm having a hard time finding a reason why this wouldn't result in a suitable hash.

how about long Pair = int1 * MAX_INT + int2?

{int1=1, int2=MAX_INT} would produce the same value as {int1=2, int2=0}.

Sorry, on review, it should be (MAX_INT+1), which is not possible for 2 to be.

how about long Pair = int1 * MAX_INT + int2?

uint_64 might work o_O?
If Jaoa's idea won't work for some reason, someone tell me!

uint64_t is the same as unsigned long.

Note that my method will not work with negative numbers.

MagmaMcFry's union idea would be better, in that case.

[RulerOfNothing]

If the points are fairly evenly spread out, couldn't you just use one of the co-ordinates as the hash value?

[Skyrunner]

I edited my hash to show an example.
I think that if you bitshift a 32 bit integer and bit-add the other one to it it should work for all ints.
Eg,
uint64_t hash = (uint64_t)n1 << 32 | n2

If the points are fairly evenly spread out, couldn't you just use one of the co-ordinates as the hash value?

You mean use either x or y as the hash?

[Rose]

Eeeh... the bitshifting is only guaranteed to work if both of the int32s are actually uint32s.

seriously, use the union, it's safer.

[RulerOfNothing]

You mean use either x or y as the hash?

Yes.

[Skyrunner]

You mean use either x or y as the hash?

Yes.

Well, then, (10,11) and (10,255) would have the same hash. Using either x or y is like projecting a plane onto a line--information is guaranteed to be lost.

Eeeh... the bitshifting is only guaranteed to work if both of the int32s are actually uint32s.

seriously, use the union, it's safer.

I don't see how the union would help things...

Hmm, maybe I can use the flattened vector offsets as the hash. (59,10) on a 256×256 map is vector[59×256+10], for example.

[Rose]

Union will help things by solving your problem in its entirety in one step.

[MadocComadrin]

If your coordinates are all positive then the flattened array value would work.

The union solution is a very nice way of handling it too. It essentially lays out the values in memory like so:

0-31 32-63
  x      y
And allows you to interpret it as either a struct of two integers x and y or and one big long (ie, the number you would get by reading 0-63 as a long).

[Mego]

If your coordinates are all positive then the flattened array value would work.

The union solution is a very nice way of handling it too. It essentially lays out the values in memory like so:

0-31 32-63
  x      y
And allows you to interpret it as either a struct of two integers x and y or and one big long (ie, the number you would get by reading 0-63 as a long).

Code: [Select]

union Coord {
    int x;
    long y;
};

Coord make_coord(int x, int y) {
    Coord c;
    c.y = y + long(x) << sizeof(int);
}

Sleepy brain says that code will work.

[MagmaMcFry]

Here's some actual working code with a short demo. I scrapped the union idea, because on 32-bit systems, the standard hash<long long> function just drops the highest significant bits, which just so happen to contain one of the coordinates, which means that method would result in a damn lot of hash collisions. What I have here is just as fast in calculation and (if I'm right about how the container uses the hash values) it actually makes the container faster.

[MorleyDev]

You know, a fun misconception I've seen a lot lately is that lists are automatically better than vectors when you want to do a lot of pushes and pops, or insertions at random points.

This often proves wrong because of the wonders of CPU-level caching. Always profile before going away from vector, except when you need iterators that will remain valid so long as the item they point to isn't removed and are therefore forced to use list. It turns out the frequent CPU cache misses are too expensive when you iterate over lists for them to stack up well against vectors in many situations where you'd think lists should be best.

Don't blame the tool if you don't use it right.

I wasn't blaming the tool, I was pointing out mistakes that result in "undefined behaviour" are the riskiest part of C++ programming, and where at best a lot of cross-platform compatibility is halted, and at worst a lot of difficult-to-track-down crashes come from.

Whilst often the same behaviour in a JIT'd language will cause a crash, but they often do things to get around that such as being explicitly specified to throw an exception with an occasionally helpful error message. You simply have to be aware how C++, not being JIT'd and being a lot more leaned towards power without restraints, doesn't give you that luxury.

For example, an iterator to a vector can in theory be invalidated as soon as that vector is modified (push or pop). It'll bite you in the arse eventually, so just never store iterators to a vector for a period in which a vector is mutable. If you do, then C#/Java would throw a somewhat readable exception here, whilst a program written in C++ will experience a seemingly random crash at best.

This kind of thing is why C++ fills the niche it does, and they are both the languages greatest strength and greatest weakness.

[Mego]

Don't blame the tool if you don't use it right.

I wasn't blaming the tool, I was pointing out mistakes that result in "undefined behaviour" are the riskiest part of C++ programming, and where at best a lot of cross-platform compatibility is halted, and at worst a lot of difficult-to-track-down crashes come from.

Whilst often the same behaviour in a JIT'd language will cause a crash, but they often do things to get around that such as being explicitly specified to throw an exception with an occasionally helpful error message. You simply have to be aware how C++, not being JIT'd and being a lot more leaned towards power without restraints, doesn't give you that luxury.

For example, an iterator to a vector can in theory be invalidated as soon as that vector is modified (push or pop). It'll bite you in the arse eventually, so just never store iterators to a vector for a period in which a vector is mutable. If you do, then C#/Java would throw a somewhat readable exception here, whilst a program written in C++ will experience a seemingly random crash at best.

This kind of thing is why C++ fills the niche it does, and they are both the languages greatest strength and greatest weakness.

I realize now that my comment was a bit ambiguous; it was meant towards dreadmullet, because he was bitching that the language operated exactly how it should, citing your post as further reasoning in addition to the link I provided.

Here's some actual working code with a short demo. I scrapped the union idea, because on 32-bit systems, the standard hash<long long> function just drops the highest significant bits, which just so happen to contain one of the coordinates, which means that method would result in a damn lot of hash collisions. What I have here is just as fast in calculation and (if I'm right about how the container uses the hash values) it actually makes the container faster.

Why... Why are you using 2654435769? This is bad for 2 reasons:

1. 2^31.305758086099136 is not 2^31-1. That would be 2147483647.
2. Hardcoding the value is bad. The C++ specification only states that each integral and floating-point data type must be at least as large as the next-smallest, with char always being 1 byte. Theoretically, sizeof(int) could be one. Instead, use std::numeric_limits<int>::max() instead, from the limits header.

[MagmaMcFry]

Here's some actual working code with a short demo. I scrapped the union idea, because on 32-bit systems, the standard hash<long long> function just drops the highest significant bits, which just so happen to contain one of the coordinates, which means that method would result in a damn lot of hash collisions. What I have here is just as fast in calculation and (if I'm right about how the container uses the hash values) it actually makes the container faster.

Why... Why are you using 2654435769? This is bad for 2 reasons:

1. 2^31.305758086099136 is not 2^31-11. That would be 2147483647.
2. Hardcoding the value is bad. The C++ specification only states that each integral and floating-point data type must be at least as large as the next-smallest, with char always being 1 byte. Theoretically, sizeof(int) could be one. Instead, use std::numeric_limits<int>::max() instead, from the limits header.

1) Yes, and what is special about 2^31-11? Why would I want 2^31-11?
2) I am basing this on the reasonable assumption that Skyrunner is compiling her program on a machine where sizeof(int)==32. If you don't want it hardcoded, just use the nearest odd integer to 256^sizeof(int)/goldenRatio.

The reason I chose that number is because I'm reasonably sure that the unsorted_map implementation is storing its elements in buckets determined by the last few bytes of the elements' hash values. The number there is there to ensure that two nearby coordinates have minimal chance to get sorted into the same bucket (which would reduce hash access speed), regardless of the amount of buckets there is.

[Mego]

Here's some actual working code with a short demo. I scrapped the union idea, because on 32-bit systems, the standard hash<long long> function just drops the highest significant bits, which just so happen to contain one of the coordinates, which means that method would result in a damn lot of hash collisions. What I have here is just as fast in calculation and (if I'm right about how the container uses the hash values) it actually makes the container faster.

Why... Why are you using 2654435769? This is bad for 2 reasons:

1. 2^31.305758086099136 is not 2^31-11. That would be 2147483647.
2. Hardcoding the value is bad. The C++ specification only states that each integral and floating-point data type must be at least as large as the next-smallest, with char always being 1 byte. Theoretically, sizeof(int) could be one. Instead, use std::numeric_limits<int>::max() instead, from the limits header.

1) Yes, and what is special about 2^31-11? Why would I want 2^31-11?
2) I am basing this on the reasonable assumption that Skyrunner is compiling her program on a machine where sizeof(int)==32. If you don't want it hardcoded, just use the nearest odd integer to 256^sizeof(int)/goldenRatio.

The reason I chose that number is because I'm reasonably sure that the unsorted_map implementation is storing its elements in buckets determined by the last few bytes of the elements' hash values. The number there is there to ensure that two nearby coordinates have minimal chance to get sorted into the same bucket (which would reduce hash access speed), regardless of the amount of buckets there is.

1) That was a typo that I corrected; it should've been 2^31-1, which is the value of INT_MAX on most machines.
2) If Skyrunner has a machine where sizeof(int)==32, I want it. You're thinking of sizeof(int)==4. But, more to the point, no matter how reasonable an assumption is, it can still make an ass out of you and me. There is a very easy way programmatically to determine INT_MAX on a computer. It's called INT_MAX (or the nicer std::numeric_limits<int>::max()). Making the code more system-independent costs absolutely nothing.

Also, it's pretty easy to make a hash collision with that code. Granted, the two points are nowhere near each other.

[MagmaMcFry]

2) If Skyrunner has a machine where sizeof(int)==32, I want it. You're thinking of sizeof(int)==4.

Code: [Select]

    c.y = y + long(x) << sizeof(int);


Goddamnit, you're infectious.

Also, it's pretty easy to make a hash collision with that code. Granted, the two points are nowhere near each other.

[warning]Do not use this hash for cryptographic purposes.[/warning]