find the first occurrence of '<IPDR>' # fast
walk the string to the '</IPDR>' # fastish
skip back to the last occurrence of 'test' # fast
walk forward to the '</IPDR>' again # fastish
signal success # done
however if the tail were missing, eg if it had '<IPDR>' at the end by mistake instead of '</IPDR>', it would go like this: find the first occurrence of '<IPDR>' # fast
walk the string to the end # fastish
skip back to the last occurrence of 'test' # fast
walk forward to end of string again # fastish
repeat last two steps for each additional occurrence of 'test'
# slow - quadratic in the number of occurrences of 'test'
(no more 'test's to try) signal failure # done
Now, this may not be a problem for the original poster: they may already have confirmed that their data is well-formed. However it is an avoidable problem, either by checking for 'test' in a separate grep (as in your original solution), or by using the 'cut' operator to avoid the useless quadratic backtracking.
Here's some code to benchmark the difference, trying with and without the 'cut' operator, with strings that both do and don't match, and with 1, 10, 100 or 1000 copies of 'test' in the string:
And the (reformatted) results: uncut1g: 12799.05/s
cut1g: 12799.05/s
uncut1b: 11821.50/s
cut1b: 8219.27/s
uncut10g: 11486.54/s
cut10g: 11486.54/s
uncut10b: 2559.05/s
cut10b: 7244.34/s
uncut100g: 5743.27/s
cut100g: 5743.27/s
uncut100b: 125.00/s
cut100b: 3381.13/s
uncut1000g: 956.48/s
cut1000g: 956.48/s
uncut1000b: 1.85/s
cut1000b: 532.38/s
From this it is clear that a) the cut operator costs nothing when it is not used (all the g(ood) matches are the same speed with and without the cut), b) when there is just one 'test' to backtrack over the cost of the extra bookkeeping is quite high (cut1b is 36% slower than the good case, while uncut1b is only 8% slower), but c) the cost is linear rather than quadratic (as the number of 'test's increases, the 'cut<n>b' version continues to give away 36% to the 'cut<n>g' version, while the 'uncut<n>b' gets slower much more dramatically.
Hugo |