Делает ли для / list ненужный реверс? - PullRequest
Новая
       85

Делает ли для / list ненужный реверс?

0 голосов
/ 30 сентября 2018

Я впервые ковырялся в Macro Stepper и заметил, что for/list расширен в код, включающий в себя нечто, называемое alt-reverse.for/list выводит каждый элемент в начало пустого списка и затем переворачивает его?Это кажется очень неэффективным.

Я написал небольшой тест: 

(define (test n)
  (time
    (for/list ([x (in-range n)])
      (list x x)))
  (time
    (for/fold ([result '()])
              ([x (in-range n)])
      (cons (list x x) result)))
  (void))

Действительно, версия for/list работает примерно в 150% случаев for/fold без reverse,разница, по-видимому, полностью связана с дополнительной сборкой мусора: 

> (test 500000)
cpu time: 1059 real time: 2079 gc time: 940
cpu time: 614 real time: 1231 gc time: 550
> (test 500000)
cpu time: 1060 real time: 3889 gc time: 907
cpu time: 770 real time: 1363 gc time: 699
> (test 500000)
cpu time: 1035 real time: 2479 gc time: 917
cpu time: 736 real time: 2535 gc time: 651

Похоже, я не должен привыкать звонить for/list.Есть ли более эффективный способ составить список в «прямом» порядке (т. Е. Где последний оцененный элемент является последним в списке)?

1 Ответ

0 голосов
/ 28 октября 2018

Просматривая историю Git, я вижу, что изменение, которое нужно сделать for/list избегать reverse, было совершено , но не сработало из-за тонкого взаимодействия спродолжения, которые могут привести к изменению поведения в четвертом времени.(Интересно, может ли предстоящий переход к бэкенду Chez Scheme означать, что «когда Racket однажды получит лучшую реализацию продолжений», это действительно может произойти в ближайшее время.)

Вы можете создать список в «forward»order by, как было сказано в первом сообщении о коммите, "cons на рекурсивный вызов".Разделы Racket Guide по рекурсии хвоста и рекурсия против итерации на самом деле обсуждают компромиссы между подходами map -тиля и for/fold -тиля.

Кроме того, для дальнейшего использования сообщество Racket стремится жить в очень активном и дружелюбном списке рассылки для пользователей ракеток и в некоторой степени в канале Slack, чем здесь, в Stack Overflow.

...