Scala（或Java）中保留插入顺序的自适应映射

Question

Scala（或Java）中保留插入顺序的自适应映射

javascalacollections

8

我想要找到并重复使用（如果可能）一个具有以下属性的地图实现：

在条目数量很少的情况下，比如小于32，在数组中进行底层存储，如[key0，val0，key1，val1，...]。这种存储方案避免了许多小型Entry对象，并且由于CPU缓存不会失效和指针不会间接进入堆，因此提供了极快的查找速度（即使它们是顺序扫描！）。
该映射应维护键/值对的插入顺序，而与条目数量无关，类似于LinkedHashMap

我们正在Scala中处理巨大的（数百万个节点/边缘）图形的内存表示，并且拥有这样的Map将允许我们以更高效的方式存储节点/边缘属性以及每个节点的边缘，适用于99％以上仅具有少量属性或邻居的节点和边缘，同时保留属性和边缘的时间顺序。

如果有人知道带有这些特性的Scala或Java映射，我将不胜感激。

谢谢

- Alex Kravets

1

仅供参考，我注意到原帖作者并不认为我的解决方案令人满意，并要求我将其删除。简而言之，我的想法是将所有内容放入索引数组中，类似Fortran的方式，然后在这个结构周围编写漂亮的包装器，使其易于处理。这种方法的优点是它非常快（主要由于只使用基元）并且自然地保留插入顺序（因为当您需要新条目时，只需将索引加1即可）。许多Fortran和C中的图形工作都是以这种方式完成的，但我同意我没有找到所需的映射。 - Rex Kerr

既然你已经在考虑实现，为什么不自己写一个呢？将数组或LinkedHashMap包装起来应该不难。 - starblue

1

你正在为一个特殊情况使用你的集合。因此，你不应该担心这种正常的保存方式。创建自己的数据结构会很有趣，可以获得更高的性能。你可以针对你的情况优化你的结构，因为似乎你非常了解你的图形。所以你应该考虑树、列表或其他东西，以获得最高可能的性能。也许你可以获得O(n*logn)或更低的运行时间性能....;) - Erhard Dinhobl

我最终会编写自己的自适应映射实现（当然是用Scala）。但我（也许是天真地）假设在实践中，有许多映射只有很少的条目，这种模式经常发生，以至于有人已经解决了这个问题 :-). - Alex Kravets

当条目数量较少时，例如 <32，则应该在类似于 [key0，val0，key1，val1，...] 的数组中进行底层存储。 - Alexey Romanov

3个回答

1

你是否使用分析器测量过 LinkedHashMap 是否对你来说太慢了？也许你不需要那个新的映射 - 过早的优化是万恶之源。无论如何，如果要在一秒钟内处理数百万甚至更多的数据，即使是最优化的映射也可能太慢了，因为在这种情况下每个方法调用都会降低性能。那么你所能做的就是将你的算法从 Java 集合重写为数组（即 int -> 对象映射）。

- iirekm

问题不仅仅是速度，而是分配、保留和垃圾回收的小 Emtry 对象的数量。 - Alex Kravets

但是分配时间会累加到程序的缓慢 - 分配的对象越多，程序就越慢，因此所有这些都归结为通过分析器进行性能测量。 - iirekm

今天，大多数计算机都有4GB的内存，内存使用优化很少有意义。然而，当有必要进行优化时，通常最好使用享元模式。Java Swing中的TreeModel中可以找到一个例子。与其使用node.getAttribute(key) = node.attributeMap.get(key)，不如使用node.getAttribute(key) = graph.attributeModel.getAttribute(node)。 - iirekm

分配会增加速度的慢 - 我同意，这就是为什么我不想分配所有那些不必要的Map.Entry对象，它们只是保存树指针 :-) - Alex Kravets

+1 赞同“过早优化是万恶之源”。 :D - Eric-Karl

0

在Java中，您可以维护一个二维数组（电子表格）。我编写了一个程序，基本上定义了一个具有3列数据和3列查找数据的2D数组。这三列是testID、SubtestID和Mode。这使我基本上可以通过testid和mode或任何组合来查找值，也可以通过静态位置引用。该表在启动时加载到内存中，并由程序引用。它可以无限扩展，可以根据需要添加新值。

如果您感兴趣，我今晚可以发布代码示例。

另一个想法可能是在程序中维护数据库。数据库旨在组织大量数据。

- Adam Outler

这个回答并没有解决我关于自适应映射的具体问题。我们考虑过其他图形表示方法，但由于很多技术原因我不能详细说明，我们必须保持“本地化”设计，其中图形节点、边缘等（所有原子）都必须有自己的属性映射对象。再次强调，我想避免常见模式，即为小型（<32个条目的映射）使用许多微小的Map.Entry类似对象以节省内存并维护CPU缓存局部性（即在实践中，扫描小数组总是比跟随堆指针链更快）。 - Alex Kravets

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ide · Accepted Answer

虽然我不知道有没有任何实现完全符合您的要求，但您可能会对查看Jakarta Commons库中的Flat3Map（source）感兴趣。

不幸的是，Jakarta库已经过时了（例如，在最新的稳定版本中没有泛型支持，尽管很高兴看到这在trunk中正在改变），我通常更喜欢Google Collections，但是了解Apache如何实现可能值得您花费时间。

Flat3Map不幸的是不能保留键的顺序，但是我对您原始帖子有一个建议。建议不要像[key0, val0, key1, val1, ...]这样将键和值存储在单个数组中，而是使用并行数组；也就是说，一个数组包含[key0, key1, ...]，另一个数组包含[val0, val1, ...]。通常我不赞成使用并行数组，但至少这样您可以拥有一个类型为K的数组，即您的键类型，以及另一个类型为V的数组，即您的值类型。在Java级别上，这有其自己的问题，因为您不能使用语法K[] keys = new K[32]；相反，您需要使用一些类型转换。