## Generating savegame names so they appear in sorted order

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Generating savegame names so they appear in sorted order

Hello!

I was playing a game, and was saving my games 1,2,3 and so on. And they appeared in order in the save-games list. However, when i got to "10", it was put under the "1" save. And the "11" under ten, and the 20 under the two, so that the list looked like this:

1
10
11
...
19
2
20
21
...
3
4
5
...

Now my question is, is there a way to name these saves such that they appear in order of their significance (or rather, insignificance).
Specifically, how to name numbers that are sorted by order of their leading digit(s), and where an empty (null) in a comparison has value<0, in sub p-space and usable to inf

You can obviously do unary, but that's in p-space.
You could also put seven zeros in front of the single digits, 6 zeros in front of the doubles, but that solution fails for n>10^9 and so would be invalid. Also a pain.

---

It would SEEM to be impossible, but I might be missing something obvious
Who, me?

Posts: 15
Joined: Wed Sep 21, 2011 4:51 am UTC

### Re: Generating savegame names so they appear in sorted order

Does it need to be human-readable / nice to look at? Because there are some simple ways to do it if that's not a requirement, if you're just generating a string that can be used (with the normal lexical comparison) to sort the original files... But they end up containing a bunch of cruft, and it won't really work if these need to be human-viewable in any way. For human-viewable, just go with 0-padding... if infinite extensibility is a concern, just have an automatic routine to go back and rename all the old files if a new one needs an extra digit.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6740
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Generating savegame names so they appear in sorted order

The canonical solution is to add leading 0s. You can also lobby the game maker to put out a patch that uses less stupid sorting, but that's not likely to happen.
EvanED

Posts: 3767
Joined: Mon Aug 07, 2006 6:28 am UTC

### Re: Generating savegame names so they appear in sorted order

Assuming letters sort after numbers, you could name your games like this:
Code: Select all
`12...9A10A11...A99B100...B999C1000...Z999999999999999999999999999ZA1000000000000000000000000000...`

The prefix is asymptotically only 1/26 the length of the name. If you can't use letters, you could use a number base less than 10 and use the remaining digits for prefixes.
Goplat

Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

### Re: Generating savegame names so they appear in sorted order

Another way is to insert a timestamp in YYYYMMDDhhmm(ss if needed) order.

20120101_1501_Game1
20120102_1256_Game2
20120103_0600_Game3
20120103_0601_Game4
...
20120124_1819_Game10
...
20120315_1945_Game156

I've included a few underscores for readability.

A lot of games sort by the savefile's timestamp and order so that the most recent savegame is uppermost.
Now I am become Geoff, the destroyer of worlds

ElWanderer

Posts: 239
Joined: Mon Dec 12, 2011 5:05 pm UTC

### Re: Generating savegame names so they appear in sorted order

ElWanderer wrote:Another way is to insert a timestamp in YYYYMMDDhhmm(ss if needed) order.

20120101_1501_Game1
20120102_1256_Game2
20120103_0600_Game3
20120103_0601_Game4
...
20120124_1819_Game10
...
20120315_1945_Game156

I've included a few underscores for readability.

A lot of games sort by the savefile's timestamp and order so that the most recent savegame is uppermost.

If you're writing the game yourself and pre-appending something to sort on, I'll second timestamping (then display with or without the timestamp, if you display it with you can do some parsing to make it more human readable).

freakish777

Posts: 328
Joined: Wed Jul 13, 2011 2:14 pm UTC

### Re: Generating savegame names so they appear in sorted order

ElWanderer wrote:Another way is to insert a timestamp in YYYYMMDDhhmm(ss if needed) order.
That will break in the year 10000. The guy who started this topic wants a naming convention that would last forever, since he rejects fixed-length zero-padding.

You could fix it by using RFC 2550 representation of the year, but that's just a more sophisticated version of the "length-prefix followed by number" scheme I described.
Goplat

Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

### Re: Generating savegame names so they appear in sorted order

Goplat wrote:Assuming letters sort after numbers, you could name your games like this:
Code: Select all
`12...9A10A11...A99B100...B999C1000...Z999999999999999999999999999ZA1000000000000000000000000000...`

The prefix is asymptotically only 1/26 the length of the name. If you can't use letters, you could use a number base less than 10 and use the remaining digits for prefixes.

Hey, brilliant! It's analogous to a float.
Makes it clear that the issue was inability to accurately differentiate between the powers, something that must be explicitly stated in the name. I was initially thinking of how it would be stored in a char/int, (with zero-padding) thinking the solution had something to do with big-endian vs little-endian.

