编程语言 13

教程里面有个小示范，有代码要跑

我就在随便一个project里 git checkout了一个分支，然后建了一个新文档rb结尾的

代码写这个文档后就用 ruby XXX.rb的代码跑起来

成功了哈哈哈 开心~

成功在编译器里看到了结果

作业一

作业里面，ihower老师写了思路很赞的代码，学起来~

然后看到同学提交的答案里面竟然可以在benchmark跑的结果里 标记出文字

好奇就自己试了一下，一下成功了哈哈哈

直接用 print "标注文字"这样加在 x.report {}的大括号里面即可

至于作业一里，哪个算法好，我觉得是第二个，因为老师也标记出来啦

当测试arr的数量级别上升到大数量级的时候，肯定第二种比较快

作业二

这其中要求 “比较当 arr 元素有10个、10000个、1000000 个时” 可以参考老师的自动生成arr的代码写法

a1 = Array.new(1000000){ rand(10) }

a2 = a1 * 1000

a3 = a2 *100

初步尝试

把其中的 while true 改善成 while n <= m 也不见好

还改正了一个符号错误 else arr[n] = element 给改成 else arr[n] == element 这才是数值相等...

依然无法执行

啊！忘记to_i了啦！！！

报错，不给执行

换一种思路 把头尾最大最小的数考虑进来

还是不能执行...

偶数奇数问题还是要解决的啊

先说明一个错误，不能用数学符号啊啊啊 写成 mid = [(m + n) / 2].to_i 符合数学符号习惯，但是代码不认啊 要用 mid = ((m + n) / 2).to_i

思路再捋一捋，大于小于号方向都写错了...

还有其他的改动 再标注一波

看着老师提供的阅读资料 改了好几处 总算显示了...

def binary_search(arr, element)
 m = arr.size - 1
 n = 0

 while n <= m
   mid = (m + n) / 2

   if arr[mid] > element
     m = mid - 1
   elsif arr[mid] < element
     n = mid + 1
   elsif arr[mid] == element
     break
   end
 end

 puts mid
end

arr = [0, 5, 13, 13, 30, 42, 52, 70, 85, 96, 103, 111, 116, 127, 130, 143, 150, 150, 161, 175, 207, 210, 218, 246, 257, 257, 263, 280, 304, 310, 326, 327, 332, 346, 360, 371, 374, 378, 406, 407, 407, 408, 428, 431, 437, 442, 445, 479, 489, 491, 505, 517, 520, 536, 548, 598, 602, 605, 618, 642, 649, 654, 659, 662, 677, 678, 682, 689, 695, 696, 697, 701, 711, 717, 727, 737, 745, 749, 754, 757, 770, 786, 802, 805, 814, 832, 840, 850, 853, 854, 888, 894, 904, 913, 913, 945, 962, 964, 972, 998]

binary_search(arr, 371) # 应该回传 35

然而我还在担心偶数奇数的问题...

我最后写的array的例子是这样的

arr1 = (1..10).to_a

arr2 = (1..10000).to_a

arr3 = (1..1000000).to_a

很偷懒 不想去思考怎么从random的array排序...结果一看我们蛋妞助教的代码，我真想抽自己...还是思考一下啊啊啊！！！

def sorted_array(length)
  arr = Array.new(length) { rand(10000) }
  arr.sort
end

a1 = sorted_array 10
a2 = sorted_array 10_000
a3 = sorted_array 1_000_000

就是这个意思

def generate_array(size)
  arr = Array.new(size) { rand(100) }
  arr.sort
end

a1 = generate_array(10)
a2 = generate_array(10000)
a3 = generate_array(1000000)

然后我参考后改成了最后这个样子

def sorted_arr(size)
  arr = Array.new(size) {rand(1000)}
  arr.sort
end

arr1 = sorted_arr(10)
arr2 = sorted_arr(10000)
arr3 = sorted_arr(1000000)

很值得玩一下，rand的括号里数值不同的话 有惊喜哦~~

好吧，对比一下我自己一小时交差式代码，跟我们蛋妞大大的代码

def binary_search(arr, element)
 m = arr.size - 1
 n = 0

 while n <= m
   mid = (m + n) / 2

   if arr[mid] > element
     m = mid - 1
   elsif arr[mid] < element
     n = mid + 1
   elsif arr[mid] == element
     break
   end
 end

 puts mid
end

arr1 = (1..10).to_a

arr2 = (1..10000).to_a

arr3 = (1..1000000).to_a

Benchmark.bm do |x|
  x.report {
   binary_search(arr1, 8)
  }
  x.report {
    binary_search(arr2, 1123)
  }
  x.report {
    binary_search(arr3, 33333)
  }
end

真实的“你看看人家！！！”系列 哈哈哈

自带标识的Benchmar.bm啊

require 'benchmark'
arr = [0, 5, 13, 13, 30, 42, 52, 70, 85, 96, 103, 111, 116, 127, 130, 143, 150, 150, 161, 175, 207, 210, 218, 246, 257, 257, 263, 280, 304, 310, 326, 327, 332, 346, 360, 371, 374, 378, 406, 407, 407, 408, 428, 431, 437, 442, 445, 479, 489, 491, 505, 517, 520, 536, 548, 598, 602, 605, 618, 642, 649, 654, 659, 662, 677, 678, 682, 689, 695, 696, 697, 701, 711, 717, 727, 737, 745, 749, 754, 757, 770, 786, 802, 805, 814, 832, 840, 850, 853, 854, 888, 894, 904, 913, 913, 945, 962, 964, 972, 998]

def binary_search(arr, element)
  l = 0
  r = arr.length - 1

  while l <= r

    mid = l + ((r - l) / 2)
    if arr[mid] == element
      return mid
    elsif arr[mid] > element
      r = mid - 1
    else
      l = mid + 1
    end
  end

  '404!'
end

# p binary_search(arr, 666)
# p arr.bsearch_index{|x| x >= 371}

def sorted_array(length)
  arr = Array.new(length) { rand(10000) }
  arr.sort
end

a1 = sorted_array 10
a2 = sorted_array 10_000
a3 = sorted_array 1_000_000

Benchmark.bm do |x|
  x.report('#binary_search with 10-element array') do
    binary_search a1, 7899
  end
  x.report('#binary_search with 10000-element array') do
    binary_search a2, 7899
  end
  x.report('#binary_search with 1000000-element array') do
    binary_search a3, 7899
  end
  x.report('#bsearch with 10-element array') do
    a1.bsearch_index { |x| x >= 7899 }
  end
  x.report('#bsearch with 10000-element array') do
    a2.bsearch_index { |x| x >= 7899 }
  end
  x.report('#bsearch with 1000000-element array') do
    a3.bsearch_index { |x| x >= 7899 }
  end
  x.report('#find_index with 1000000-element array') do
    a3.find_index 7899
  end
end