Cách chọn một dòng từ tệp văn bản trong python

Tôi đã hỏi câu hỏi này trong Nghiên cứu của Microsoft, trong nhóm chống thư rác ban đầu và trong nhóm Khoa học dữ liệu/Học máy Office. Chúng tôi thích câu hỏi này vì nó đề cập đến các vấn đề về xác suất, thuật toán và hệ thống

Ngay cả khi đã nghỉ hưu ở Microsoft, chúng tôi vẫn nghĩ về câu hỏi ngẫu nhiên. Ví dụ, gần đây chúng ta đã biết về

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

3. Đó là một thùng Rust sử dụng các hướng dẫn CPU SIMD để tăng tốc, trong số những thứ khác, đếm các dòng trong một tệp. Như chúng tôi sẽ mô tả sau, việc học cái thùng của chúng tôi đã dẫn dắt — một cách gián tiếp — đến việc cải thiện giải pháp yêu thích của chúng tôi cho câu hỏi về dòng ngẫu nhiên

Chúng tôi đã tổ chức bài viết này dưới dạng một loạt các câu hỏi và gợi ý. Nếu muốn, bạn có thể cố gắng tự trả lời các câu hỏi trước khi xem câu trả lời của chúng tôi

Trong bài viết này, chúng tôi sẽ đưa ra câu trả lời bằng Python. Để biết câu trả lời trong Rust, hãy xem phiên bản Rust của bài viết này. Bạn cũng có thể thích đọc cả hai ấn bản như một cách để so sánh hai ngôn ngữ

Chúng tôi đã cho người được phỏng vấn lời khuyên này cho các cuộc phỏng vấn bảng trắng

• Vui lòng đặt câu hỏi làm rõ. [Trong khuôn khổ bài viết này, bạn có thể đọc thêm một chút để xem chúng tôi có giải thích rõ. ]
• Bắt đầu với một thuật toán chính xác trước, ngay cả khi nó có thể không tối ưu. Nếu chúng tôi muốn một thuật toán tốt hơn, chúng tôi sẽ nhắc bạn về thuật toán đó bằng các câu hỏi tiếp theo
• Đừng lo lắng về cú pháp chính xác. Ví dụ: chúng tôi không quan tâm liệu bạn có nhớ chính xác phương pháp tạo số ngẫu nhiên hay không. [Trong bài viết này, chúng tôi sẽ đưa ra câu trả lời bằng Python. ]
• Nếu bạn gặp khó khăn, chúng tôi có thể cung cấp một số gợi ý. [Một lần nữa, trong khuôn khổ bài viết này, hãy đọc xa hơn một chút để tìm gợi ý. ]

Hãy bắt đầu với những câu hỏi

Q. Bạn sẽ chọn một dòng ngẫu nhiên từ một tệp văn bản có độ dài không xác định như thế nào?

A. Trước tiên chúng ta phải làm rõ ý nghĩa của một dòng ngẫu nhiên. Ý chúng tôi là mọi dòng trong tệp văn bản đều có cơ hội được trả về như nhau. Nói cách khác, chúng tôi muốn thuật toán chọn trong số các dòng thông qua phân phối đồng đều

Yêu cầu này có nghĩa là bạn không thể sử dụng thuật toán này, mà chúng tôi sẽ gọi là

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

4

• Hỏi hệ thống tập tin về độ dài của tập tin
• Chọn ngẫu nhiên một vị trí tệp và tìm đến vị trí đó
• Trả lại một dòng gần vị trí

phụ Q. Có chuyện gì với

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

4 vậy?

Phụ A. Mặc dù thuật toán có thể trả về bất kỳ dòng nào trong tệp, nhưng nó trả về các dòng dài hơn với xác suất cao hơn các dòng ngắn hơn và do đó, không chọn các dòng thông qua phân phối đồng đều

Qua một bên. Chúng tôi muốn được yêu cầu làm rõ điều này. Nó phân biệt ý nghĩa hàng ngày của “ngẫu nhiên” với ý nghĩa kỹ thuật được sử dụng trong thống kê, khoa học dữ liệu, lý thuyết quyết định và học máy

Dấu. Nếu bạn đang viết mã bằng Python và cần giải quyết vấn đề về dòng ngẫu nhiên một cách nhanh chóng [nhưng chính xác], bạn sẽ làm gì?

Chúng tôi đã hỏi GitHub Copilot về một giải pháp và nó đã cung cấp cho chúng tôi mã này. Gọi nó là

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

6

Điều này rõ ràng là chính xác và nhanh chóng. Như một phần thưởng, nó sử dụng

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

