1
$\begingroup$

Sorry in advance if I didn't choose the right tags for the question, I wasn't sure.

So I'm a programmer and writing a saving/loading system for data. The way I was serializing (saving) vectors is via creating lists and storing the vector coordinates in those lists. So if I have a Vector3, I save that vector as a list of 3 elements where list[0] is x, list[1] is y and list[2] is z. When loading I just read the values from the list and create a vector from those values.

Then I thought, can't I just somehow convert the vector coords to a number, and just serialize/save that number? and when loading I go in reverse to get the vector?

If the vector's coords are single digits the solution is quite simple. Ex [1, 2, 3] => 123

It gets more tricky if the coords have more digits. I thought about a solution (which currently only works if the coords are integers, not floats) and this is what I came up with:

Given the vector [11, 7, 450] I also flatten the vector, so I get: 117450 and then append that number with 213. where 2 is the number of x's digits, 1 is y's digits and 3 is z's digits. So we get 117450213. Going in reverse is no problem.

My problem is how to deal with float numbers. I can deal with them the same way by storing the number of digits after each decimal place as well. So if we had [7.5, 12.75, 3.25] I'd convert that to 75 1275 325|11 22 12 (the spaces and | are just for clarity). The first 11 represents how many digits x has before and after the decimal point, so 1 before, 1 after. You get the idea. This however could yield large numbers quite easily so imagine a vector [100.32234, 24.24101, 200.5029333] ... yeah... not so great.

I'm sure there's a better way of doing it, so what's the best way to achieve what I want? And, is there an official mathematical term for what I'm trying to do?

Thanks.

Edit: Please note I don't want to store the values in an array, list or anything that allocates memory. That's why I want something to do with numbers and math (CPU effort more than memory)

$\endgroup$
  • $\begingroup$ You could convert the float numbers into fractions, but the resulting array would not be easy to store either. $\endgroup$ – Peter Nov 29 '14 at 18:37
1
$\begingroup$

Any (finite) list of numbers can be encoded as a single number since the "size" of an infinite set $X$ is the same as the size of $X^n = X \times X \times \cdots \times X$.

However, from the practical side of things, your vectors don't really allow for all possible real entries. You are using floating point numbers (or fixed size integers) which only allow for a finite range of values.

Let's say you use a 1 byte floating point numbers (or a 1 byte integer if you like). Then to keep track of a vector with 3 coordinates, you need 3 1 byte floating point numbers. Unless you encode them as a single number, in which case you'll need to use a 3 byte number to encode them. So in the end, there's no memory savings. Plus you have the down side of more complicated code and more processor time.

Your best bet is to stick with an array. Which, in the end, essentially just places the 3 numbers side-by-side in memory automatically accomplishing what you're trying to do anyway. :)

As for a mathematical term, I'm not aware of one - maybe an "encoding". The computer science term would be a "hash function".

$\endgroup$
  • $\begingroup$ Thanks for the reply. I guess I'll go with lists. I thought there was some math magic trick one could pull off lol. I have a better idea anyway, that is going data-oriented instead of object-oriented. So say I have 10 objects with a position vector, instead of creating 10 lists one foreach object to store its position, I create only 1 list for all the positions of those 10 objects. Or 3 lists one for x coords, the others are for y and z. I'd at least get a better memory layout and I bet I'd get more performance. $\endgroup$ – vexe Nov 29 '14 at 18:49
  • $\begingroup$ Sounds like you've got it all sorted out. I'd sum this whole discussion up with the "there's no free lunch" principle. :) $\endgroup$ – Bill Cook Nov 29 '14 at 20:40
1
$\begingroup$

There is a name in computer science itself for what you are trying to do - you want a hash function for your vectors. In general, it is nearly impossible to get a perfect hashing function, i.e., one that has no "collisions" at all. So you aim for something halfway decent and maintain a linked-list for all the entries whose hash function gives that index. As long as your hash function works well, search time is still O(1).

$\endgroup$
  • $\begingroup$ Thanks for your response. Assume we have the perfect hashing algorithm for vectors that gives us unique hashcodes (integers). How would we then recreate the vector from the resulting hash? $\endgroup$ – vexe Nov 29 '14 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.