原始值的映射替代 [英] Map alternative for primitive values

问题描述

我对我的应用程序进行了一些性能分析，结果之一表明，堆中大约18％的内存被类型为Double的对象使用.事实证明，这些对象是Map中的值，在这里我无法使用原始类型.

I did some profiling on my application and one of the results turned out that about 18% of memory on the heap is used by objects of type Double. It turns out these objects are the values in Maps, where I cannot use the primitive type.

我的推理是，double的原始类型比其对象Double消耗更少的内存.有没有一种方法可以拥有像数据结构这样的映射，该映射可以接受任何类型的键作为键，并接受原始的double作为值?

My reasoning is that the primitive type of double consumes less memory than it's object Double. Is there a way to have a map like data structure, that would accept any type as key and a primitive double as values?

主要操作为:

• 插入(可能只有一次)
• 查找(按键包含)
• 检索(按键)
• 迭代

我拥有的典型地图是:

• HashMap<T, HashMap<NodeData<T>, Double>> graph
• HashMap<Point2D, Boolean> onSea(虽然不是双精度值)
• ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>

• HashMap<T, HashMap<NodeData<T>, Double>> graph
• HashMap<Point2D, Boolean> onSea (though not a double value)
• ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>

所有与Java 8一起使用.

All used with Java 8.

附录

我主要对解决此类地图的框架不感兴趣，但对解决这些问题时应考虑的问题不感兴趣.如果需要，任何此类框架背后的概念/思想/方法是什么.或者解决方案也可能在另一个层次上，即按照某些模式(例如@Ilmari Karonen在其答案中指出)将对象替换为地图.

I am mainly not interested in frameworks that have a solution to these type of maps, but on what has to be considered when addressing these issues. If you want, what are the concepts/ideas/approaches behind any such framework. Or the solution may be also on another level, where the maps are replaced with objects following a certain pattern like @Ilmari Karonen pointed out in his answer.

推荐答案

其他人已经建议了几种原始值映射的第三方实现.为了完整起见，我想提到一些您可能要考虑的完全摆脱地图的方法.这些解决方案并非总是可行的，但是一旦有可能，它们通常将比任何映射都更快，内存效率更高.

Others have already suggested several third-party implementations of primitive-valued maps. For completeness, I'd like to mention some ways to get rid of the maps entirely that you might want to consider. These solutions won't always be possible, but when they are, they will usually be both faster and more memory-efficient than any map can be.

一个简单的double[]数组可能不像精美的地图那样性感，但几乎没有什么可以在紧凑性和访问速度上胜过它.

A simple double[] array may not be as sexy as a fancy map, but very little can beat it in compactness and speed of access.

当然，数组有很多限制:数组的大小是固定的(尽管您总是可以创建一个新数组并将其内容复制到其中)，并且它们的键只能是小的正整数，为了提高效率，应该足够密集(即，已使用密钥的总数应该是最高密钥值的相当大的一部分).但是，如果您的键碰巧是这种情况，或者如果您可以安排这种情况，那么原始值数组可能会非常有效.

