在日志(N)时间内插入和更新，性能更好
我正在使用Java开发一些金融算法。我有一个复杂的数据结构，有许多属性需要在算法的生命周期内更新。有时这个数据结构被更新超过1000次.
为了提高性能，特别是对于get(search)/update/insert，我决定使用TreeMap作为容器，在这方面非常有效。
现在是最具挑战性的部分。我需要更新需要从容器中检索它的数据结构属性，它需要：
- 检查容器是否有对象
- 如果是，则获取对象，否则创建新对象并添加到映射中。
- 如果对象存在于容器中，则更新它。
这个过程需要三个x(N)，即检查、获取和放置。我想在一个日志(N)时间内完成这个任务。
为此，我的解决办法是：
我总是使用insert/update/get在映射( put )中添加对象。put返回旧对象，我用旧值更新当前对象，这解决了log(n)，但是不同的对象丢失了对前一个对象的引用，因为新值在映射中被替换了。
是否有更好的解决方案或更好的容器来更新数据结构。我可以使用List并使用集合的二进制搜索，但为此，我需要重新排序数据结构，因为列表没有排序。
好心指南
回答 3
Stack Overflow用户
发布于 2016-01-28 11:48:07
我觉得你做得很好。
O(k.log(n)) = O(log(n))
其中k是常数。所以你的时间复杂度实际上是O(log(n))
Stack Overflow用户
发布于 2016-01-28 11:59:26
如果切换到1和2，就可以一次实现ConcurrentMap.computeIfAbsent(.)。它返回新/旧对象，以便您可以更新它。
如果是Java-7，那么putIfAbsent就需要一个额外的new --如果构建成本很高的话，这可能是件坏事。
Stack Overflow用户
发布于 2016-01-28 12:15:32
如果您不害怕周围有可变对象(您似乎已经给出了建议的解决方案)，那么您可以使用1-2操作来完成它。而不是
1. contains()
2a. exists? get(), modify, put()
2b. doesn't exist? create, put()你可以直接做
1. get()
2a. null? create put()
2b. not-null? modify object contents, as you already have reference这样，您就可以对现有对象进行1次搜索操作，并对非现有对象进行2次搜索操作。
如果您想进一步改进它，您可能需要使用ConcurrentHashMap (在您克服了对hashcode的不信任之后;)和putIfAbsent
1. old = putIfAbsent(createFresh())
2. old not null? update old说到这一点，我通常试图避免那些比单一方法的生存期更长的可变对象。在某种程度上，您可能想要多线程您的处理，而拥有可变的东西将使它变得更加复杂。但是有各种各样的权衡(比如记忆压力)，所以这取决于你。但是，请认真研究hashmap，它们可能是您在这里可以做的最大的优化，而不管对象(Im)的易变性如何。
https://stackoverflow.com/questions/35060529
复制相似问题
腾讯云开发者
