时间戳

首页 > 解决方案 > 队列的两种实现中速度差异的解释

scala - 队列的两种实现中速度差异的解释

问题描述

我有以下实现队列的代码。一种使用链表，另一种使用两个堆栈（具有昂贵的出队操作），这反过来也使用链表实现。

我很困惑为什么堆栈实现上的入队操作更快，即使它们都使用相同的底层数据结构（链表）。我的代码如下（不显示重现行为所必需的操作）。

case class Node[T](data: T, var next: Node[T])

class StackList[T] {

  private var top: Node[T] = _

  private var total: Int = 0

  def push(item: T): Unit = {
    val o = top
    val n = Node(item, o)
    total = total + 1
    top = n
  }
}

class QueueStackDq[T] extends Queue[T] {

  val in = new StackList[T]

  val out = new StackList[T]

  private var total: Int = 0

  /**
    * Add an element to the queue's tail
    */
  def enqueue(item: T): Unit = {
    total = total + 1
    in.push(item)
  }
}



class QueueList[T] extends Queue[T] {

  private var tail: Node[T] = _

  private var head: Node[T] = _

  private var total: Int = 0


  /**
    * Add an element to the queue's tail
    */
  def enqueue(item: T): Unit = {
    val n = Node(item, null) // Create new node
    if (total == 0) {
      head = n
      tail = n
    }
    total += 1
    tail.next = n
    tail = n
  }
}

使用 1,000,000 条记录测试入队操作表明，链表实现在 0.01 秒内运行，而堆栈实现在 0.00026 秒内运行！这是一个显着的时间差异！

标签： scalaperformance

解决方案

我为这个示例问题创建了一个基于ScalaMeter的基准测试并将其放在GitHub 上。

在我的机器上，我为您的原始程序（标记为 V1.0）获得了如下基准（以毫秒为单位的计时）：

QueueStackDq: 5.757413
QueueList:    5.699053

在删除冗余并修复我评论中提到的错误后，基准变为（标记为 V2.0）：

QueueStackDq: 5.317035
QueueList:    5.670139

无论哪种方式，两种实现之间都没有太大差异（并且这些结果可能没有统计学意义，因为基准测试的样本量并不大）。

因此，要回答您的问题，事实证明堆栈实现毕竟并没有快几个数量级。您最初认为这两种方法应该相似的直觉是正确的，因为它们使用相似的数据结构。

顺便说一句，在Scalanull中使用和可变变量和集合是不受欢迎的。不使用任何一个的功能版本会更容易推理。

推荐阅读