Rubyバイナリ検索では、すでに配列に配列されている値が認識されない

Question

配列に項目を追加しています。それらを追加するには、アプリケーションバイナリ検索を現在の配列にします。存在する場合、項目を追加しません。項目が存在しない場合には、それが追加されます：

while (line = fileObj.gets) 

    itemD = line.split(" ") 
    number = itemD.at(0) 
    name = itemD.at(1) 

    if (search(items, number) == -1) 
    # Doesn't add if item already exists 
    puts "Already have: #{number} - #{name}" 
    else 
    # Adds a new item to the list 
    items << Item.new(number, name) 
    end 
end 

以上、私のループは、ファイルからの入力を読み込み、番号と名前を取ります。その後、番号を検索します。関わらず

58  Item 1 
17  Item 2 
58  Item 3 
76  Item 4 
06  Item 5 
08  Item 6 
17  Item 7 
21  Item 8 
76  Item 4 
76  Item 4 
00  Item 9 
49  Item 10 
40  Item 11 
79  Item 12 
31  Item 13 

：

def search(array, key) 
    min = 0 
    max = array.length-1 
    mid = 0 

    while(min <= max) 
    mid = lo + ((min - max)/2) 

    if array[mid].number == key 
     return -1 
    elsif array[mid].number < key 
     min = mid + 1 
    else 
     max = mid - 1 
    end 
    end 

    puts "#{key} not found in array" 
end 

私の基本的なテストケースを使用しているとき、私は問題に気づいた：上記のコードは、それが正しく動作していない以下のコード（バイナリサーチ）ですので、完全に正常に動作します別の名前、それは項目3を追加しません（すでに存在しているので、良いです）。次に、2番目のアイテム4に移動します。そのアイテムを追加しますが、3番目のアイテム4に移動し、配列にあることを通知して追加しません。

58 not found in array 
17 not found in array 
Already have: 58 - Item 3 
76 nfia 
06 nfia 
08 nfia 
17 nfia 
21 nfia 
76 nfia (WRONG) 
Already have: 76 - Item 4 (CORRECT) 
00 nfia 
49 nfia 
40 nfia 
79 nfia 
31 nfia 

次は私が唯一の1項目、複数回のテストケースを作った：私の出力は、（問題をトレースを助けるために）以下の通りである

58  Item 1 
58  Item 1 
58  Item 1 
58  Item 1 
58  Item 1 

それは正しく、最初に追加し、次のに気付き4（適切に追加しない）。それがちょうど追加された直後とは対照的に、数字がリストの後ろに現れるならば、明らかにそれ以上のことがあります。だから、次の私がテストした：

58  Item 1 
08  Item 6 
58  Item 1 
08  Item 6 
58  Item 1 
08  Item 6 
58  Item 1 
08  Item 6 
58  Item 1 
08  Item 6 

をこれは私が出力とを参照するが、それの興味深い反復てるものを示しています

58 nfia 
08 nfia 
Already have 58 
08 nfia (WRONG) 
58 nfia (WRONG) 
already have 
already have 
already have 
already have 
already have 

誰かがそれは私の中で要素を気づく理由で私を助けることができます配列は時間の一部ですが、必ずしもそうではありません。助けてくれてありがとう、私はそれを感謝します！

Answer 1

RubyがメソッドArray#bsearchにバイナリ検索を実行する方法を示していること以外は、バイナリ検索メソッドで他の人が問題を解決できるようにします。タスクを実行するためにもっとRubyのような方法を提案したいと思います。

コード

require 'set' 

def process_file(fname) 
    s = Set.new 
    items = [] 
    File.foreach(fname) do |line| 
    pair = line.split 
    if s.add?(pair) 
     items << Item.new(*pair) 
    else 
     puts "Already have: %s - %s" % pair 
    end 
    end 
    items 
end 

例

のは、テストファイルを作成してみましょう。

str =<<_ 
Humpty Dumpty 
sat on 
a wall. 
Humpty Dumpty 
had a 
great fall. 
_ 

FName = "test" 

File.write(FName, str) 
    #=> 61 

それを確認しましょう。

puts File.read(FName) 
Humpty Dumpty 
sat on 
a wall. 
Humpty Dumpty 
had a 
great fall. 

クラスItemが必要です。

class Item 
    def initialize(*pair) 
    @pair = pair 
    end 
end 

準備は整いました。

process_file(FName) 
    Already have: Humpty - Dumpty 
    #=> [#<Item:0x007f978404e2f0 @pair=["Humpty", "Dumpty"]>, 
    # #<Item:0x007f978404c810 @pair=["sat", "on"]>, 
    # #<Item:0x007f9784046370 @pair=["a", "wall."]>, 
    # #<Item:0x007f978403ced8 @pair=["had", "a"]>, 
    # #<Item:0x007f9784037e88 @pair=["great", "fall."]>] 

Set::new、IO::foreach、String#splitとSet#add?を参照してください。IOメソッド（foreachなど）は、のサブクラスであるクラスFileで一般に呼び出されます。

Answer 2

上記のコードは完全に正常に動作しますので、それは

