Easier method to compute minimal perfect hash?
I have smallish(?) sets (ranging in count from 0 to 100) of unsigned 32 bit integers. For a given set, I want to come up with minimal parameters to describe a minimal(istic) perfect hash of the given set. High level of the code I used to experiment with the idea ended up something like:
def murmur(key, seed=0x0):
// Implements 32bit murmur3 hash...
return theHashedKey
sampleInput = [18874481, 186646817, 201248225, 201248705, 201251025, 201251137, 201251185, 184472337, 186649073, 201248625, 201248721, 201251041, 201251153, 184473505, 186649089, 201248657, 201251009, 201251057, 201251169, 186646818, 201248226, 201248706, 201251026, 201251138, 201251186, 186649074, 201248626, 201248722, 201251042, 201251154, 186649090, 201248658, 201251010, 201251058, 201251170]
for seed in range(11111): // arbitrary upper seed limit
for modulus in range(10000):
hashSet = set((murmur(x, seed=seed) % modulus for x in sampleInput))
if len(hashSet) >= len(allValves):
print('minimal modulus', modulus, 'for seed', seed)
break
This is just basic pseudo code for a 2 axis brute force search. I add lines by keeping track of the different values, I can find seed and modulus values that give a perfect hash and then select the one with the smallest modulus.
It seems to me that there should be a more elegant/deterministic way to come up with these values? But that's where my math skills overflow.
I'm experimenting in Python right now, but ultimately want to implement something in C on a small embedded platform.
hash perfect-hash
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
add a comment |
I have smallish(?) sets (ranging in count from 0 to 100) of unsigned 32 bit integers. For a given set, I want to come up with minimal parameters to describe a minimal(istic) perfect hash of the given set. High level of the code I used to experiment with the idea ended up something like:
def murmur(key, seed=0x0):
// Implements 32bit murmur3 hash...
return theHashedKey
sampleInput = [18874481, 186646817, 201248225, 201248705, 201251025, 201251137, 201251185, 184472337, 186649073, 201248625, 201248721, 201251041, 201251153, 184473505, 186649089, 201248657, 201251009, 201251057, 201251169, 186646818, 201248226, 201248706, 201251026, 201251138, 201251186, 186649074, 201248626, 201248722, 201251042, 201251154, 186649090, 201248658, 201251010, 201251058, 201251170]
for seed in range(11111): // arbitrary upper seed limit
for modulus in range(10000):
hashSet = set((murmur(x, seed=seed) % modulus for x in sampleInput))
if len(hashSet) >= len(allValves):
print('minimal modulus', modulus, 'for seed', seed)
break
This is just basic pseudo code for a 2 axis brute force search. I add lines by keeping track of the different values, I can find seed and modulus values that give a perfect hash and then select the one with the smallest modulus.
It seems to me that there should be a more elegant/deterministic way to come up with these values? But that's where my math skills overflow.
I'm experimenting in Python right now, but ultimately want to implement something in C on a small embedded platform.
hash perfect-hash
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13
add a comment |
I have smallish(?) sets (ranging in count from 0 to 100) of unsigned 32 bit integers. For a given set, I want to come up with minimal parameters to describe a minimal(istic) perfect hash of the given set. High level of the code I used to experiment with the idea ended up something like:
def murmur(key, seed=0x0):
// Implements 32bit murmur3 hash...
return theHashedKey
sampleInput = [18874481, 186646817, 201248225, 201248705, 201251025, 201251137, 201251185, 184472337, 186649073, 201248625, 201248721, 201251041, 201251153, 184473505, 186649089, 201248657, 201251009, 201251057, 201251169, 186646818, 201248226, 201248706, 201251026, 201251138, 201251186, 186649074, 201248626, 201248722, 201251042, 201251154, 186649090, 201248658, 201251010, 201251058, 201251170]
for seed in range(11111): // arbitrary upper seed limit
for modulus in range(10000):
hashSet = set((murmur(x, seed=seed) % modulus for x in sampleInput))
if len(hashSet) >= len(allValves):
print('minimal modulus', modulus, 'for seed', seed)
break
This is just basic pseudo code for a 2 axis brute force search. I add lines by keeping track of the different values, I can find seed and modulus values that give a perfect hash and then select the one with the smallest modulus.
It seems to me that there should be a more elegant/deterministic way to come up with these values? But that's where my math skills overflow.
I'm experimenting in Python right now, but ultimately want to implement something in C on a small embedded platform.
hash perfect-hash
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
I have smallish(?) sets (ranging in count from 0 to 100) of unsigned 32 bit integers. For a given set, I want to come up with minimal parameters to describe a minimal(istic) perfect hash of the given set. High level of the code I used to experiment with the idea ended up something like:
def murmur(key, seed=0x0):
// Implements 32bit murmur3 hash...
return theHashedKey
sampleInput = [18874481, 186646817, 201248225, 201248705, 201251025, 201251137, 201251185, 184472337, 186649073, 201248625, 201248721, 201251041, 201251153, 184473505, 186649089, 201248657, 201251009, 201251057, 201251169, 186646818, 201248226, 201248706, 201251026, 201251138, 201251186, 186649074, 201248626, 201248722, 201251042, 201251154, 186649090, 201248658, 201251010, 201251058, 201251170]
for seed in range(11111): // arbitrary upper seed limit
for modulus in range(10000):
hashSet = set((murmur(x, seed=seed) % modulus for x in sampleInput))
if len(hashSet) >= len(allValves):
print('minimal modulus', modulus, 'for seed', seed)
break
This is just basic pseudo code for a 2 axis brute force search. I add lines by keeping track of the different values, I can find seed and modulus values that give a perfect hash and then select the one with the smallest modulus.
It seems to me that there should be a more elegant/deterministic way to come up with these values? But that's where my math skills overflow.
I'm experimenting in Python right now, but ultimately want to implement something in C on a small embedded platform.
hash perfect-hash
hash perfect-hash
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
asked Jan 18 at 23:43
Travis GriggsTravis Griggs
10.1k1358107
10.1k1358107
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13
add a comment |
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54262799%2feasier-method-to-compute-minimal-perfect-hash%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54262799%2feasier-method-to-compute-minimal-perfect-hash%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I would first determine a murmur seed that results in a collision-free set of 32-bit values. Then, with that set, determine the smallest modulus that still yields a collision-free set. The work factor should be additive instead of multiplicative for this algorithm.
– James K Polk
Jan 19 at 14:56
Isn’t that what I’m already doing in the code? I guess algorithmically, I could make sure I don’t have any hash collisions first, before looking for minimal modulus, but that’s still just a brute force loop approach.
– Travis Griggs
Jan 19 at 18:06
no, you have nested loops, thus the work factor is multiplicative. I'm talking about two loops at the same level. First one determines the seed, second one determines the modulus. Unless you want the absolute minimum modulus across all seeds, which your code doesn't do.
– James K Polk
Jan 19 at 18:13