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):
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:
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):
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.
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.
