I have two arrays of Strings, for example sentences and words. If any word is found in a sentence e.g. sentence =~ /#{word}/ I want to reject the sentence from the sentence array. This is easy to do with a double loop, but I'm wondering if there is a more efficient way of doing this, maybe with logical operators?
-
On rereading this, it is unclear to me what you mean by "I want to reject it from the the array" - are you rejecting elements from the words array or the sentence array?Dave Kirby– Dave Kirby2009-12-06 19:27:21 +00:00Commented Dec 6, 2009 at 19:27
-
Right, confusing. Clarified.Matt– Matt2009-12-06 19:35:59 +00:00Commented Dec 6, 2009 at 19:35
Add a comment
|
4 Answers
Array subtraction is your friend here:
words.each do |word|
sentences -= sentences.grep(/#{word}/)
end
It's still the same basic time complexity (probably less efficient overall), but you can get around writing out the double loop.
Be aware that with this solution, words need not match entire whitespace separated words in the sentence. So, the word cat would knock out the sentence: String concatenation is gross.
1 Comment
Matt
Thanks p. Doing something similar right now but your version a little prettier. Aware of the regex issues, just wanted a simple example to illustrate the problem.
Joining strings into a Regexp is a pretty bad idea because backtracking slows things down horribly and because you run into limits on the regex size pretty quickly. (Though it may work well in practice if wordarray is small)
Consider using one of the DictionaryMatcher Ruby Quiz solutions.
Then you can operate as follows:
dm=DictionaryMatcher.new
wordarray.each{|w| dm << w}
sentencearray.reject{|s| s =~ dm}
2 Comments
Matt
Thanks much for the pointers, prefix trees are cool, and in fact I have a comment in existing code to check them out for this problem.
Ken Bloom
It isn't the prefix-trees that's cool. It's the Knuth-Morris-Pratt matching that's cool, though there was another less theoretically efficient algorithm in the solutions that nevertheless benchmarked better.
You could join all the words together into one regex, with the words separated by the "|" character.
sentence =~ /word1|word2|..../
You can convert the word array into a suitable regex with array.join("|").
If the words are likely to contain regex metacharacters then enclose each word in in non-capturing brackets.
sentence =~ /(?:word1)|(?:word2)|..../
Using a single regex should be much more efficient than looping through the words array, since the regex will be compiled into a single statetable.
4 Comments
Matt
Nice! I forgot about this approach. Thanks. Will benchmark it vs. perimosocordiae's answer.
Matt
Dave- what's the #~ format doing in this case? Did you mean =~?
Dave Kirby
Whoops - the #~ was a typo - I did mean =~
perimosocordiae
Did you ever do that benchmark, Matt? I'm curious to know what kind speed-up you actually get.
words = [...]
sentences = [....]
result = sentences.select{|sentence| !words.any?{|word| sentence =~ /#{word}/}}
