dsmtools.utils.misc

This module holds all the ungrouped utilities.

View Source

 1"""
 2This module holds all the ungrouped utilities.
 3"""
 4
 5from queue import LifoQueue
 6from typing import Generator, Callable, Any
 7
 8
 9def safe_recursion_bootstrap(func: Callable[[Any], Generator]) -> Callable[[Any], Any]:
10    """Convert a recursion function to a stack-size-limitless one, without changing the recursion limit of your system.
11
12    It requires that:
13    1. your recursion function has been refactored to a **generator**, i.e. `yield` instead of `return` everywhere,
14    even for `return None`, which is often omitted at the end of the function. Also, `yield` for any call of itself
15    within the recursion.
16    2. The decorator adds a new keyword argument 'stack' to the recursion function, so your recursion function should
17    not contain a 'stack' argument itself.
18    3. Everytime you start the recursion, you must provide a new stack by keyword 'stack', as something
19    like `func(.., stack=LifoQueue())`, and within the function, the signature must be `func(..., stack=stack)` to
20    pass this stack along. Don't do anything else with the stack. The decorator will handle everything.
21
22    This way, you can call the recursion and retrieve the result same as the normal one.
23
24    ### Explanations
25
26    To be short, it turns the searching process into a generator lets you initialize a stack to store the generators.
27    Long as there is memory for the stack, there will be no overflow. The speed is comparable to the bare recursion.
28
29    The reason for passing a new stack each time you call is for the compatibility for parallel computation. A decorator
30    with a stack in there is fine only when the decoration takes place locally.
31
32    The recursion runs like decorator -> func -> decorator -> return, so the recursion stack never exceeds 2.
33    """
34
35    def wrapped_func(*args, stack: LifoQueue, **kwargs):
36        if not stack.empty():               # where next goes to, return the generator directly
37            return func(*args, stack=stack, **kwargs)
38        recur = func(*args, stack=stack, **kwargs)       # initialized generator
39        while True:
40            if isinstance(recur, Generator):
41                stack.put(recur)
42                recur = next(recur)
43            else:       # it's a number then, computation done for this branch
44                stack.get()
45                if stack.empty():
46                    break
47                recur = stack.queue[-1].send(recur)     # send the result back to its parent
48        return recur
49
50    return wrapped_func

def safe_recursion_bootstrap(func: Callable[[Any], Generator]) -> Callable[[Any], Any]: View Source

10def safe_recursion_bootstrap(func: Callable[[Any], Generator]) -> Callable[[Any], Any]:
11    """Convert a recursion function to a stack-size-limitless one, without changing the recursion limit of your system.
12
13    It requires that:
14    1. your recursion function has been refactored to a **generator**, i.e. `yield` instead of `return` everywhere,
15    even for `return None`, which is often omitted at the end of the function. Also, `yield` for any call of itself
16    within the recursion.
17    2. The decorator adds a new keyword argument 'stack' to the recursion function, so your recursion function should
18    not contain a 'stack' argument itself.
19    3. Everytime you start the recursion, you must provide a new stack by keyword 'stack', as something
20    like `func(.., stack=LifoQueue())`, and within the function, the signature must be `func(..., stack=stack)` to
21    pass this stack along. Don't do anything else with the stack. The decorator will handle everything.
22
23    This way, you can call the recursion and retrieve the result same as the normal one.
24
25    ### Explanations
26
27    To be short, it turns the searching process into a generator lets you initialize a stack to store the generators.
28    Long as there is memory for the stack, there will be no overflow. The speed is comparable to the bare recursion.
29
30    The reason for passing a new stack each time you call is for the compatibility for parallel computation. A decorator
31    with a stack in there is fine only when the decoration takes place locally.
32
33    The recursion runs like decorator -> func -> decorator -> return, so the recursion stack never exceeds 2.
34    """
35
36    def wrapped_func(*args, stack: LifoQueue, **kwargs):
37        if not stack.empty():               # where next goes to, return the generator directly
38            return func(*args, stack=stack, **kwargs)
39        recur = func(*args, stack=stack, **kwargs)       # initialized generator
40        while True:
41            if isinstance(recur, Generator):
42                stack.put(recur)
43                recur = next(recur)
44            else:       # it's a number then, computation done for this branch
45                stack.get()
46                if stack.empty():
47                    break
48                recur = stack.queue[-1].send(recur)     # send the result back to its parent
49        return recur
50
51    return wrapped_func

Convert a recursion function to a stack-size-limitless one, without changing the recursion limit of your system.

It requires that:

your recursion function has been refactored to a generator, i.e. yield instead of return everywhere, even for return None, which is often omitted at the end of the function. Also, yield for any call of itself within the recursion.
The decorator adds a new keyword argument 'stack' to the recursion function, so your recursion function should not contain a 'stack' argument itself.
Everytime you start the recursion, you must provide a new stack by keyword 'stack', as something like func(.., stack=LifoQueue()), and within the function, the signature must be func(..., stack=stack) to pass this stack along. Don't do anything else with the stack. The decorator will handle everything.

This way, you can call the recursion and retrieve the result same as the normal one.

Explanations

To be short, it turns the searching process into a generator lets you initialize a stack to store the generators. Long as there is memory for the stack, there will be no overflow. The speed is comparable to the bare recursion.

The reason for passing a new stack each time you call is for the compatibility for parallel computation. A decorator with a stack in there is fine only when the decoration takes place locally.

The recursion runs like decorator -> func -> decorator -> return, so the recursion stack never exceeds 2.