Generating savegame names so they appear in sorted order

[Who, me?]

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

[phlip]

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.

[EvanED]

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.

[Goplat]

Assuming letters sort after numbers, you could name your games like this:

Code: Select all

1
2
...
9
A10
A11
...
A99
B100
...
B999
C1000
...
Z999999999999999999999999999
ZA1000000000000000000000000000
...


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.

[ElWanderer]

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.

[freakish777]

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

[Goplat]

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.

[Who, me?]

Assuming letters sort after numbers, you could name your games like this:

Code: Select all

1
2
...
9
A10
A11
...
A99
B100
...
B999
C1000
...
Z999999999999999999999999999
ZA1000000000000000000000000000
...


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.

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.

[EvanED]

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 foo
1 2 bar
1 3 baz
...
1 9 borg
2 10 foo
2 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".

[Xanthir]

That's not infinitely extensible, though. :/

[WarDaft]

All you need is a character that is sorted before numbers, like "." is, and you can do this:

Code: Select all

1 . guz
3 . ish
2 98 . feh
2 11 91233485234 . buh
3 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

1
2
3
4
5
51
52
533
...
74
75
751
752
..
874
875
8751
...


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.

[phlip]

All you need is a character that is sorted before numbers, like "." is, and you can do this:

Code: Select all

1 . guz
3 . ish
2 98 . feh
2 11 91233485234 . buh
3 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...

[Who, me?]

You can also pretend that you are approaching 1, and add another digit every time you close half the distance. IE:

Code: Select all

1
2
3
4
5
51
52
533
...
74
75
751
752
..
874
875
8751
...


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

1
2
3
...
9
90
91
92
93
...
99
990
991
992
...



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

90
91
92
93
...
98
99
9900
9901
9902
...
9999
99990000
99990001
99990002
...
99999999
9999999900000000


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

[phlip]

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

[Yakk]

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

[skeptical scientist]

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 ¹⁷/₁₆log(log(n)) characters in the prefix for n, rather than ¹/₂₆log(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.)

[WarDaft]

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

0
1.0
1.1
...
1.8
1.9
2.00
2.01
...
2.99
3.100
3.101
...
4.9999
50.00000
...
74.99999999999999999999999999999
750.000000000000000000000000000000
...


It takes roughly log₅(log₁₀(n)) + log₁₀(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.

[Xanthir]

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.

[Yakk]

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"⁹⁹11"0"^{10^100}
then encodes a googleplex in a sort-friendly manner. ("x"^y denotes y repeats of the character x).

[windel]

Yakk, a pretty good idea, it might be useful to me. thanks!

[Xanthir]

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"⁹⁹11"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.

[WarDaft]

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.

[phlip]

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  99221095
1000000 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/python
def 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 val

vals = range(0, 1000)
from fractions import Fraction # so we don't have to worry about rounding errors
for i in vals:
   print "%7d %-8s %-9s" % (i, encode(i, Fraction(1,10)), encode(i, Fraction(1,3)))

[WarDaft]

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

0
1
...
4
50
51
..
66
670
670
..
749
7500
7501
..
7999
80000
..
83332
833330
..

So in an n digit bracket, you have 10ⁿ(1/n-1/(n+1)) [give or take, rounding errors] items. Let's call this S_n. S_n/S_n+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.

[Xanthir]

This is why I prefer Yakk's scheme, by the way - the overhead is loglog rather than log.

[WarDaft]

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.

[Who, me?]

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

1
10
11
100
...

huh...

[WarDaft]

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

1
10
100
11

[Who, me?]

right, duh

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

1
10
100
11

[Elvish Pillager]

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

1
2
...
9
Z10
Z11
...
Z99
ZZ0100
...
ZZ9999
ZZZ00010000
...
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

11
12
...
19
9110
9111
...
9199
9910100
...
9919999
999100010000
...
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

11
12
...
19
1a
...
1Z
Z110
Z111
...
Z1ZZ
ZZ10100
...
ZZ1ZZZZ
ZZZ100010000
...
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.