On Nov 26, 2009, at 2:10 AM, Simon King wrote: > Hi Robert! > > On Nov 26, 9:46 am, Robert Bradshaw <rober...@math.washington.edu> > wrote: > [...] >>>> I think this makes perfect sense...I'm actually surprised it's not >>>> implemented that way already. >> >>> That's impossible. >> >> Over-allocating the number of generators ahead of time whenever you >> need more to achieve O(log(n)) rather than O(n) ring enlargements for >> n used variables (where n is, of course, not know ahead of time) >> seems >> easy enough to me. > > Over-allocation could indeed be a good idea. > > By "impossible" I meant: When you have > sum([x[i] for i in range(1001)] > it is impossible to guess that eventually you will have 1000 variables > already at the time when you create x[0].
Yeah. I think this is just a stress test for how well the ring works with many dynamically created variables, not an actual application. > And when you create x[1000] first, then you have two approaches: > 1) I don't know whether any other variable will be used, thus, I only > create x[1000] and nothing else. That's the sparse implementation. > 2) If x[1000] is used, it is likely that x[999] will be used as well. > So, I create x[0],...,x[1000] at once. That's the dense > implementation. With over-allocation one might not even need the dense/sparse distinction--creating 1000 variables in a "sparse" manner would only need 10 reallocations. (There could still be the question of how expensive it is to do arithmetic between very old and very new variables, without timing and looking at the actual code I'm not sure if this is a concern.) - Robert -- 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
