Use a hash-table for value look-up #2

Closed
x3ro opened this Issue Jun 24, 2012 · 3 comments

Projects

None yet

2 participants

@x3ro
Contributor
x3ro commented Jun 24, 2012

If I am not completely mistaken, assoc.js takes O(n) time for associative array lookup. This could be improved by additionally creating an object, which in JavaScript are implemented as hashtables, that directly maps a given key to an array index, for example:

x = [['c', 'f'], ['a', 'b'], ['c', 'd']]

Would result in an object like this:

y = { c: [0, 2], a: [1] }

Now a lookup could be done in O(1) time like this:

key = "c"
x[y[key][0]]

Of course this approach would preserve the shadowing functionality. Is this something you'd like to see implemented in assoc.js?

@txus
Owner
txus commented Jun 24, 2012

You're absolutely right! That would be nice :) Would you want to implement it?

@x3ro
Contributor
x3ro commented Jun 24, 2012

Yeah, I'll give it a shot and submit a pull request when I'm done. :)

@x3ro
Contributor
x3ro commented Jun 26, 2012

Guess I can close this as it has been merged in #5 :)

@x3ro x3ro closed this Jun 26, 2012
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment