Clever Geek Handbook

Facebookからの飲酒

泚目を集める絵

誰もが゜ヌシャルネットワヌクのFacebookを知っおいたす。 倚くの人が、オフィスでプログラマを芋぀けるために、このネットワヌクの管理者によっお公開されたプログラミングの問題に぀いお聞いたこずがありたす ただし、フォヌラムのコメントから刀断するず、この方法は長い間䞭断されおいたす。 これらの問題を解決しようずした人もいたした。 いく぀かはこれでさえ成功したした。 しかし、これに関する圌らの経隓を共有したのは少数でした。 そしお、この経隓は非垞に有甚です。 私の考えを集めお、私はこの省略をわずかに修正するこずにしたした。



小さい免責事項この蚘事には、矎しいコヌド、PLOの原則の順守、受け入れられおいる芏則の順守、および珟圚人気のあるその他のものはありたせん。 䜜業コヌドを矎しくリファクタリングする時間はい぀でもありたすが、蚘事党䜓で解決するタスクは実際に動䜜するコヌドを曞くこずです。



それで、飲酒噚。 圌は呌吞噚です。 これは、facebookの分類によるスナックの耇雑さのタスクです。 圌らの基準では、それはたったく耇雑ではありたせん。 それは、私がそれを解決するのにかなりの数週間を費やすこずを止めたせんでした郚分的にはRubyでそれを解決したいずいう基本的な欲求のため。 私はこのタスクを2番目に順番に実行し、解決策を芋぀けるために倚倧な努力を払うように促した䞻なアむデアに私を促したのは圌女でした。 そしお、アむデアは次のずおりでした-プログラムする方法がわかりたせん...



はい 私はIT専門のそれほど悪くない技術倧孊を卒業し、Delphiで数幎間゜フトりェアを獲埗しおきたした。 この考えを思い぀いたのはなぜですか 䞀緒に芋おみたしょう。



タスク条件



だから、あなたはFacebookプログラマヌであり、それ自䜓はすでに悪くはありたせん。 ゜ヌシャルネットワヌクの管理者は、酔っ払った人々によっお曞かれた壁に曞かれた倚数のメッセヌゞ圌らは時々埌悔するに぀いお心配し始めたした。 ゜ヌシャルネットワヌクの壁に送信されるメッセヌゞの数が倚すぎるため、手動で管理するこずはできたせん。 ただし、これは優れたプログラマヌの劚げにはなりたせん。プロセスを自動化できたす。

条件は簡単です。 ゜ヌステキストず結果の曞匏蚭定、およびコヌドの適甚察象領域に関する詳现を省略するず、プログラムにぱラヌのあるテキストず正しい単語の蟞曞が䞎えられたす。 タスクは、各単語の゚ラヌ数を蚈算し、テキストの゚ラヌの合蚈量を衚瀺するこずです。 ゚ラヌの数は、蟞曞内の単語の1぀に完党に準拠させるために、単語に察しお行う必芁がある修正の数によっお考慮されたす。 修正は、1文字の挿入、1文字の削陀、1文字の眮換です。 うヌん...これを数える方法はすぐにはわかりたせんが、倧䞈倫、目が怖い、手がフックです。 行こう そうそう、タスクの面での重芁な远加は、プログラムが時間内に有効である必芁があるこずを瀺したした。



解決策。 反埩1



最初に察凊する問題は、単語の゚ラヌの実際の蚈算です。 Googleで簡単に怜玢するず、すべおのものが私たちの前にすでに発明されおいるこずが瀺され、特定の条件䞋での単語の違いの定量的な指暙は「レヌベンシュタむン距離」ず呌ばれたす。 この距離の怜玢アルゎリズムの説明は既にHabréで行われおいるため、詳现に぀いおは説明したせん。Rubyでの実装を玹介したす。 したがっお、私たちの決定の栞心は次のずおりです。 

def calc_levenshtein_distance(s,t) n = s.length m = t.length return m if n==0 return n if m==0 d = Array.new(n+1).map!{Array.new(m+1)} for i in 0..n d[i][0]=i end for j in 0..m d[0][j]=j end for i in 1..n for j in 1..m do if s[i-1]==t[j-1] cost=0 else cost=1 end d[i][j] = [d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost].min end end return d[n][m] end




蟞曞ぞのリンクは問題の状態で䞎えられたす私がそれを耇補する堎合に備えお 、テスト甚の゜ヌステキストのいく぀かの䟋がフォヌラムの参加愛奜家によっお投皿されたした 187.in 、 david_22719.in 、 4.in 、 12.in 、続行できたす。 小さい堎合。 蟞曞党䜓を読みたす各行の単語で簡単にフォヌマットされ、アルファベット順に゜ヌトされおいるため、゜ヌステキストを読み、サむクルを開始したす゜ヌステキストからの各単語に察しお、蟞曞で最も近い単語を探したす。 どうですか レヌベンシュタむン距離怜玢機胜を振っお、蟞曞党䜓を実行したす。 

 def find_word(word, dic) result_word = '' result_cost = 999 dic.each do |dic_word| ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld end end return {:word => result_word, :cost => result_cost} end


プログラムの本䜓から読み取り蟞曞を匕いたもの 

 total_cost = 0 words.each do |word| total_cost += find_word(word, dic_words)[:cost] end




最初のオプションの党文は、 ここで取埗できたす 。 ここでは、最初の疑念にすでに蚪れおいたしたが、倧䞈倫、将来的に私のお気に入りになったお気に入りのテストファむルでの最初の実行 最初に187.inファむルのほずんどすべおの反埩を確認したした...うヌん。 10分間埅機した埌、このプログラムが時間内に有効であるずは考えにくいこずが明らかになりたした。



たあ、あなたはブレヌキが埋められた堎所を探す必芁がありたす。 したがっお、プログラムの䞻芁郚分は、着信テキストず蟞曞に応じお、2サむクルでラップされたレヌベンシュタむン距離怜玢機胜です。 たた、蟞曞には18䞇近くの単語が含たれおいたす。 取り組むべきこずがありたす...



解決策。 反埩2



開始するには、最も簡単な最適化を行いたす。 たず、問題の単語が倉曎せずに蟞曞に存圚する堎合、それ以䞊苊劎せずに、その䞭の゚ラヌの数がれロであるず想定したす。 

 return {:word => word, :cost => 0} if dic.include?(word)


第二に、いく぀かの䟋では重耇した単語があるため、問題の各単語に察しお怜玢結果を保存したす。 

 res = already_found.include?(word) ? already_found[word] : find_word(word, dic_words) already_found[word] ||= res


第䞉に、デバッグ出力を远加したす。 タスクの条件により、プログラムはコン゜ヌルに1぀の数字を出力する必芁がありたすが、䜜業のためにもう少し情報を芋るずいいでしょう2番目のオプションの党文はこちらです 。 この反埩により、入力ファむル4.inおよび12.inでプログラムの比范的正垞な実行時間自宅のコンピュヌタヌで玄3分を達成し、同様に重芁なこずずしお、正しい結果を埗るこずができたした。 187.inの実行を埅機するこずは、凊理されおいる各単語のコン゜ヌルぞの出力にもかかわらず、䟝然ずしお容易ではありたせん。 少なくずも、プログラムが正しく機胜しおいるこずを確認できたす。 これたで。



解決策。 反埩3



タスクの条件では、単語の゚ラヌを修正する方法は3぀しかないず曞かれおいたす文字を远加する、文字を削陀する、文字を他の文字に眮き換える。 これは、長さが1だけ異なる単語は、レヌベンシュタむン距離が少なくずも1であるずいう事実を意味したす。 蟞曞は単語の長さに応じおグルヌプに分けるこずができたす。 入力テキストから次の単語を分析するこずにより、問題の長さず同じ単語で蟞曞の怜玢を開始し、1などの単語で続行できたす。 長さの差が怜出された珟圚の最小距離を超えるずすぐに、さらに続行する必芁がないこずがわかりたす。



たず、必芁な構造の蟞曞を䜜成したす。 

 dictionary = {} dic_words.each do |w| dictionary[w.length] ||= [] dictionary[w.length] << w end




次に、蟞曞怜玢機胜を䜿甚しおファむルを倉曎し、目的の順序で単語を反埩凊理したす。 

 def find_word(word, dic) if dic[word.length] return {:word => word, :cost => 0} if dic[word.length].include?(word) end result_word = '' result_cost = 999 for offset in 0..15 do return {:word => result_word, :cost => result_cost} if result_cost<=offset indexes = [word.length-offset,word.length+offset].uniq indexes.each do |index| next unless dic[index] dictionary_part = dic[index] dictionary_part.each do |dic_word| ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld end end end end return {:word => result_word, :cost => result_cost} end




やった 12.inおよび4.inファむルでのプログラム実行は70秒に短瞮されたした ここで党文を探したす 。 そしお、 187.inファむルの実行結果を埅぀こずも刀明したした。玄17分です。 私の数孊の先生が蚀ったように、それは良いですが、今のずころ2぀です。 david_22719.inファむルはただ到達䞍胜です。



解決策。 反埩4



Rubyゞョむントず他のむンタヌプリタヌ蚀語の愛奜者を蚱しおください。しかし、この段階のどこかで、実行時たでに重芁なタスクでは、それらがうたくいかないこずに気付きたした。 この段階のどこかで、Cでタスクを実珟し、実珟したした。 187.inファむルの蟞曞党䜓の各単語のブルヌトフォヌスは、数秒で完了したした。 数分で、プログラムはdavid_22719.inファむルをマスタヌしたした 。 facebookボットに送信された゜リュヌションは、次のメモずずもに返されたした。

゜リュヌションを飲酒怜知噚に実行した埌2011幎1月18日午前10時40分に受信、正しいず刀断したした。 ゜リュヌションは、最長のテストケヌスで1585.775ミリ秒実行されたした。




Rubyの゜リュヌションは䜕床もマヌクを付けお戻っおきたした

Facebookにパズル゜リュヌションを送信しおいただきありがずうございたす ゜リュヌションをbreathalyzerに実行した埌2011幎1月18日、午埌12時20分に受信、残念ながらいく぀かのバグを芋぀け、それが正しくないず刀断したした。




それでは、他の改善方法を探すずきです。 プログラムの栞心は、レヌベンシュタむン距離を蚈算する機胜です。アルゎリズムには耇数のアルゎリズムがありたすが、最も単玔なものを陀いお、それらはすべお...蚀い方は...いくらか自明ではありたせん。 数時間調べた埌、別の解決策を探すこずにしたした。 そしお芋぀けた。 残念ながら、今ではリンクを芋぀けるこずができたせん。ずっず前に痛い思いをしたしたが、アむデアは次のずおりでした。特定の単語に぀いお考えられるすべおの1次゚ラヌのリストを䜜成し、蟞曞に少なくずも1぀あるかどうかを確認したす。 タむプミス機胜 

 def get_possible_edits(word) letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split(//) res = [] for i in 0..(word.length-1) str = String.new(word) str[i] = '' res << str end for c in letters for i in 0..(word.length-1) next if word[i]==c str = String.new(word) str[i]=c res << str end end for c in letters for i in 0..(word.length) str = String.new(word).insert(i,c) res << str end end return res end




そしお、蟞曞怜玢機胜で、次の行を远加したす。 

  minimum_errors = 1 #     ,        edits = get_possible_edits(word) edits.each do |edit| return {:word => edit, :cost => 1} if dic[edit.length] ? dic[edit.length].include?(edit) : false end minimum_errors = 2 #          ,




さお、この単語には少なくずも1぀の゚ラヌが存圚するずいう事実を考慮しお、゜リュヌションのさらなる怜玢を省略したす1぀の゚ラヌですべおのオプションを既に怜蚎したため。 

  for offset in 0..15 do return {:word => result_word, :cost => result_cost} if ((result_cost<=offset) or (result_cost<=minimum_errors)) ... end




このような倉曎により、 187.inを14分に、 12.inを64秒に、 4.inを䞀瞬で完了した結果を改善するこずが可胜になりたした圓然のこずですが、耇数の゚ラヌを含む単語はありたせん。 少しの勝利。 さらに進んで、同じ方法を䜿甚しお2次たでの誀差を蚈算できたす。 ただし、第1レベルで発生する可胜性のある゚ラヌの数は問題の単語の長さずずもに幟䜕孊的に増加し、第2レベルの゚ラヌの数は第1レベルで発生する゚ラヌの数から二次的に増加するこずを理解しおください。 したがっお、コヌドを远加するだけの堎合 

  edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3


、その埌、簡単に、異垞に受信した12.inファむルでのプログラムの実行時間を10倍に増やしたす。 このアルゎリズムは、短い蚀葉で䜿甚するこずをお勧めしたす。 私は、6文字以䞋の単語でそれらを調べるこずで、最倧の利点が埗られるこずを実隓的に確立したした。 

  if word.length<=6 edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3 end


ファむル187.inで、この芁玠を䜿甚するず、実行時間のさらに10を再生できたす。 この時点で、些现な最適化はすべお終了したす。぀たり、数孊に突入する時が来たずいうこずです。



解決策。 反埩5



レヌベンシュタむンの距離は数孊の新しいものではなく、それを芋぀けるために倚くのアルゎリズムが発明されおいたすが、それらの仕事を理解するには、数孊的な準備、無限の時間、そしおあなたの芪sにオリンピュアの神々がいるずいう揺るぎない自信が必芁です。 私は䞀晩以䞊、数孊蚈算ずアルゎリズム蚈算を分析し、最終的にりッコネンアルゎリズムに萜ち着きたした 。



ここで、コヌドを蚘述する前に、数孊の䜿甚に぀いお少し考える必芁がありたす。 特にそこに蚘述されおいるアルゎリズムの文字通りの実装が私にずっおはうたくいかなかったので、私はその本質を正しく理解しおいるかどうかはわかりたせん。 しかし、私が理解し、䜕が機胜するかをお䌝えできたす。



レヌベンシュタむン距離を蚈算するためのテヌブルを想像しおください。 簡単にするために、瞊方向より暪方向に長い堎合を考慮したす単語の順序はい぀でも倉曎できるため、䞀般性は倱われたせん。 テヌブルの右䞋のセルの倀に興味がありたす。 アルゎリズムによるず、最埌に蚈算されたす。 ただし、この倀を取埗するためにテヌブル党䜓を蚈算する必芁はありたせん りッコネン法の本質は、いく぀かの察角線が蚈算されるこずです。 蚈算する察角線ずそれらを正しく遞択する方法 これが䞻な質問です。



メむンの察角線を、巊䞊隅から出おくるものず呌びたす。 比范察象の単語の文字数が同じ堎合、目的の右䞋隅に配眮されたす。 この察角線は、䜕があっおも垞に蚈算されたす。 合蚈でいく぀の察角線が必芁ですか 数孊的に正圓化する準備はできおいたせんが、経隓的に少なくずも3぀の察角線が必芁であるこずがわかりたした。



語長の差が少なくずも2文字である堎合、メむンの察角線の右偎のすべおの察角線は、右䞋隅に解を衚瀺する察角線たで単玔に蚈算されたす語長が異なるず、長い方が氎平方向に曞き蟌たれるず思いたす。



異なる語長の蚈算



単語の長さが1文字異なる堎合、察角線がメむンの巊偎に远加され、単語の長さが同じ堎合、察角線がメむンの巊偎ず右偎に远加されたす。



同じ語長での蚈算

図では、メむンの察角線は緑色で、蚈算されたものは黄色で、解は赀色で匷調衚瀺されおいたす。



テヌブル蚈算関数の各ステップは、その呚囲の3぀の最小倀および遷移コスト係数ずしお新しいセルの倀を蚈算するため、テヌブルのスキップされたセルが蚈算に圱響を䞎えないように、明らかに倧きな数たずえば50で初期化する必芁がありたす前ず同様に、巊䞊のセルはれロに初期化されたす。 コヌドでは、次のようになりたす。 

 def min3(a,b,c) m = a < b ? a : b return m < c ? m : c end def calc_levenshtein_distance(s,t) return calc_levenshtein_distance(t,s) if s.length<t.length n = s.length m = t.length return m if n==0 return n if m==0 d = Array.new(m+1).map!{Array.new(n+1).map!{50}} d[0][0]=0 p = (n==m) ? 1 : 0 #   q = (nm<=1)? 1 : 0 #   for j in 1..[(n-m+p),n].min d[0][j]=d[0][j-1]+1 end for i in 1..m do for j in (i - q)..[(i + n - m + p),n].min do if j==0 d[i][j] = d[i-1][j]+1 else cost = 1 cost = 0 if t[i-1] == s[j-1] d[i][j] = min3(d[i-1][j] + 1 , d[i][j-1] + 1 , d[i-1][j-1] + cost) end end end return d[m][n] end




改善は明らかです。187.inはすでに6分で完了し、 12.inは25秒で完了しおいたす。 しかし、それでも、他の䜕かを思い぀くのはいいこずです。 5回目の反埩の党文はこちらです。



解決策。 反埩6



すでに加速されおいる機胜を可胜な限り加速するにはどうすればよいですか たあ、たずえば、あなたは単にそれを呌び出すこずはできたせん。 明らかに以前に芋぀かった以䞊の量で明らかに䞀臎しない単語のレヌベンシュタむン距離を考慮する必芁はありたせん。 しかし、速床をいくらか埗るために、この倀を蚈算し、レヌベンシュタむン距離よりもさらに高速にする方法は 私は理想のふりをしたせんが、なんずか思い぀いたのです。 各単語に26個の倀の配列を保存するこずにしたした。各倀は、この単語で英語のアルファベットの察応する文字が䜕回芋぀かったかを瀺しおいたす。 これらの配列を䜿甚した2぀の単語の差は、配列の察応する倀の差の合蚈ずしお蚈算できたす。 

 def arr_diff(a1,a2) res = 0 for i in 0..25 do res += (a1[i]-a2[i]).abs end return res end




もちろん、このような違いはレヌベンシュタむン距離よりもさらに抜象的ですが、より高速に蚈算できたす。 圌女はどのように助けるこずができたすか レヌベンシュタむン距離は、そのようなハッシュの違いにどのように関係したすか 最も重芁な関係は、単語の1文字を远加および削陀するず、これらの䞡方の意味に䞀床に1文字が远加されるこずです。 単語内で2぀の文字が亀換された堎合、元の単語からの新しい単語のレヌベンシュタむン距離は2になりたすが、察応する配列の差はれロになりたす。 文字の構成は保持されたす。 そしお、単語の文字を他の文字に倉曎するず、配列の差は2増加したすが、レヌベンシュタむン距離は1だけになりたす。したがっお、 䞋からの配列の差の制限はかなり匱いです単語の長さの差を差し匕くず、任意の数の眮換が可胜レヌベンシュタむン距離の増加に぀ながるが、配列の差の増加にはならない文字語の最小゚ラヌ数が奇数の堎合、課すこずができる唯䞀の䞋限は1です。 マットは文字の順列では達成できたせん、および䞊蚘 -配列の違いはレヌベンシュタむンの倍の距離を超えるこずはできたせん。



䞊蚘に基づいお、レヌベンシュタむン距離diffずオフセットの長さの違いを持぀2぀の単語の堎合、配列の違いは[offset、2 * diff-offset]の範囲にあるず蚀えたす。 実際、ボトムを制限するために、単語の最小゚ラヌ数の掚定倀を䜿甚するこずもできたすたずえば、1次のすべおのタむプミスを列挙しお単語を芋぀けられなかった堎合、少なくずも2぀の゚ラヌがあるず蚀えたす。 ゚ラヌの最小数ずワヌド長の差の差が奇数である堎合぀たり、ワヌドの長さの差に加えお、少なくずもN個の゚ラヌずNの奇数がある堎合、ワヌド配列の最小の可胜な差を1増やすこずができたす- [offset +min_errors-offset 2、2 * diff-offset] 偶数Nの堎合、配列の違いに圱響しない文字の順列により偶数のレヌベンシュタむン゚ラヌが発生する可胜性があるため、远加の制限を課すこずはできたせん。



この知識を䜿甚しお、レヌベンシュタむン距離蚈算関数に䞎えられた単語をフィルタリングしおみたしょう。 蟞曞の単語の配列は、蟞曞の読み取り時にすぐにはカりントされたせんが、必芁に応じお、短い入力ファむルに察しお䞍必芁な蚈算を行わないように、読み取り時に察応する配列のみを初期化したす。 

 dictionary = {} dic_words.each do |w| dictionary[w.length] ||= {} dictionary[w.length][w] = Array.new(26,0) end


珟圚の単語ず蟞曞を比范するたびに、前の比范の結果がわかりたす。 怜玢からの距離が3の単語が既に芋぀かっおいる堎合、距離が長い単語は関心がなくなるため、その単語に察応する配列の違いに制限を課すこずができたす。 この堎合の蟞曞怜玢機胜は次のようになりたす。 

  def find_word(word, dic) if dic[word.length] return {:word => word, :cost => 0} if dic[word.length].include?(word) end minimum_errors = 1 #     ,        edits = get_possible_edits(word) edits.each do |edit| return {:word => edit, :cost => 1} if dic[edit.length] ? dic[edit.length].include?(edit) : false end minimum_errors = 2 #          ,        if word.length<=6 edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3 end result_word = '' result_cost = 999 wordhash = Array.new(26,0) word.each_byte{|b| wordhash[b-65]+=1} for offset in 0..15 do return {:word => result_word, :cost => result_cost} if ((result_cost<=offset) or (result_cost<=minimum_errors)) indexes = [word.length-offset,word.length+offset].uniq indexes.each do |index| next unless dic[index] dictionary_part = dic[index] if dictionary_part[dictionary_part.keys.first].max==0 #       ,    dictionary_part.each do |key, val| key.each_byte{|b| val[b-65]+=1} end end lower_bound = (minimum_errors-offset>0 ? minimum_errors-offset : 0).abs%2 + offset higher_bound = 2*result_cost - offset dictionary_part.each do |dic_word, dic_wordhash| a = arr_diff(dic_wordhash,wordhash) next if a<lower_bound or a>higher_bound ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld higher_bound = 2*result_cost - offset end end end end return {:word => result_word, :cost => result_cost} end




したがっお、 187.inファむルは66秒 12.in -5.5秒で実行できるこずがわかりたす。 これは、プログラムの最初のバヌゞョンで衚瀺されるたたは衚瀺されない時間ず比范しお非垞に優れおおり、 david_22719.inファむルの解決策を芋るのに数時間埅぀こずさえできたすが、 結局のずころ 、facebookボットを通過するには十分ではありたせん。



解決策。 反埩7



しかし、それから私は鈍った。 実行を高速化する方法を習埗しおいないため、Rubyの䞀般的な機胜、特にバヌゞョン1.8.6の機胜に基づいた玔粋に技術的な手段に頌らなければなりたせんでした。 たずえば、䞉項挔算子aBcは埓来のif-elseよりも高速であるこずが実隓的にわかりたした。 oneい蚈算を1行で行うず、䞀時倉数を䜜成するオプションから䞀瞬勝おるこずを孊びたした。 短い倉数名は実行プロセスを高速化できるずいう神話を吊定したした。 正芏衚珟を䜿甚しおファむル党䜓を解析するこずは、行ごずに読み取るよりも速く動䜜するこずがわかりたした...オブゞェクトの䞍芁な初期化や䞍芁なメモリ割り圓おを削陀するために䜕時間もコヌドをなめるず、さらに数秒倱うこずがありたしたが、それでも十分ではありたせんでしたボットを通過したす。 そしお、私はあきらめたした。



解決策。 癜い旗



私は、圌らが通垞それに入れるずいう意味で完党にcompletelyめないこずに決めたした。 Rubyで問題を解決するずいう考えを拒吊したした。 少なくずも玔粋なRubyでは...はい、あなたは正しく理解したので、少しチヌトしおCの力に頌るこずに決めたした。数時間適切なマニュアルを吞った埌、私は2行のレヌベンシュタむン距離を考慮するRuby拡匵を曞きたした 

 #include <ruby.h> #ifndef max #define max( a, b ) ( ((a) > (b)) ? (a) : (b) ) #endif #ifndef min #define min( a, b ) ( ((a) < (b)) ? (a) : (b) ) #endif void Init_levenshtein(); VALUE distance(VALUE self, VALUE rwm, VALUE rwn); void Init_levenshtein() { VALUE cLevenshtein = rb_define_class("Levenshtein",rb_cObject); rb_define_singleton_method(cLevenshtein, "distance", distance, 2); } VALUE distance(VALUE self, VALUE rwm, VALUE rwn) { char *wm, *wn; int res; wm = StringValuePtr(rwm); wn = StringValuePtr(rwn); res = LeveDist(wm,wn); return INT2NUM(res); } int min3(int a, int b, int c) { int Min = a; if (b < Min) Min = b; if (c < Min) Min = c; return Min; } int LeveDist(char *s, char *t) { char* wm; char* wn; int m, n, q, p, cost, i, j; int loop1, loop2; char* d; int res = -1; if (strlen(s) > strlen(t)) { wm = t; wn = s; } else { wm = s; wn = t; } m = strlen(wm); n = strlen(wn); d = calloc((m + 1)*(n + 1),sizeof(char)); memset(d, 50, (m + 1)*(n + 1)); p = (n==m) ? 1 : 0; q = (nm<=1)? 1 : 0; *d = 0; loop1 = min(n, n - m + p); for (j = 1; j <= loop1; j++) *(d + j) = *(d + j - 1) + 1; for (i = 1; i <= m; i++) { loop2 = min(n, i + n - m + p); for (j = (iq); j <= loop2; j++) { if (j == 0) { *(d + i * (n + 1) + j) = *(d + (i - 1)*(n + 1) + j) + 1; } else { cost = 1; if (*(wm + i - 1) == *(wn + j - 1)) cost = 0; *(d + i * (n + 1) + j) = min3(*(d + (i - 1)*(n + 1) + j) + 1, *(d + i * (n + 1) + j - 1) + 1, *(d + (i - 1)*(n + 1) + j - 1) + cost); } } } res = *(d + m * (n + 1) + n); free(d); return res; }




さお、それは次のようになりたした 

 require 'levenshtein' ... Levenshtein.distance(word,dic_word)


その埌、6回目の繰り返しで説明した自分自身の最適化がメむンブレヌキになり、しぶしぶ拒吊する必芁がありたした発明するのに苊劎しおかなりの時間がかかりたした。



解決策。 勝利



私は認めなければならない、私は最終的にWindows甚の結果の゜リュヌションをマスタヌしたせんでした。Linuxの仮想マシンでコンパむルされおボットに送信され、数時間埌にメヌルボックスに次の圢匏のメッセヌゞが届きたした。

Facebookにパズル゜リュヌションを送信しおいただきありがずうございたす゜リュヌションを飲酒噚に実行した埌2011幎1月25日午前3時4分に受信、正しいず刀断したした。゜リュヌションは、最長のテストケヌスで5097.469ミリ秒実行されたした。


もちろん、これはCでの完党な怜玢よりも3倍遅いですが、それでも十分な速さで開始できたす



おわりに



結論ずしお、い぀ものように、いく぀かの蚀葉に぀いお。このようなテキストの壁の埌、少し道埳を蚀うこずは眪ではありたせん。コヌドのすべおの蚈算をスキップしお結論に盎行した人たちにずっお、この蚘事はオンラむン呌吞噚の問題を解決するこずに぀いおではありたせん。圌女はRubyでのプログラミングに぀いおも話しおいたせん。それは、䞀般的なプログラミング、適切な゜リュヌションの発芋に぀いおです。私たち党員が同様の問題を解決する矩務があるわけではありたせん。非垞に倚くの人々が最初に芋぀けた解決策を送信したすが、その有効性、パフォヌマンス、矎しさ、利䟿性を必芁ずしないずいう理由だけで気にしたせん。残念ながら、この方法は脳を錆びさせるので、時々同様の電荷を䞎えるず䟿利です。心はプログラマヌの䞻な歊噚であり、階士の剣のように、研ぎ柄たしお戊闘に備えおおく必芁がありたす。







More articles:


All Articles