proposal: container/list: add trimming APIs #42040
Comments
|
Can't you do this already using |
ianlancetaylor
changed the title
|
The point is that for accomplishing the same result as the Trim functions i have proposed, you need to iterate the elements from front/back of the list, remove each of them up to the element to want your list to be trimmed to, which could go up to O(n-1) in time complexity. p.s: While in my implementation of the trim functions, I did not work on finding a workaround not to iterate through the elements being trimmed off, to maintain the correct length of the resulting list,. But I suppose an specific implementation is off the topic of the proposal. and even if there would not be a get away from that, these 2 APIs would provide a standard, safe and more performant (more perfomant than series of |
|
When generics happens, we are likely to deprecate list entirely in favor of new, properly typed APIs. This seems like a likely decline because we are not modifying this API anymore (ever). But feel free to use the code as the base of an implementation that does exactly what you want. |
|
No change in consensus, so declined. |
Motivation
LinkedLists are a good candidate for creating dynamic sliding windows over streams of data, and maintain some aggregated values for the data captured inside the window. They are suitable because they have O(1) Time complexity to push data to the back of the window, without performance issues of dynamic array/slice size. Also a pointer to the beginning of the window would be simply a pointer to an element in the list to allow O(1) access.But there is one downside to this application: as the stream continues to flow, the
LinkedListinside which we are maintaing our window would keep growing in size and there is no way currently in the Gocontainer/listimplementation to cut the old data which are past the window off it.Ofcourse I am certain one could think of many more general use cases for the functionalities I am going to propose.
Proposal
So I am proposing to add 2 APIs to the Go's
LinkedListimplementation to provideLeft TrimandRight Trimfunctionality, which would simply let the user cut the list into smaller one which considering theLinkedListstructure, could be accomplished by as easy as modifying therootandstart/endelements pointers to their neighbours.As an addition a
SubListAPI could also be provided which would allow for cutting both ends based on the provided elements at once.How
Well the how is very simple and I have already mentioned that in the Proposal section, but to be more specific, I have already applied my thoughts on a copy of the Go
container/list, which could be used as an ultimate demonstation of my thoughts accompanied with tests.https://github.com/siaminator/linked-list/blob/7c49a02b37803a6ca379a4546b95f2145d433ad9/list.go#L242
https://github.com/siaminator/linked-list/blob/7c49a02b37803a6ca379a4546b95f2145d433ad9/list.go#L259
There is one caveat to this functionality on
LinkedList, which is to maintain the correct length of the list after trimming. there is no way other than iterating through the cut part elements to be able to calculate the new lenght of the resulting array. I have took advantage of this iteration to unlink cut elements from each other to faciliate grabage collection.The text was updated successfully, but these errors were encountered: