Computer >> Máy Tính >  >> Lập trình >> Ruby

Tổng quan về cấu trúc dữ liệu dành cho nhà phát triển Ruby

Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là một cách cụ thể để tổ chức và truy cập dữ liệu .

Các ví dụ bao gồm:

  • Mảng
  • Cây nhị phân
  • Hàm băm

Các cấu trúc dữ liệu khác nhau vượt trội ở các nhiệm vụ khác nhau.

Ví dụ:mã băm rất tuyệt nếu bạn đang muốn lưu trữ dữ liệu giống như từ điển (từ và định nghĩa) hoặc danh bạ điện thoại (tên và số của người đó).

Biết cấu trúc dữ liệu nào có sẵn và đặc điểm của từng người trong số họ , sẽ giúp bạn trở thành một nhà phát triển Ruby tốt hơn.

Đó là những gì bạn sẽ học được trong bài viết này!

Hiểu mảng

Mảng là cấu trúc dữ liệu đầu tiên mà bạn tìm hiểu khi bắt đầu đọc về lập trình.

Mảng sử dụng một đoạn bộ nhớ liền kề nơi các đối tượng được lưu trữ lần lượt mà không có khoảng trống giữa chúng.

Không giống như các ngôn ngữ lập trình cấp thấp hơn, như C, Ruby thực hiện tất cả công việc khó khăn trong việc quản lý bộ nhớ của bạn, mở rộng kích thước mảng tối đa và thu gọn nó khi bạn xóa các phần tử.

Công dụng :

  • Làm cơ sở cho các cấu trúc dữ liệu nâng cao hơn
  • Để thu thập kết quả từ việc chạy một vòng lặp
  • Thu thập các mặt hàng

Bạn sẽ tìm thấy các mảng ở khắp mọi nơi, chẳng hạn như split &chars các phương thức chia nhỏ một chuỗi thành một mảng ký tự.

Ví dụ :

out = []

10.times { |i| out << i }

out
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Bảng sau đây cho bạn thấy các hoạt động của mảng khác nhau hoạt động như thế nào khi kích thước của mảng tăng lên.

Nếu bạn không quen với ký hiệu phức tạp về thời gian, hãy đọc bài viết này.

Độ phức tạp về thời gian cho mảng :

Hoạt động Độ phức tạp
đẩy O (1)
pop O (1)
truy cập O (1)
tìm thấy O (n)
xóa O (n)

Tại sao điều này lại hữu ích?

Bởi vì nó cho bạn biết đặc điểm hiệu suất của mảng.

Nếu bạn đang thực hiện nhiều find hoạt động trên một mảng HUGE sẽ chậm ...

Nhưng nếu bạn biết chỉ mục nào cần sử dụng, thì một mảng sẽ hoạt động nhanh chóng vì O(1) phức tạp về thời gian.

Chọn cấu trúc dữ liệu của bạn với tiêu chí này :

  1. Đặc điểm hiệu suất => Bạn đang làm gì với dữ liệu? Tập dữ liệu của bạn lớn đến mức nào?
  2. Hình dạng &dạng dữ liệu của bạn => Bạn đang làm việc với loại dữ liệu nào? Bạn có thể sắp xếp lại dữ liệu của mình để phù hợp với cấu trúc dữ liệu hơn không?

Cấu trúc dữ liệu băm

Bạn có ánh xạ giữa mã quốc gia và tên quốc gia không?

Hoặc có thể bạn chỉ muốn đếm thứ.

Đó chính xác là những gì hàm băm hữu ích!

Hàm băm là một cấu trúc dữ liệu trong đó mọi giá trị đều có khóa và khóa này có thể là bất kỳ thứ gì , như một chuỗi, một số nguyên, một ký hiệu, v.v.

Nó hoạt động như thế nào?

Hàm băm chuyển đổi khóa của bạn thành một số (sử dụng hash trong Ruby) và sau đó sử dụng số đó làm chỉ mục. Nhưng bạn không cần phải hiểu điều đó để có thể sử dụng hàm băm trong các chương trình Ruby của mình.

Công dụng :

  • Đếm các ký tự trong một chuỗi
  • Ánh xạ từ thành định nghĩa, tên với số điện thoại, v.v.
  • Tìm các bản sao bên trong một mảng

Ví dụ :

"aaabcd"
  .each_char
  .with_object(Hash.new(0)) { |ch, hash| hash[ch] += 1 }

# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}

Độ phức tạp về thời gian :

Hoạt động Độ phức tạp
cửa hàng O (1)
truy cập O (1)
xóa O (1)
find (value) O (n)

Hàm băm là một trong những cấu trúc dữ liệu hữu ích nhất khi nói đến hiệu suất vì O(1) không đổi lưu trữ, xóa và thời gian truy cập.

Tìm trong ngữ cảnh của hàm băm có nghĩa là bạn đang tìm kiếm một giá trị cụ thể.

Ngăn xếp

