prüfen, wenn ein Teil eines Wortes ist in vordefinierten Array enthalten

Question

Aus Gründen eines Beispiel habe ich die folgende Zeichenfolge:

"Federal INSURANCE Mortgage" 

Ich möchte überprüfen, ob jedes Wort in dieser Zeichenfolge in dem folgenden Array vorhanden ist :

BAD_WORDS = %w{LLC CORPORATION INSURANCE COMPANY GEICO} 

In unserem Beispiel ist VERSICHERUNG vorhanden. Also sollte es wahr werden. Dies ist, was ich getan habe:

BAD_WORDS = %w{LLC CORPORATION INSURANCE COMPANY GEICO} 
BAD_WORDS.detect {|word| "Federal INSURANCE Mortgage".index(word) }.present? 
=> true 
BAD_WORDS.detect {|word| "Federal Mortgage".index(word) }.present? 
=> false 

Ist dies der beste Weg, um dieses Problem in Ruby zu lösen?

Answer 1

Sowohl Ihr Weg als auch die Antwort (die jetzt gelöscht wird) durchlaufen den Eingang und durchlaufen Wörter für jedes Eingangswort, wodurch die Laufzeit O (n) wird. Wenn Sie eine große Eingabe haben und viele Wörter, die langsam werden könnten.

Die Ruby Array Schnitt Methode verwendet einen Hash unter den Deckeln, so dass es den gleichen Job in O (n) tun kann.

("Federal INSURANCE Mortgage".split & BAD_WORDS).any? 

Siehe hier: Computing set intersection in linear time?

Answer 2

Das am besten mit einem regulären Ausdruck durchgeführt wird, und für diese Aufgabe eine Montage ist einfach, mit Regexp.union:

BAD_WORDS = %w{LLC CORPORATION INSURANCE COMPANY GEICO} 
BAD_WORDS_RX = Regexp.union(*BAD_WORDS) 

"Federal INSURANCE Mortgage".match(BAD_WORDS_RX) 
# => #<MatchData "INSURANCE"> 

Dies wird nun auch tun Teilwort übereinstimmt, was unerwünscht sein könnte, aber die Worte in Ihrem Beispiel sind alle ziemlich einzigartig.

Ihr Ansatz besteht darin, über die Wörter zu iterieren und zusätzlich über ein Array von schlechten Wörtern zu iterieren. Das ist N * M Komplexität, oder anders gesagt, es ist geometrisch langsam. Wenn Ihre Saiten länger werden oder die schlechte Liste größer wird, wird es schmerzhaft teuer.

Ein regulärer Ausdruck ist sehr kostengünstig, sobald er erstellt wurde, und die Erstellungskosten sind nominal.

Eine kleine Verbesserung zu Ihrem Original ist die Verwendung eines Set anstelle eines Arrays. Diese haben konstante Nachschlagezeit.