-
-
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." |
gets, to_i и т.п. работает только с одним числом, в котором число байтов = количеству цифр одного числа (1-4 например)
когда считаем сложность - имеем дело с количеством чисел (10000 например)
Если чисел n, то оценка сверху количества байт: O(n_log(n)).
Сложность алгоритма по байтам: O(log(b)) ==> по числам: O(log(n_log(n))) ==> O(log(n) + log(log(n))) ==> O(n).
Это легко проверить эмпирически если считать количество вызовов. Оно линейно растёт относительно количества чисел.
Для сравнения. Реализация на питоне для 1000 чисел работает в два раза быстрее чем эта. Для миллиона чисел выходит разница в два порядка.
Да нет же. Здесь же не каждое число из файла читается. Бинарный поиск скачет по файлу вперёд-назад, а gets и to_i работают O(log(N)) раз. Или я чего-то не понимаю? А максимальная длина одного числа в байтах lg(N).
P.S. - ответ на предпредыдущий комментарий. С предыдущим поспорить сложно. Будет посмотреть.
Может быть, seek имеет линейную сложность? Тогда всё плохо - алгоритм был бы логарифмическим, если бы не реализация seek.
Причём, в общем случае, при фрагментированном файле, seek действительно вряд ли константа.
check_range вызывается дважды на каждой итерации (безусловно). Тут экспонента. Она гасится тем, что глубина -- логарифм. Итого: O(n).
Вполне себе условно. Третья ветка if.
В фибоначчи тоже if. Не тупи. Посчитай сам, если мне не веришь. Добавь счётчик вызовов и посмотри.
Я тоже не знаю по какому алгоритму работает seek, и если его сложность O(n), то конечно теряется смысл его использования.
Абсолютный seek(pos) используется только один раз, но этого достаточно чтоб испортить все до O(n*ln(n)).
Но что точно: если вы читаете весь файл подряд, у вас однозначно O(n), никакие буферизации и прочие уловки никак не помогут, и уже нет смысла городить бинарный поиск в полученном массиве, а проще и честнее добавить проверочку соседей по ходу считывания.
Ух ты ж ёжик, так вот почему здесь не требуется указывать количество чисел!
Так это не мешает читать из файла логарифмически - здесь алгоритм сам по себе линейный. Мдя. Но можно допилить до логарифма, если seek не подгадит.
уже нет смысла городить бинарный поиск в полученном массиве
Задача-то скорее академическая. Спасибо большое за идею побайтового seek - там точно прячется общий O(log(N)), если не подпортит seek.
И вам спасибо - за критику и наоборот! :)
В таком виде не прячется. Деление пополям байтов даёт такую фигню, что числа разбиты неравномерно, правая часть длиннее (там числа плотнее). Получается как с несбалансированным деревом, вместо log(n) вылазит n.
Надо бить не пополам.
Кстати - с 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
Это чисто формально логарифм. Файловый ввод/вывод и так буферизован.
Сложность gets тоже неплохо бы посчитать. Она не меньше O(n).
to_i тоже просканнирует все байты как O(n).
:)