On Wed, May 30, 2012 at 1:44 AM, Joachim Durchholz <[email protected]> wrote: > Am 30.05.2012 08:20, schrieb Aaron Meurer: > >> 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. > > > Maybe my assumption is wrong. I'm assuming that at each level, > subexpressions are entered into a dict. > > If that's true, the hashcodes for all subexpressions will be recomputed > whenever an expression is being built from subexpressions. > > >> 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. > > > Does the hash code depend on the subexpressions? > (x+(y+z)) should have a different hash code than (x+(y+a)), for example.
Yes, but that's not exactly sub-expressions. x + y + z is denested into Add(x, y, z). A better example would be x + y*z, which is Add(x, Mul(y, z)). Aaron Meurer > > > -- > 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.
