Решение упражнения 1.22 из SICP
К сожалению, пауза в публикации решений затянулась. Буду наверстывать.
В 22-ом упражнении нас просят произвести замер производительности алгоритма вычисления простых чисел и подтвердить (или опровергнуть) экспериментально то теоретическое заключение, что его порядок роста равен Θ(√n).
Сначала вычислим, как указано в условии, наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Я несколько видоизменил код из условия с тем, чтобы сделать вывод более компактным и выводить только найденные простые числа. Также, поскольку я использую DrScheme, я сделал (runtime) (этой функции нет в стандартной библиотеке) алиасом для стандартной функции (current-milliseconds).
Код для экспериментов выглядит следующим образом:
(define (runtime) (current-milliseconds))
(define (timed-prime-test n) (start-prime-test n (runtime)))
(define (start-prime-test n start-time) (if (prime? n) (report-prime n (- (runtime) start-time)) false))
(define (report-prime n elapsed-time) (display n) (display " *** ") (display elapsed-time) (newline) true)
(define (search-for-primes number-from prime-count) (if (> prime-count 0) (if (timed-prime-test number-from) (search-for-primes (+ number-from 1) (- prime-count 1)) (search-for-primes (+ number-from 1) prime-count))))
В результате получаем:
> (search-for-primes 1000 3) 1009 *** 0 1013 *** 0 1019 *** 0
> (search-for-primes 10000 3) 10007 *** 0 10009 *** 0 10037 *** 0
> (search-for-primes 100000 3) 100003 *** 0 100019 *** 0 100043 *** 0
> (search-for-primes 1000000 3) 1000003 *** 0 1000033 *** 0 1000037 *** 0
Как видим, все измеренные временные интервалы нулевые. Это связано с тем, что современные компьютеры настолько быстры, что успевают выполнить все операции за время, меньшее порога чувствительности функции (current-milliseconds). Во времена выхода первого и даже второго издания SICP вычислительная мощь компьютеров была куда скромнее.
Для получения более интересных результатов, которые позволят проверить гипотезу о равенстве порядка роста Θ(√n), мы просто будем рассчитывать простые числа для интервалов, начинающихся с больших значений.
Вот что получается, если вычислять по 3 наименьших простых числа, начиная с 100 000 000 000, 1 000 000 000 000, 10 000 000 000 000, 100 000 000 000 000:
> (search-for-primes 100000000000 3) 100000000003 *** 422 100000000019 *** 672 100000000057 *** 672
> (search-for-primes 1000000000000 3) 1000000000039 *** 2328 1000000000061 *** 1922 1000000000063 *** 2062
> (search-for-primes 10000000000000 3) 10000000000037 *** 6188 10000000000051 *** 6157 10000000000099 *** 6297
> (search-for-primes 100000000000000 3) 100000000000031 *** 19844 100000000000067 *** 21765 100000000000097 *** 21016
Усредняя время вычисления по каждой из троек чисел, получаем:
n1=1011, t1=589 мс
n2=1012, t2=2104 мс, t2/t1=3.57
n3=1013, t3=6214 мс, t3/t2=2.95
n4=1014, t4=20875 мс, t4/t3=3.36
Все отношения tk+1/tk достаточно близки к √(nk+1/nk)=√10=3.16, то есть мы можем говорить, что гипотеза о равенстве порядка роста Θ(√n) подтверждается на практике.
Так же утвердительно мы можем ответить и на вопрос о совместимости полученного результата с предположением, что программы на машине затрачивают на выполнение задач время, пропорциональное числу шагов. Это очень важный факт, который, впрочем, как и многие другие важные и основополагающие факты, кажется очевидным.
Comments
Comment from Sergey Khenkin
Date: October 10, 2007, 9:31 pm
Любопытно, что Кен Дик, на которого я люблю ссылаться время от времени, в своем решении (http://www.kendyck.com/archives/2005/05/23/solution-to-sicp-exercise-122/) не смог ни подтвердить, ни опровергнуть гипотезу о порядке роста равном квадратному корню.
Pingback from SICP по-русски » Blog Archive » Решение упражнения 1.23 из SICP
Date: October 10, 2007, 10:25 pm
[…] SICP по-русски Структура и интерпретация компьютерных программ: заметки и решения « Решение упражнения 1.22 из SICP […]
Pingback from SICP по-русски » Blog Archive » Решение упражнения 1.24 из SICP
Date: October 11, 2007, 8:30 pm
[…] упражнение также базируется на упражнении 22, так что изучите его до того, как переходить к […]
Comment from Johnny
Date: November 5, 2009, 11:24 am
Странно. Похоже в DrScheme 4.2.2 (r5rs) current-milliseconds уже не является стандартной функцией. Вставляю ваш код и: reference to undefined identifier: current-milliseconds.
Comment from smersh
Date: December 30, 2009, 7:21 pm
2Johnny нужно установить новый язык SICP (установка работает только с последней версией drscheme!). Там рантайм уже есть в стандартной библиотеке.
http://www.neilvandyke.org/sicp-plt/
Comment from Dmitri
Date: July 25, 2010, 9:46 pm
В последней DrRacket вместо (runtime) следует использовать (current-inexact-milliseconds), тогда значения выдаются нормальные.
Кроме того, в вашем решении вы забыли выполнить условие задачи, что проверять следует только нечетные числа. Примерно вот так:
(define (odd? n)
(= (remainder n 2) 1))
(define (search-for-primes start-num count)
(if (< 0 count)
(if (timed-prime-test start-num)
(search-for-primes (+ start-num 1) (- count 1))
(search-for-primes (+ start-num 1) count))))
Write a comment