paint-brush
SeqGen: Thư viện tôi đã tạo để tạo trình tựby@crazyrat
530
530

SeqGen: Thư viện tôi đã tạo để tạo trình tự

crazyrat7m2023/12/15
Read on Terminal Reader

Một chuỗi (nói một cách không chính thức) là một tập hợp các phần tử (chủ yếu là số) trong đó việc tạo ra từng phần tử dựa trên (các) phần tử trước đó. Ví dụ cơ bản nhất là một chuỗi tuyến tính đơn giản gồm các số nguyên dương trong đó phần tử đầu tiên là 0 và phần tử tiếp theo là phần tử trước cộng một, vì vậy chúng ta có thể lấy phần tử thứ hai bằng cách thêm một vào phần tử đầu tiên và chúng ta có thể lấy phần tử thứ ba. phần tử bằng cách thêm phần tử này vào phần tử thứ hai, v.v. Chuỗi tuyến tính sẽ có dạng như sau: {0, 1, 2, 3, …, n}.
featured image - SeqGen: Thư viện tôi đã tạo để tạo trình tự
crazyrat HackerNoon profile picture

Giới thiệu:

Nếu bạn tìm kiếm trên Internet một thư viện có thể tạo ra các chuỗi, bạn khó có thể tìm thấy một thư viện nào, mặc dù chuỗi là khái niệm cốt lõi của toán học rời rạc và khoa học máy tính.


Trong bài viết ngắn này, chúng ta sẽ xem xét thư viện mà tôi đã viết để tạo chuỗi có tên SeqGen .

Trình tự là gì?

Một chuỗi (nói một cách không chính thức) là một tập hợp các phần tử (chủ yếu là số) trong đó việc tạo ra từng phần tử dựa trên (các) phần tử trước đó.


Ví dụ cơ bản nhất là một chuỗi tuyến tính đơn giản gồm các số nguyên dương trong đó phần tử đầu tiên là 0 và phần tử tiếp theo là phần tử trước cộng một, vì vậy chúng ta có thể lấy phần tử thứ hai bằng cách thêm một vào phần tử đầu tiên và chúng ta có thể lấy phần tử thứ ba. phần tử bằng cách thêm phần tử này vào phần tử thứ hai, v.v. Chuỗi tuyến tính sẽ trông như thế này: {0, 1, 2, 3, …, n} .


Một ví dụ phức tạp hơn có thể là dãy Fibonacci trong đó hai phần tử đầu tiên là 0 và 1 và phần tử tiếp theo là tổng của hai phần tử trước đó. Dãy số Fibonacci sẽ có dạng như sau: {0, 1, 1, 2, 3, 5, 8, 13, 21, …, n}


Chúng ta có thể nhận thấy từ phía trên rằng một chuỗi được xác định với hai thuộc tính:

  • Các yếu tố ban đầu
  • Hàm tạo phần tử tiếp theo

Sử dụng Thư viện:

2.0_ Phụ thuộc:

Thư viện SeqGen được viết bằng ngôn ngữ lập trình Rust; để theo dõi, bạn cần cài đặt Rust .

2.1_ Tạo dự án:

Hãy tạo một dự án mới để sử dụng thư viện SeqGen; chúng ta có thể làm như vậy với hàng hóa:

 $ cargo new --bin sequence && cd sequence


Bây giờ, hãy thêm thư viện làm phần phụ thuộc cho dự án của chúng ta:

 $ cargo add seqgen


Bây giờ, chúng ta đã sẵn sàng sử dụng thư viện.

Tạo một chuỗi:

Trong SeqGen, quy trình tạo trình tự ánh xạ trực tiếp tới hai thuộc tính của trình tự mà chúng tôi đã kết luận trong phần Trình tự là gì; chúng ta phải xác định các phần tử ban đầu và hàm tạo ra phần tử tiếp theo (được gọi là hàm chuyển tiếp trong SeqGen).


Hãy tạo chuỗi tuyến tính:

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new() .initial_elements(vec![0]) .transition_function(|alive_elements, current_element_index| { alive_elements.last_element().unwrap() + 1 }); }


Kiểu Sequence là một cấu trúc đại diện cho một trình tự; bằng cách gọi hàm liên quan new() trên loại này, chúng ta nhận được một phiên bản mới chưa được xác định. Trong trường hợp không xác định này, chúng ta có thể gọi các phương thức để xác định nó.


Phương thức đầu tiên là initial_elements() chấp nhận một vectơ gồm các phần tử làm đối số và đặt nó làm phần tử ban đầu của thể hiện.


Phương thức thứ hai là transition_function() lấy làm đối số là một bao đóng thể hiện sự chuyển đổi từ các phần tử hiện có sang phần tử tiếp theo.


Việc đóng này có quyền truy cập vào hai đối số: đối số đầu tiên là alive_elements đại diện cho các phần tử hiện có và thứ hai là current_element_index (thuộc loại usize ) là chỉ mục của phần tử hiện tại trong thế hệ. Xem bảng dưới đây để minh họa chức năng chuyển tiếp.


Phần tử hiện tại trong thế hệ

sống_elements

current_element_index

1

[0]

1

2

[0, 1]

2

3

[0, 1, 2]

3

n

[0, 1, 2, 3, …, n]

n


alive_elements thuộc loại SequencePart , chúng ta sẽ xem xét loại SequencePart ở phần sau của bài viết này


Vì chỉ mục của phần tử cũng là giá trị của nó trong chuỗi tuyến tính nên chúng ta có thể đơn giản hóa ví dụ trên thành:

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new().transition_function(|_, i| i); }


Ở đây, chúng ta không cần xác định các phần tử ban đầu và không cần truy cập vào các phần tử trực tiếp; chúng tôi chỉ cần chỉ mục (được đặt tên là i trong trường hợp này) và chúng tôi chỉ cần trả về nó.


