Repository: dgasmith/opt_einsum
Pull request #110 (2019-11-18 20:20:38)

add 'high quality' auto optimize presets
## Description
Adds two ``optimize=`` presets, ``'random-greedy-128'``, and ``'auto-hq'``. These let you allow much more time for finding the path than the ``'auto'`` path targets.

``'auto-hq'`` uses:
*  ``'optimal'`` for ``n<=5``
*  ``'dp'`` for ``n<=16``
*  ``'random-greedy-128 '`` for ``n>16``

The handover from ``'dp'`` to ``'random-greedy-128 '`` works pretty smoothly in terms of timings for the random regular-like graphs. But for *planar*-like graphs, ``'dp'`` can really go 2 or 3 times bigger than 16. No sure if there is any easy way one might detect these kind of situations, but just a good point to keep in mind!

cc @mrader1248

## Status
- [x] Ready to go


codecov[bot]: # [Codecov](https://codecov.io/gh/dgasmith/opt_einsum/pull/110?src=pr&el=h1) Report
> Merging [#110](https://codecov.io/gh/dgasmith/opt_einsum/pull/110?src=pr&el=desc) into [master](https://codecov.io/gh/dgasmith/opt_einsum/commit/3eb88476a23eb2b6c58949550525097945ead21a?src=pr&el=desc) will **increase** coverage by `0.01%`.
> The diff coverage is `100%`.



Patch:
diff --git a/docs/source/path_finding.rst b/docs/source/path_finding.rst
index 5693809..77a5389 100644
--- a/docs/source/path_finding.rst
+++ b/docs/source/path_finding.rst
@@ -27,9 +27,16 @@ best of these it can while aiming to keep path finding times below around 1ms.
 An analysis of each of these approaches' performance can be found at the bottom
 of this page.
 
-Finally, for large and complex contractions, there is the
-``'random-greedy'`` approach, which samples many greedy paths and can be
-customized to explicitly spend a maximum amount of time searching.
+For large and complex contractions, there is the ``'random-greedy'`` approach,
+which samples many (by default 32) greedy paths and can be customized to
+explicitly spend a maximum amount of time searching. Another preset,
+``'random-greedy-128'``, uses 128 paths for a more exhaustive search.
+See :ref:`RandomGreedyPathPage` page for more details on configuring these.
+
+Finally, there is the ``'auto-hq'`` preset which targets a much larger search
+time (~1sec) in return for finding very high quality paths, dispatching to the
+``'optimal'``, ``'dynamic-programming'`` and then ``'random-greedy-128'`` paths
+depending on contraction size.
 
 If you want to find the path separately to performing the
 contraction, or just inspect information about the path found, you can use the
diff --git a/opt_einsum/__init__.py b/opt_einsum/__init__.py
index 0ec9eb6..ae5dc78 100644
--- a/opt_einsum/__init__.py
+++ b/opt_einsum/__init__.py
@@ -21,3 +21,4 @@ del get_versions, versions
 
 
 paths.register_path_fn('random-greedy', path_random.random_greedy)
+paths.register_path_fn('random-greedy-128', path_random.random_greedy_128)
diff --git a/opt_einsum/path_random.py b/opt_einsum/path_random.py
index aae17e5..54c567e 100644
--- a/opt_einsum/path_random.py
+++ b/opt_einsum/path_random.py
@@ -12,7 +12,7 @@ from collections import deque
 
 from . import helpers, paths
 
-__all__ = ["RandomGreedy", "random_greedy"]
+__all__ = ["RandomGreedy", "random_greedy", "random_greedy_128"]
 
 
 class RandomOptimizer(paths.PathOptimizer):
@@ -370,3 +370,6 @@ def random_greedy(inputs, output, idx_dict, memory_limit=None, **optimizer_kwarg
     """
     optimizer = RandomGreedy(**optimizer_kwargs)
     return optimizer(inputs, output, idx_dict, memory_limit)
+
+
+random_greedy_128 = functools.partial(random_greedy, max_repeats=128)
diff --git a/opt_einsum/paths.py b/opt_einsum/paths.py
index 697f866..de1bb20 100644
--- a/opt_einsum/paths.py
+++ b/opt_einsum/paths.py
@@ -13,8 +13,8 @@ import numpy as np
 from . import helpers
 
 __all__ = [
-    "optimal", "BranchBound", "branch", "greedy", "auto", "get_path_fn",
-    "DynamicProgrammingOptimizer", "dynamic_programming"
+    "optimal", "BranchBound", "branch", "greedy", "auto", "auto_hq",
+    "get_path_fn", "DynamicProgrammingOptimizer", "dynamic_programming"
 ]
 
 
@@ -992,8 +992,27 @@ def auto(inputs, output, size_dict, memory_limit=None):
     return _AUTO_CHOICES.get(N, greedy)(inputs, output, size_dict, memory_limit)
 
 
+_AUTO_HQ_CHOICES = {}
+for i in range(1, 6):
+    _AUTO_HQ_CHOICES[i] = optimal
+for i in range(6, 17):
+    _AUTO_HQ_CHOICES[i] = dynamic_programming
+
+
+def auto_hq(inputs, output, size_dict, memory_limit=None):
+    """Finds the contraction path by automatically choosing the method based on
+    how many input arguments there are, but targeting a more generous
+    amount of search time than ``'auto'``.
+    """
+    from .path_random import random_greedy_128
+
+    N = len(inputs)
+    return _AUTO_HQ_CHOICES.get(N, random_greedy_128)(inputs, output, size_dict, memory_limit)
+
+
 _PATH_OPTIONS = {
     'auto': auto,
+    'auto-hq': auto_hq,
     'optimal': optimal,
     'branch-all': branch_all,
     'branch-2': branch_2,


Test patch:
diff --git a/opt_einsum/tests/test_contract.py b/opt_einsum/tests/test_contract.py
index bc0d4c6..04a3f06 100644
--- a/opt_einsum/tests/test_contract.py
+++ b/opt_einsum/tests/test_contract.py
@@ -97,7 +97,8 @@ tests = [
 ]
 
 
-all_optimizers = ['optimal', 'branch-all', 'branch-2', 'branch-1', 'greedy', 'random-greedy', 'dp']
+all_optimizers = ['optimal', 'branch-all', 'branch-2', 'branch-1', 'greedy',
+                  'random-greedy', 'random-greedy-128', 'dp', 'auto', 'auto-hq']
 
 
 @pytest.mark.parametrize("string", tests)