The Idea
Have a Last-In-First-Out queue (implements java.util.Queue<E>) that will release old elements so that garbage collection (GC) can remove them. Like a cache that is a stack.
Continue reading “WeakAssQueue”Computer Programming for Humanoids
LIFO queue that will drop old elements when needed.
Have a Last-In-First-Out queue (implements java.util.Queue<E>) that will release old elements so that garbage collection (GC) can remove them. Like a cache that is a stack.
Continue reading “WeakAssQueue”Stalin-Sort using divide and conquer.
I just love this idea:
But when you have an input such as [42,1,2,3,4,5,6]
you just get
[42]
instead of [1,2,3,4,5,6]
. You can get a better result if you use divide and conquer. And that is something Stalin would do, don’t you think? So I implemented a recursive solution in Java. It tries all possible results, which is not a single pass and therefore defeats the purpose of having a fast O(n)
algorithm. And my implementation isn’t even in-place. A new data structure has to be created. That’s why I also added an implementation using a linked list, which is what Mathew describes.
The code is on pastebin: https://pastebin.com/rEmvZSiA
Here’s an implementation of a multiset in Java 8. It uses a Map<T, Integer>
to count how many times an object was inserted (multiplicity). It is not thread-safe, but there’s synchronizedMultiset(...)
and it always knows the current size in O(1)
. With the method asMap()
you can get a view of the multiset as a Map
, that will allow modification of the underlying multiset.
The code is on GitHub: github.com/claudemartin/multiset
This started as a simple implementation and is not rather complex. The iterator allows to remove elements during iteration. I tried to write my own Spliterator
, but it wasn’t faster than the default implementaion. Many methods are optimized and I added some set operations for multisets (union, intersect, minus). With merge(...)
you can merge two multisets with any operation.