Code thư giãn
White

nguyenduyhao1111 viết ngày 07/10/2016

Chắc hẳn ai cũng từng gặp bài như sau:

Cho số từ 1..100 
In ra 'Fizz' nếu chia hết cho 3. 
In ra 'Buzz' nếu chia hết cho 5 

À dễ qúa chứ còn gì.
Ta dễ dàng giaỉ bằng mã giả như sau:

i = chạy từ 1..100
Nếu i % 3 == 0 thì in 'Fizz'
Nếu i % 5 == 0 thì in 'Buzz'

Và ta code như sau:

def fb(n)
  s = ''
  (1..n).each do |i|
    puts 'Fizz' if i % 3 == 0
    puts 'Buzz' if i % 5 == 0
  end                   
end

Tuy nhiên bạn sẽ mất đủ 2*n lần so sánh.
Vậy ta biến đổi một chút như sau:
Ta tăng 3 và tăng 5 thay vì tăng 1

def fb1(n)
  x = 0
  y = 0
  while(x + 3 <= n || y + 5 <= n)
    if( x + 3 <= y + 5)
      x += 3
      puts "Fizz"
    else
      y += 5
      puts "Buzz"
    end
  end
end

Khá ok rồi.
Nhưng vẫn còn cách nhanh hơn nữa.
Để ý sẽ thấy quy luật cứ 3 số chia hết cho 5 thì có 5 số chia hết cho 3.
alt text
Như vậy ta có thể viết như sau: (Lưu ý hiện cách giải thứ 3 đúng với n chia hết 5 :D)

FIZZ = ["Fizz","Fizz\nFizz","Fizz\nFizz"]
def fb2(n)
  t = n/5
  t.times do |i|
    puts FIZZ[i%3]
    puts "Buzz"
  end
end

Kết qủa benchmark 3 hàm fb(n) , fb1(n), fb2(n) theo thứ tự sau:

       user     system      total        real
   0.030000   0.000000   0.030000 (  0.023087)
   0.010000   0.000000   0.010000 (  0.009984)
   0.000000   0.000000   0.000000 (  0.004115)

Có thể thấy:
fb2 chạy nhanh gấp 2 lần fb1
fb1 chạy nhanh gấp 20 lần fb
p/s : Tùy cách implement mà kết qủa benchmark có thể sau khác.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

nguyenduyhao1111

13 bài viết.
41 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
19 2
Mở đầu Khi bạn đi sâu vào thế giới linux , bạn tìm thấy nhiều điều khó có thể hiểu ngay lập tức. Và 1 trong những thứ này là khái niệm socket. Tô...
nguyenduyhao1111 viết gần 2 năm trước
19 2
White
13 0
Khái niệm : Mapreduce là một mô hình lập trình, thực hiện quá tình xử lý tập dữ liệu lớn. Mapreduce gồm 2 pha : map và reduce. Hàm Map : Các xử l...
nguyenduyhao1111 viết 2 năm trước
13 0
White
12 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết 2 năm trước
12 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
13 bài viết.
41 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!