Jump to content
Site Stability Read more... ×
  • Advertisement
Sign in to follow this  

Simple Lookup Equation

This topic is 2806 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The problem is pretty simple I think, for some reason I'm just not sure how to approach it.
I've written a container similar to a deque which resizes similar to std::vector (newSize = oldSize*2 + 1).
I want to make my lookup time O(N).

I need to be able to determine my chunk and chunk sub-index.
For instance, if I look up Container1[4] I would find chunk 2 sub-index 0, and Container2[4]
would find chunk 0 sub-index 4.


0 1 2 3 4 5 6 7
1 3 7 15 31 63 127 255

0 1 2 3 4 5 6 7
5 11 23 47 95 191 383 767

It is also important to note that the initial number of elements in a chunk is arbitrary.

I'm a little embarrassed to ask such a simple math question, but I have been stuck on this one.
Thanks in advance for any help!

Share this post

Link to post
Share on other sites
The number of elements in chunk 'n' is k*2^(n+1)-1, for given k (k=1 in Container1, k=6 in Container2)

The number of elements in all chunks preceeding chunk 'n' is k*2^(n+1) - 2*k - n


Given your index 'i', the chunk to be looked up is however unfortunately... not solvable smile.png

The reason it's not solvable (with elementary functions at least) is that your chunk sizes aren't actually doubling in size, if they were it'd be trivial to find which chunk an index belongs to, and once that is known the sub-index is trivial

Share this post

Link to post
Share on other sites
I'm not averse the changing the sizing algorithm to be more cooperative.
The amount that it sizes is relatively unimportant, as long as it scales significantly on each resize.

I'm going to mull over your math and see if I can glean inspiration from it. It'd be very helpful to know
the function to find the chunk assuming chunk assuming it was doubling in size.
Both of these functions are very helpful. Thank you! smile.png

I'm starting to think of this as a linear equation, based on your math:
y = k*2[sup]x[/sup]

...So all I need to do is solve for x.

x = chunk index
y = number of elements at x chunks
k = initial number of elements per chunk

2[sup]x[/sup] = y / k

[font=Times New Roman]

[color=#000000][color=#000000]log[sub]b[/sub]([/font][font=Times New Roman]

[color=#000000][color=#000000]m[color=#FF0000][sup]n[/sup][/font][font=Times New Roman]

[color=#000000][color=#000000]) = [/font][font=Times New Roman]

[color=#FF0000]n[/font][font=Times New Roman]

[color=#000000][color=#000000] · log[sub]b[/sub](m), therefore...[/font]

x * log[sub]2[/sub](2) = log[sub]2[/sub]( y / k )
x = log[sub]2[/sub]( y / k )

The truncated value of x should be the chunk index.
I'm not sure if further simplification can be done, or my math makes any sense, but it seems to work.

x = log[sub]2[/sub]( y / k + 1 )
...to compensate for zero-based indexing.

Share this post

Link to post
Share on other sites

I may be a little late to the party, but I think the solution to the problem is f(n) = (k + 1) * 2^n - 1, where n is the chunk index (starting at zero) and k is the number of elements in the first chunk. So, using logarithms like you did above, you get

n = log2((f(n) + 1) / (k + 1))


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!