On Sat, 20 Apr 2024 at 11:36, Claude Warren <cla...@xenei.com> wrote:
> The LayerdBloomFilter has a method find() that returns an array of ints
> that are the indices into the layer array. This is easily reproducible
> using an iterator.
> There is also get() method that takes an integer argument (an index of the
> bloom filter) and returns the Bloom filter from the layer. This is
> reproducible but not as efficient using an iterator.
>
Note that using an iterator is how the LinkedList would do this. We are not
using an ArrayList with Order(1) retrieval time.
So performance of the current implementation here is already Order(n).
> I think the array is the proper structure.
>
If an array is the correct structure then we should type to List. Typing to
an interface allows changing the implementation with no effect on the API.
For example changing to a concurrent data structure.
The question is what is the most important functionality? Order(1) add and
remove from the head and tail of the layers (Deque) or Order(1) retrieval
of layers by depth index (List).
Re: find
It currently returns the layer index. What would you do with this other
than call get(index) to get the BloomFilter. We could support this with a
different find method:
// find each bloom filter layer that contains the IndexProducer
// API can be changed if this is required to return as soon as a filter is
found that satisfies some requirement (Predicate vs Consumer).
public void findEach(IndexProducer indexProducer, Consumer<BloomFilter>
result)
Why else do you require indices of layers? If there is no use case
other than layer retrieval then this seems to be the wrong API.
Alex
> Claude
>
> On Fri, Apr 19, 2024 at 11:06 AM Alex Herbert <alex.d.herb...@gmail.com>
> wrote:
>
> > On Fri, 19 Apr 2024 at 08:26, Claude Warren <cla...@xenei.com> wrote:
> >
> > > While the Deque makes clear the idea of enqueueing and dequeueing the
> > > layers it does not have the method to natively traverse and extract
> > entries
> > > from the middle of the queue. Nor would I expect it to. So I think
> the
> > > Deque does not accurately reflect how the collection of Bloom filters
> is
> > > utilized.
> > >
> >
> > You can traverse and remove entries with the Iterator of the Deque:
> >
> > Deque<Integer> d = new LinkedList<>();
> > d.addAll(Arrays.asList(1, 2, 3, 4, 5));
> > for (Iterator<Integer> it = d.iterator(); it.hasNext();) {
> > int i = it.next();
> > if (i == 3) {
> > it.remove();
> > }
> > }
> > System.out.println(d);
> >
> > prints:
> >
> > [1, 2, 4, 5]
> >
> > So it is easy to iterate the layers and remove them in Order(1) time (per
> > removal).
> >
> > Alex
> >
> >
> > >
> > > On Wed, Apr 17, 2024 at 2:17 PM Alex Herbert <alex.d.herb...@gmail.com
> >
> > > wrote:
> > >
> > > > Looks good to me.
> > > >
> > > > Any opinions on changing the LayerManager to keep the layers in a
> Deque
> > > > rather than a LinkedList. I think it would only require a change to
> the
> > > > following method:
> > > >
> > > > public final BloomFilter get(int depth)
> > > >
> > > > Performance will be the same as the Deque can be a LinkedList. This
> is
> > > more
> > > > about how any custom downstream code is currently using the
> collection
> > of
> > > > layers.
> > > >
> > > > Alex
> > >
> > >
> >
>
>
> --
> LinkedIn: http://www.linkedin.com/in/claudewarren
>
