Принимая Chicken-Scheme в качестве реализации, вот попытка с некоторыми результатами.
(use srfi-1)
(use extras)
(time (unfold (lambda(x)(= x 1000000))
(lambda(x)(random 1000))
(lambda(x)(+ x 1)) 0))
(time (let loop ([n 1000000] [r '()])
(if (zero? n)
r
(loop (- n 1) (cons (random 1000) r)))))
(define (range min max body)
(let loop ((current min) (ret '()))
(if (= current max)
ret
(loop (+ current 1) (cons (body current ret) ret)))))
(time (range 0 1000000 (lambda params (random 1000))))
Результаты здесь с csc -O3 t.scm
0.331s CPU time, 0.17s GC time (major), 12/660 GCs (major/minor)
0.107s CPU time, 0.02s GC time (major), 1/290 GCs (major/minor)
0.124s CPU time, 0.022s GC time (major), 1/320 GCs (major/minor)
Как видите, версия автора намного медленнее, чем рекурсивные вызовы с простым хвостом. Трудно сказать, почему вызов раскрытия происходит намного медленнее, но я предполагаю, что это потому, что выполнение вызовов функции занимает намного больше времени.
2 другие версии очень похожи. Моя версия - почти то же самое, за исключением того, что я создаю функцию высокого порядка, которую можно использовать повторно.
В отличие от простого цикла, его можно использовать повторно для создания диапазона функций. Позиция и текущий список отправляются в функцию, если они необходимы.
Версия более высокого порядка, вероятно, лучший способ сделать это, даже если для его выполнения требуется немного больше времени. Вероятно, это также из-за вызовов функций. Его можно оптимизировать, удалив параметры, и он будет работать почти так же быстро, как названный let.
Преимущество версии более высокого порядка состоит в том, что пользователю не нужно писать сам цикл и его можно использовать с абстрактной лямбда-функцией.
Редактировать
Глядя на этот конкретный случай. Если мы хотим создать миллион элементов в диапазоне от 0 до 999, мы могли бы создать вектор фиксированной длины, равный миллиону, со значениями от 0 до 999. Перемешать вещь обратно после. Тогда весь случайный процесс будет зависеть от функции shuffle, которая не должна создавать новые значения подкачки памяти, может быть быстрее, чем генерация случайных чисел. Тем не менее, метод случайного выбора все еще полагается на случайный.
Редактировать 2
Если вам действительно не нужен список, вы можете использовать вместо него вектор.
Вот моя вторая реализация с vector-map
(time (vector-map (lambda (x y) (random 1000)) (make-vector 1000000)))
# 0.07s CPU time, 0/262 GCs (major/minor)
Как видите, это ужасно быстрее, чем использование списка.
Редактировать 3 веселья
(define-syntax bigint
(er-macro-transformer
(lambda (exp rename compare)
(let ((lst (map (lambda (x) (random 1000)) (make-list (cadr exp)))))
(cons 'list lst)))))
100000
0.004s CPU time, 0/8888 GCs (major/minor)
Возможно, это не очень хорошая идея, но я чувствовал, что это может быть интересно. Поскольку это макрос, он будет выполняться во время компиляции. Время компиляции будет огромным, но, как вы видите, улучшение скорости также огромно. К сожалению, используя курицу, я не смог составить список из миллиона. Я предполагаю, что тип, который он может использовать для создания списка, переполняется и обращается к недопустимой памяти.
Для ответа на вопрос в комментариях:
Я не профессионал Схемы. Я тоже новичок в этом, и, как я понимаю, именованный цикл или функция высокого порядка должны быть подходящим вариантом. Функция высокого порядка хороша тем, что ее можно использовать повторно. Вы можете определить
(define (make-random-list quantity maxran)
...)
Тогда это другая интересная часть, так как схема - это все о функциях высокого порядка. Затем вы можете заменить реализацию make-random-list на что угодно. Если вам нужно выполнение времени компиляции, определите макрос, в противном случае используйте функцию. Все, что действительно важно, - это иметь возможность использовать его повторно. Это должно быть быстро и не использовать память.
Здравый смысл говорит вам, что при меньшем выполнении это будет быстрее, хвостовые рекурсивные вызовы не должны занимать память. А когда вы не уверены, вы можете скрыть реализацию в функции, которая может быть оптимизирована позже.