ruby - 奇怪的数组行为？

Question

我一直在练习编写一些算法(求职面试时间)，并且正在编写 Huffman 压缩算法，并遇到了 Ruby 数组类中看似奇怪的行为。

一旦我构建了我的堆，我就会对我的树进行预序遍历，并将符号和二进制值存储在哈希表中。方法如下。

def encode(huffman_tree, encoded_chars, binary)
    if huffman_tree.is_leaf?
        encoded_chars[huffman_tree.symbol] = binary
    else
        encode(huffman_tree.left, encoded_chars, binary + '0')
        encode(huffman_tree.right, encoded_chars, binary + '1')    
    end
end

这很好用，但我之前一直传入一个空数组作为二进制参数，然后附加到该数组

def encode(huffman_tree, encoded_chars, binary)
    if huffman_tree.is_leaf?
        encoded_chars[huffman_tree.symbol] = binary
    else
        encode(huffman_tree.left, encoded_chars, binary << 0)
        encode(huffman_tree.right, encoded_chars, binary << 1)    
    end
end

我承认只使用字符串更有意义，但我认为我应该能够用数组做同样的事情。但是，当我使用二进制作为数组运行算法时，每次对编码的递归调用都会导致二进制数组的大小增加(我认为每次方法返回时它都应该超出范围)这是使用二进制作为字符串运行的示例输出和然后作为一个数组。有人可以解释为什么会这样吗？

string
00000,
00001,
0001,
001,
01000,
01001,
0101000,
01010010

array
00000,
000001,
0000011,
00000111,
000001111000,
0000011110001,
00000111100011000,
0000011110001100010

Answer 1

您误解了运算符在这种情况下的工作方式:

string = 'test'
# => 'test'
string + 'string'
# => 'teststring'
string
# => 'test'
string << 'string'
# => 'teststring'
string
# => 'teststring'

字符串 +方法返回表示组合值的新字符串。数组 <<运算符向数组附加一些内容，它不会创建新副本。

你可能想要的是:

binary + [ 0 ]

这将创建一个新数组，但效率不是特别高。

重要的是要记住，Ruby 中的变量代表对对象的引用，任何作为参数传入的值都是共享引用。除非您使用指针或其他某种显式引用，否则其他语言将隐式复制所有参数以避免此问题。

换句话说，传递给方法的数组与方法接收的数组相同，因此对它的任何修改都在方法的范围之外。