2

I am tasked with an animated graph based on a timeline, and I am having trouble finding a suitable data structure and/or algorithm that's reasonably efficient. I have a working system suffering from performance issues the larger my data set becomes.

Let's say I have a set of people in an array

[Bob, Jane, Kevin, Alice, Bob, Alice, Jane, Bob, Fred]

My end result will be a series of columns corresponding to how many people appear x number of times in the array.

Bob - 3 times
Jane, Alice - 2 times
Kevin, Fred - 1 times

This would translate in my graph to

Column 1 - 2 people who appear 1 time
Column 2 - 2 people who appear 2 times
Column 3 - 1 person who appears 3 times

Ordinarily, this data structure is a one time pass to build, and very quick. However, I have been tasked to build this as a timeline of the people in the array, in the order of the array.

Bob is the first person in the array. So we take him off and apply him to our graph. He currently is the only person factored in. So after we process him, our columns are

Column 1 - 1 person who appears 1 time
Column 2 - 0 people who appear 2 times
Column 3 - 0 people who appear 3 times

Next we add Jane, Kevin and Alice, so we have:

Column 1 - 4 people who appears 1 time
Column 2 - 0 people who appear 2 times
Column 3 - 0 people who appear 3 times

Now, we add Bob again, and our graph changes. Bob no longer factors in column one.

Column 1 - 3 people who appears 1 time (Jane, Alice and Kevin)
Column 2 - 1 person who appear 2 times (Bob)
Column 3 - 0 people who appear 3 times

This continues until the end of the array. The peformance currently slows when there are more than a few hundred data points.

I also need to know the end state of the graph up front to calculate sizing.

Can anyone assist with a structure/algorithm to store/manage the data so that performance remains linear?

  • My first observation is that, if this is a very sparse array (i.e. many columns with zero people), I don't think you need to bother storing the zeroes. If you use a dictionary with name as key and count as value, you can simply remove those entries that go to zero. – Robert Harvey Dec 11 '18 at 19:01
  • 1
    But it's unclear to me why you're getting a slowdown. A few hundred data points is not a lot, even with a linear list. Maybe you can show us your code that's implementing the algorithm? – Robert Harvey Dec 11 '18 at 19:03
  • @RobertHarvey I think it's because I am doing lots of filtering of the original array every iteration to calculate the full set of columns (yes, i know that's bad, which is why I am trying to find a solution). Unfortunately, I don't have access to the source from where I am writing this at the moment. – Jason Dec 11 '18 at 19:09
  • 1
    Can you provide a bit of pseudocode? – Robert Harvey Dec 11 '18 at 19:13
2

The most difficult requirement to me is the ordering requirement in your output if I understood correctly, like here:

Column 1 - 3 people who appears 1 time (Jane, Alice and Kevin)
Column 2 - 1 person who appear 2 times (Bob)

... if it's important that Jane appears before Alice, and Alice before Kevin in the output for the column. That makes the problem a tiny bit tricky.

Any time we're talking about ordering requirements of this sort combined with the need to remove elements from the middle (without a linear-time traversal to find the element as would typically be required for a singly-linked list), my goto solution is a doubly-linked list*.

  • I realize doubly-linked lists can have problems with memory efficiency, specifically spatial locality. I'll cover how to mitigate that later on if that becomes an issue in ways that will still tend to beat linear-time removals from the middle of a contiguous random-access sequence.

However the doubly-linked list is only half the solution. If you imagine we have a linked list storing people with each column, then when we encounter a person yet again in the input data, we'd have to iterate through the entire linked list to find the person and remove them before appending them to the next column's linked list. That linear-time traversal requirement becomes explosive with more and more people we encounter.

So the second part of the solution I suggest is to associate/map not only which column a person belongs in to a person, but also store a pointer/reference/index/handle to the linked list node storing them in that column. With that when we encounter a person a 2nd time, 3rd time, etc, we don't need to linearly traverse the column's list to find the relevant list node to remove. We can remove that node in constant-time.

That makes our data look like this:

struct Column
{
     // Stores the people in the column (the ones with matching 
     // counts).
     LinkedList<String> people;
};

struct Person
{
     // Stores the number of times we've encountered the person.
     // This also doubles over as an index (after subtracting 1)
     // to the column.
     int count;

     // Stores the position/node handle in the linked list associated to
     // the column to avoid a linear-time traversal when we want
     // to find/remove the person from the column.
     LinkedList<String>::iterator list_position;
};