Theo cách tương tự, chúng ta có thể định nghĩa dãy Fibonacci:

 use seqgen::prelude::*; fn main() { let fib_seq = Sequence::new() .initial_elements(vec![0, 1_u128]) .transition_function(|alive_elements, i| { let x = alive_elements.nth_element(i - 1).unwrap(); let y = alive_elements.nth_element(i - 2).unwrap(); x + y }); }

Vì dãy Fibonacci tăng theo cấp số nhân nên việc tạo ra hơn 187 phần tử có định nghĩa này sẽ khiến u128 bị tràn. Một định nghĩa tốt hơn sẽ sử dụng big int thay vì u128 .

Sử dụng Trình tự :

Sau khi xác định trình tự của mình, chúng ta có thể truy cập các phần tử của nó:

 use seqgen::prelude::*; fn main() { let mut linear_seq = Sequence::new().transition_function(|_, i| i); let some_element = linear_seq.nth_element(111); println!("{some_element}"); }

Ở đây, chúng ta đang truy cập phần tử thứ 111 bằng phương thức nth_element() để trả về một tham chiếu bất biến cho phần tử ( &usize trong trường hợp này).


Lưu ý rằng chúng tôi đã tạo ra linear_seq có thể thay đổi. Đó là bởi vì phương thức nth_element() sẽ làm thay đổi các phần tử còn sống của chuỗi.


Bằng cách này, chúng ta có thể truy cập bất kỳ phần tử nào của chuỗi (từ phần tử có chỉ mục 0 đến phần tử có chỉ mục usize::MAX .)


Chúng ta cũng có thể lặp lại trình tự giống như bất kỳ trình lặp Rust nào:

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new().transition_function(|_, i| i); linear_seq.for_each(|e| println!("{e}")); }


Mã này sẽ in tất cả các phần tử của chuỗi (từ phần tử 0 đến phần tử usize::MAX ):

 $ cargo run -q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...


Chúng ta có thể lấy các phần tử lẻ từ chuỗi bằng mã sau:

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new().transition_function(|_, i| i); let odd_elements = linear_seq.filter(|e| e % 2 != 0); odd_elements.for_each(|e| println!("{e}")); }


Đầu ra:

 $ cargo run -q 1 3 5 7 9 11 13 ...


Trình tự mà chúng tôi xác định là lười biếng, nghĩa là các phần tử sẽ không được tạo trừ khi cần thiết (trong trường hợp lặp lại) hoặc được yêu cầu rõ ràng (sử dụng phương thức nth_element() ).

Làm việc với các phần của chuỗi :

Đôi khi, chúng ta chỉ cần làm việc với các phần của chuỗi, trong trường hợp này, chúng ta có các phần của chuỗi.


Có ba loại phần trình tự:

  • AliveElementsPart
  • ImmutableRangePart
  • MutableRangePart


AliveElementsPart:

Chúng ta có thể lấy các phần tử trực tiếp bằng phương thức alive_elements() trên chuỗi:

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new() .transition_function(|_, i| i) .pre_generate(111); let alive_elements = linear_seq.alive_elements(); for alive_element in alive_elements { print!("{alive_element} "); } }

Mã này sẽ in tất cả các phần tử còn sống (0 đến 110 trong trường hợp này vì chúng tôi đã tạo trước 111 phần tử).


Phần phạm vi bất biến:

Phạm vi bất biến là phạm vi của các phần tử còn sống; họ không thể thay đổi trình tự. Nếu bạn tạo một phạm vi bất biến và không phải tất cả các phần tử của nó đều tồn tại, bạn sẽ gặp lỗi (lỗi DeadRange ).


Chúng ta có thể tạo một phạm vi bất biến bằng phương thức range() trả về Result . Biến thể OkImmutableRangePart và biến thể ErrRangeError . RangeError có thể là biến thể InvalidRange (trong trường hợp phần đầu của dải ô lớn hơn phần cuối của nó) hoặc có thể là biến thể DeadRange (trong trường hợp không phải tất cả các phần tử của dải ô đều tồn tại):

 use seqgen::prelude::*; fn main() { let linear_seq = Sequence::new().transition_function(|_, i| i); let range = linear_seq.range(0, 3).unwrap(); for e in range { println!("{e}") } }


Đoạn mã này sẽ hoảng loạn với lỗi DeadRange vì không có phần tử còn sống. Chúng ta có thể sửa lỗi này bằng cách sau:

 use seqgen::prelude::*; fn main() { let mut linear_seq = Sequence::new().transition_function(|_, i| i); linear_seq.generate(3); let range = linear_seq.range(0, 3).unwrap(); for e in range { println!("{e}") } }

Ở đây, chúng tôi đã tạo 3 phần tử để làm cho phạm vi hợp lệ.


MutableRangePart:


Một phạm vi có thể thay đổi có thể làm thay đổi trình tự (tạo các phần tử).


Chúng ta có thể sử dụng một phạm vi có thể thay đổi như vậy:

 use seqgen::prelude::*; fn main() { let mut linear_seq = Sequence::new().transition_function(|_, i| i); let mut_range = linear_seq.range_mut(0, 111).unwrap(); for e in mut_range { println!("{e}"); } }


Mã này sẽ in các phần tử từ 0 đến 110.

Sản xuất:

Cảm ơn bạn đã đọc đến cuối bài viết này và tôi hy vọng bạn tìm thấy điều gì đó hữu ích trong đó. Nếu bạn có bất kỳ đề xuất nào có thể cải thiện thư viện này, vui lòng mở một vấn đề trên GitHub và nếu bạn muốn đóng góp cho thư viện thì điều đó thật tuyệt vời.


Cũng được xuất bản ở đây