Of course, arrays come with a bunch of limitations: their size is fixed (although you can always create a new array and copy the old one's content into it) and their keys can only be small positive integers which, for efficiency, should be reasonably dense (i.e. the total number of used keys should be a reasonably large fraction of the highest key value). But if that happens to be the case for your keys, or if you can arrange for it to be the case, arrays of primitive values can be very efficient.

尤其是，如果您可以为每个键对象分配一个唯一的小整数ID，则可以将该ID用作数组的索引.同样，如果您已经将对象存储在一个数组中(例如，作为某些更复杂的数据结构的一部分)，并按索引查找它们，则可以简单地使用同一索引在另一个数组中查找任何其他元数据值.

In particular, if you can assign a unique small integer ID to each key object, then you can use that ID as an index into an array. Similarly, if you're already storing your objects in an array (e.g. as part of some more complex data structure) and looking them up by index, then you can simply use the same index to look up any additional metadata values in another array.

如果您实现了某种冲突处理机制，则甚至可以省去ID唯一性的要求，但是到那时，您就可以很好地实现自己的哈希表了.在某些情况下，可能实际上是有道理的，但通常在那时，使用现有的第三方实现可能会更容易.

You could even dispense with the ID uniqueness requirement, if you implemented some kind of a collision handling mechanism, but at that point you're well on your way towards implementing your own hash table. In some cases that might actually make sense, but usually at that point it's probably easier to use an existing third-party implementation.

与其维护从关键对象到原始值的映射，为什么不仅仅将那些值变成对象本身的属性?毕竟，这就是面向对象编程的全部内容.将相关数据分组为有意义的对象.

Instead of maintaining a map from key objects into primitive values, why not just make those values into properties of the objects themselves? This is, after all, what object-oriented programming is all about — grouping related data into meaningful objects.

例如，为什么不给点加一个布尔值onSea而不是维护HashMap<Point2D, Boolean> onSea?当然，您需要为此定义自己的自定义点类，但是没有理由为什么不能让它扩展标准的Point2D类，以便可以将自定义点传递到任何方法中要求Point2D.

For example, instead of maintaining a HashMap<Point2D, Boolean> onSea, why not just give your points a boolean onSea property? Of course, you'll need to define your own custom point class for this, but there's no reason why you can't make it extend the standard Point2D class if you want, so that you can pass your custom points into any method that expects a Point2D.

同样，这种方法可能并不总是直接有效，例如如果您需要使用无法修改的类(但请参见下文)，或者要存储的值与多个对象相关联(例如，在ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>中).

Again, this approach may not always work directly, e.g. if you need to work with classes that you cannot modify (but see below), or if the values you want to store are associated with more than one object (as in your ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>).

但是，对于后一种情况，您仍然可以通过适当地重新设计数据表示来解决问题.例如，您可以定义一个Edge类，而不是将加权图表示为Map<Node, Map<Node, Double>>:

However, for the latter case, you may still be able to solve the problem by suitably redesigning your data representation. For example, instead of representing a weighted graph as a Map<Node, Map<Node, Double>>, you can define an Edge class like:

class Edge {
    Node a, b;
    double weight;
}

，然后向每个包含与该节点相连的边的节点添加一个Edge[](或Vector<Edge>)属性.

and then add an Edge[] (or Vector<Edge>) property to each node that contains any edges connected to that node.

如果您有多个具有相同键的映射，并且不能如上述建议那样将值转换为键对象的新属性，请考虑将它们分组为单个元数据类，并从键将单个映射创建为该对象的对象班级.例如，考虑定义单个元数据类，而不是Map<Item, Double> accessFrequency和Map<Item, Long> creationTime，

If you have multiple maps with the same keys, and cannot just turn the values into new properties of the key objects as suggested above, consider grouping them into a single metadata class and creating a single map from the keys into objects of that class. For example, instead of a Map<Item, Double> accessFrequency and a Map<Item, Long> creationTime, consider defining a single metadata class like:

class ItemMetadata {
    double accessFrequency;
    long creationTime;
}

并具有一个Map<Item, ItemMetadata>来存储所有元数据值.这比拥有多个地图更节省内存，并且还可以避免重复的地图查找，从而节省时间.

and having a single Map<Item, ItemMetadata> to store all the metadata values. This is more memory-efficient than having multiple maps, and may also save time by avoiding redundant map lookups.

在某些情况下，为方便起见，您可能还希望在每个元数据对象中包括对其相​​应主对象的引用，以便您可以通过对元数据对象的单个引用来访问这两个对象.自然而然地成为...

In some cases, for convenience, you may also wish to include in each metadata object a reference to its corresponding main object, so that you can access both through a single reference to the metadata object. Which naturally segues into...

作为前两种选择的组合，如果您不能直接在关键对象中添加额外的元数据属性，请考虑改为使用装饰器.因此，例如，您可以直接执行以下操作，而不是直接使用额外的属性创建自己的点类:

As a combination of the previous two alternatives, if you cannot directly add extra metadata properties into the key objects, consider instead wrapping them with decorators that can hold the extra values. Thus, for example, instead of directly creating your own point class with extra properties, you could simply do something like:

class PointWrapper {
    Point2D point;
    boolean onSea;
    // ...
}

如果愿意，您甚至可以通过实现方法转发将这个包装器变成一个成熟的装饰器，但是即使是简单的哑"包装器也可以满足许多目的.

If you like, you can even turn this wrapper into a full-blown decorator by implementing method forwarding, but even just a simple "dumb" wrapper may be sufficient for many purposes.

如果您然后可以安排仅存储和使用包装器，则此方法最有用，这样您就无需查找与未包装对象相对应的包装器.当然，如果确实需要偶尔执行此操作(例如，因为您仅从其他代码接收到未包装的对象)，则可以使用单个Map<Point2D, PointWrapper>来执行此操作，但是实际上您可以返回上一个替代方法

This approach is most useful if you can then arrange to store and work with just the wrappers, so that you never need to look up the wrapper corresponding to an unwrapped object. Of course, if you do need to do that occasionally (e.g. because you're only receiving the unwrapped objects from other code), then you can do that with a single Map<Point2D, PointWrapper>, but then you're effectively back at the previous alternative.

这篇关于原始值的映射替代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！