Issue 3720042: code review 3720042: suffixarray: implememted FindAllIndex regexp search (Closed)
|
Created:
14 years, 6 months ago by gri Modified:
13 years, 12 months ago Reviewers:
CC:
r, rsc, golang-dev Visibility:
Public. |
Descriptionsuffixarray: implememted FindAllIndex regexp search
Implementation uses fast suffixarray lookup to find
initial matches if the regular expression starts with
a suitable prefix without meta characters.
Patch Set 1 #Patch Set 2 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #Patch Set 3 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #Patch Set 4 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #
Total comments: 11
Patch Set 5 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 6 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 7 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 8 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 9 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 10 : code review 3720042: suffixarray: implemented FindAllIndex regexp search #Patch Set 11 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #Patch Set 12 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #
Total comments: 13
Patch Set 13 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #Patch Set 14 : code review 3720042: suffixarray: implememted FindAllIndex regexp search #
Total comments: 4
MessagesTotal messages: 18
Hello r, rsc (cc: golang-dev@googlegroups.com), I'd like you to review this change.
Sign in to reply to this message.
There's a typo in the change description. "Implemented" should have an 'n'.
Sign in to reply to this message.
PTAL - fixed this and several other documentation gotcha's On Thu, Dec 16, 2010 at 9:47 PM, <r@golang.org> wrote: > There's a typo in the change description. "Implemented" should have an > 'n'. > > > > http://codereview.appspot.com/3720042/ >
Sign in to reply to this message.
http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:96: // If the regular expression has a prefix of at least 2 non-meta characters, s/non-meta characters/non-metacharacters/ (see below) http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:105: // find the first meta-character index in the rexexp expression; s/rexexp/regular/ (it's a typo and redundant) http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:106: // the prefix before is meta character free and can be fed into s/before // s/meta character/metacharacter/ (that's a first: make you go teutonic - but meta is a prefix, not a word) s/character free/character-free/ (hyphenate compound adjectives) http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:109: meta := sort.Search(len(expr), func(i int) bool { return regexp.HasMeta(expr[0 : i+1]) }) i've realized this isn't what you want. you really want a method on the regexp to say whether it contains metacharacters, which is not the same thing (consider the expr `\.`. the purely textual definition is the right one for a string interface but not for this purpose. i will give you what you need. http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:117: // is a chance that there are even more and we redo the search. i don't understand this comment. rewrite for clarity. http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:123: if meta == len(expr) && len(expr) > 0 { if len(expr) == 0, you shouldn't be here at all. http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:124: // regexp contains no meta characters; convert the Lookup result s/meta /meta/ again and throughout the comments http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:158: // occurences. s/r/rr/ http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:172: // TODO(gri) could optimize simple cases such as (a|b). we don't identify ourselves in TODOs in the public code http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:177: // regexp has a non-empty meta-character free prefix expr[0:m1]; s/meta-character free/metacharacter-free/ http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... src/pkg/index/suffixarray/suffixarray.go:185: // r compiled and expr[0:m1] is meta-character free ditto etc.
Sign in to reply to this message.
On Thu, Dec 16, 2010 at 9:59 PM, <r@golang.org> wrote: > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > File src/pkg/index/suffixarray/suffixarray.go (right): > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:96: // If the regular > expression has a prefix of at least 2 non-meta characters, > s/non-meta characters/non-metacharacters/ (see below) > > Done. > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:105: // find the first > meta-character index in the rexexp expression; > s/rexexp/regular/ (it's a typo and redundant) > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:106: // the prefix before is > meta character free and can be fed into > s/before // > s/meta character/metacharacter/ (that's a first: make you go teutonic - > but meta is a prefix, not a word) > s/character free/character-free/ (hyphenate compound adjectives) > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:109: meta := > sort.Search(len(expr), func(i int) bool { return regexp.HasMeta(expr[0 : > i+1]) }) > i've realized this isn't what you want. you really want a method on the > regexp to say whether it contains metacharacters, which is not the same > thing (consider the expr `\.`. the purely textual definition is the > right one for a string interface but not for this purpose. i will give > you what you need. > Ok. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:117: // is a chance that there > are even more and we redo the search. > i don't understand this comment. rewrite for clarity. > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:123: if meta == len(expr) && > len(expr) > 0 { > if len(expr) == 0, you shouldn't be here at all. > If len(expr) == 0 than meta == 0; i.e., meta <= 1 and case below using regexp directly is doing it's job. No need to special case it before. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:124: // regexp contains no meta > characters; convert the Lookup result > s/meta /meta/ again and throughout the comments > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:158: // occurences. > s/r/rr/ > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:172: // TODO(gri) could > optimize simple cases such as (a|b). > we don't identify ourselves in TODOs in the public code > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:177: // regexp has a non-empty > meta-character free prefix expr[0:m1]; > s/meta-character free/metacharacter-free/ > Done. > > > http://codereview.appspot.com/3720042/diff/8001/src/pkg/index/suffixarray/suf... > src/pkg/index/suffixarray/suffixarray.go:185: // r compiled and > expr[0:m1] is meta-character free > ditto etc. Done. > > > http://codereview.appspot.com/3720042/ >
Sign in to reply to this message.
my point is that for this application, an empty string is pointless and expensive to search for. it should just be an error caught higher up.
Sign in to reply to this message.
On Thu, Dec 16, 2010 at 10:42 PM, Rob 'Commander' Pike <r@golang.org> wrote: > my point is that for this application, an empty string is pointless > and expensive to search for. it should just be an error caught higher > up. > Then this FindAllIndex diverges from what regexp.FindAllIndex does for that case. ok with me, but I wanted to avoid the difference.
Sign in to reply to this message.
good point. i was thinking of this as being inside godoc, but as a library it needs to handle the empty string. -rob
Sign in to reply to this message.
Hello r, rsc (cc: golang-dev@googlegroups.com), I'd like you to review this change.
Sign in to reply to this message.
http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:93: // matches of the entire regular expression r, where a match is a pair s/entire // http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:96: // if n == 0. If the regular expression has a non-empty literal prefix i don't think the implementation needs description. also it overpromises - if there are many instances of the literal prefix but relatively few matches it won't be "very fast". http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:123: redo1: Maybe make the loop explicit? LookupLoop: for n1 := n;; { http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:125: if len(indices) > 0 { if len(indices) == 0 { return } drops a level of indentation, makes it easier to remember what's going on. same two comments apply to second loop http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:151: // It's ok for n1 to overflow - it wil become s/wil/will/
Sign in to reply to this message.
http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:122: if complete && prefix != "" { i think the prefix check here is wrong, and that Lookup should handle empty strings http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:153: // indices. is it not easy to add new entries as opposed to recomputing all entries? i suppose it's a rare case not worth fussing over http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:170: // the indices of possible complete matches, use these starting s/,/;/ http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:172: r = regexp.MustCompile("^" + r.String()) // compiles because r compiled perhaps worth a comment that in our regexp package ^ matches beginning of input, not beginning of line
Sign in to reply to this message.
Hello r, rsc (cc: golang-dev@googlegroups.com), Please take another look.
Sign in to reply to this message.
http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:93: // matches of the entire regular expression r, where a match is a pair On 2010/12/17 19:56:14, rsc wrote: > s/entire // Done. http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:96: // if n == 0. If the regular expression has a non-empty literal prefix On 2010/12/17 19:56:14, rsc wrote: > i don't think the implementation needs description. > also it overpromises - if there are many instances of > the literal prefix but relatively few matches it won't > be "very fast". Done. http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:125: if len(indices) > 0 { On 2010/12/17 19:56:14, rsc wrote: > if len(indices) == 0 { > return > } > > drops a level of indentation, > makes it easier to remember what's going on. > > same two comments apply to second loop Done. http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:151: // It's ok for n1 to overflow - it wil become On 2010/12/17 19:56:14, rsc wrote: > s/wil/will/ Done.
Sign in to reply to this message.
On Fri, Dec 17, 2010 at 11:58 AM, <r@golang.org> wrote: > > > http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... > File src/pkg/index/suffixarray/suffixarray.go (right): > > > http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:122: if complete && prefix != > "" { > i think the prefix check here is wrong, and that Lookup should handle > empty strings > added TODO - separate CL > > > http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:153: // indices. > is it not easy to add new entries as opposed to recomputing all entries? > i suppose it's a rare case not worth fussing over > maybe possible, but complicated (maybe another CL) - also it's probably rare > > > http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:170: // the indices of possible > complete matches, use these starting > s/,/;/ > Done. > > > http://codereview.appspot.com/3720042/diff/31002/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:172: r = regexp.MustCompile("^" > + r.String()) // compiles because r compiled > perhaps worth a comment that in our regexp package ^ matches beginning > of input, not beginning of line > > Done. > > http://codereview.appspot.com/3720042/ >
Sign in to reply to this message.
LGTM http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:162: // the indices of possible complete matches; use these starting s/these/these as/ http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:172: // there cannot be more). it would be fine here to say // Same comment about Lookup applies here as in the loop above.
Sign in to reply to this message.
LGTM http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... File src/pkg/index/suffixarray/suffixarray.go (right): http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:92: // FindAllIndex returns a list of at most n non-overlapping successive This comment should mention that they are not necessarily the first n. http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... src/pkg/index/suffixarray/suffixarray.go:156: // worst-case scenario: no literal prefix might as well move above if complete && prefix != "". then the if simplifies and this code doesn't have to worry about Lookup being different
Sign in to reply to this message.
*** Submitted as http://code.google.com/p/go/source/detail?r=23006c94f1aa *** suffixarray: implememted FindAllIndex regexp search Implementation uses fast suffixarray lookup to find initial matches if the regular expression starts with a suitable prefix without meta characters. R=r, rsc CC=golang-dev http://codereview.appspot.com/3720042 Committer: Robert Griesemer <gri@golang.org>
Sign in to reply to this message.
On Fri, Dec 17, 2010 at 1:43 PM, <rsc@golang.org> wrote: > LGTM > > > > > http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... > File src/pkg/index/suffixarray/suffixarray.go (right): > > > http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:92: // FindAllIndex returns a > list of at most n non-overlapping successive > This comment should mention that they are not necessarily the first n. > Done. > > > http://codereview.appspot.com/3720042/diff/44001/src/pkg/index/suffixarray/su... > src/pkg/index/suffixarray/suffixarray.go:156: // worst-case scenario: no > literal prefix > might as well move above if complete && prefix != "". > then the if simplifies and this code doesn't have to worry > about Lookup being different Done. > > > http://codereview.appspot.com/3720042/ >
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
