Ruby開発用アルゴリズム

すべてのソフトウェア開発者は古典的な古い学校のアルゴリズムについて聞いた.あなたが質問をするならばその品はあなたのためです.
アルゴリズムを議論するとき、バイナリ探索アルゴリズムはすぐに私の心に来る.あなたがそれについて聞いていないか、あなたの知識をリフレッシュしたいならば、私はあなたに見てみることを提案します.
だから、我々は本当に知っていると覚えてどのようにバイナリ検索動作し、どのように実装するには、我々はすでにしている場合Array#find_index ルビーでのメソッド?

実験
ちょっと楽しい実験を書きましょう.私の計画は、プレーンルビーでバイナリ検索アルゴリズムを実装することです.があるMain モジュールとカスタム関数#b_index

# script.rb
module Main
  # @param array [Array<Object>]
  # @param value [Object]
  # @return [Integer] index of element or -1
  def self.b_index(array, value)
    low = 0
    high = array.size

    while low < high
      mid = ((low+high) / 2).floor
      midval = array[mid]
      if midval < value
        low = mid+1
      elsif midval > value
        high = mid
      else
        return mid
      end
    end
    -1
  end
end

別のケースをチェックするためにいくつかのテストを書きましょう.

# spec/test1_spec.rb
require 'rspec'
require_relative '../script'

RSpec.describe 'Script' do
  context 'array with integers' do
    it { expect(Main.b_index([], 1)).to eq(-1) }
    it { expect(Main.b_index([1,2,3,4], 1)).to eq(0) }
    it { expect(Main.b_index([1,2,3,4], 2)).to eq(1) }
    it { expect(Main.b_index([1,2,3,4], 3)).to eq(2) }
    it { expect(Main.b_index([1,2,3,4], 4)).to eq(3) }
  end

  context 'array with similar values' do
    it { expect(Main.b_index([2,2,2], 2)).to eq(1) }
    it { expect(Main.b_index([1,2,2,2,13], 2)).to eq(2) }
  end

  context 'array with string values' do
    it do
      expect(Main.b_index(['a', 'b', 'c'], 'z')).to eq(-1)
      expect(Main.b_index(['a', 'b', 'c'], 'a')).to eq(0)
      expect(Main.b_index(['a', 'b', 'c'], 'b')).to eq(1)
      expect(Main.b_index(['a', 'b', 'c'], 'c')).to eq(2)
      expect(Main.b_index(['a', 'b', 'c'], 'z')).to eq(-1)
    end
  end
end

だから、それは動作!すべてのテストが渡されます.別のテストケースを書きましょうArray#find_index

# spec/test2_spec.rb
require 'rspec'
require_relative '../script'

RSpec.describe 'Match with Array#find_index' do
  # it runs Array#find_index and match result with value
  def test_helper(array, value)
    answer = array.find_index(value)
    answer.nil? ? -1 : answer
  end

  (1..100).to_a.each do |i|
    context "array from 0 to #{i}" do
      arr = (0..i).to_a
      arr.each do |j|
        number = j
        it "can find #{number}" do
          expect(Main.b_index(arr, number)).to eq(test_helper(arr, number))
        end
      end
    end
  end
end

だから、バグなしで動作する!🐞

ベンチマークと結果
最も興味深いのは、ベンチマークテストをArray#find_index メソッド.

# race.rb
require_relative './script'
require 'benchmark'

# we will create an array with 50_000 numbers
i = 50_000
puts "test an array from 0 to #{i}"
arr = (0..i).to_a

Benchmark.bm do |x|
  # benchmark for `Array#find_index`
  x.report('standard find_index') do
    arr.each { |number| arr.find_index(number) }
  end

  # benchmark for our custom function
  x.report('my b_index') do
    arr.each { |number| Main.b_index(arr, number) }
  end
end

それを実行し、結果を見てみましょう.

$ bundle exec ruby race.rb
test an array from 0 to 50000
       user     system      total        real
standard find_index  7.970743   0.003301   7.974044 (  7.976267)
my b_index  0.061279   0.000458   0.061737 (  0.062213)

我々のアルゴリズムがより速いのは素晴らしいArray#find_index メソッド.理由はArray#find_index 用途linear search algorithm そして、それはビットo表記法を持ちますO(n) . バイナリ検索はパフォーマンスO(log n) .

数字だけでなく
数字と文字列は退屈です.カスタムオブジェクトと一致できますか?もちろん、はい!

# spec/test3_spec.rb
require 'rspec'
require_relative '../script'

# our custom Object
class MyObject
  include Comparable

  # @param number [Integer]
  def initialize(number)
    @number = number
  end

  attr_reader :number

  def <=>(object)
    if object.is_a?(self.class)
      number <=> object.number
    elsif object.is_a?(Integer)
      number <=> object
    else
      raise 'Can not compare the type'
    end
  end
end

# and tests
RSpec.describe 'Custom objects test' do
  # it runs Array#find_index and match result with value
  def test_helper(array, value)
    answer = array.find_index(value)
    answer.nil? ? -1 : answer
  end

  (1..100).to_a.each do |i|
    context "array from 0 to #{i}" do
      arr = (0..i).map { |i| MyObject.new(i + 1) }
      arr.each do |obj|
        number = obj.number
        it "can find MyObject with #{number}" do
          expect(Main.b_index(arr, number)).to eq(test_helper(arr, number))
        end
      end
    end
  end
end

すごい、それは働く!そして、あなたは巨大な配列でデータを見つけようとするとき、あなたのアプリケーションでパフォーマンスを向上させることができるバイナリ・サーチを見ます.

結論
アルゴリズムを知ることはダミーチェックではなく、特に最適化のために非常に役に立つことができます.私は、記事があなたのアプリケーションでパフォーマンスを改善するのを助けることを望みます.私は記事があなたにインスピレーションを与え、あなたはアルゴリズムを勉強続ける✨
ソースコードへのリンクhere