Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Float Datastructure


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Whiteclaws   Members   -  Reputation: 114

Like
0Likes
Like

Posted 20 May 2014 - 06:59 PM

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[i], 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.



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 20 May 2014 - 07:08 PM

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.

#3 Hodgman   Moderators   -  Reputation: 31121

Like
0Likes
Like

Posted 20 May 2014 - 07:11 PM

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 );



#4 Bacterius   Crossbones+   -  Reputation: 9068

Like
0Likes
Like

Posted 20 May 2014 - 07:14 PM

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).


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#5 SeanMiddleditch   Members   -  Reputation: 6450

Like
6Likes
Like

Posted 20 May 2014 - 09:07 PM

Hashing floats is a terrible idea. Never do it. Floats that look the same (even when printed or inspected in a debugger) can still be a little different and have different bit patterns. Floats that compare equal (0 and -0) have different bit patterns. Floats that have identical bit patterns can compare unequal (NaN). Just say "no" to float hashes. Even using things like std::map is problematic.

If you need to map floats, you either need to sanitize them to a discrete range first or use something like a flat_map with an epsilon key compare. Since these are positions, you should probably use some kind of spatial data structure.

Your requirements of efficient and compact are too vague. What usage pattern are you seeing? How many distinct keys? How much clustering do have? Which of efficient or compact is more important?

#6 Álvaro   Crossbones+   -  Reputation: 13662

Like
1Likes
Like

Posted 20 May 2014 - 10:02 PM

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.

#7 Whiteclaws   Members   -  Reputation: 114

Like
0Likes
Like

Posted 21 May 2014 - 05:45 AM

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

#8 Hodgman   Moderators   -  Reputation: 31121

Like
2Likes
Like

Posted 21 May 2014 - 06:31 AM

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).




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS