Re^7: Possessive sub-pattern with non-greedy content + recursion: WHY does this work??

[Anonymous Monk]

I'd be _really_ grateful if someone points me to a GH PWC #145 Perl's eertree code.

Please don't, I completely forgot how to navigate PWC recap, and only checked "Blogs with Creative Title". There aren't too many not-empty GH sub-directories anyway. There, a few regex-based solutions, and quite a few Rosetta-Perl-snippet-like, but correct/fast (in O(N2) sense) -- a plenty to choose from to benchmark against instead of really really bad Rosetta Perl sample :-).

Of eertree solutions: Mr. roger-bell-west's solution (gonna mention nicknames w/o people knowing... how else to refer to code snippets?) gives only 'a ama m ana n p l c' for 'amanaplanacanalpanama' input. They say it's Rosetta Python's port, but then it's broken port, had to disqualify, sorry.

Mr. polettix' code generates "Use of uninitialized value in array element" warnings for non-trivial inputs, and 'ertreetre' "palindrome" for 'eereertreetree' input. Had to disqualify, sorry.

Others seem to be correct, I gave them 1+ MB string input (50K randomly interspersed 'amanaplanacanalpanama's, similar to parent node), then in seconds:

colin-crain     4.41618514060974
e-choroba       8.4720139503479
james-smith     5.69543313980103
wlmb            0.999744176864624

All but choroba's are able to generate unique PD's only; so it's not the same league/work they do. Judging by "ee" vs. "ee(1)", it's 1:2 ratio of work/time. As imperfect test as it is, but it reveals the fastest of them all (subroutines which modify lexicals in enclosing scope(s)? Assignment operator w/o space on each side? Go figure) -- i.e. until "ee" arrival 3.5 years later:

ee              0.81856107711792
ee (1)          1.62736701965332

"ee" is a call to return unique PD's, "ee(1)" is "find them all".

BTW, looking at Mr.james-smith and Mr.wlmb code/comments ("growing a PD on each side of a 'center'"?) -- it's either they do not quite "eertree" as described in PDF, or it's somewhat modified algorithm described elsewhere I haven't seen.