cần trợ giúp thiết kế cho thuật toán tìm kiếm theo cách hiệu quả hơn

Question

Tôi gặp sự cố liên quan đến khu vực sinh học. Ngay bây giờ tôi có 4 tệp RẤT LỚN (mỗi với 0,1 tỷ dòng), nhưng cấu trúc khá đơn giản, mỗi dòng của các tệp này chỉ có 2 trường, cả hai đều là viết tắt của một loại gen.

Mục tiêu của tôi là: thiết kế một thuật toán hiệu quả có thể đạt được những điều sau đây: Tìm một vòng tròn trong nội dung của 4 tệp này. Vòng tròn được định nghĩa là:

field #1 in a line in file 1 == field #1 in a line in file 2 and 
field #2 in a line in file 2 == field #1 in a line in file 3 and 
field #2 in a line in file 3 == field #1 in a line in file 4 and 
field #2 in a line in file 4 == field #2 in a line in file 1 

Tôi không thể nghĩ ra một cách đàng hoàng để giải quyết việc này, vì vậy tôi chỉ viết một vòng lặp brute-force-ngu ngốc-4-lớp-lồng nhau cho bây giờ. Tôi đang suy nghĩ về việc sắp xếp chúng theo thứ tự bảng chữ cái, ngay cả khi điều đó có thể giúp ích một chút, nhưng sau đó nó cũng hiển nhiên rằng bộ nhớ máy tính sẽ không cho phép tôi tải mọi thứ cùng một lúc. Ai có thể cho tôi biết một cách tốt để giải quyết vấn đề này một cách hiệu quả về thời gian và không gian? Cảm ơn!!

Answer 1

Trước hết, tôi lưu ý rằng bạn có thể sắp xếp một tập tin mà không cần giữ nó bộ nhớ cùng một lúc, và rằng hầu hết các hệ điều hành có một số chương trình thực hiện điều này, thường được gọi là "sắp xếp". Thông thường bạn có thể làm cho nó để sắp xếp trên một lĩnh vực trong một tập tin, nhưng nếu không bạn có thể viết lại mỗi dòng để có được nó để sắp xếp theo cách bạn muốn.

Với điều này, bạn có thể kết nối hai tệp bằng cách sắp xếp chúng sao cho tệp đầu tiên được sắp xếp trên trường # 1 và cột thứ hai trên trường # 2. Sau đó bạn có thể tạo một bản ghi cho mỗi trận đấu, kết hợp tất cả các trường và chỉ giữ trong bộ nhớ một đoạn từ mỗi tệp nơi tất cả các trường bạn đã sắp xếp có cùng giá trị. Điều này sẽ cho phép bạn kết nối kết quả với một tệp khác - bốn kết nối như vậy sẽ giải quyết được sự cố của bạn.

Tùy thuộc vào dữ liệu của bạn, thời gian cần để giải quyết vấn đề của bạn có thể phụ thuộc vào thứ tự bạn thực hiện kết nối. Một cách khá ngây thơ để sử dụng điều này là, ở mỗi giai đoạn, lấy một mẫu ngẫu nhiên nhỏ từ mỗi tệp và sử dụng để xem có bao nhiêu kết quả sẽ theo sau mỗi kết nối có thể và chọn kết nối tạo ra kết quả ít nhất. Một cách để lấy một mẫu ngẫu nhiên của N mục từ một tệp lớn là lấy N dòng đầu tiên trong tệp và sau đó, khi bạn đã đọc trong m dòng cho đến nay, hãy đọc dòng tiếp theo, và sau đó với xác suất N/(m + 1) trao đổi một trong N dòng được giữ cho nó, bỏ đi. Tiếp tục cho đến khi bạn đã đọc toàn bộ tệp.

Answer 2

Dưới đây là một thuật toán:

• Chọn một cấu trúc tra cứu thích hợp: Nếu trường # 1 là một số nguyên, sử dụng bit lĩnh vực hoặc một cuốn từ điển (hoặc một bộ) nếu nó là một chuỗi; Sử dụng cấu trúc tra cứu cho mỗi tệp, ví dụ 4 trong trường hợp của bạn
• Giai đoạn khởi chạy: Đối với mỗi tệp: phân tích cú pháp dòng tệp và đặt bit theo bit thích hợp hoặc thêm trường vào từ điển trong tra cứu tương ứng cấu trúc cho tệp.
• Sau khi khởi tạo cấu trúc tra cứu ở trên, hãy kiểm tra điều kiện trong câu hỏi của bạn.

Độ phức tạp của điều này phụ thuộc vào việc triển khai cấu trúc tra cứu. Đối với các trường bit, nó sẽ là O (1) và cho tập hợp hoặc từ điển, nó sẽ là O (lg (n)), vì chúng thường được thực hiện như một cây tìm kiếm cân bằng. Độ phức tạp hoàn toàn sẽ là O (n) hoặc O (n lg (n)); giải pháp bạn trong câu hỏi có độ phức tạp O (n^4)

Bạn có thể lấy mã và giải pháp cho các lĩnh vực bit từ here

HTH

Answer 3

Dưới đây là một cách tiếp cận:

Chúng tôi sẽ sử dụng các ký hiệu FXY trong đó x = số lĩnh vực, y = file_no

Sắp xếp mỗi 4 tập tin trên các lĩnh vực đầu tiên.

Đối với mỗi trường F11, tìm kết quả phù hợp trong tệp 2. Đây sẽ là tuyến tính. Lưu các kết quả phù hợp này với tất cả bốn trường vào một tệp mới. Bây giờ, sử dụng tệp này và sử dụng trường tương ứng trong tệp này và nhận tất cả các kết quả phù hợp từ tệp3. Tiếp tục cho file4 và trở lại file1.

Bằng cách này, khi bạn tiến tới từng tệp mới, bạn đang xử lý số lượng dòng ít hơn. Và kể từ khi bạn đã sắp xếp các tập tin, tìm kiếm trong tuyến tính và có thể được thực hiện bằng cách đọc từ đĩa.

Đây là độ phức tạp trong O (n log n) để phân loại và O (m log n) để tra cứu, giả sử m < < n.

Answer 4

Sẽ dễ dàng hơn một chút để giải thích nếu Tệp 1 của bạn là một cách khác (vì vậy mỗi phần tử thứ hai trỏ đến phần tử đầu tiên trong tệp tiếp theo).

1. Bắt đầu với File 1, sao chép nó vào một tập tin mới viết mỗi cặp A, B như B, A, 'REV'

2. Nối các nội dung của file 2 để nó viết mỗi A, B cặp như A, B, 'FWD'

3. Sắp xếp các tập tin

4. Process tập tin trong khối với giá trị ban đầu cùng

   • Trong nhóm đoạn đường vào REV và FWD của
   • Lấy sản phẩm Descartes của vòng quay và fwds (vòng lặp lồng nhau)
   • Viết phù hợp với ngược (Fwd) concat (rev) trừ token
   lặp đi lặp lại
   • ví dụ B, A, 'REV' và B, C, 'FWD' -> C, B, A, 'REV'

5. Nối tệp tiếp theo vào tệp đầu ra mới này (thêm 'FWD' vào mỗi dòng)

6. Lặp lại từ bước 3

Thực chất bạn đang xây dựng một chuỗi theo thứ tự ngược và sử dụng một thuật toán sắp xếp tập tin dựa trên để đưa chuỗi lại với nhau có thể được kết hợp.

Tất nhiên sẽ dễ dàng hơn khi chỉ đọc những tệp này vào cơ sở dữ liệu và để cho nó hoạt động ...