Normal unification is decently fast. A simple implementation in another
project is here<https://github.com/logpy/logpy/blob/master/logpy/core.py#L58>.
However our implementation of unification in an associative/commutative
context is naive and painfully slow. AC matching is a hard problem but in
the 90s this was a fairly hot topic; and a lot of work was done on
algorithms and data structures to make it fast. In short we could make
this fast if we wanted to but it might take some gruntwork.
On Thu, Mar 14, 2013 at 6:11 PM, Aaron Meurer <asmeu...@gmail.com> wrote:
> How fast is this? Does it scale well for large expressions with many
> variables? Can it be modified to return the mapping?
>
> By the way, Dummy is a subclass of Symbol, so doing .atoms(Symbol,
> Dummy) is redundant.
>
> Aaron Meurer
>
> On Sun, Mar 10, 2013 at 10:44 PM, smichr <smi...@gmail.com> wrote:
> > If two expression trees are structurally the same they should unify under
> > some mapping of symbols. usympy makes this very easy to test for:
> >
> >>>> def structurally_equal(a, b):
> > ... from sympy.unify import usympy
> > ... if isinstance(a, (list, tuple)):
> > ... if type(a) != type(b): return False
> > ... a = Tuple(*a)
> > ... b = Tuple(*b)
> > ... # disambiguate symbols that are in common
> > ... bsym = b.atoms(Symbol, Dummy)
> > ... common = a.atoms(Symbol, Dummy) & bsym
> > ... if common:
> > ... b = b.xreplace(dict(zip(common, [Dummy() for c in common])))
> > ... try:
> > ... next(usympy.unify(a, b, {}, variables = list(bsym)))
> > ... return True
> > ... except:
> > ... return False
> > ...
> >>>> structurally_equal([1], [1])
> > True
> >>>> structurally_equal([1], (1,))
> > False
> >>>> structurally_equal(Sum(x, (x, 1, 2)), Sum(y, (y, 1, 2)))
> > True
> >>>> structurally_equal(Sum(x, (x, 1, 2)), Sum(y, (y, 1, 21)))
> > False
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "sympy" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to sympy+unsubscr...@googlegroups.com.
> > To post to this group, send email to sympy@googlegroups.com.
> > Visit this group at http://groups.google.com/group/sympy?hl=en.
> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+unsubscr...@googlegroups.com.
> To post to this group, send email to sympy@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sympy+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
