Map with a numeric (rather than string) key

[pdwyer]

Long time no see, still alive though.

After a long break with no PB'ing I got an invite for the Gomoku programming comp again, and, while I'm not that good at it I thought I'd brush off my old v2 and make a new version and enter again, get met back into PB and see what the new version(s) hold

This new Map() feature looks nice, if I want to use it more like a hash table with a numeric key rather than like a dictionary with a string key is there a good way to do it? or do I need to roll my own?

[infratec]

Hi Paul,

for a first test use Str(Numeric) as key.
Is it fast enough, that's the easiest way

Best regards,

Bernd

[pdwyer]

Probably not fast enough, although for some reason I didn't think of the obvious so I will remember it for next time Thanks

I only have about 100 different lookup values but the values will be between 0 and 1,000,000,000 (ish) so an array index is a huge memory waste but I seem to recall something called a "sparse array" so I might check that, perhaps I got a bit excited when I saw the new MAP feature and didn't stop to ask if a hash was the best data structure. With this, It can be slow to add elements or build the data structure but it has to be very lean for lookups, so throwing the value straight into an array index to retrieve the contents structure is about as fast as I can think of (ie zero search time, direct reference, so sparse array might be indirect reference and still fast)

I need to call this over 100 million times per move which will be a few seconds. the faster I can do it the more I can do it in the time and the deeper down the game tree I can search. The tree is already as alpha-beta pruneded and Iteratively deepened as I can get my mind around, so I need the heuristic pattern lookup to happen as fast as possible.

[Trond]

I need to call this over 100 million times per move which will be a few seconds.

That's going to be hard to achieve no matter the data structure. When I loop an empty loop 100 million times it takes 400 milliseconds. It can't be many calculations in there before the time is used up.

[pdwyer]

So you see I have space for only a few instructions per loop
260ms on my pc (see below), which isn't bad but a year or two old now.

The 100,000,000 is not set in stone, alpha beta cutoffs can find a good move at a shallow level meaning it's sometimes 10,000 board checks. When it's high I expect it to take 15 seconds or so but that still means a board score heuristic needs to run in about 100 instructions or so if possible so strings and search loops will mess things up. The current setup I have now has the speed but is too simple and can't catch enough board info, my second design was good info wise but 100x too slow (after optimisations) so now I have a new design thats faster but I want to squeeze more out and I think a sharper data structure for use with better algorithms is the way to go.

(But I kind of barked up the wrong tree with the MAPs I think )

Code: Select all

DisableDebugger

MessageRequester("start","GO")
timed.l = ElapsedMilliseconds()

For i = 1 To 100000000

    k.l = j.l + 1

Next

done.l = ElapsedMilliseconds() - timed
MessageRequester("stop",Str(done))

[Trond]

Maybe you should try to make your own map. It doesn't have to be complicated, in fact it's probably faster if it's not.

[inc.]

This new Map() feature looks nice, if I want to use it more like a hash table with a numeric key rather than like a dictionary with a string key is there a good way to do it? or do I need to roll my own?

Have a look at this map, beside supporting string- and numeric-values it also comes with diff. hashing algos you can chose from and ... a quadratic probing for speed purposes.
Also it makes use of PB's internal object management.

http://www.development-lounge.de/viewto ... 177#p55177

Is it what you're looking for?

[idle]

I don't know what you need to store or retrieve though if you can ascribe an Id to the data then you could possibly use a bit index or a bloom filter instead of a map.

also maybe you could use a trie but then you have an overhead of a pointer array at each node, for a numeric trie each Node in the trie would have 10 elements 0-9 but you only add a single number at a given level once

so if you add 1,2,10,100,101,102,103

-12--------
0----------
0123 ------

if each number represented a possible move you can easily look up what they are from a given level