( 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 at >> http://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