// Stores the columns. We can add columns as needed. If reallocation
// of columns turns out to be expensive, you can store pointers to them
// and/or preallocate (reserve) many columns in advance.
ArrayList<Column> columns;

// Maps a person's name to associated data.
Map<String, Person> people;

I suspect this might already give you sufficient performance as it reduces the operation of removing a person from a column and adding them to a new one to no worse than logarithmic time, and easily constant-time (if you use a hash table for the map).

Yet below are some further optimizations you can make if you need to take it that far in response to hotspots.

Optimizing Map<String, Person>

The most natural sort of thing to reach for here is a hash table for the map. That would give you constant-time lookups to get from a person's name to the corresponding Person data which gives you the column index and list node to remove upon encountering them an nth time (as well as inserting them to the first column if they don't exist in the map).

However, I've managed to benchmark and improve the times of a string interning library using an optimized trie over C++'s hash_map when string keys are involved. That said, implementing a very optimized trie is not a trivial task, and if you don't already have one available, I would look for every possible reason not to bother unless you're actually seeing hotspots there.

Another alternative is that I've been assuming your original input data consists of strings for people's names. If that's not the case and they're objects within your control, if they can store an index with a dense range, then the map can simply turn into a parallel array. That would be cheaper than both solutions above since we just access elements in an array and don't even have to go through string keys or hash lookups.

Optimizing LinkedList<String>

This is getting a bit towards micro-optimizations (but not necessarily with microscopic effects, I've gotten "mega" effects from it) but you can implement linked lists (and all other linked structures, including trees) using contiguous arrays as the memory backing and largely mitigate the memory inefficiencies there (the need to dynamically allocate each node separately, and likewise mitigate the loss of spatial locality), and all without reaching for custom memory allocators like free lists. We can actually do this sort of thing:

template <class T>
struct ListNode
{
     T element;

     // The previous and next pointers are just relative indices into 
     // an array. -1 can be used in place of a null pointer.
     // If the node has been removed from the list, instead of pointing
     // to the prev/next node in the list, they point to the prev/next
     // free node to reclaim for subsequent insertions.
     int prev, next;
};

// Stores all the nodes contiguously in an array.
ArrayList<Node<T>> nodes;

// Stores an index to the first node in the list or -1 if the 
// list is empty.
int head;

// Stores an index to the last node in the list or -1 if the 
// list is empty.
int tail;

// Stores an index to the first free node or -1 if there are none.
int free_head;

Spatial locality still degrades in this case if you do many insertions and removals to/from the middle of this "array linked list", but at least you don't get cache misses with every single node being traversed. You can likewise easily restore the spatial locality if your copy constructor (or some other copying function) traverses the list and then inserts to the copy in order of traversal. When you remove nodes from the "array linked list", you push them to the free stack (see free_head above) which just involves manipulating integers. When you insert to the list, you append to the back of the array unless a free node is available to reclaim and then set the prev index of the node to the tail index and then the tail index to the node's position in the array (your standard CS doubly-linked list logic, only with relative indices instead of pointers and this "free stack" on the side).

If you do it that way, then the "handle" stored in Person to the linked list node likewise just turns into a relative index (integer) into the nodes array.

I actually implement practically all linked structures this way nowadays. The downside is that it can't deallocate memory every time you individually remove nodes (they don't get deallocated, they get pushed to the free list/stack), and it could allocate some more nodes than necessary at once when the array is reallocated to fit more nodes. Further it does invalidate pointers to the nodes so we have to work with relative indices to avoid invalidation (which means we need access to both the linked list and index to access an element through an index). In spite of all this I've found it much less of a hassle in performance-critical areas over reaching for custom allocators, and the copy constructor can compact the list (avoid the free nodes and make the nodes array tight) as well as restore any spatial locality that was lost as a result of insertions/removals to/from the middle.

Visualization of the "array linked list" after inserting some elements (our "free list/stack" is still empty and storing -1 to indicate null): enter image description here

Now we want to remove a node from the middle, so we adjust the links (which are just indices into the array) for the neighboring nodes to skip it: enter image description here

And then we push the node to the free stack (we set the free_head index to the node's index, and set the node's next link/index to the current value of the free head): enter image description here

Now if we want to insert a new node to the back of the "array linked list", we first pop off an index from the free stack if it's not empty. Then we overwrite the array at that position (if the free stack is empty and free_head is -1, we just append to the back of the array instead of overwriting an existing part of the array). Then we make our tail point to this new index and update the links on the new node (the rest is straightforward linked list implementation besides the free stack stuff).

