Created
May 30, 2012 07:49
-
-
Save dmitriy-kiriyenko/2834414 to your computer and use it in GitHub Desktop.
Find two skipped numbers in a natural sequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Run it only with ruby 1.9. | |
range = (1..(ARGV[0] || 10).to_i) | |
@g = Random.new | |
def gen_skips(n, range, ready = []) | |
return ready if ready.size == n | |
gen_skips(n, range, ready.push(@g.rand(range)).uniq) | |
end | |
skips = gen_skips(2, range).sort | |
fn = 'data.txt' | |
puts "Generating...\n\n" | |
step = [range.first, (range.last - range.first + 1)/100].max.to_i | |
File.open(fn, 'w') do |f| | |
range.each do |n| | |
print '*' if n % step == 0 | |
f.puts(n) unless skips.include?(n) | |
end | |
end | |
puts "\n\nGenerated #{fn} with numbers from #{range.first} to #{range.last} with #{skips.join(', ')} skipped." |
Никакой уличной магии. :)
Фишка в том что пропуски сканятся только в парах ближайших соседей с любым отклонением от последовательного порядка, типа [3;5], [2;7].
Ну и начало вычисляется отдельно, учитывая что это не обязательно 1.
За код "с душком" прошу прощения, я пока писал на это не обращал внимания, а теперь отлежаться должно для рефакторинга, так что заранее благодарю.
Да я всё понимаю - я ж не говорю, что вы плохо написали, я говорю, что так сразу не прочитаешь =) Не за что извиняться.
Обновлённая производительность:
10000 1000000 100000000
=====================================================================================
python andy128kpython.py 0.046 1.188 couldn't wait
sbcl --script andy128k.lisp 0.073 0.675 heap exchausted
ruby bronislav.rb 0.148 0.761 couldn't wait
ruby zhck.rb 0.149 0.739 couldn't wait
ruby dmitriy-kiriyenko.rb 0.152 1.139 couldn't wait
* ruby raven29_cool.rb 0.145 0.158 0.161
ruby raven29.rb 1.885 3:34.870 not measured
mysql test_num < dmitriy-kiriyenko.sql 1:13.460 not measured not measured
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Не совсем понимаю, как вам удаётся обойтись ещё и без знания количества пропущенных чисел, а код лёгким к чтению не назовёшь.
Но результаты вполне впечатляют, так что, завтра чтобы понять, буду рефакторить =)