2

rubymonkの演習に取り組んでいるときに、ハード サイズ制限のあるスタックを実装するように求められました。あまりにも多くの値をプッシュしようとした場合、または空のスタックをポップしようとした場合は、'nil' を返す必要があります。

私の解決策は以下にあり、その後に彼らの解決策が続きます。私のものは、IDE で指定できるすべてのテストに合格しましたが、rubymonk のテストには失敗しました。しかし、それは私の質問ではありません。

問題は、私のバージョンのようにスタックを縮小および拡大するのではなく、スタックを 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

1

彼らの解決策は、トップを見つけようとするときに nil をテストしません。

@top 値を最上位の要素のインデックスとして使用し、新しい要素が追加または削除されるたびにそれを増減します。これは、@top.succおよび@top.predメソッドの呼び出しによって行われます。

何かがポップされたときにスタックをゼロで埋める特別な理由はありません。理論的には、@top カウンターを減らして、そのスタック位置にあるものをそのままにしておくことができます。@Jan Dvorak が指摘したように、ガベージ コレクターからのメモリ リークを防ぐために、スタックは再び nil で埋められます。

あなたのバージョンは、Array.pop と Array.push の実装に依存しています。それらの特定の実装はわかりませんが、値をポップするときに、これらは実際には割り当てられたスペースを縮小しない可能性があります。

配列のサイズを常に変更することがパフォーマンスの問題になる理由:

サイズ 2 の配列を作成したいとします。これを行うには、Ruby はオペレーティング システムに、継続的に使用されず、サイズ 2 の配列を保持するのに十分な大きさのメモリのチャンクを要求する必要があります。これには 24 バイトが必要であるとしましょう。

したがって、2 つだけではなく 3 つの値をプッシュする場合は、サイズ 3 の配列のデータを保持できるオペレーティング システムから別のメモリ チャンクを要求する必要があります。これには 32 バイトが必要であるとしましょう。この新しい場所は、以前の 24 バイトの後に別のプログラムが独自の値を格納した可能性があるため、以前のメモリのチャンクと同じ場所ではない可能性があります。ここで、サイズ 2 の配列を新しい場所にコピーする必要があります。その後、3 番目の値をその配列に追加できます。

ここで要点は、rubys Array クラスは実際にはこのように動作しないということです。オペレーティングシステムから最初に指示されたよりも多くのメモリを常に要求する可能性が非常に高く、ポップのたびにそのメモリが減少することはありません。さらに、要求されたメモリが大きくなっても、おそらく Array 要素を 1 つ増やすことはありませんが、メモリが不足した場合は、一度に 2 倍のメモリを取得しようとするだけです。

于 2013-10-26T15:46:11.137 に答える