-
-
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." |
И вам спасибо - за критику и наоборот! :)
Кстати - с check_range я действительно промахнулся, в проекте у меня было проверять каждый интервал, а не только парный, но в реализации как-то забылось.
А надо бы исправить, если получится.
С трудом продравшись сквось мрак сишного кода убедился - это вроде как если и O(N), то неявно. В винде вызывается http://msdn.microsoft.com/en-us/library/1yee101t(v=vs.80).aspx, в остальных вызывается вот это:
/* License: Ruby's */
off_t
_lseeki64(int fd, off_t offset, int whence)
{
long u, l;
int e;
HANDLE h = (HANDLE)_get_osfhandle(fd);
if (!h) {
errno = EBADF;
return -1;
}
u = (long)(offset >> 32);
if ((l = SetFilePointer(h, (long)offset, &u, whence)) == -1L &&
(e = GetLastError())) {
errno = map_errno(e);
return -1;
}
return ((off_t)u << 32) | l;
}
Мне кажется, что это константа.
В таком виде не прячется. Надо бить не пополам.
@raven29 что-то такое говорил, что это не мешает. Если мешает, как думаешь, с этим можно побороться, @andy128k? Потому что исправить второй недостаток, обязав указывать количество пропущенных чисел, как это делаем мы с тобой, довольно просто.
P.S. Гоню. Это код тоже из винды. Код для других операционок тупо найти не могу поиском по Руби.
andy128k
Деление пополям байтов даёт такую фигню, что числа разбиты неравномерно, правая часть длиннее (там числа плотнее). Получается как с несбалансированным деревом, вместо log(n) вылазит n.
raven29
Можно показать, что в самом худшем случае такое разбиение приблизительно дает пропорцию 3/4 : 1/4 (вместо 1/2 : 1/2) и соответственно приводит к сложности ln(2)/ln(4/3)O(ln(n)) = O(ln(n)), а время выполнения увеличивает менее чем в ln(2)/ln(4/3) = 2.4 раза. Здесь занудствовать не буду, но желающим могу предоставить подробное доказательство.
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
Задача-то скорее академическая. Спасибо большое за идею побайтового seek - там точно прячется общий O(log(N)), если не подпортит seek.