任何微弱的实习集合（对不可变对象） [英] Any weak interning collections (for immutable objects)

问题描述

在涉及不变的对象某些情况下，将有可能对许多不同的对象，以进入存在其中具有相同的语义。一个简单的例子是阅读文本的多行从一个文件转换为字符串。从程序的角度看，一个事实，即两行具有相同的字符序列将是巧合，但是从程序员的角度的大量复制的可预期。如果多串情况下是相同的，改变引用的不同实例为引用单个实例可以节省内存，同时也将促进它们之间的比较（如果两个字符串引用指向相同的字符串，就没有必要做一个character-逐个字符比较，以确定它们是相同的）。

In some situations involving immutable objects, it will be possible for many distinct objects to come into existence which are semantically identical. A simple example would be reading many lines of text from a file into strings. From the program's perspective, the fact that two lines have the same sequence of characters would be "coincidence", but from the programmer's perspective a large amount of duplication may be expected. If many string instances are identical, changing the references to those distinct instances into references to a single instance will save memory, and will also facilitate comparisons between them (if two string references point to the same string, there's no need to do a character-by-character comparison to determine that they are identical).

有关某些情况下，系统提供的串实习设施可能是有用的。它有，然而，一对夫妇的限制，例如：

For some scenarios, the system-provided string interning facility may be useful. It has, however, a couple of severe limitations:

1. 当一个字符串被拘留，该拘​​留的副本将永远活着，不论是否存在任何其他的参考吧
2. 在该字符串实习工厂只用字符串的作品，而不是与其他任何不变类型使用。

1. Once a string is interned, that interned copy will live forever, whether or not there exists any other reference to it
2. The string interning facility only works with strings, and is not usable with any other immutable types.

如果存在着一个真实的 WeakDictionary＆LT; ImmutableClassType，ImmutableClassType＆GT; （每个元素，键和值将是相同的），code可以这样做：

If there existed a true WeakDictionary<ImmutableClassType, ImmutableClassType> (for each element, the key and value would be identical), code could do something like:

if (theDict.TryGetValue(myString, ref internedString))
  myString = internedString;
else
  theDict[myString] = myString;

不幸的是，我不知道任何内置的 WeakDictionary＆LT的;关键字类型，valType＆GT; 类在.NET。此外，它似乎浪费生成每个项目的键和值，弱引用时，两个引用总是指向同一个东西。

Unfortunately, I am unaware of any built-in WeakDictionary<keyType, valType> class in .net. Further, it would seem wasteful to generate a weak reference for each item's key and value, when both references would always point to the same thing.

我读过一些关于 ConditionalWeakTable ，这听起来像一个有趣的课，但我不认为这将是有用的在这里，因为我们的目标是要能够采取一个实例，并找到另一个独立的实例，在语义上是等价的。

I've read some about ConditionalWeakTable, and that sounds like an interesting class, but I don't think it would be usable here, since the goal is to be able to take one instance and find another independent instance which is semantically equivalent.

有关，其中一个类的实例将有一个定义良好的生命周期的情况下，也可能是合理使用传统的词典合并相同的实例。在很多情况下，然而，可能很难知道何时这样的词典应该被抛弃或在其内的物品清理。 A 的WeakReference 为主的实习收集会避免这样的问题。有没有这样的事情存在，或可以容易地实现？

For situations where instances of a class will have a well-defined lifetime, it may be reasonable to use a conventional Dictionary to merge identical instances. In many cases, however, it may be difficult to know when such a Dictionary should be abandoned or the items within it cleaned out. A WeakReference-based interning collection would avoid such issues. Does such a thing exist, or could it be readily implemented?

附录 作为svick指出，一个词典＆LT; WeakReference的，WeakReference的＆GT; 从某种程度上说是有问题的，因为是定义没有实际的方法是的IEqualityComparer 这将有一个活的WeakReference 返回其目标的 GetHash code 的价值，并有死亡之一，不断返回该值。人们可以定义一个结构，其中将包括一个整数的目标散列code值（在构造函数中设置），而其自身的 GetHash code 将返回该整数。略有好转可能是使用一个 ConditionalWeakTable 链接的目标的WeakReference 来一个终结对象可以用来入队表要删除的项目。

Addendum As svick noted, a Dictionary<WeakReference, WeakReference> would be somewhat problematical as there would be no practical way to define an IEqualityComparer which would have a live WeakReference return the GetHashCode value of its target, and have a dead one continue to return that value. One could define a struct which would contain an integer target-hashcode value (set in the constructor), and whose own GetHashCode would return that integer. A slight improvement might be to use a ConditionalWeakTable to link the target of the WeakReference to a finalizable object which could be used to enqueue table items for deletion.

我不知道正确的平衡是想急切地清理字典，与采用较为被动的方法之间有什么（如执行添加项目时，如果上次扫描还有的是至少有一个GC扫，和添加的项的数量自上次扫描超过幸存它）的项数。通过一切在字典清扫不会是免费的，但ConditionalWeakTable可能不会要么是自由的。

I'm not sure what the proper balance is between trying to eagerly cleaning out the dictionary, versus taking a somewhat more passive approach (e.g. perform a sweep when adding an item if there's been at least one GC since the last sweep, and the number of items added since the last sweep exceeds the number of items that survived it). Sweeping through everything in the dictionary isn't going to be free, but ConditionalWeakTable probably isn't going to be free either.

