mic*_*sza 5 collections smalltalk gnu-smalltalk
我想知道为什么这不在 GNU Smalltalk 中终止：
s := Set new. s add: s
理论上，s应该只是一个包含空集的集合。但是执行它只会永远循环，炸毁堆。
有趣的是，
((s := Set with: 4 with: 5 with: 6) add: s) size.终止并计算为 4。
ASet是一种HashedCollection专门为快速会员检查而设计的。a 内部Set有一个稀疏HashTable数组，其中包含许多空槽以最大限度地减少冲突次数。当我们将一个元素添加到 时，计算为，其中是mod运算，是表的长度。如果 at 的槽已被占用，则会递增，直到找到空闲槽，并将元素存储在那里（注意，因为 Smalltalk 数组是基于的。）Set 实际上是如何工作的]#add:SetindexHashTable(hash \\\\ size) + 1#\\\\sizeindexindex+ 11
现在，让我们看看问题代码会发生什么：
\n\n1. s := Set new.\n2. s add: s.\n如上所述，在步骤 2 中，add: s将计算：
s hash \\\\ p + 1\n其中p是 \ 的内表的初始槽数s（质数，在首次创建集合时设置为5或，稍后根据需要增加。）7
到目前为止，一切都很好。但可能有一些
\n\n在哪里？根据 Smalltalk 方言，元素的#printOn:下一个版本可能存在问题。add:
印刷问题
\n\n可能发生的一个问题#printOn:是无限递归。当打印 时s，人们也想打印它的元素，在我们的例子中，这种方法将递归地尝试s在过程中打印，从而创建无限的循环。
为了防止这种情况发生，Pharo使用 a LimitedWriteStream，它会在一定次数的迭代后停止写入，从而破坏递归（如果存在）。
我自己还没有检查过，但这似乎是 GNU Smalltalk 中发生的问题（根据问题。）
\n\n请注意，仅打印 中的最大数量的元素是不够的Set。事实上，我们的集合只包含一个元素（它本身），这足以创建递归。
加法问题
\n\ns正如 @aka.nice 在他的评论中所观察到的，第二次添加时也必须小心。为什么？因为，正如我们在上面的介绍中所看到的，消息add: s需要计算s hash \xe2\x80\xa6。又是如何s hash定义的呢？这是个有趣的问题。爱闲聊的人经常会遇到在某些课堂上实施善意的问题#hash。既然s是一个集合，那么很容易将hash其元素考虑到最终结果，对吧？Pharo 采用的是这种方法，看一下：
hash\n | hash |\n hash := self species hash.\n self size <= 10 ifTrue:\n [self do: [:elem | hash := hash bitXor: elem hash]].\n ^hash bitXor: self size hash\n它吞下了诱饵。为什么？因为集合s有 1 个元素（本身），所以条件self size <= 10是true，该方法会s hash再次尝试递归计算，导致哦哦，Stack Overflow。
实施时要小心Collection >> #printOn:。即使集合不包含自身，如果存在从其中一个元素到包含它的集合的间接引用，也可能会出现递归。
实施时要小心Collection >> #hash（同样的原因）
Collection向自身添加 a 时要小心。更一般地，当集合包含具有（可能是间接）引用的元素时要小心，因为枚举这样的集合可能很棘手。
在数学（科学）中，集合不能是其自身的元素（这是集合论公理明确禁止的）。因此，在违反这条来自极其成熟和进化的科学知识体系的规则之前，请重新考虑您的模型。
| 归档时间： |
|
| 查看次数： |
517 次 |
| 最近记录： |