如何在Racket中创建一个列表，您可以按照添加元素的相同顺序进行迭代

Question

构建一个事物列表，然后需要按照添加到列表中的相同顺序对列表进行迭代，这是一个非常常见的编程用例。一个简单的例子可能是记录编译器错误，然后为用户打印它们。您希望源代码中较早的、您首先解析的错误是首先打印到屏幕上的错误。

但在Lisp/Scheme/Racket中，列表只有一个头指针，没有尾指针。这意味着您只能廉价地将元素添加到开头，并且只能以与添加顺序相反的顺序廉价地迭代元素。在学习Racket的过程中，我看到了很多构建列表，然后在(reverse the-list)上迭代的代码。在实践中，对于许多应用程序来说，这应该是可以的，但每次出现这种情况时，都必须向算法添加额外的N个运算，这似乎有点愚蠢。

有没有一个标准的习语/最常见的解决方案来解决这个问题？我总是可以用尾指针滚动我自己的列表类型，或者在Racket的可变向量上重新实现C++std:：vector，但这似乎足够常见，应该有一个已经建立的最佳实践来做什么。

Answer 1

我想不出用普通的Racket列表做这件事的任何方法。

有一个有效的替代方案，看看Racket的队列：https://docs.racket-lang.org/functional-data-structures/Queues.html

Banker’s Queue为排队、头和尾提供了摊销的O(1(时间，根据您的用例，这是您需要的功能。

更新：有几个队列适用于您的场景，@ben rudgers在评论中提到的另一个队列是强制队列：https://docs.racket-lang.org/data/Imperative_Queues.html

这也为enqueue!和dequeue!提供了恒定的时间。

Answer 2

我对C++中的std：：向量并不完全熟悉，但我相信Racket的可增长向量非常相似，可以用于此。可以通过添加(require data/gvector):https://docs.racket-lang.org/data/gvector.html

Answer 3

你知道他们说什么

真正的问题是程序员花了太多时间在错误的时间、错误的地点担心效率；过早优化是万恶之源(或者至少是大多数it(。

我所说的"他们"是指唐纳德·克努思和托尼·霍尔。

比较队列实现

下面的代码运行#lang racket的Bankers'Queue、Imperative Queue和一个颠倒的普通旧列表。这就是它们运行的顺序。每个都在一个计时函数内运行。'major垃圾收集是在运行每个垃圾之前在定时函数之外完成的。

#lang racket
(require data/queue) ;; the imperative queue
(require (rename-in pfds/queue/bankers
                    (queue->list bq2list)))
(define (run)
  (writeln "bankers' queue for 10,000")
  (writeln "imperative queue for 1,000,000")
  (writeln "reversed list for 1,000,00")
  (collect-garbage 'major)
  ;; bankers' queue
  (time 
   (define q (queue))
   (for ((i (range 10000)))
     (enqueue i q))
   (bq2list q)
   'done)
  (collect-garbage 'major)
  ;; imperative queue
  (time 
   (define q (make-queue))
   (for ((i (range 1000000)))
     (enqueue! q i))
   (queue->list q))
  (collect-garbage 'major)
  ;; reversed list
  (time
   (define q
     (for/list ((i (range 1000000)))
       i))
   (reverse q))
  'done)
(run)

典型输出

Welcome to DrRacket, version 6.6 [3m].
Language: racket, with debugging; memory limit: 1024 MB.
"bankers' queue for 10,000"
"imperative queue for 1,000,000"
"reversed list for 1,000,00"
cpu time: 1748 real time: 1752 gc time: 1000
cpu time: 664 real time: 664 gc time: 272
cpu time: 436 real time: 436 gc time: 180
'done
> (run)
"bankers' queue for 10,000"
"imperative queue for 1,000,000"
"reversed list for 1,000,00"
cpu time: 752 real time: 754 gc time: 8
cpu time: 660 real time: 661 gc time: 248
cpu time: 456 real time: 460 gc time: 192
'done
> (run)
"bankers' queue for 10,000"
"imperative queue for 1,000,000"
"reversed list for 1,000,00"
cpu time: 776 real time: 779 gc time: 40
cpu time: 692 real time: 693 gc time: 256
cpu time: 456 real time: 458 gc time: 184
'done
> 

插入结果

1. 一个惯用的简单的旧的反向列表往往是最快的[至少在这个天真的实现中]。由于减少了簿记和做预期的(即惯用的(事情，这并不特别令人惊讶。

2. 命令队列的速度与天真列表的速度大致相同。Racket的实现使用struct的。由于这些是Racket生态系统中更高级别类型的基本构建块，因此基于它们构建的数据结构的性能也就不足为奇了。如果队列语义很重要，那么队列抽象可能值得运行得慢一点。

3. 有时我在编程时会感到不耐烦，我听说这是一种美德，如果由于我的不耐烦而将Bankers’Queue的迭代次数从一百万减少到一万次是一种良性行为，那么也许有传闻证据表明这是一个良性行为。无论如何，Bankers‘Queue的运行速度比其他任何一个都慢两个数量级。当然，速度只是衡量性能的一个指标。线程安全是另一个问题，速度权衡可能是值得的