BucketList<T>March 21, 2021
BucketList<T>is a data structure that performs exceptionally well for a certain usage scenario:
n(list size) is large.
- Fast index-based access:
- Fast index-based removal:
In my use case, this reduced the runtime from 7 hours to 17 seconds!
An Interesting Problem
In December of last year I took part in solving the Advent of Code programming puzzles for the first time. Since then I became a bit obsessed with that and started solving also the older events going back until 2015.
Day 19 of 2016 presented an interesting challenge
that took me a while to solve (with a reasonable runtime) and led to the solution based
BucketList<T> data structure.
The basic idea behind this problem is that we have a:
- Circular data structure.
- Maintain a current element.
- Find the element opposite of the current element.
- Advance the current element by one.
- Repeat until the list has only one element left.
A poor solution
My first approach was using a
LinkedList which performed OK for small list sizes.
But for large lists (e.g. 3.001.330 was my puzzle input) the performance was dismal.
List size: 3001330. END after 26696.1142087 seconds.
That's a runtime of more than 7 hours 😬.
The problem was the linear search for locating the opposite element in the list that caused
Using a simple
List<T> (instead of
LinkedList<T>) performed equally bad because
in that case the remove operation causes a runtime complexity of
To sum it up:
A better (by a lot) solution
So I needed a data structure with linear or better performance for:
My solution was a custom data structure I called
BucketList (ha ha) which:
- maintains the elements in a list of lists
- that have the same maximum size (hence, buckets).
This way, when performing an index-based lookup I have nearly constant¹
O(1) access to elements
and removal is only limited by the
List<T> performance of a single bucket.
k amounts to the number of buckets which should be negligibly low compared
To sum it up:
k: number of buckets
n: bucket size (list size
This brought the runtime down dramatically!
List size: 3001330. END after 17.0722168 seconds.
17 seconds ... way better 🤩.
Here's the full source code for BucketList.
Note: A bucket size of
25.000worked best in that specific scenario but your mileage may vary, of course, and depends on the problem input size.
- I only used
BucketList<T>for this specific problem so far.
- The runtime performance depends on the selection of a bucket size for a given list size.
InsertAtcase is not yet considered.
- I'm sure that this data structure exists already with a different name. However, I came up with this on my own when solving my problem, so give me that ;-).