What is the most efficient way to access particula

Question

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.

I can think of several options:

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.

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.

Answer 1

I would look into LinkedHashSet. It maintains insertion order of a HashSet.

Answer 2

Perhaps a combination of Treeset and the apache commons collections API CollectionUtils.get() would solve your problem

Answer 3

A couple of points:

• Sort of a non-answer, but when I last needed to re-implement a frequent itemset mining algorithm, I went with FP-growth, which has performance on-par (or better) than a priori and, in my opinion, is easier to implement. This technique was developed by Jiawei Han and others, basically has a dedicated chapter in Data Mining: Concepts and Techniques.

• There are several open-source tools that take a pretty standardized input (one list of integers per line; integers represent items, lines represent itemsets). Some of them give you a choice of algorithms. Many of them are available here with permissive licenses: http://fimi.ua.ac.be/src/

• Keep in mind that using just any List implementation doesn't get you O(1) element access unless you specifically use an array/vector. More likely, you'll get better mileage out of keeping a mostly- or fully sorted array (with binary search for finding elements over a specific limit, and usual indexing for random access).

Answer 4

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

You can find the result of this work at http://code.google.com/p/indexed-tree-map/