-
-
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." |
lseek это из слоя POSIX совместимости. Тут тупо перевызывается системный SetFilePointer.
Ещё одно решение. По дате подано вовремя, и это наш новый стажёр. https://gist.github.com/2850061
Производительность:
10000 1000000
=============================================================
python andy128kpython.py 0.046 1.188
sbcl --script andy128k.lisp 0.073 0.675
ruby bronislav.rb 0.148 0.761
ruby zhck.rb 0.149 0.739
ruby dmitriy-kiriyenko.rb 0.152 1.139
ruby raven29.rb 1.885 3:34.870
mysql test_num < dmitriy-kiriyenko.sql 1:13.460 not measured
Доказательство валидности байтового разбиения.
Кстати я вчера ошибся: пессимистическая оценка 3/4 : 1/4 неверная, правильно 5/8 : 3/8, что еще лучше и дает снижение производительности по сравнению с точным рабзиением в ln(2)/ln(8/5) = 1.5
- Числа данного разряда присутствуют в полном составе.
Т.е. в интервал включено 10^n-10^(n-1) n-разрядных чисел. В этом случае присутствие любого количества чисел до этого разряда даст отклонение от 1/2 : 1/2 не более 1/10.
Действительно среднее количество цифр (m - количество предыдущих цифр, заметим что их m <= 10^(n-1), это используется в доказательстве второго неравенства)
((10^n-10^(n-1))_n + ...)/(10^n-10^(n-1)+m) > ((10^n-10^(n-1))_n)/(10^n-10^(n-1)+m) > ((10^n-10^(n-1))_n)/(10^n) = (9/10)_n
Это означает что во вторую часть разбиения войдут только n-разрядные числа в количестве
x = ((10^n-10^(n-1))_n + ...)/(2_n) > (10^n-10^(n-1))/2 - середина ряда всех n-значных чисел
x = ((10^n-10^(n-1))_n + ...)/(2_n) < ((10^n-10^(n-1))_n + 10^(n-1)n)/(2_n) = (10^n-10^(n-1))/2 + 10^(n-1)/2 = (с точностью 1/10) = ((10^n-10^(n-1))/2)(1+10^(n-1)/10^n) = (11/10)*(10^n-10^(n-1))/2
Т.е. весь хвост предшествующих чисел сдвинет середину не более чем на 1/10 - Числа данного разряда присутствуют в неполном составе.
Тогда за ними следующего разряда уже нет, и важно только влияние предыдущего разряда, т.к. весь остальной хвост предыдущих дает отклонение не более 1/10 (см. 1). В этом случае середина числового ряда определяется количеством m1 n-значных и m2 (n-1)-значных чисел. Для малых и больших m1 оно приближается к байтовой середине и достигает максимального отклонения от байтовой середины при m1=m2(=m). В этом случае вторая часть разбиения содержит только n-разрядные числа в количестве
x = (m_(n-1)+m_n)/(2_n) = m_(1-1/(2_n))
Соответственно первая часть содержит
m+(m-x) = m_(1+1/(2_n)) всего n- и (n-1)-разрядных чисел
Таким образом, с точностью 1/10 (см. 1) имеем разбиение в отношении (1/2-1/(4_n)) : (1/2+1/(4*n))
Это отношение с ростом n монотонно приближается к вожделенной 1/2 : 1/2
При n=1, (n-1)=0 имеем 3/4 : 1/4, но это нереальный случай.
Реальная пессимистческая оценка начинается с n=2 и дает 5/8 : 3/8.
Полагаю, что доказательство максимума при m1=m2 из пункта 2 приводить необязательно: нужно рассмотреть отдельно случаи m1>m2 и m1<m2, а дальше - максимум кусочно-линейной функции, доступно любому знающему алгебру в объеме 7 классов средней школы.
Как терминировать мой бинарный поиск, я уже понял, это оказалось совсем несложно.
Когда будет свободное время в ближайшие день-два, допишу.
Спасибо Андрею за конструктивную часть критики в этом направлении.
Все получилось, код здесь:
https://gist.github.com/2908925
типичные средние результаты:
partition algorithm | 10,000 | 1,000,000 |
---|---|---|
"5/8" partition | 0.004767s | 0.009469s |
"1/2" partition | 0.004643s | 0.009897s |
Напомню, что все корректно работает для любого количества пропусков в любых конфигурациях, включая пропуски нескольких чисел подряд и пропуски с начала ряда (это касается функции check_range_pos(), подробности см. ниже).
Дима, а можно проверить это на вашем компе? Сравнить интересно, на правах "вне конкурса", конечно :)
И еще: поскольку для правильного кода потребовалась функция для подсчета числа байт-позиций в заданном целочисленном интервале, захотелось уже и реализовать алгоритм честного деления "1/2". Функция check_range_pos() - деление "5/8" (по байтам), check_range_num() - деление "1/2" (по числам). Эта функция не столь универсальна, т.к. будет глючить в случае нескольких пропущенных чисел подряд.
Что интересно, что их производителдьность практически совпадает, иногда даже "5/8" работает быстрее чем "1/2". Это скорее всего связано с тем, что "1/2" требует больше операций, возможно теоретическая разница проявится на бОльших количествах.
Я гонял тесты у себя дома, там завтра и запущу ваш. Это очень интересно. Спасибо вам большое. Решение прочитаю точно.
Деление по числам, в виду не универсальности, не так интересно, особенно с учётом того, что оно не столь однозначно лучше.
Спасибо!
С нетерпением жду результата... :)
Не совсем понимаю, как вам удаётся обойтись ещё и без знания количества пропущенных чисел, а код лёгким к чтению не назовёшь.
Но результаты вполне впечатляют, так что, завтра чтобы понять, буду рефакторить =)
Никакой уличной магии. :)
Фишка в том что пропуски сканятся только в парах ближайших соседей с любым отклонением от последовательного порядка, типа [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
andy128k
raven29