2

在进行ruby​​monk练习时，我被要求实现一个具有硬大小限制的堆栈。如果我尝试推送太多值，或者我尝试弹出一个空堆栈，它应该返回“nil”。

我的解决方案如下，然后是他们的解决方案。我的通过了我可以在我的 IDE 中提供的所有测试，而它没有通过 ruby​​monk 的测试。但这不是我的问题。

问题是，为什么他们选择用 nil 填充堆栈，而不是像我的版本那样让它收缩和增长？

它只会使他们的代码更复杂。

这是我的解决方案：

class Stack
  def initialize(size)
    @max = size
    @store = Array.new
  end

  def pop
    empty? ? nil : @store.pop
  end

  def push(element)
    return nil if full?
    @store.push(element)
  end

  def size
    @store.size
  end

  def look
    @store.last
  end

  private

  def full?
    @store.size == @max
  end

  def empty?
    @store.size == 0
  end
end

这是公认的答案

class Stack
  def initialize(size)
    @size = size
    @store = Array.new(@size)
    @top = -1
  end

  def pop
    if empty?
      nil
    else
      popped = @store[@top]
      @store[@top] = nil
      @top = @top.pred
      popped
    end
  end

  def push(element)
    if full? or element.nil?
      nil
    else
      @top = @top.succ
      @store[@top] = element
      self
    end
  end

  def size
    @size
  end

  def look
    @store[@top]
  end

  private

  def full?
    @top == (@size - 1)
  end

  def empty?
    @top == -1
  end
end
4

3 回答 3

5

我猜他们为什么这样做是因为他们不想使用array.pop并且 array.push您正在使用您的解决方案。那是一个教程，你正在学习实现一个 STACK ，所以如果你使用 ruby​​ array(pop和push) 给出的内置方法，那么那是非常没用的 :) 。

所以基本上他们试图让你的东西不那么抽象，所以你需要忘记 ruby​​ 已经包含pop，push然后编写一个解决方案，之后它看起来就像他们的解决方案。

我不是要批评你，只是说这个练习有什么意义。

请记住，在大学里，我们把所有的时间都花在了实现堆栈、套接字和其他东西上，后来我们意识到，对于很多东西来说，它们是定义的扩展。所以我建议一次性忘掉所有你知道的东西，然后做这些练习:)。

于 2013-10-26T15:59:21.293 回答
1

他们的解决方案在尝试找到顶部时不会测试 nil。

他们使用@top 值作为最顶层元素的索引，并在添加或删除新元素时递增和递减它。这是通过@top.succand@top.pred方法调用完成的。

没有特别的原因，为什么当某些东西被弹出时，他们用 nils 填充他们的堆栈。从理论上讲，他们可以只减少@top 计数器并将该堆栈位置的任何内容留在那里。正如@Jan Dvorak 指出的那样，堆栈再次被 nils 填充，以防止垃圾收集器的内存泄漏。

您的版本依赖于 Array.pop 和 Array.push 的实现。在弹出一个值时，这些可能实际上不会缩小分配的空间，尽管我不知道它们的具体实现。

为什么不断改变 Array 的大小是一个性能问题：

假设您要创建一个大小为 2 的数组。要做到这一点，ruby 必须向操作系统询问一块连续未使用且足够大以容纳大小为 2 的数组的内存。假设这需要 24 个字节。

因此，如果您现在要推送 3 个值而不是仅 2 个值，则必须从操作系统请求另一块内存，该内存现在可以保存大小为 3 的数组的数据。假设这需要 32 个字节。这个新位置可能与您之前的内存块不在同一个位置，因为在您之前的 24 个字节之后，另一个程序可能存储了他自己的值。现在您必须将大小为 2 的数组复制到新位置，然后才能将第三个值添加到该数组中。

现在的重点是rubys Array 类实际上并没有这种方式。它很可能总是会请求比您最初告诉操作系统更多的内存，并且不会在每次弹出后减少该内存。此外，如果它变大，它可能不会将请求的内存增加 1 个 Array 元素，但可能只是在内存不足时尝试一次获得两倍的内存。

于 2013-10-26T15:46:11.137 回答
1

他们没有充分的理由以这种方式实施他们的解决方案。在我看来，作为一个以编写 Ruby 应用程序为生的人，你的代码更好。

（一个区别是它们不允许将nils 推入堆栈。这可能是您的代码未通过测试的原因。）

于 2013-10-26T15:51:32.797 回答