phlip wrote:Does it need to be human-readable / nice to look at? Because there are some simple ways to do it if that's not a requirement, if you're just generating a string that can be used (with the normal lexical comparison) to sort the original files... But they end up containing a bunch of cruft, and it won't really work if these need to be human-viewable in any way. For human-viewable, just go with 0-padding... if infinite extensibility is a concern, just have an automatic routine to go back and rename all the old files if a new one needs an extra digit.

It would be strange if a solution wasn't easily readable, at the very least for the small numbers as it would be short for those: it would have to be sub linear space; very small for n=1-4+, which would make it surprising if they weren't human readable.
Who, me?

Posts: 15
Joined: Wed Sep 21, 2011 4:51 am UTC

### Re: Generating savegame names so they appear in sorted order

Actually that inspires another slightly reasonablish way of doing it.

Use the schema
Code: Select all
`<# digits> <number> <description>`

a la
Code: Select all
`1 1 foo1 2 bar1 3 baz...1 9 borg2 10 foo2 11 bar...`

Not bad. You can go to 999,999,999 with that schema, and more if you allow letters as your "number of digits".
EvanED

Posts: 3767
Joined: Mon Aug 07, 2006 6:28 am UTC

### Re: Generating savegame names so they appear in sorted order

That's not infinitely extensible, though. :/
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4005
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Generating savegame names so they appear in sorted order

All you need is a character that is sorted before numbers, like "." is, and you can do this:
Code: Select all
`1 . guz3 . ish2 98 . feh2 11 91233485234 . buh3 214 1098349013847598374029837459328759032875903\...2857239048573249857324958732791783264987126347691\...8679087172364876120398710976368423631628344513324\...2583344336120874613465425653132455423341523545213\...554612352347563245452327 . fish`

You can also pretend that you are approaching 1, and add another digit every time you close half the distance. IE:
Code: Select all
`123455152533...7475751752..8748758751...`
Not quite as efficient on digits, but more intuitive and readable I think. Also, you don't actually have to follow any particular scheme for adding digits, you can do it almost at random as long as you don't wait about as long as possible, you'll still end up with roughly exponential growth for the size of your save names.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

WarDaft wrote:All you need is a character that is sorted before numbers, like "." is, and you can do this:
Code: Select all
`1 . guz3 . ish2 98 . feh2 11 91233485234 . buh3 214 1098349013847598374029837459328759032875903\...2857239048573249857324958732791783264987126347691\...8679087172364876120398710976368423631628344513324\...2583344336120874613465425653132455423341523545213\...554612352347563245452327 . fish`

I'm not sure what you're trying to do here, but your sample is definitely not lexically sorted...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6740
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Generating savegame names so they appear in sorted order

WarDaft wrote:
You can also pretend that you are approaching 1, and add another digit every time you close half the distance. IE:
Code: Select all
`123455152533...7475751752..8748758751...`
Not quite as efficient on digits, but more intuitive and readable I think. Also, you don't actually have to follow any particular scheme for adding digits, you can do it almost at random as long as you don't wait about as long as possible, you'll still end up with roughly exponential growth for the size of your save names.

Hm, If i understand you correctly, it's along the lines of:

Code: Select all
`123...990919293...99990991992...`

Which would work, but it's in p-space, as each new digit could only fit ten new names.
It's like reverse zero padding though, pretty cool.

Although that WOULD work if you could dynamically expand the digits after, like this

Code: Select all
`9091 9293...9899990099019902...9999999900009999000199990002...999999999999999900000000`

Which DOES expand in sub-linear space. It's a bit like int overflow.
Who, me?

Posts: 15
Joined: Wed Sep 21, 2011 4:51 am UTC

### Re: Generating savegame names so they appear in sorted order

Who, me? wrote:Hm, If i understand you correctly, it's along the lines of: [...] Which would work, but it's in p-space, as each new digit could only fit ten new names.

It's along the lines of that, but different, and it'll actually be in lspace (each new digit allows 5 times as many numbers as the previous digit before you need an additional digit).
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6740
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Generating savegame names so they appear in sorted order

# is the value operator.