このステートメントが間違っている正しく動作していない以下のコード（バイナリサーチ）です：上記のコードははない「完璧に動作しません良い "。特に、バイナリサーチでは配列のソートが必要なので、searchを呼び出す前にソートするか、新しい項目を正しい場所に挿入して、配列が常にソートされるようにする必要があります。ただし、配列の末尾には、numberに関係なく項目をスティックするだけで、配列を並べ替えることはできません。

numberで参照されるオブジェクトが実際にはStringであり、数値ではないという2番目のバグもあります。それは単に変数の命名が間違っているかもしれませんが、残りのコードからは、実際には数字になるように見えます。特に、11が2より小さくなるように実際に意図しているかどうかはわかりません。これは文字列の場合です。

searchメソッドに少なくとも1つのバグがあります。loはどこにも定義されていません。

代わりにminを意味すると仮定しても、数式はまだ間違っていますが、それ以外の方法ではなくmin + ((max - min)/2)である必要があります。しかし、実際には、体操全体は必要ではありません。これは、算術演算が壊れている言語でのみ必要です。 Rubyは完全に2つの整数をエラーなしで一緒に追加できるので、(min + max)/2を実行するだけで済みます。

もう1つの問題は、searchメソッドの戻り値が本当に意味をなさないことです。 1つは、実際にアイテムを取得するには戻り値が無駄です。 searchメソッドは、アイテムを返すか、配列のようなインデックス可能なシーケンスの場合は、アイテムのインデックスを返します。 searchメソッドは、アイテムが存在する場合は-1を返し、存在しない場合はnilを返します。つまり、アイテムが存在するかどうかだけを伝えます。それはひどく有用ではありません。あなたがGoogleに検索クエリを入力した場合、「あなたが探しているものは存在しますが、どこにいるのかわかりません。または、あなたが誤って落としたコンタクトレンズを探すのに助けを求める人もいれば、「見つけました！」と言います。それからちょうど歩いてください。

そこには、バイナリサーチの2つの形式が一般的です：それは存在している場合は、1つは、要素のインデックスを返し、何か他のもの（例えば-1またはnilまたはNULLまたはいくつかの他の特別な指定された値）は、そうでない項目が「doesnのことを伝えるために存在しない。他の形式では、項目が存在する場合、その項目がシーケンス内のどこに属しているかの指標が常に戻されます。バイナリ検索では配列をソートする必要がありますが、配列をソートするのは意味がありません（バイナリ検索はO（n）と比較してO（n）を必要とするだけなので、あなたのキーは数字なので、比較ベースのソートではO（n * log n）比較（またはO（n））を取るので、単純なリニア検索よりも全体的に処理速度が遅くなります。あなたがアイテムが属していない場合でも、それが属しているインデックスを示すバイナリ検索のフォームが必要であることを意味するシーケンスの正しい場所にアイテムがあります（特にない場合はです。適切な場所）。

残念ながら、これらのバグや設計ミスを修正すると、単純なスタックオーバーフローの回答の範囲を超えます。

代わりに、プログラムを設計する上で最も重要なステップの1つは、使用するデータ構造を決定することです。この場合、配列に重複がないようにしたいと思っています。これは実際に配列を必要とせず、むしろ配列を必要としているようです。たぶん、ソートされたセットが必要ですが、あなたの説明とコードから、実際にそのプロパティが必要なようには見えません。私はそれをRubyのやり方をしないしようとしていた

class Item < Struct.new(:number, :name) 
    def eql?(other) 
    number.eql?(other.number) 
    end 

    def hash 
    number.hash 
    end 

    # the following are only needed for a sorted set 

    def <=>(other) 
    number <=> other.number 
    end 

    include Comparable 
end 

require 'set' 

items = File.foreach('filename.txt'). 
    map {|line| number, name = line.chomp.split(nil, 2); Item.new(number.to_i, name) }. 
    to_set 
#=> #<Set: {#<struct Item number=58, name="Item 1">, 
      #<struct Item number=17, name="Item 2">, 
      #<struct Item number=76, name="Item 4">, 
      #<struct Item number=6, name="Item 5">, 
      #<struct Item number=8, name="Item 6">, 
      #<struct Item number=21, name="Item 8">, 
      #<struct Item number=0, name="Item 9">, 
      #<struct Item number=49, name="Item 10">, 
      #<struct Item number=40, name="Item 11">, 
      #<struct Item number=79, name="Item 12">, 
      #<struct Item number=31, name="Item 13">}> 

# if you want a sorted set instead: 

items = SortedSet.new(File.foreach(filename.txt)) {|line| 
    number, name = line.chomp.split(nil, 2); Item.new(number.to_i, name) 
} 
#=> #<SortedSet: {#<struct Item number=0, name="Item 9">, 
        #<struct Item number=6, name="Item 5">, 
        #<struct Item number=8, name="Item 6">, 
        #<struct Item number=17, name="Item 2">, 
        #<struct Item number=21, name="Item 8">, 
        #<struct Item number=31, name="Item 13">, 
        #<struct Item number=40, name="Item 11">, 
        #<struct Item number=49, name="Item 10">, 
        #<struct Item number=58, name="Item 1">, 
        #<struct Item number=76, name="Item 4">, 
        #<struct Item number=79, name="Item 12">}>