up vote 0 down vote favorite

(There are some questions about time-efficient sparse arrays but I am looking for memory efficiency.)

I need the equivalent of a List<T> or Map<Integer,T> which

  1. Can grow on demand just by setting a key larger than any encountered before. (Can assume keys are nonnegative.)
  2. Is about as memory-efficient as an ArrayList<T> in the case that most of the indices are not null, i.e. when the actual data is not very sparse.
  3. When the indices are sparse, consumes space proportional to the number of non-null indices.
  4. Uses less memory than HashMap<Integer,T> (as this autoboxes the keys and probably does not take advantage of the scalar key type).
  5. Can get or set an element in amortized log(N) time where N is the number of entries: need not be linear time, binary search would be acceptable.
  6. Implemented in a nonviral open-source pure Java library (preferably in Maven Central).

Does anyone know of such a utility class?

I would have expected Commons Collections to have one but it did not seem to.

I came across org.apache.commons.math.util.OpenIntToFieldHashMap which looks almost right except the value type is a FieldElement which seems gratuitous; I just want T extends Object. It looks like it would be easy to edit its source code to be more generic, though I would rather use a binary dependency if one is available.

share|improve this question
2  
Please read this: meta.stackoverflow.com/questions/5234 and fix your accept rate – David Heffernan Sep 27 '12 at 16:42
feedback

2 Answers

up vote 1 down vote accepted

I would try with trove collections, there is TIntObjectMap which can work for your intents.

share|improve this answer
That looks good. I tried adapting OpenIntToFieldHashMap to a generic value type, which seems to have worked with ~10min work, but it only performs marginally better than TIntObjectMap. – Jesse Glick Sep 27 '12 at 17:06
It's good that you accepted an answer here. Now please have a look at your previous questions. – David Heffernan Sep 27 '12 at 17:15
feedback
up vote 0 down vote

A test case:

import gnu.trove.map.TIntObjectMap;
import gnu.trove.map.hash.TIntObjectHashMap;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import org.netbeans.insane.scanner.CountingVisitor;
import org.netbeans.insane.scanner.ScannerUtils;
public class Demo {
    public static void main(String[] args) throws Exception {
        System.out.println("HashMap size: " + sizeof(useHashMap()));
        System.out.println("TIntObjectMap size: " + sizeof(useTIntObjectMap ()));
        System.out.println("IntHashMap size: " + sizeof(useIntHashMap()));
    }
    private static int sizeof(Object o) throws Exception {
        CountingVisitor counter = new CountingVisitor();
        ScannerUtils.scan(null, counter, Collections.singleton(o), false);
        return counter.getTotalSize();
    }
    private static Object useIntHashMap() {
        // (source for this class not shown)
        IntHashMap<String> m = new IntHashMap<>(1000, "?", String.class);
        Random r = new Random();
        for (int i = 0; i < 9999; i++) {
            m.put(r.nextInt(Integer.MAX_VALUE), "val" + i);
        }
        return m;
    }
    private static Object useHashMap() {
        Map<Integer,String> m = new HashMap<>(1000);
        Random r = new Random();
        for (int i = 0; i < 9999; i++) {
            m.put(r.nextInt(Integer.MAX_VALUE), "val" + i);
        }
        return m;
    }
    private static Object useTIntObjectMap() {
        TIntObjectMap<String> m = new TIntObjectHashMap<>(1000);
        Random r = new Random();
        for (int i = 0; i < 9999; i++) {
            m.put(r.nextInt(Integer.MAX_VALUE), "val" + i);
        }
        return m;
    }
}

and the results:

HashMap size: 1017504
TIntObjectMap size: 853216
IntHashMap size: 846984
share|improve this answer
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.