7 để mở tệp trong trình quản lý ngữ cảnh, đây là một cách thực hành tốt. Để kiếm được một phần thưởng khác, bạn có thể đề cập rằng mã sẽ đưa ra một ngoại lệ đối với các tệp trống

Mặt khác, mã này đọc toàn bộ tệp vào bộ nhớ và do đó, sẽ không hoạt động trên các tệp lớn. Ngoài ra [một điểm nhỏ], có thể thay thế

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

8 bằng

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

9

Qua một bên. Bạn có thể viết mã thuật toán này trong một dòng.

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

0. Tuy nhiên, chúng tôi không thích các giải pháp một dòng chỉ ảnh hưởng đến khả năng đọc

Hãy theo dõi bằng cách yêu cầu một giải pháp hoạt động trên các tệp lớn

Q. Sử dụng ít bộ nhớ, làm cách nào bạn có thể chọn một dòng ngẫu nhiên từ tệp văn bản có độ dài không xác định?

A. Trước tiên chúng ta phải làm rõ “chút trí nhớ”. Đối với câu hỏi này, giả sử rằng bạn có thể lưu trữ bất kỳ dòng nào từ tệp hoặc một vài dòng chứ không phải tất cả các dòng

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

0 giải quyết vấn đề bằng 1. đếm số dòng trong tệp, 2. chọn ngẫu nhiên một chỉ mục dòng, 3. trả về dòng có chỉ mục đó. [Trong suốt bài viết này, “index0” là một chỉ mục bắt đầu đếm từ 0. Nếu một chỉ mục bắt đầu đếm từ 1, chúng tôi sẽ gọi nó là “index1”. ]

Trên máy của tôi, kết quả này

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

1

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

0là chính xác. Tôi cũng sẽ tặng mã này một phần thưởng cho

• sử dụng trình tạo số ngẫu nhiên với nguồn gốc rõ ràng — học máy và khoa học dữ liệu thường yêu cầu khả năng tái tạo, thậm chí từ tính ngẫu nhiên
• [rất nhỏ] sử dụng các chuỗi định dạng Python, bao gồm cả nghìn dấu phân cách
• đề cập rằng nó trả về

  r = rng.random[]
  index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

  3khi được áp dụng cho một tệp trống

Không bắt buộc, nhưng điều thú vị là việc triển khai nhiều chức năng hơn này

Ngoài 1. Thông tin lai lịch. Mã này sử dụng trình lặp Python. Khi

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

4 được áp dụng cho trình lặp Python, giá trị tiếp theo trong chuỗi được trả về hoặc nếu chuỗi hoàn tất, một ngoại lệ sẽ được đưa ra. Hàm

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

5 có thể bỏ qua trong một trình vòng lặp mà không trả về giá trị. Biểu thức

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

6 trả về một đối tượng, trong số những thứ khác, một trình vòng lặp trên các dòng trong tệp. Hàm

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

7 nhận một trình lặp và trả về một trình vòng lặp mới sao cho mỗi lệnh gọi tới

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

4 trên trình vòng lặp mới sẽ trả về một chỉ mục bắt đầu từ 0 và một giá trị từ trình vòng lặp ban đầu

Ngoài 2. Chúng tôi sẽ không phạt ai đó vì mắc lỗi từng lỗi một với

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

9 hoặc

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

5. Tuy nhiên, chúng tôi có thể hỏi làm thế nào mã có thể được kiểm tra để kiểm tra các lỗi như vậy

Tiếp theo chúng tôi theo dõi bằng cách yêu cầu một thuật toán nhanh hơn

Q. Trong một lượt, bạn có thể chọn một dòng ngẫu nhiên từ tệp văn bản có độ dài không xác định không?

A. Sau một gợi ý, chúng ta sẽ phát triển một thuật toán thông qua một loạt các câu hỏi phụ

Dấu. Hãy nghĩ về điều này một cách đệ quy

phụ Q. Đặt mình vào vị trí của chương trình. Nếu chúng tôi hứa với bạn rằng tệp chứa chính xác một dòng, bạn nên làm gì?

Phụ A. Nếu tệp chứa chính xác một dòng, chỉ cần xuất nó

phụ Q. Rất tiếc, chúng tôi đã nói dối bạn. Tệp có thể chứa chính xác một hoặc hai dòng, nhưng không có số lượng dòng nào khác. Những gì bạn nên làm?

Phụ A. Với xác suất 0. 5, thay thế kết quả mà chúng ta sẽ xuất ra, bằng dòng thứ hai

