访问 SortedSet 中特定元素的最有效方法是什么？

Question

我想使用一个已排序的集合，但可以通过索引访问其中的元素，即我想要同时具有集合和列表特征的集合。 Java.util.TreeSet 非常接近我的需要，但不允许通过索引进行访问。

我可以想到几个选项：

1. 每次需要特定元素时，我都可以迭代 TreeSet。
2. 当我需要访问特定元素时，我可以维护一个 TreeSet 并从中生成一个列表。
3. 和上面一样，只缓存List，直到Set改变。
4. 我可以有一个列表，并在需要添加元素时自行对其进行排序。
5. 等等。

各种选择之间存在各种权衡。我希望有人能给我一些好的建议。要回答有关“为什么要这样做？”的潜在问题，请阅读Apriori< /a> 算法。

Answer 1

https://github.com/geniot/indexed-tree-map

我有同样的问题。于是我就拿了java.util.TreeMap的源码，写了IndexedTreeMap。它实现了我自己的IndexedNavigableMap：

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

该实现基于红黑树中节点权重发生变化时的更新。权重是给定节点下的子节点数量加一 - self。例如，当一棵树向左旋转时：

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight 只是将权重更新到根：

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

当我们需要通过索引查找元素时，这里是使用权重的实现：

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

查找键的索引也非常方便：

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);
    
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

您可以在 https://github.com/geniot/indexed-tree 找到这项工作的结果-地图

Answer 2

有几点：

• 有点无法回答，但是当我最后一次需要重新实现频繁项集挖掘算法时，我选择了 FP-growth，它的性能与先验相当（或更好）而且，在我看来，更容易实施。该技术是由Jiawei Han等人开发的，基本上在数据挖掘：概念与技术中有专门的章节。 有点没有答案，但是

• 有几种开源工具采用相当标准化的输入（每行一个整数列表；整数代表项目，行代表项目集）。其中一些让您可以选择算法。其中许多都可以在此处获得许可：http://fimi.ua.ac.be/src/

• 请记住，除非您专门使用数组/向量，否则仅使用任何 List 实现都不会获得 O(1) 元素访问。更有可能的是，通过保留大部分或完全排序的数组（使用二分搜索查找超过特定限制的元素，以及用于随机访问的通常索引），您将获得更好的效果。

Answer 3

也许是 Treeset 和 apache commons 集合 API CollectionUtils.get() 会解决你的问题

Answer 4

我会研究LinkedHashSet。它维护 HashSet 的插入顺序。