3 ms·
Well, Java would still come out on top, in all likelihood. I don't think even the idiomatic solutions in Python/Ruby/etc. would be faster unless they have some
by devinj 17y ago
Well, Java would still come out on top, in all likelihood. I don't think even the idiomatic solutions in Python/Ruby/etc. would be faster unless they have some really nice JIT compilers I'm not aware of, or they changed the algorithm. They'd sure as hell be a lot smaller, though.
The real Python code I'd use to implement the defined algorithm would be a fifth of the size and running time (7 lines, sans whitespace, runs in 16.4 µs versus 92.7 µs under his timing scheme (it should really use min/timeit, not average/custom-timing-solution)).
import collections
def kill(size, nth):
chain = collections.deque(reversed(xrange(size)))
while len(chain) > 1:
chain.rotate(nth)
chain.popleft()
return chain.pop()
- keefe 17y agoThank you for this addition - this is a great article, exactly why I visit this site. I'm fairly surprised about the groovy execution time, I wonder if the ruby etc. enthusiasts could generate another set of benchmarks that support their particular bias.
- algorias 17y agoHow about: def kill(size, nth): lst = range(size) offset = nth-1 len_ = len(lst) while len_ > 1: del lst[offset::nth] offset = (offset - len_)% nth len_ = len(lst) return lst[0] It will reduce the list by 1/3rd each pass, so it's significantly faster at larger sizes.
- devinj 17y agoLooks great, except for the corner case of nth = 1. I was too lazy to figure out the slicing solution myself. :)