SortedValue -> Base10Digit (Value = value of base 10 digit)
SortedValue -> LongValue (Value = #LongValue)
LongValue -> Length_Digits[#Length] (Value = #Digits)
Length -> Base10Digit (Value = value of base 10 digit)
Length -> A LongValue (Value = #LongValue)
Digits[n] -> n Base10Digits, not starting with a 0 (Value = Digits interpreted as a base 10 value)

And write out LongValue as your index.

The number 1 as a LongValue:
1_1
The number 1000 as a LongValue:
4_1000
A 10 digit number as a LongValue:
A2_10_1234567890
A 100 digit value:
A3_100_(100 digits here)
A 1 million digit value:
A7_1000000_(1 million digits here)
A 10^100 digit value:
AA2_100_(1 followed by 100 zeros)_(10^100 digit value)

This handles arbitrary number of save files. And in simple cases, you just put in # of digits_digits of value. Only after you have a google saves do you need to start with the A prefixes.

The number of A prefixes is about log*(n). The cost of the longest string is log(n) in size. log(n)*log*(n) is swallowed up by O(n) when you add the sizes together, so this doesn't significantly lengthen long numbers.

If I remember rightly, this behaves nicer than the Y10K standard does when fed large numbers. So if you are planning on having more saves in your directory than there are particles in the universe, think ahead and use this system.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk

Posts: 10039
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Generating savegame names so they appear in sorted order

Goplat wrote:Assuming letters sort after numbers, you could name your games like this: 1-9, A10-A99, B100-B999, ...
The prefix is asymptotically only 1/26 the length of the name. If you can't use letters, you could use a number base less than 10 and use the remaining digits for prefixes.

That is very nice.

It's obvious how to make a unary code which sorts correctly under lex, and as noted, the standard decimal code sorts correctly between numbers with the same number of digits, but not necessarily between numbers with different numbers of digits. Your method works by basically having a unary code for the number of digits of n (i.e. log n), followed by the standard decimal code for n.

You could drop the prefix's asymptotic fraction of the length from 1/27 to 0 by doing two levels of this trick: a unary code for log(log(n)) using letters K-Z, followed by a decimal code for log(n) using letters A-J, followed by a decimal code for n using digits 0-9. This uses approximately 17/16log(log(n)) characters in the prefix for n, rather than 1/26log(n).

It looks like Yakk's post above is doing roughly this, but generalizing to n levels rather than one or two levels, and sticking a unary code for the number of levels out front. (I didn't bother reading his code, which looked ugly and had confusing notation, and just looked at his examples.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 5920
Joined: Tue Nov 28, 2006 6:09 am UTC

### Re: Generating savegame names so they appear in sorted order

Hmm, suppose we don't like unary prefix codes or trying to count in letters. We can take the first method I proposed as a prefix, using a . to separate terms. The first number is not specifying the number of following digits, it is merely a unique tag.

Code: Select all
`01.01.1...1.81.92.002.01...2.993.1003.101...4.999950.00000...74.99999999999999999999999999999750.000000000000000000000000000000...`
It takes roughly log5(log10(n)) + log10(n) characters to name game n. It's not the most compact, but I think it's rather more readable. We can do the same for a recursive notation to make it more compact as well, but really, it's not necessary.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

skeptical scientist wrote:It looks like Yakk's post above is doing roughly this, but generalizing to n levels rather than one or two levels, and sticking a unary code for the number of levels out front. (I didn't bother reading his code, which looked ugly and had confusing notation, and just looked at his examples.)

Yeah, I couldn't understand what Yakk's code was attempting to say either. Based on his examples, his algorithm is:

1. Start with the save number, in normal base 10.
2. Prepend to that the number of digits in the save number (in base 10) and an underscore.
3. If the number just prepended had more than 1 digit, prepend its number of digits and an underscore. Repeat this step until the prepended number has 1 digit.
4. Prepend a number of As equal to the number of groups minus 2.

His last example, though, should be: AA3_101_(1 followed by 100 zeros)_(10^100 digit value)

This, of course, depends on "A" sorting after all digits. Interestingly, as far as I can tell it doesn't depend on the relative sorting order of "_" - it appears the separator can be anything, with any sort order (including in the middle of the digits) and still work. If one doesn't mind ruining readability even further, one could even use a digit as the separator. Use 9 as your unary prefix, 0 as your separator, and encode all your numbers in base-9 instead, and you can do the whole scheme with just the ten basic digits.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4005
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Generating savegame names so they appear in sorted order

Sorry about that bastard stepchild of boost::spirit grammar I used. It is nearly computer parse-able!

But yes, that is the idea. Quite reasonably efficient after your value gets unreasonably large. The number of A prefixes and _ infixes grows with log*, which is (in a sense) the absolute overhead of the format (you have to communicate the size of of the value, and the size of the size of the value, etc).

Really, you don't need a _ character at all. I just added it for readability. If you want to do it only with digits, nevermind base 9 -- simply state that any value starting with a 9 must be encoded as a 1 digit longer value starting with a 0, then use 9 as the prefix character.

9931011"0"9911"0"10^100
then encodes a googleplex in a sort-friendly manner. ("x"y denotes y repeats of the character x).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk

Posts: 10039
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Generating savegame names so they appear in sorted order

Yakk, a pretty good idea, it might be useful to me. thanks!
Last edited by windel on Thu Mar 29, 2012 8:20 am UTC, edited 4 times in total.

windel

Posts: 1
Joined: Tue Mar 27, 2012 2:58 pm UTC

### Re: Generating savegame names so they appear in sorted order

Yakk wrote:Really, you don't need a _ character at all. I just added it for readability. If you want to do it only with digits, nevermind base 9 -- simply state that any value starting with a 9 must be encoded as a 1 digit longer value starting with a 0, then use 9 as the prefix character.

Really, you only need to handle leading-9 in the frontmost group, since it's the only one that can clash with prefixes in an ambiguous way. And *then* all you need to do is start a new group instead (after all, writing it as "09" would start a new group anyway). This would be the only case where a group has the value "1", but that's okay. All you need to do is change rule 3 in my algo to say "If the number just prepended is >= 9".

9931011"0"9911"0"10^100
then encodes a googleplex in a sort-friendly manner. ("x"y denotes y repeats of the character x).

After seeing this, I think we should use a separator. ^_^

Anyway, I like the elegance and compactness of this system. A number which would, roughly, take the entire universe's entire history just to output has an overhead of only 107 digits (or 110 characters if you include separators). Gotta love loglog growth.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4005
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Generating savegame names so they appear in sorted order

Hmm. I just noticed just how many 9s there are in my system for larger numbers... this seems... redundant somehow. EG a googleplex would be prefixed:
Spoiler:
99999999999999999999
99999999999999999999
99898213021137226341
78698294000625207709
56422803697817288669
82167119870084093236
07338592410087585449
220.
42 nines just sitting there taking up space. Let's count them with a second prefix instead. That gives us:
Spoiler:
762.898213021137226341
78698294000625207709
56422803697817288669
82167119870084093236
07338592410087585449
220.
As the whole prefix. This is only 106 characters and so has totally counteracted the drawback of gaining only 'half' the benefit of each digit.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

Well, you can change the behaviour of your solution on a scale by changing the cutoff... "after some proportion x of all the numbers between the previous digit-adding and running out of numbers, add another digit". You proposed having x=0.5, meanwhile having x = 0.9 would be just "count to 9, then add another digit at 0 and increment it to 9, then add another digit and repeat", which would be asymptotically linear.

A smaller x has shorter number for large values, but longer numbers for short values. For instance, compare these:
Code: Select all
`      n x=0.1    x=0.5     x=0.9      0 0        0         0      1 10       1         1      2 11       2         2      3 12       3         3      4 13       4         4      5 14       50        5      6 15       51        6      7 16       52        7      8 17       53        8      9 18       54        90     10 190      55        91     11 191      56        92[...]    100 2719     820       999999999991   1000 34570    93970     9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991  10000 412129   974845    Yeah no. 100000 4719160  992210951000000 52572439 996605470`
By the time you get to a million, the 0.1 value is a digit shorter than the 0.5 value, and also hasn't even gotten close to reaching a leading 9 yet, while the 0.5 value already has two.

Spoiler:
Code: Select all
`#!/usr/bin/pythondef encode(num,x):   val = 0   maxlen = 10   cutoff = maxlen * x   intcutoff = int(cutoff) # convert the fractional value to an integer value of ceil(cutoff) to make the comparison in the loop faster   if intcutoff != cutoff:      intcutoff += 1   for i in xrange(num):      val += 1      if val >= intcutoff:         val *= 10         maxlen *= 10         cutoff *= 10         cutoff = (maxlen - cutoff) * x + cutoff         intcutoff = int(cutoff)         if intcutoff != cutoff:            intcutoff += 1   return valvals = range(0, 1000)from fractions import Fraction # so we don't have to worry about rounding errorsfor i in vals:   print "%7d %-8s %-9s" % (i, encode(i, Fraction(1,10)), encode(i, Fraction(1,3)))`
While no one overhear you quickly tell me not cow cow.
but how about watch phone?

phlip
Restorer of Worlds

Posts: 6740
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Generating savegame names so they appear in sorted order

That'll only decrease the size of the 9s by a percentage on average. 0.1 should reduce them by a factor of ln 0.5 / ln 0.9 * log 5 / log 9 (very close to 9).

What I found interesting was that the overhead in choosing 5 eventually becomes entirely wrapped up in the 9s.

But perhaps we can do something with the cutoff. Let's make it change over time. In fact, let's make 'the next' cutoff 1-1/(1+d) where d is the number of digits. So we count:
Spoiler:
Code: Select all
`01...45051..66670670..74975007501..799980000..83332833330..`

So in an n digit bracket, you have 10n(1/n-1/(n+1)) [give or take, rounding errors] items. Let's call this Sn. Sn/Sn+1 in fact tends towards 10, and so eventually we will be using every additional digit virtually ideally. We will still have a bit of unnecessary overhead creep in however... an unbounded amount in fact, since the harmonic series diverges. But this value should be proportional to the logarithm of the number of digits, and again, we can just take them out with a second prefix.

I'm not sure that this is asymptotically better than just x = 0.5 and prefixing the 9s though, I haven't coded it up properly yet. In the long run, the number of non-prefix-9 digits in the nth prefix seems to be within 1 of the digits of n regardless of base, so adding complexity seems unnecessary.
Last edited by WarDaft on Sun Apr 01, 2012 7:52 pm UTC, edited 3 times in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

This is why I prefer Yakk's scheme, by the way - the overhead is loglog rather than log.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4005
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Generating savegame names so they appear in sorted order

Hmm? My overhead for a googolplex was actually one less, even with the separators. The logs I stated at the begining work out to a constant, describing relative redundant overhead with only one layer and a constant cutoff ratio.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

Wait... I just realised binary works...

1
10
11
100
...

huh...
Who, me?

Posts: 15
Joined: Wed Sep 21, 2011 4:51 am UTC

### Re: Generating savegame names so they appear in sorted order

Er, either 1 comes before 0, or it comes after zero. So it would actually be more like:

1
10
100
11
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1538
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Generating savegame names so they appear in sorted order

right, duh

WarDaft wrote:Er, either 1 comes before 0, or it comes after zero. So it would actually be more like:

1
10
100
11
Who, me?

Posts: 15
Joined: Wed Sep 21, 2011 4:51 am UTC

### Re: Generating savegame names so they appear in sorted order

I reasoned this problem out without reading the responses, and ended up with a solution a lot like the "unary prefix" one. Given some further thought, I've come up with an (arguably) slightly better one, but I don't think there are any significant improvements that can be made.

Rationale:

Look at just the first character. There are finitely many possible things that it can be, and the choice of first character is (non-strictly) increasing in the savefile number, so there's a last character that it will be - for convenience, let's assume that that "last character" is Z. Since there are infinitely many more savefiles after the first one that starts with Z, there are infinitely many files that start with Z and finitely many that don't.

Apply the same logic to the second character. All but finitely many files start with ZZ. All but finitely many files start with ZZZ. And so forth.

In order to be less than linear, the number of files whose names start with n Zs and then a non-Z must increase as n increases. Obviously, the length of the filenames at any given Z-prefix length is bounded (since there are finitely many of them and each filename is finite in length). And obviously, we can't encode more information than (number of possible characters)^(name length bound past the Z-prefix), and there's no asymptotic benefit in *not* making every name at a given Z-prefix length be as long as that bound.

The only question is, what should be the function f(Z) from Z prefix length to number of characters after that? Goplat's solution has that be a linear function. But if it's asymptotically better than linear, then the Z prefix length will be entirely insignificant as the number increases, while if it's linear or worse, then the Z prefix length will be a noticeable extra cost for really, really big numbers. For purely asymptotic considerations, anything better than linear is fine. For practical considerations, we don't want it to go up ridiculously fast.

f(Z) = 2^Z seems like a natural choice.

So you'd have something like

Code: Select all
`12...9Z10Z11...Z99ZZ0100...ZZ9999ZZZ00010000...ZZZ99999999...`

To absolutely maximize the asymptotic efficiency, you can use *all* the available letters to help represent the numerical value. For instance, if we were only allowed 0-9 (and used 9 as the prefix character instead of Z)...

One catch is that you can't write numbers that start with 9 right after the prefix. One way to do that is to always put a delimiter character, like "1", after the prefix, which would be ignored (and there's always only one of it, so it's not asymptotically significant):

Code: Select all
`1112...1991109111...91999910100...9919999999100010000...999199999999...`

And just write the numbers in a higher base if you're allowed to use more characters than that. I'm pretty sure there's no way to do asymptotically better than that. 0-Z would look like this:

Code: Select all
`1112...191a...1ZZ110Z111...Z1ZZZZ10100...ZZ1ZZZZZZZ100010000...ZZZ1ZZZZZZZZ...`

The only solution I'd actually use for savefiles is Goplat's, which seems quite reasonable. Either that, or just use file managers that put things in numerical order.
1.708*10-51 / static_cast<char>(0x46 + 7*(rand()&1)) / no / the Divided States of America

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

Elvish Pillager

Posts: 943
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.