7c45f63f61e478233f0c2ad3006b178c

Base WHAT??? Well, 62 is the number of alphanumeric characters. Base 64 makes more sense, but nobody can agree about what the two missing characters should be.

Ruby's Numeric#to_s(base = 10) method works great, but won't accept a base above 36. Hence my implementation, which works, but is VERY VERY SLOW.

Update: Rubinius actually does support base 62, and provides the c-code that does it:

http://www.google.com/codesearch?hl=en&q=+package:%22http://code.fallingsnow.net/svn/rubinius/trunk%22+mp_toradix_nd+show:8_qyRkJt6rs:_xHLAYhCNJI:gMCPZeygnhk&sa=N&cd=2&ct=rc&cs_p=http://code.fallingsnow.net/svn/rubinius/trunk&cs_f=shotgun/external_libs/libtommath/bn_mp_toradix_nd.c#first

Seems like my algorithm is plenty fast, it's just Ruby being s.l.o.w.

1
2
3
4
5
6
7
8
9
10
11
SIXTYTWO = ('0'..'9').to_a + ('a'..'z').to_a + ('A'..'Z').to_a

def to_s_62(i)
  return '0' if i == 0
  s = ''
  while i > 0
    i,r = i.divmod(62)
    s = (SIXTYTWO[r]) + s
  end
  s
end

Refactorings

No refactoring yet !

1f393f50dc29119d656c91d6701ddbba

Jeremy Weiskotten

November 2, 2007, November 02, 2007 02:48, permalink

2 ratings. Login to rate!

This seems to be about 20% faster. The test below runs the method for all numbers from 0 to 1 million.

Ruby is notoriously slow when it comes to concatenating strings, especially with the + operator. The << operator is faster. By using that operator, then reversing the string when finished, you should end up with the same result.

I also squeezed a bit more by computing the remainder and divisor separately instead of with divmod, avoiding the construction and cleanup of an Array.

You might be able to squeeze more out using bit shifting to divide and compute the remainder, but I think this is much better.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def to_s_62(i)
  return '0' if i == 0
  s = ''
  while i > 0
    s << SIXTYTWO[i.modulo(62)]
    i /= 62
  end
  s.reverse
end

# the test
start = Time.now
1_000_000.times do |i|
  to_s_62(i)
end
puts Time.now - start

Your refactoring





Format Copy from initial code

or Cancel