Jump to content
  • Advertisement
Sign in to follow this  
Whiteclaws

Float Datastructure

This topic is 1672 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

Hello there Gamedev,

 

So I've been looking for a datastructure that would respond to my conditions for quite some time with not much luck, knowing that much experiences dwells here, here I am ...

 

The purpose is to store positions (floats) linearly with as less overhead as possible, kinda like an arr, where i is a float, or something near that, like a function that would return a value when fed with a float (get(1.25) = x), that value stored at that key (float) before (store(x, 1.25))

 

The datastructure must be:

~ Memory-Efficient

~ As Fast as possible

 

That's it, if you know anything like this then feel free to post here

Your help is appreciated and thanks for reading cool.png

 

Whiteclaws.

Share this post


Link to post
Share on other sites
Advertisement
I am not sure I understood your description. Are you looking for a structure that maps floats to floats? Binary trees and a hashes are the most common choices.

Share this post


Link to post
Share on other sites

Do you insert new values into the container often, or is it static after construction?

If someone looks up a float value that doesn't exist, does it give interpolated results?

e.g. data.store(1.5 => 0); data.store(2.5 => 1); assert( data.get(2.0)==0.5 );

Share this post


Link to post
Share on other sites

You are just looking for a map (key-value datastructure), which can be implemented efficiently in C using, for instance, a hash table. A float is 32 bits in size, so you can reinterpret it as a uint32_t to use as a small, compact key. Take a look at uthash, libcfu, etc.. they might meet your needs (though they might have variable amounts of overhead, but generally they are probably fast enough, but if performance is critical you can always roll your own suited to your particular needs).

Share this post


Link to post
Share on other sites
If you are going to set up all the contents once and then just query the data structure, a vector of pairs of floats (key-value) is a good way to go. You can use binary search to find values there relatively quickly, and you are certainly wasting very little memory.

Share this post


Link to post
Share on other sites
No, I'd like it to return a Null of something like that if said position is not filled, and I'm almost not going to change the final data, compact because I'll be loading it with a lot of data, I mean like a lot ... Efficient because I'm going to access it literally millions or even billions of time each second

Share this post


Link to post
Share on other sites
As above, you could either use a hash-map, a sorted tree, or just a sorted array.

You need to be aware of the problems inherent with comparing floats though, also as mentioned above... Two algebraic calculations that should give the same results, might produce different values -- e.g. It's possible that x*3 != x+x+x

If you're doing math, and then using the result to look up a value in your container, it very likely will break often...

That said, if you're not doing math, such that the floats may as well just be integers, a hash-map will do you well.
Otherwise, if you can define some kind of error tolerance (epsilon) -- e.g. So 1.9999 is seen as close enough to 2.0 -- then I would just sort your data into a big array of floats, and then a big array of associated values. Binary search the fist array until you find a match (or don't) then return the value at that index (or null).

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!