On Tue, May 29, 2012 at 11:57 AM, Joachim Durchholz <[email protected]> wrote: > Am 29.05.2012 07:10, schrieb Aaron Meurer: > >> _hashable_content generally contains >> other Basic objects. So what I really want is the "fully denested" >> _hashable_content, where each Basic object is recursively replaced >> with its _hashable_content. I've no idea how expensive that would be >> to compute. > > > The behavior will be quadratic with number of levels of sets. This could > start to impact us on deeply nested expressions - not with anything a human > would enter, but if somebody wants to use SymPy from a script, this might be > different. (I'm talking of thousands of nesting levels.) > One way to set that might be to simplify x+0+0+...+0 (1000 terms, then retry > with 100,000 ;-) ).
I don't see how it's quadratic. Maybe I'm missing something. The problem I do see is that it's inherently recursive, meaning we are limited by the Python stack (unless we do it with a manual stack). Actually, it seems that hash() itself works regardless of this fact, which is interesting. If I create a highly nested expression, one where I know that recursively calling hashable_content() will overflow the stack, I can still hash it. Aaron Meurer > > The downside of caching is that each mutator must invalidate the cached > hash. (Unless mutators are disallowed once an object is entered into a dict. > Or the mutable objects are really copy-on-write ones. I don't know whether > any of these paths is available already, or feasible if unavailable - we're > deep into Systems Programming Land here.) > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
