访问SortedSet中特定元素的最有效方法是什么？ [英] What is the most efficient way to access particular elements in a SortedSet?

问题描述

我想使用一个已排序的集合，但我可以通过索引访问元素，即我想要一些具有Set和List特征的东西。 Java.util.TreeSet非常接近我的需求，但不允许通过索引进行访问。

I want to use a collection that is sorted, but one in which I can access elements by index, i.e. I want something that has characteristics of both a Set and a List. Java.util.TreeSet comes real close to what I need, but doesn't permit access via an index.

我可以想到几个选项：

1. 每次我需要一个特定元素时，我都可以迭代一个TreeSet。


2. 我可以维护一个TreeSet并生成一个当我需要访问特定元素时从中列出。


3. 与上面相同，只有缓存List才会更改Set。


4. 我可以拥有列表并在我需要添加元素时自行排序。


5. 等。

1. I could iterate through a TreeSet every time I needed a particular element.
2. I could maintain a TreeSet and generate a List from it when I needed to access a particular element.
3. Same as above, only cache the List until the Set changes.
4. I could have a List and sort it myself whenever I needed to add an element.
5. etc.

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

There are various trade-offs between the various options. I'm hoping somebody can give me some good advice. To answer the potential questions as to "why would you ever want to do that?", please read about the Apriori algorithm.

推荐答案

我遇到了同样的问题。所以我拿了java.util.TreeMap的源代码并写了 IndexedTreeMap 。它实现了我自己的 IndexedNavigableMap ：

I had the same problem. So I took the source code of java.util.TreeMap and wrote IndexedTreeMap. It implements my own IndexedNavigableMap:

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

实施基于更新红黑树中的节点权重改变了。权重是给定节点下的子节点数加一个自身。例如，当树向左旋转时：

The implementation is based on updating node weights in the red-black tree when it is changed. Weight is the number of child nodes beneath a given node, plus one - self. For example when a tree is rotated to the left:

    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只是更新权重到根：

updateWeight simply updates weights up to the root:

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

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

And when we need to find the element by index here is the implementation that uses weights:

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);
}

还可以非常方便地找到密钥的索引：

Also comes in very handy finding the index of a key:

    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;
}

您可以在 http://code.google.com/p/indexed-tree-map/

这篇关于访问SortedSet中特定元素的最有效方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！