[Python-ideas] FW: Idea: Compressing the stack on the fly

[Joshua Landau]

On 12 September 2013 09:34, M.-A. Lemburg <mal at egenix.com> wrote:
> On 12.09.2013 09:03, Joshua Landau wrote:
>> On 12 September 2013 07:59, M.-A. Lemburg <mal at egenix.com> wrote:
>>> On 12.09.2013 06:29, Joshua Landau wrote:
>>>> Does anyone actually write recursive Python code where the recursion
>>>> in a significant bottleneck? The only such code I can think of is
>>>> either for a tree, in which case stack depth is irrelevant, or bad
>>>> code.
>>>
>>> Any kind of backtracking algorithm will need recursion or a separate
>>> stack data structure to keep track of the various decisions made
>>> up to a certain point on the path.
>>>
>>> The C stack is rather limited in size, so a recursive parser can
>>> easily blow up if it uses the C stack alone for managing
>>> backtracking.
>>
>> What sort of algorithm would backtrack that many times? I doubt a
>> parser would and I can't think of anything worse ATM.
>
> Oh, that's easy. It just depends on the given data set that you're
> working on and how often you have to branch when working on it.
>
> http://en.wikipedia.org/wiki/Backtracking lists a few problems.
>
> Here's a regular expression example that would blow the stack,
> if the re module were still using it (it was fixed in 2003 to
> no longer do):
>
>     re.match('(.*a|.*b|x)+', 'x' * 100000)
>
> The expression still uses exponential time, though.

Ah, Regex. 'Could'a guessed.

I'll file that under "bad code". *wink*