The resulting diagram is scary-looking (and I might have drawn it incorrectly -- I'm squinting at it now and it looks like I might have missed updating a link) but only because I'm drawing how the nodes are laid out in memory in this array. It's a straightforward linked list implementation with the exception of the fact that we're using indices and have this "free stack/list" concept to reclaim previously removed node positions in the array on subsequent insertions to the back of the list.

enter image description here

And I devoted a rather hefty section to the linked list because so many people nowadays seem to think linked lists are almost useless (like favoring random-access sequences even when they need to remove from the middle of massive sequences). They have a point given how important the CPU cache is nowadays. But they can be a lot more useful in daily scenarios if we utilize this sort of "array linked list" approach to mitigate the immediate loss of spatial locality you get between nodes. In that case we're basically storing the nodes contiguously in an array but just storing indices to skip around in the array to get from one element to the next and from one to the previous. Of course if we start having to skip around too much all over the place then we've lost the spatial locality to get from one node to another as it is ordered in the linked nature of the array, but at least that takes a lot of insertions and removals from the middle before it degrades too much that way, and it's rather easy to restore (also we might still benefit from temporal locality of neighboring nodes in the array if we can access them before they're evicted from the cache). In my measurements they still tend to outperform just using a random-access sequence in large input cases that need frequent removals from the middle.

I'm still rather competitive performance-wise in my field and sometimes I feel like my ability to outperform some of my competitors isn't coming from algorithmic magic so much as just utilizing linked lists and leaning heavily on my profilers and little things like that while many of my peers have become allergic to them, but in a way where I don't degrade locality of reference too much or involve dynamic allocations per node. Of course if I implemented them the same way I started out when CPU caches were almost non-existent and pointers were a quarter of the size, they'd perform very poorly nowadays. But I've turned my old implementations into "array linked lists" with great benefit and in ways that still outperform turning them into just random-access sequences using arrays with linear-time insertions/removals to/from the sequence.

  • 1
    I ended up reworking the solution due to time constraints. And I probably should have mentioned the need to run it in a browser client, hence javascript. However this solution is really effective and well thought, so I'm accepting it. – Jason Dec 14 '18 at 22:31
  • Cheers! These methods should be applicable, even the micro-optimizations to linked lists, independent of the language (provided the language can store some type of "unboxed" primitive type contiguously in memory in an array). The basic idea though is a doubly-linked for constant-time removal and some sort of efficient associative structure (logarithmic time or better) storing the linked list node as part of what it maps to a key. The two combined let you preserve the relative ordering requirements of elements as they are inserted to the list while eliminating the linear-time [...] – Dragon Energy Dec 15 '18 at 11:16
  • [...] traversal you might otherwise need to find/remove that element from the list. – Dragon Energy Dec 15 '18 at 11:16
1

So you need an iterative approach where you could step/process one person at a time... mhmm

How about you do it like this:

// data structures look like this:
Map<String, Integer> personCount; // HashMap !
List<Integer> columnCount; // ArrayList !
// give columnCount an initial capacity of 128
// so that it grows in 64 increments/decrements
// to avoid reallocation/resizing of buffer
// which is costly

columnCount array represents your "graph". columnCount.get(i) -->

"Column " + (i+1) + " - " + columnCount.get(i) + " people who appear(s) " + (i+1) + " time(s)"

and here is how I would process a person:

process(String person) {
  Integer count = personCount.get(person)
  if (count != null) {
    personCount.put(person, count+1);
    int idx = count-1;
    columnCount.set(idx, columnCount.get(idx)-1);
    if (columnCount.size() < count) {
      columnCount.add(1);
    } else {
      columnCount.set(idx+1, columnCount.get(idx+1) + 1);
    }
  } else {
    personCount.put(person, 1);
    if (columnCount.isEmpty()) {
      columnCount.add(1);
    } else {
      columnCount.set(0, columnCount.get(0)+1);
    }
  }
}

To output your graph, just do this ~

for (int i = 0; i < columnCount.size(); ++i) {
  print "Column " + (i+1) + " - " + columnCount.get(i) + " people who appear(s) " + (i+1) + " time(s)"
}

The process method should be sufficiently "efficient" and be able to process thousands of data-points in a timely fashion.

The complexity of the process method should be O(1) in case the hashmap contains well/evenly distributed content. Otherwise, if they all map to one index (which is unlikely) the worst case scenario would be O(n). But I will go with O(1).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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