23

具体来说，我需要一个集合，它使用一个字段 A 进行访问，使用另一个字段（字段 S）进行排序，但接受重复的排序集合就足够了。

我经常遇到这种情况，我需要这个集合，而 TreeMap 不是一个选项，因为它不允许重复。所以现在是时候在这里问了。正如在此处和此处的stackoverflow上指出的那样，有几种解决方法-即：

  • PriorityQueue：缓慢更新（remove(Object) + add(Object)），以及原始键的装箱
  • 斐波那契堆：内存浪费（？）
  • TreeMap<Field_S, List<Value>>：对我来说问题是列表的内存开销和原始键的装箱
  • 排序列表或数组：问题是插入和删除速度慢 -> 我应该实现一个分段排序列表吗？
  • 来自番石榴的TreeMultimap （文档）：外部依赖和可能内存效率低下（？）

谁有更好的建议？或者我应该扮演我自己的排序数据结构（哪一个？）？其他来源（在 Java 中，开源，带有单元测试和小型 deps）也会很好。

更新

目前有关我的用例的更多详细信息（尽管我上次也有类似的需求）。我有一个集合（数百万）我想要的参考资料

  • 轮询或获取有关字段 S 的最小元素
  • 并在字段 A 的帮助下更新字段 S
  • 字段 S 的相同值可能会发生。字段 A 实际上是一个指向另一个数组的整数
  • 我想要的唯一依赖是trove4j。如果需要，我可以使用不同的 mahout 集合。但不是番石榴，因为虽然是一个不错的库，但集合并没有调整为内存效率（装箱/拆箱）。

所以所有人都在呼唤斐波那契堆，但我担心每个元素的开销太大 -> 这就是我考虑使用内存效率更高的“排序+分段数组”解决方案的原因。

4

6 回答 6

7

当您需要排序集合时，您应该仔细分析您的需求。
如果大多数操作是插入并且只有少数要搜索，那么使用排序集合，即保持集合中的元素不断排序，这不是一个好的选择（由于保持元素在插入时排序的开销，这将是最常见的操作）。
在这种情况下，最好保留未排序的集合并仅在需要时进行排序。即在搜索之前。你甚至可以使用一个简单的List排序（使用Collections.sort即合并排序）在需要时。但我建议谨慎使用，因为为了高效，假设您在处理大数据。在非常小的数据中，即使是线性搜索也足够好。

如果大多数操作是搜索，那么您可以使用排序集合，从我的角度来看，有可供选择的数据结构（您已经提到了一些），您可以进行基准测试以查看哪个适合您的需求。

于 2012-10-10T20:25:56.680 回答
3

番石榴TreeMultiset怎么样？你要求什么：一个接受重复的排序集合。虽然对它的性能一无所知。

于 2012-10-10T20:21:00.160 回答
2

我决定推出自己的但不是最佳解决方案，只是一个 TreeMap 变体。如果我会在内存方面微调这个集合，我会保持更新。速度已经比之前的 PriorityQueue 尝试好很多，因为我需要 collection.remove(Object) 方法（用于更新条目）：

package com.graphhopper.coll;

import gnu.trove.iterator.TIntIterator;
import gnu.trove.set.hash.TIntHashSet;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * A priority queue implemented by a treemap to allow fast key update. Or should we use a standard
 * b-tree?
 */
public class MySortedCollection {

    private int size;
    private int slidingMeanValue = 20;
    private TreeMap<Integer, TIntHashSet> map;

    public MySortedCollection(int size) {
        map = new TreeMap<Integer, TIntHashSet>();
    }

    void remove(int key, int value) {
        TIntHashSet set = map.get(value);
        if (set == null || !set.remove(key))
            throw new IllegalStateException("cannot remove key " + key + " with value " + value
                    + " - did you insert " + key + "," + value + " before?");
        size--;
        if (set.isEmpty())
            map.remove(value);
    }

    public void update(int key, int oldValue, int value) {
        remove(key, oldValue);
        insert(key, value);
    }

    public void insert(int key, int value) {
        TIntHashSet set = map.get(value);
        if (set == null)
            map.put(value, set = new TIntHashSet(slidingMeanValue));
//        else
//            slidingMeanValue = Math.max(5, (slidingMeanValue + set.size()) / 2);
        if (!set.add(key))
            throw new IllegalStateException("use update if you want to update " + key);
        size++;
    }

    public int peekValue() {
        if (size == 0)
            throw new IllegalStateException("collection is already empty!?");
        Entry<Integer, TIntHashSet> e = map.firstEntry();
        if (e.getValue().isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        return map.firstEntry().getKey();
    }

    public int peekKey() {
        if (size == 0)
            throw new IllegalStateException("collection is already empty!?");
        TIntHashSet set = map.firstEntry().getValue();
        if (set.isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        return set.iterator().next();
    }

    public int pollKey() {
        size--;
        if (size < 0)
            throw new IllegalStateException("collection is already empty!?");
        Entry<Integer, TIntHashSet> e = map.firstEntry();
        TIntHashSet set = e.getValue();
        TIntIterator iter = set.iterator();
        if (set.isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        int val = iter.next();
        iter.remove();
        if (set.isEmpty())
            map.remove(e.getKey());
        return val;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSlidingMeanValue() {
        return slidingMeanValue;
    }

    @Override
    public String toString() {
        return "size " + size + " min=(" + peekKey() + "=>" + peekValue() + ")";
    }
}
于 2012-10-15T20:15:34.617 回答
1

您需要决定是否需要外部依赖项。我不会为这样的事情推出自己的实现。

也就是说，你几乎没有告诉我们你用它做什么，以及你打算用它做什么。如果没有足够的数据，我们只能告诉你这么多——你真的需要以随机顺序访问元素吗？你希望这个系列有多大？我们真的没有足够的数据来挑选适合您需求的正确数据结构。

也就是说，这里有一些我会考虑的选项。

  • ArrayList或者PriorityQueue，取决于你是否真的需要支持remove(Object)。你？你确定吗？（即使您确实需要支持remove(Object)，如果集合可能保持较小，我也会选择此选项。）
  • 不是TreeList您链接到的，而是Apache Commons CollectionsTreeList。尽管有这个名字，它实际上并不维护排序顺序，但它所做的是支持 O(log n) 从列表中的任何位置添加、删除和获取。使用二进制搜索，您可能会根据值的排序部分实现添加、删除或查找的 O((log n)^2) 时间。
  • 你链接到的TreeList，或者——如果你和我一样，关心List合同——一个定制的 Guava ListMultimap，用Multimaps.newListMultimap(new TreeMap<K, Collection<V>>, new Supplier<List<V>>() { public List<V> get() { return new ArrayList<V>(); }}).

如果您还关心原始装箱，或者不能容忍第三方依赖项，那么您将别无选择，只能编写自己的数据结构。我只是将上面的实现之一调整为您的原始类型，但这将是一个非常痛苦的过程。

最后：我真的很想听听您的用例。Guava 对这样的事情没有任何支持，因为我们没有足够的需求，或者没有看到更复杂的数据结构真正适合的用例。

于 2012-10-10T23:41:23.963 回答
1

我会选择skiplist - 比树更节省内存，允许重复，为插入和删除提供O（logn）。您甚至可以实现索引跳过列表，它将允许您进行索引访问，这是树很难获得的。

于 2016-12-28T22:55:08.943 回答
0

我对 TreeMultimap 有很好的经验https://guava.dev/releases/19.0/api/docs/com/google/common/collect/TreeMultimap.html

于 2012-10-10T20:29:46.533 回答