SubList of GapList as immutable GapList

[Henrik Nissen Ravn]

Hi Thomas,

I'm looking into your GapList and find it extremely compelling as I'm having exactly the basic use case that you describe in your summary paper: removing at beginning and inserting at end.

I'm using fork/join recursive/sequential processing cutting the array in halves per iteration until the size is appropriate for sequential processing. As I see it that cannot be done with GapList as of now because of the gap.

However, I believe it would be quite easy to implement a getSubList for GapList that would return an adjusted (not to include a gap) and immutable (because gaps cannot be controlled) slice of the original GapList as an immutable GapList.

What do you think?

Regards
Henrik Nissen Ravn
Sr. Solutions Architect
CA technologies

[Thomas Mauch]

Hi Henrik

I'm not exactly sure what exactly you try to achieve and where the problem with GapList compared to other list implementations like ArrayList is.
The fact that GapList uses a gap is completely invisible to the caller, so all operations you can execute against the List interface or an ArrayList instance are also valid for GapList.
You can e.g. use this code to split both GapList or ArrayList.

    static <T> List<T>[] split1(List<T> list) {
        int size = list.size();
        int mid = size/2;
        List<T> leftList = list.subList(0, mid);
        List<T> rightList = list.subList(mid, size);
        return (List<T>[]) new List<?>[] { leftList, rightList };
    }

Be careful however not to change the splitted lists in a non structural way as this will corrupt the data structure.
In this case you would need a splitting operation which copies the elements, as shown here for IList/GapList.

    static <T> IList<T>[] split2(IList<T> list) {
        int size = list.size();
        int mid = size/2;
        IList<T> leftList = list.getAll(0, mid);
        IList<T> rightList = list.getAll(mid, size-mid);
        return (IList<T>[]) new IList<?>[] { leftList, rightList };
    }

If you're looking for something different, please provide more details.

Regards
Thomas

[Henrik Nissen Ravn]

Hi Thomas,

I'm forking/joining like this:

    protected Summary compute() 

{

   int length = end - start;

   if (length <= THRESHOLD) 

     return sequentialIterator.iterateSequentially(start, end);

   

   RegressionRecurser<DataPoint, Summary> leftTask = new RegressionRecurser<DataPoint, Summary>(data, start, start + length/2, sequentialIterator);

   leftTask.fork();

   RegressionRecurser<DataPoint, Summary> rightTask = new RegressionRecurser<DataPoint, Summary>(data, start + length/2, end, sequentialIterator);

   Summary rightResult = rightTask.compute();

   Summary leftResult = leftTask.join();

   leftResult.merge(rightResult);

   return leftResult;

}

I.e. I'm using indexes into the ArrayList directly. Conceptually it would be nicer to use an immutable SubList provided such can be provided without copying elements - as I don't need to update the SubLists just iterate over them. I can do that efficiently with ArrayList but not with GapList.

Your IList implementation of doGetAll creates a new IList by copying elements - hence, reducing performance gains of GapList.

This is opposed to ArrayList that does NOT create a SubList by copying elements but just creates an imutable SubList that refers to the original underlying array.

Hence, my request: that GapList would provide a getSubList that would create a imutable SubList without copying elements but just refering to the underlying array. In order to optimize SubList performance the immutable SubLists could even be created without any gap.

Obviously I could use GapList with indexes directly as I do now with ArrayList. But, as said I find the SubList approach conceptually more correct, transparent, and general. And hence worth supporting directly in with GapList.getSubList(0, list.size()/2). 

Hope this clarifies my thoughts.

Regards & thanks

Henrik

--
Sie erhalten diese Nachricht, weil Sie in Google Groups ein Thema der Gruppe "brownies-collections" abonniert haben.
Wenn Sie sich von diesem Thema abmelden möchten, rufen Sie https://groups.google.com/d/topic/brownies-collections/M_hC0bvzny4/unsubscribe auf.
Wenn Sie sich von dieser Gruppe und allen Themen dieser Gruppe abmelden möchten, senden Sie eine E-Mail an brownies-collect...@googlegroups.com.
Weitere Optionen finden Sie unter https://groups.google.com/d/optout.

[Thomas Mauch]

Hi Henrik

As it seems your looking for List.subList(start, end) and as said you can use this method with GapList as you can use it for ArrayList.

So if you want the elements copied, you use
- GapList.getAll(start, length)
and if you want them shared, you use
- GapList.subList(start, end)
So in my understanding, GapList offers you both options.

Or what am I still missing?
Thomas

[Henrik Nissen Ravn]

Hi Thomas,

No, your thinking is correct. You're not missing.

Looking closer into your implementation I realize that my idea probably won't fly. It is not as simple to add as I first thought.

I'll test GapList and try to measure the performance benefit.

Btw. have you used GapList with the Perst persistence database? Any issues? 

Thanks

Henrik

--