Một chồng đĩa giống như một chồng đĩa, bạn đặt đĩa này lên trên đĩa khác và bạn chỉ có thể lấy đĩa lên trên.

Điều này hữu ích hơn so với âm thanh lúc đầu!

Công dụng :

  • Thay thế các phương thức đệ quy bằng một vòng lặp thông thường
  • Theo dõi công việc còn lại phải làm, để lại công việc gần đây nhất ở trên cùng
  • Đảo ngược một mảng

Ví dụ :

stack = [1,2,3,4,5]

(1..stack.size).map { stack.pop }

# [5, 4, 3, 2, 1]

Có, bạn có thể sử dụng reverse thay vào đó.

Đây chỉ là một ví dụ để cho bạn thấy đặc điểm cụ thể này của ngăn xếp.

Độ phức tạp về thời gian :

Hoạt động Độ phức tạp
đẩy O (1)
pop O (1)
tìm thấy ---
truy cập ---

Lưu ý rằng ngăn xếp (và hàng đợi) chỉ có hai hoạt động, insert &delete hoặc push &pop .

Mặc dù có thể tìm kiếm bên trong ngăn xếp, nhưng nó rất hiếm.

Cách sử dụng cây nhị phân

Hầu hết các nhà phát triển Ruby có lẽ đã nghe nói về cây nhị phân nhưng chưa bao giờ sử dụng cây.

Tại sao vậy?

Đầu tiên, chúng tôi không có triển khai cây nhị phân tích hợp sẵn.

Thứ hai, cây nhị phân không hữu ích cho các thử thách lập trình hàng ngày, không giống như các mảng và hàm băm mà bạn sử dụng mọi lúc.

Nhưng cây nhị phân là một cấu trúc dữ liệu rất thú vị .

Tổng quan về cấu trúc dữ liệu dành cho nhà phát triển Ruby

Trên thực tế, có rất nhiều biến thể, như cây Trie (được trình bày trong phần tiếp theo), cây nhiều đường như B-Tree (được sử dụng trong cơ sở dữ liệu) và Heap.

Công dụng :

  • Nén dữ liệu
  • Bảng định tuyến
  • Cây cú pháp tóm tắt (AST)

Ví dụ :

# https://github.com/jamesconant/bstree

require 'bstree'

root = Bstree::Node.new(5)

root.insert(2)
root.insert(7)

root.search(3)
# nil

Độ phức tạp về thời gian :

Hoạt động Độ phức tạp
chèn O (log n)
xóa O (log n)
tìm thấy O (log n)
truy cập ---

Cây nhị phân cân bằng là khi tất cả các nút có hai nút con và tất cả các lá có cùng cấp độ

Nếu một cây trở nên không cân bằng, hiệu suất sẽ giảm xuống O(n) .

Trong cây nhị phân tự cân bằng (như cây Đỏ-đen hoặc cây AVL), mọi thao tác cần thời gian tỷ lệ với chiều cao (hoặc cấp độ) của cây.

Lưu ý rằng không có thời gian truy cập vì để truy cập vào một nút trước tiên bạn phải tìm thấy nó ...

Trong trường hợp đó, bạn sẽ có O(log n) để truy cập.

Nhưng nếu giữ một tham chiếu (dưới dạng một biến) đến một nút cụ thể, thì đó sẽ là O(1) thời gian truy cập.

Cấu trúc dữ liệu Trie

Trie là một cấu trúc dữ liệu dạng cây chuyên biệt.

Nó hữu ích cho việc làm việc với các từ và sau đó nhanh chóng tìm kiếm các từ bắt đầu bằng tiền tố hoặc tìm kiếm từ đầy đủ.

Công dụng :

  • Trò chơi chữ
  • Trình kiểm tra chính tả
  • Đề xuất tự động hoàn thành

Ví dụ :

# https://github.com/gonzedge/rambling-trie

require 'rambling-trie'

trie = Rambling::Trie.create('words.txt')

trie.include?('chocolate')
# true
trie.include?('salmon')
# true

Độ phức tạp về thời gian :

Hoạt động Độ phức tạp
thêm O (k)
bao gồm? O (k)
từ O (k)

Trong bảng này, tôi sử dụng k để biểu thị kích thước của chuỗi đầu vào, trong khi n được sử dụng để biểu thị kích thước của chính cấu trúc dữ liệu.

Vì vậy, đối với từ apple , k sẽ là 5.

Tóm tắt

Bạn đã học về các cấu trúc dữ liệu phổ biến, công dụng và đặc điểm chính của chúng cũng như cách sử dụng chúng trong Ruby.

Tổng quan về cấu trúc dữ liệu dành cho nhà phát triển Ruby

Khi áp dụng kiến ​​thức mới này, bạn sẽ có thể giải quyết vấn đề nhanh hơn!

Bạn có thể chia sẻ bài đăng này cho tôi nếu bạn thấy nó hữu ích?

Xin cảm ơn 🙂