-
-
Save dmitriy-kiriyenko/2834414 to your computer and use it in GitHub Desktop.
# 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
Все получилось, код здесь:
https://gist.github.com/2908925
типичные средние результаты:
Напомню, что все корректно работает для любого количества пропусков в любых конфигурациях, включая пропуски нескольких чисел подряд и пропуски с начала ряда (это касается функции check_range_pos(), подробности см. ниже).
Дима, а можно проверить это на вашем компе? Сравнить интересно, на правах "вне конкурса", конечно :)
И еще: поскольку для правильного кода потребовалась функция для подсчета числа байт-позиций в заданном целочисленном интервале, захотелось уже и реализовать алгоритм честного деления "1/2". Функция check_range_pos() - деление "5/8" (по байтам), check_range_num() - деление "1/2" (по числам). Эта функция не столь универсальна, т.к. будет глючить в случае нескольких пропущенных чисел подряд.
Что интересно, что их производителдьность практически совпадает, иногда даже "5/8" работает быстрее чем "1/2". Это скорее всего связано с тем, что "1/2" требует больше операций, возможно теоретическая разница проявится на бОльших количествах.