phụ Q. Xin lỗi, chúng tôi lại nói dối. Tệp có thể chứa chính xác một, hai hoặc ba dòng. Những gì bạn nên làm?

Phụ A. Với xác suất ⅓, thay thế kết quả mà chúng ta sắp xuất ra, bằng dòng thứ ba

Xác suất chọn của mỗi dòng là

• dòng đầu tiên. 1 × ½ × ⅔= ⅓
• dòng thứ 2. ½ × ⅔= ⅓
• dòng thứ 3. ⅓= ⅓

Vì vậy, phân phối xác suất là thống nhất. Chúng ta có thể khái quát hóa điều này thành

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

31

Qua một bên. Tôi [Carl] nhớ lại một người được phỏng vấn đã bắt đầu chứng minh tính đúng đắn của thuật toán này thông qua quy nạp. Tôi có thể nói rằng họ có thể dễ dàng làm điều đó, vì vậy tôi đã ngăn họ lại và tiếp tục. Họ kiếm được tiền thưởng

Thưởng Q. Chúng tôi chưa bao giờ hỏi điều này trong một cuộc phỏng vấn, nhưng bạn có thể viết đệ quy

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

31 không?

tiền thưởng A. Đây là

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

33

Các tham số tùy chọn của Python hoạt động tốt với đệ quy. Đáng buồn thay, Python gặp sự cố nếu bạn lặp lại hơn vài nghìn lần. Mã này sử dụng đệ quy đuôi gói để tránh sự cố đó. Tuy nhiên, ngay cả với điều đó, mã đệ quy này chạy chậm hơn hàng trăm lần so với mã lặp

Qua một bên. Suy nghĩ một cách thực tế, one-pass có quan trọng so với two-pass? . Nếu bạn có thể đợi 20 giây cho một dòng ngẫu nhiên, bạn có thể đợi từ 20 đến 40 giây. Mặt khác, một số dữ liệu — “dữ liệu truyền trực tuyến” — không thể truy cập hai lần, vì vậy

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

31 có giá trị thực tế

Một khái quát đơn giản cho

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

35, mà chúng tôi sẽ không trình bày, là chọn nhiều dòng ngẫu nhiên, không chỉ một. Wikipedia mô tả [ít nhiều]

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

35 và sự khái quát hóa này trong bài viết về Lấy mẫu hồ chứa. Thuật toán đơn giản R

Trong các cuộc phỏng vấn, đây thường là nơi chúng tôi dừng lại với “dòng ngẫu nhiên từ một tệp”. Tuy nhiên, gần đây chúng tôi đã biết về Thùng rỉ sét

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

3. Thùng

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

3 sử dụng các hướng dẫn CPU SIMD để tăng tốc, trong số những thứ khác, đếm số dòng trong một tệp. Điều đó khiến chúng tôi chơi với vấn đề một lần nữa. Điều này dẫn đến một cách tiếp cận mới và một thuật toán cải tiến. Thuật toán mới không sử dụng

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

3. Tuy nhiên, trong trường hợp cụ thể trả về một dòng ngẫu nhiên, nó vượt trội hơn so với Tối ưu tổng quát hơn. Thuật toán L được mô tả trong Wikipedia

Qua một bên. Chúng tôi gọi đây là “thuật toán mới”, nhưng có thể nó đã được phát hiện sớm hơn. Trong mọi trường hợp, chúng tôi hy vọng bạn sẽ thấy thuật toán và sự phát triển của nó thú vị

Như trước đây, chúng tôi sẽ trình bày thuật toán mới thông qua một loạt câu hỏi và gợi ý. Tuy nhiên, chúng tôi chưa bao giờ đặt những câu hỏi này cho người được phỏng vấn

Q. Trong một lượt, bạn có thể chọn một dòng ngẫu nhiên từ một tệp văn bản có độ dài không xác định sao cho trình tạo số ngẫu nhiên được gọi là ít hơn nhiều so với số dòng n không?

A. Chúng ta phải làm rõ “ít hơn nhiều”. Chúng tôi muốn nói rằng số lần gọi đến trình tạo số ngẫu nhiên nhỏ hơn O[n] [xem ký hiệu Big O - Wikipedia]. Nói cách khác, giảm một hoặc một nửa số cuộc gọi là không đủ. Số lượng cuộc gọi ngẫu nhiên được yêu cầu sẽ tăng tỷ lệ thuận với, ví dụ: log[n] hoặc sqrt[n]

Dấu. Đầu tiên sửa đổi

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

31 để in chỉ mục của mọi mục được gán cho

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

