speeding up Min Max

[Rohan Mallick]

I am very very new to this organization, correct me if I didn't understand the issue. And I don't know much about the code

Is there any progress?

Algo is surely O(n**2). But n**2 comparisions are required only if most of the elements are uncomparable. In practice majority would be of similar kinds, for >1000 elements. Practical running time can be reduced. I had few ideas too. 

Any suggestions will be appreciated

[Oscar Benjamin]

Hi Rohan,

I assume that you are referring to this github issue:
https://github.com/sympy/sympy/issues/16249

It's good to reference the issue because most of the people on this
mailing list won't be familiar with it. Also it probably makes sense
to ask questions about the issue on the issue.

One obvious thing to do would be to partition the set of objects
according to their comparability. The is_comparable property tells
whether an object can be evaluated numerically to a real Float e.g.:

In [1]: x = Symbol('x')

In [2]: x.is_comparable
Out[2]: False

In [3]: sqrt(2).is_comparable
Out[3]: True

In [4]: sqrt(2).n()
Out[4]: 1.41421356237310

Expressions that have is_comparable=True can normally be compared with
< or > or in fact the new internal functions is_lt and is_gt. For
these expressions the simple algorithm for computing min/max is fine.
The main class of expressions that has comparable=False is those that
have free symbols. Expressions with free symbols can sometimes be
compared e.g.:

In [5]: a, b = symbols('a, b', positive=True)

In [6]: a + b > a
Out[6]: True

It is also possible that we can have is_comparable=False at the same
time as a comparison being possible e.g.:

In [5]: e = 1 - a

In [6]: e.is_comparable
Out[6]: False

In [7]: e < sqrt(2)
Out[7]: True

That suggests that partitioning based on is_comparable is not perfect.
However it probably does make sense to compute the min/max of those
args that have is_comparable=True as a first step before getting to
the all-to-all comparison.

If the symbols don't have any assumptions set then it is unlikely that
any comparisons will be significant. This is especially true in the
worst case where every expression is simply a different symbol and
none of those symbols has any assumptions set. A simple way to check
for this would be to query arg.is_extended_real for each of the
arguments. If is_extended_real is None then the assumptions system is
unable to conclude that the expression is even real so it's also
unlikely that any ordering comparison would give a meaningful result.
The algorithm can avoid comparing any expressions that have
is_extended_real=None. There is no computational cost in computing
is_extended_real because it is already checked for each of the
arguments in _new_args_filter and the result of that check will be
cached on the argument's assumptions dictionary.

Oscar

> --
> 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+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d0ac8a1f-6391-4e6e-8aab-274af455eaabn%40googlegroups.com.