Aug 23, 2016

Newest open source project: managed-commons-collections-squarelist

I've published the source for a tentative 1.0.0-beta for this MIT-Licensed project at GitHub.


What is a SquareList?


Basically a squared (same depth as width) structure formed from a List of LinkedLists, with items kept in ascending order, so that in constant time you can know the minimum and the maximum values, O(1). Also by being almost 'square' you can insert/search/delete values in a worst case time of O(sqrt(n)).


Implementation details


I implemented it as a generics-based collection, in C#, for .NetStandard1.0 .

Loosely based on an article published in the May 2013 issue of Dr Dobb's Journal, by Mark Sams.

This implementation allows for multiple instances of the same value to be inserted, and then deleted one-at-a-time or wholesale.
Thinking in performance, search for counting/existence is done bidirectionally, but removal scans only in the forward direction, to have stable behavior (remove the first found) when duplicates exist.

The trade-off is obviously about using more memory to achieve better performance, as there is no copying of large swaths of memory, or linear scans of the total mass of data, but the downside is lots of pointers from each node in both directions.

UPDATE: No longer using linked-lists for the columns, these now manage slices of a big array containing the whole set of values. So inserts now are penalized with moving blocks of values around, but the minimum subset is moved to create spaces for the insert. Problem still being worked on is about performing searches on sets that have a large part of it deleted. Shrinking the array is now done manually while expanding it is still automatic.
Post a Comment