41. Gọi đây là “giữ các chỉ số”. Chạy mã trên, giả sử, 1.000.000 mặt hàng

đầu ra

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

1

Điều này nói rằng khi chúng tôi chạy với hạt giống ngẫu nhiên 0, mục đầu tiên [chỉ mục 1] được giữ lại như một kết quả có thể. Sau đó, không có mục nào được giữ cho đến mục thứ 36, sau đó là mục thứ 41. Nếu trình vòng lặp chứa từ 922.409 đến 1.000.000 mục, thì mục thứ 922.409 sẽ là mục cuối cùng được giữ và do đó sẽ được trả về

Các chỉ số giữ dường như tăng theo cấp số nhân. Nếu phỏng đoán đó là đúng, số lượng chỉ số giữ là O[log n], trong đó n là số mục trong iterator

phụ Q. Chúng tôi có thể tạo ngẫu nhiên một chuỗi các chỉ số giữ trực tiếp không?

Phụ A. Đúng. Chúng tôi đã trình bày chi tiết giải pháp của mình trong một bài báo kỹ thuật ngắn, trực tuyến [Meek & Kadie, Lựa chọn ngẫu nhiên truyền trực tuyến bằng cách sử dụng phân phối hình học suy giảm, 2022]. Chúng tôi gọi phân phối của các chỉ số giữ là "Phân phối hình học suy giảm". Chúng tôi chỉ ra rằng nếu

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

42 là số chỉ mục giữ nguyên, thì chúng tôi có thể tạo số tiếp theo với

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

trong đó

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

43 tạo ra một giá trị dấu phẩy động thống nhất giữa 0. 0 [bao gồm] và 1. 0 [độc quyền]. Thưởng.

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

44 xử lý trường hợp rất, rất khó xảy ra khi tạo ra 0. 0 ngẫu nhiên. Ngoài ra, hãy nhớ lại quy ước của chúng tôi rằng “index1” là một chỉ mục bắt đầu được tính từ 1 thay vì 0

Bây giờ chúng ta có thể sử dụng cái nhìn sâu sắc này để tạo ra

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

45

Chúng ta có thể tin tưởng vào mã bằng cách sử dụng nó để chọn một số từ 0 [bao gồm] đến 100 [không bao gồm], 100.000 lần

Các ô đầu ra phải trông thống nhất. Họ làm gì

Thuật toán này khác với Tối ưu. Thuật toán L [do Wikipedia khuyến nghị] theo hai cách quan trọng

• r = rng.random[]
  index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

  45 chỉ hoạt động để chọn một mục ngẫu nhiên, trong khi Thuật toán L có thể chọn bất kỳ số lượng mục ngẫu nhiên cụ thể nào
• Khi chỉ muốn một mục ngẫu nhiên,

  r = rng.random[]
  index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

  45 cần một số ngẫu nhiên cho mỗi chỉ mục giữ, trong khi Thuật toán L cần hai

Do đó, đối với trường hợp đặc biệt mà chúng tôi chỉ muốn một mục ngẫu nhiên,

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

45 sử dụng một nửa số lần rút ngẫu nhiên so với Thuật toán L

Bản tóm tắt

Chúng tôi đã thấy bốn cách để chọn ngẫu nhiên một mục từ một chuỗi có độ dài không xác định. Trong ngữ cảnh của tệp văn bản, giải pháp đầu tiên yêu cầu tệp vừa với bộ nhớ. Giải pháp tiếp theo sử dụng ít bộ nhớ hơn nhưng yêu cầu hai lần chuyển qua tệp. Sau đó, chúng tôi đã sử dụng phép tính xác suất để giảm điều này xuống còn một lượt. Giải pháp một lượt đó yêu cầu một số ngẫu nhiên trên mỗi dòng. Giải pháp cuối cùng yêu cầu số ngẫu nhiên ít hơn nhiều so với dòng. Nó cũng sử dụng một nửa số ngẫu nhiên như thuật toán “tối ưu” [tổng quát hơn]

Không mã nào của chúng tôi sử dụng các phương pháp cấp hệ thống như

r = rng.random[]
index1 = index1 + max[ceil[r * index1 / [1.0 — r]],1]

3 để tăng tốc độ truyền tuyến tính qua một tệp. Thêm tối ưu hóa cấp hệ thống sẽ là một tiện ích mở rộng thú vị

Vui lòng theo dõi Carl trên Medium. Tôi viết về lập trình khoa học bằng Rust và Python, học máy và thống kê. Tôi có xu hướng viết khoảng một bài báo mỗi tháng