PPS 另一种观点我想的，但我想它可能不会是一个弱实习的做法一样有用，将有一个逻辑上不变型抱一个可变的时间戳值，并且它接受一个比较方法的通过参数参考。如果两个不同的实例被发现是相等的，它们的时间戳值将被检查。如果两个零，他们将被从一个全局计数器（-1，-2，-3，等）分配连续负数。其中有（或分配）的下时间戳值的参数将随后由其他所取代。

PPS Another notion I was thinking of, but I figured it probably wouldn't be as useful as a weak-interning approach, would be to have a logically-immutable type hold a mutable "timestamp" value, and have a comparison method which accepts its arguments by ref. If two different instances are found to be equal, their timestamp values would be examined. If both zero, they would be assigned consecutive negative numbers from a global counter (-1, -2, -3, etc.). The parameter which had (or was assigned) the lower timestamp value would then be replaced by the other.

使用这样的方法，如果多个实例都针对对方反复比较，多参考文献将被替换成提到老的实例。根据使用模式，这可能会导致最同一对象实例被合并，而无需使用任何种类的实习字典的。应用这种方法与嵌套的对象，但是，这需要不可变对象允许嵌套对象引用突变为指向其他据称，相同的嵌套对象。这应该是罚款，如果所谓相同的对象始终是，而且可能会造成相当奇特的不端行为如果不。

Using such an approach, if many object instances were repeatedly compared against each other, many of the references would be replaced with references to "older" instances. Depending upon usage patterns, this may result in most of the identical object instances being merged without the use of any sort of interning dictionary. Applying such an approach with nested objects, however, would require that "immutable" objects allow nested-object references to be mutated to point to other supposedly-identical nested objects. This should be fine if "supposedly-identical" objects always are, but could cause rather bizarre misbehavior if not.

推荐答案

您可以创建类似词典＆LT; WeakReference的，WeakReference的＆GT; 与自定义相等比较器和修剪那些不再活在适当的时间。有一个问题是，如何从字典中删除死 WeakRefrence ，因为你无法通过引用相等（记住，你必须使用自定义的相等比较器）或将其删除指数。可能的解决方案是创建一个类继承自的WeakReference 并有正确的哈希值code，即使引用是死了。或者你可以在自定义其包装结构。

You could create something like Dictionary<WeakReference, WeakReference> with a custom equality comparer and prune those that are no longer alive at appropriate times. One problem with that is how to remove a dead WeakRefrence from the dictionary, because you can't remove it by reference equality (remember, you have to use custom equality comparer) or index. Possible solutions are creating a type that inherits from WeakReference and has correct hash code even if the reference is dead. Or you could wrap it in a custom struct.

但正如你所说，这将是很好，如果每个参考是从字典中取出后立即死亡。我认为，要做到这一点的唯一方法就是以某种方式使用终结。但是，如果你不想（或不能）修改了字典中的类型，这将变得相当复杂。

But as you said, it would be nice if each reference was removed from the dictionary immediately after it died. I think the only way to do this is to somehow use finalizers. But if you don't want to (or can't) modify the type in the dictionary, this will get quite complicated.

其基本思想是，你将有弱引用与上述相同的字典（有关如何删除项仍然适用的注意事项），但你也有一个终结使用附加辅助对象的每个项目在字典中 ConditionalWeakTable 。而在这终结，你会从字典中删除的项目。因为如何 ConditionalWeakTable 的作品，如果在字典中的一个项获得GCed，附加的对象也不能免俗，这意味着它的终结将被调用，因此该项目将予以除名词典

The basic idea is that you will have the same dictionary of weak references as above (the caveats about how to remove items still apply), but you also attach a helper object with a finalizer to each item in the dictionary using ConditionalWeakTable. And in that finalizer, you will remove the item from the dictionary. Because of how ConditionalWeakTable works, if an item in the dictionary gets GCed, the attached object will too, which means its finalizer will be called and so the item will be removed from the dictionary

这篇关于任何微弱的实习集合（对不可变对象）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！