-
Notifications
You must be signed in to change notification settings - Fork 57
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
The rank hash table could be further reduced (~7%) #80
Comments
Many thanks for your interest and hard work. Your contributions are very welcome, I'll be very interested in reviewing your PR. It's fine to completely replace Python with another (e.g. Java), or have two scripts that co-exist if you wish. |
I was in the process of contributing a whole java project for this (not only the script part but having a whole Java evaluator where all "magic numbers" can be recomputed by a single command in the build script, so I still have some work to do to have cleaner code. During this I realized that your last optimisation of the hashtable was not by using different size parameters, but computing ranks in a different orders. I applied the same technique in my code (effectively obtaining an array of 42077 elements for M=31 as in current code) to my prime factor, and the size decreased even more. Now it is 34843, which is a 17% decrease compared to current code !! I am still working on this and I will definitely do a PR as soon as the code is clean and readable enough, but since the algorithm to compute the most compact hash table changed, I will redo a bruteforce search to see if another prime can create an even shorter hash table |
Wonderful! |
HI, first of all, thank you for sharing this awesome project, I was looking for a card evaluation algorithm for a custom project in Java and yours is clearly excellent (my Java implementation evaluate a random hand in ~8ns, while generating a random hand take ~16ns)
Since I wanted to understand how it worked and not copying magic numbers from your source code, I had a look on the hash table generator script (perfect_hash.py) and I enhance it so that it runs fast enough to do a brute force search of what parameters produce the smallest hash table. The script take 1 hour to compute an hash table, mine is doing the computation in roughly 1 second
Currently, the best value I have are M = 2369371, power = 9 (so side = 512), and it produce a rank array of 38995 elements, down from 42077 in your source code (so it's a 7% decrease on that table)
FYI, Here are the changes I made on your algorithm :
Moreover, there is a mismatch between perfect_hash.py and the current hash table : the scripts uses M=31 which compute an hash table of size 44969 (which was the hash table used in an earlier version of the C code)
The text was updated successfully, but these errors were encountered: