search

chen870647924 / guava-libraries

Automatically exported from code.google.com/p/guava-libraries
Apache License 2.0
0 stars 0 forks source link

List implementation supporting efficient insertion and removal #869

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Discussed on the mailing list here: 
http://groups.google.com/group/guava-discuss/browse_thread/thread/638f67245b8de2
16/cca83b40a1966698?lnk=gst&q=avl+list#cca83b40a1966698

I'm convinced of the utility of this (mostly by Jesse), and I have an 
implementation I've been playing with, but if we want to do this, it seems like 
it'd be worth spending a lot of time optimizing and tweaking.

Original issue reported on code.google.com by wasserman.louis on 16 Jan 2012 at 7:39

GoogleCodeExporter commented 9 years ago 
Nice. We still need the rest of the team to cast judgement on whether this 
problem is common enough for Guava; we received some abuse recently for 
including too much in our tiny library.

Original comment by limpbizkit on 16 Jan 2012 at 8:19

GoogleCodeExporter commented 9 years ago 
Definitely agreed.  I'm not _quite_ convinced myself, but mostly convinced.

Original comment by wasserman.louis on 16 Jan 2012 at 10:59

GoogleCodeExporter commented 9 years ago 
It's another case like MinMaxPriorityQueue -- just one more class, serves a 
specialized purpose most people won't use, but for those who do need it it's 
just the ticket. I tentatively like the idea of having this in Guava. Guava 
should have more than just convenience apis.

Original comment by kevinb@google.com on 19 Jan 2012 at 5:23

GoogleCodeExporter commented 9 years ago 
Welp, it passes the ListTestSuiteBuilder with flying colors.  Should I put up a 
patch?

Original comment by wasserman.louis on 19 Jan 2012 at 7:32

GoogleCodeExporter commented 9 years ago 
(Relevant: 
http://microbenchmarks.appspot.com/run/wasserman.louis@gmail.com/edu.uchicago.lo
wasser.fingertree.ListBenchmark/1207004 )

Original comment by wasserman.louis on 19 Jan 2012 at 7:36

GoogleCodeExporter commented 9 years ago 
Also, I have no idea what to call it.  I'd like to give it some name that lets 
us change the backing implementation -- to skip lists, for example -- but 
indicates that it's good for adds and removes.

Original comment by wasserman.louis on 19 Jan 2012 at 7:37

GoogleCodeExporter commented 9 years ago 
It would be unconventional to switch out the backing implementation for a 
public general-purpose collection implementation class.  These are usually 
bound to their specific implementations by name, and if we come up with a 
better, we add a new thing, maybe deprecating the old.

We went the opposite direction for *immutable* collections, but those feel a 
little different. (handwave)

FingerTreeList or AvlTreeList (I don't actually know which this is at this 
point :-)) may work, buut, there is a sight issue that "Tree" anywhere in the 
name will make a majority of users assume this has to do with Comparators.

Original comment by kevinb@google.com on 19 Jan 2012 at 5:28

GoogleCodeExporter commented 9 years ago 
FingerList?

Original comment by wasserman.louis on 19 Jan 2012 at 7:31

GoogleCodeExporter commented 9 years ago 
Also, throwing it out: InsertionList?

Original comment by wasserman.louis on 19 Jan 2012 at 9:44

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 30 May 2012 at 7:43

GoogleCodeExporter commented 9 years ago 
Java also has Names with "Tree" in it that's actually not a tree. "TreeSet" for 
example. So, I would simply say TreeList, cause that's what it is.

Original comment by v.woch...@gmail.com on 29 Dec 2012 at 6:26

GoogleCodeExporter commented 9 years ago 
Eh?  TreeSet is implemented with a tree...

Original comment by lowas...@google.com on 29 Dec 2012 at 6:39

GoogleCodeExporter commented 9 years ago 
Issue 1237 has been merged into this issue.

Original comment by cpov...@google.com on 8 Jan 2013 at 5:36

GoogleCodeExporter commented 9 years ago 
The benchmark from comment #5 is a dead link, can you provide a working one?

Original comment by xaerx...@gmail.com on 10 Apr 2013 at 9:58

GoogleCodeExporter commented 9 years ago 
http://1.microbenchmarks.appspot.com/run/wasserman.louis@gmail.com/edu.uchicago.
lowasser.fingertree.ListBenchmark/1207004

Original comment by gak@google.com on 11 Apr 2013 at 3:40

GoogleCodeExporter commented 9 years ago 
This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:14

GoogleCodeExporter commented 9 years ago

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

GoogleCodeExporter commented 9 years ago

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:09