After a few tests, lists are slightly better for append/pop than set is for add/remove. Obviously remove(i) for lists is linear, and hence much longer than it is in sets...
I will take a look at the Graph section considering this :-) Nathann On Dec 10, 10:30 am, Nathann Cohen <nathann.co...@gmail.com> wrote: > ( I forgot to add that in all these cases, lists represent Sets and > nothing else ( no repetition, no order, etc... )) > > 2009/12/10 Nathann Cohen <nathann.co...@gmail.com>: > > > In understand, but then there are many places where lists are used in > > the Graph section where sets would greatly improve the performances ! > > > Nathann > > > 2009/12/10 Simon King <simon.k...@nuigalway.ie>: > >> Hi Nathann! > > >> On Dec 10, 9:02 am, Nathann Cohen <nathann.co...@gmail.com> wrote: > >> [...] > >>> time cA=diffA(a,b) > >>> CPU times: user 29.36 s, sys: 0.09 s, total: 29.45 s > >>> Wall time: 29.76 s > > >>> time cB=diffB(a,b) > >>> CPU times: user 0.03 s, sys: 0.01 s, total: 0.04 s > >>> Wall time: 0.04 s > > >> Not a big surprise, I would say. I mean, think what "v in b" does, if > >> b is a list that does not contain v, and what it does if b is a set. > >> AFAIK, a set is internally represented by a sorted binary tree that, > >> ideally, is balanced. > > >> So, in order to find out that v is NOT in a list of 1024 elements, you > >> need 1024 comparisons. But to find out that it is not in a set of 1024 > >> elements, you need 10 comparisons. > > >>> It may even be interesting to directly write an function computing the > >>> difference of two lists through Sets... > > >> What do you mean exactly by "difference of lists"? Note that lists > >> have a fixed order and may contain repetitions, but sets have not. So, > >> list(Set(a).difference(Set(b))) is certainly not what I would call a > >> difference of list a with list b. > > >> Example: > > >> sage: a = [4,4,2,1,2,3,2,3,1] > >> sage: b = [4,3] > >> sage: Sb = Set(b) > >> sage: list(Set(a).difference(Sb)) > >> [1, 2] > >> Both the sequential order and the multiplicities from the original > >> list are lost! > > >> sage: [x for x in a if x not in Sb] > >> [2, 1, 2, 2, 1] > >> This is more like a difference of lists, isn't it? > > >> Cheers, > >> Simon > > >> -- > >> To post to this group, send an email to sage-devel@googlegroups.com > >> To unsubscribe from this group, send an email to > >> sage-devel+unsubscr...@googlegroups.com > >> For more options, visit this group > >> athttp://groups.google.com/group/sage-devel > >> URL:http://www.sagemath.org > > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
