On Fri, Mar 14, 2014 at 2:03 PM, Georgios Tzanakis <gtzana...@gmail.com> wrote: > > On Fri, Mar 14, 2014 at 4:49 PM, Robert Bradshaw > <rober...@math.washington.edu> wrote: >> >> Note that >> >> <int>L[i][<int>rows[i]] + j %w == 0: >> >> would probably be just (or nearly) as fast as >> >> ((<int>(<tuple>L[i])[<int>(rows[i])])+j %w)==0 > > > Good to know, thanks.. > >> >> >> If you're going to be dealing with arrays of ints you might want to >> look into NumPy > > > Hmm.. I wish I knew that earlier, I deal with many of such arrays. > >> >> and/or memory views for even more speed. > > > Could you elaborate a bit on that? Or just give me a link?
https://www.google.com/search?q=numpy+cython >> On Thu, Mar 13, 2014 at 7:58 PM, Georgios Tzanakis <gtzana...@gmail.com> >> wrote: >> > Hi Simon, >> > >> > I really appreciate your thorough answer! Indeed there was a bug and I >> > had >> > to do a couple of changes >> > to the code, but I understood a lot of things about how to use Cython >> > and >> > was able to use it properly >> > and have improvements. On top of that, I didn't know about the timeit >> > function which is a life saver. >> > >> > Everything is clear.. Thank you, sir! >> > >> > Best, >> > George >> > >> > >> > On Thu, Mar 13, 2014 at 8:48 AM, Simon King <simon.k...@uni-jena.de> >> > wrote: >> >> >> >> Hi! >> >> >> >> On 2014-03-12, geo909 <gtzana...@gmail.com> wrote: >> >> > But I'm still not sure how to use things properly. So, for instance, >> >> > is >> >> > the >> >> > following optimization reasonable? >> >> > (there is an ~30% increase in speed from pure python code) >> >> >> >> It is easy to get more. >> >> >> >> But first: Is there a bug in your code? >> >> >> >> You write >> >> if all( [(L[i][rows[i]]+j %w)==0] ): >> >> Thus, the argument to "all" is a list with precisely one item. >> >> >> >> If it is not a bug, then you should replace it with >> >> if (L[i][rows[i]]+j%w)==0: >> >> >> >> I assume that it is not a bug, and thus I used this improvement in all >> >> my >> >> attempts that I describe below. >> >> >> >> > # L: A list of tuples of positive integers, each having a couple of >> >> > hundred >> >> > elements. >> >> > # L itself has length at most 3 or 4. >> >> > >> >> > # e: A tuple of integers. e has length no more than a couple of >> >> > hundred. >> >> > # w a small integer >> >> >> >> Since there is frequent access to the items of L and e, you should tell >> >> Cython >> >> that L is a list and that e is a tuple. >> >> >> >> Also, itertools.product yields tuples, so, "rows" in your function is a >> >> tuple. Again, there is frequent acces to the items, thus, you should >> >> declare that rows is a tuple. >> >> >> >> On the other hand, commonzeros is accessed at most a couple of times, >> >> thus, no need to make it "cdef int". >> >> >> >> But it seems to me that the most important line is (after removing the >> >> needless "all") this: >> >> if (L[i][rows[i]]+j %w)==0: >> >> >> >> Let's try to be particularly careful here, since it occurs in an inner >> >> loop, and the annotation appears dark yellow. >> >> >> >> The items of L are tuples. Thus, one could do >> >> (<tuple>L[i])[rows[i]]+j >> >> to make access to the tuple items faster. >> >> >> >> Furthermore, the items in the tuple L[i] are ints, and we want to add >> >> it >> >> with an int. Hence, >> >> if ((<int>(<tuple>L[i])[rows[i]])+j %w)==0: >> >> will make it faster (actually, inserting the <int> makes the execution >> >> time drop to 50% compared with a version that only has <tuple>). >> >> >> >> With >> >> L = [tuple([randint(1,10^8) for i in range(400)]), >> >> tuple([randint(1,10^8) for i in range(300)]), >> >> tuple([randint(1,10^8) >> >> for i in range(500)]), tuple([randint(1,10^8) for i in >> >> range(200)])] >> >> e = tuple([randint(1,10^8) for i in range(350)]) >> >> w = 5 >> >> >> >> and a pure Python version of your function (where I have replaced the >> >> "all(...)" as indicated above), I get >> >> sage: timeit("myfunction(L,e,w)") >> >> 5 loops, best of 3: 1.11 s per loop >> >> >> >> However, when cythoning your function as follows >> >> {{{ >> >> %cython >> >> import itertools >> >> def myfunction(list L, tuple e, int w): >> >> cdef int lenL = len(L) >> >> cdef int i,j >> >> cdef tuple rows >> >> for rows in itertools.product(range(w), repeat=lenL): >> >> commonzeros=0 >> >> for j in e: >> >> for i in range(lenL): >> >> if ((<int>(<tuple>L[i])[<int>(rows[i])])+j %w)==0: >> >> commonzeros+=1 >> >> if commonzeros==4: >> >> return(1) >> >> return(0) >> >> }}} >> >> I get >> >> sage: timeit("myfunction(L,e,w)") >> >> 5 loops, best of 3: 18.6 ms per loop >> >> >> >> If you now look at the annotated version of the function, you'll see >> >> that >> >> for rows in itertools.product >> >> remains dark yellow. >> >> >> >> So, if one wanted to optimise further, one should try to improve that. >> >> Since you iterate over len(L) copes of range(w) (rather than over the >> >> product of lists of different size), it should be not too difficult to >> >> write a custom iterator in Cython. >> >> >> >> But perhaps the speedup (111 ms --> 18.6 ms) is good enough for you? >> >> >> >> Best regards, >> >> Simon >> >> >> >> >> >> -- >> >> You received this message because you are subscribed to a topic in the >> >> Google Groups "sage-support" group. >> >> To unsubscribe from this topic, visit >> >> https://groups.google.com/d/topic/sage-support/S9eXmSVoo9E/unsubscribe. >> >> To unsubscribe from this group and all its topics, send an email to >> >> sage-support+unsubscr...@googlegroups.com. >> >> >> >> To post to this group, send email to sage-support@googlegroups.com. >> >> Visit this group at http://groups.google.com/group/sage-support. >> >> For more options, visit https://groups.google.com/d/optout. >> > >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "sage-support" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> > an >> > email to sage-support+unsubscr...@googlegroups.com. >> > To post to this group, send email to sage-support@googlegroups.com. >> > Visit this group at http://groups.google.com/group/sage-support. >> > For more options, visit https://groups.google.com/d/optout. >> >> -- >> You received this message because you are subscribed to a topic in the >> Google Groups "sage-support" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/sage-support/S9eXmSVoo9E/unsubscribe. >> To unsubscribe from this group and all its topics, send an email to >> sage-support+unsubscr...@googlegroups.com. >> To post to this group, send email to sage-support@googlegroups.com. >> Visit this group at http://groups.google.com/group/sage-support. >> For more options, visit https://groups.google.com/d/optout. > > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-support+unsubscr...@googlegroups.com. > To post to this group, send email to sage-support@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
