Accessing Subsets of an Array Efficiently

mscottveach

Newish to Processing/java and suspect that the answer to this might simply be a data structure I don't know about...

So, this is a question about best practices.

Basically, I have a medium-sized ArrayList of custom objects (about 300,000 of them). The objects each have a time stamp (a LocalDateTime). I pull them in form a file and when I do they're in chronological order.

Most of the work I am doing on this data involves looking at subsets based on time. So, for example, i often need to display an hour's worth of the data. Or sometimes I need to count how many objects have a time stamp from a particular date.

At first, I was just searching the array every time i needed to find a particular day or hour's worth but it seemed like a waste; so I built maps that indexed the array by some time. So, if I want to quickly access one day's worth of objects then I use my "ByDay" map where the key is a string that represents a day and the value is the index where that day starts in my array.

And I have a few of these maps. One for every major division of time: BYMonth, ByWeek, ByDay and ByHour.

It works and is more efficient than searching my array everytime but it feels incredibly clunky for what must be a common problem. Is there some data structure that maybe I'm not aware of that solves this kind of problem more elegantly? Or more efficiently? Have I stumbled squarely into the purview of databases? Should I be using a lightweight database to do this for me?

Anyway, I hope that's clear. I feel like I'm missing some vocabulary that would help me talk about this more clearly.

GoToLoop

Maybe instead of regular Map, go w/ TreeSet + Comparator:

1. http://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html
2. http://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

Got no previous experience w/ TreeSet though. But here's some template for you to start w/:

import java.util.Comparator;

static final Comparator BY_HOUR = new Comparator<Stamp>() {
  int compare(Stamp s1, Stamp s2) {
    return s2.hour - s1.hour;
  }
};

static final Comparator BY_MONTH = new Comparator<Stamp>() {
  int compare(Stamp s1, Stamp s2) {
    return s2.month - s1.month;
  }
};

import java.util.TreeSet;

final TreeSet<Stamp> byHour  = new TreeSet<Stamp>(BY_HOUR);
final TreeSet<Stamp> byMonth = new TreeSet<Stamp>(BY_MONTH);

void setup() {
  Stamp st = new Stamp();
  byHour.add(st);
  byMonth.add(st);
  exit();
}

class Stamp {
  int hour, day, week, month;
}

GoToLoop

Plus some previous forum threads about it:

1. https://forum.Processing.org/two/discussions/tagged/treemap
2. https://forum.Processing.org/two/discussions/tagged/comparator

GoToLoop

BtW, a simpler option is keep using List for each ordering; and then call Collections's sort() over each 1:

http://docs.Oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-java.util.Comparator-

Do that for each List whenever an object is added or removed or change its state! L-)