Thử nghiệm đơn vị một thuật toán phức tạp

Question

Bạn sẽ viết các xét nghiệm để thử nghiệm một giải pháp cho một số thuật toán khá phức tạp như the N Queens problem như thế nào? Những gì tôi có nghĩa là những gì nên cách tiếp cận phù hợp với thử nghiệm một thuật toán mà

1. có nhiều giải pháp (bạn không biết/không quan tâm có bao nhiêu trong số họ tồn tại),

2. bạn có thể chỉ có một tập con nhỏ của tất cả các giải pháp có thể và

3. xác minh rằng giải pháp là chính xác có thể hơi phức tạp một chút (có thể so sánh về độ phức tạp với chính thuật toán).

Tôi biết rằng những điều kiện này không có trong chính vấn đề N-Queens, nhưng tôi đã đề cập đến nó để cung cấp một ví dụ.

Answer 1

Khi thử nghiệm các thuật toán phức tạp, bạn dựa vào 'dữ liệu' cần được xác minh. Giả sử rằng bạn đã có một giải pháp (dữ liệu) ở một số dạng vấn đề. Bạn chỉ cần lấy dữ liệu và để thuật toán của bạn chạy qua và xem các câu trả lời có khớp không. Lấy ví dụ về giải một câu đố n bằng cách sử dụng thuật toán, nó không xác định, nhưng bạn có một dữ liệu để xác minh giải pháp.

Answer 2

Trong ví dụ của bạn, tôi nghĩ bạn đang nói bạn muốn đơn vị kiểm tra thuật toán xác minh giải pháp được đề xuất.

Bạn muốn để trang trải các trường hợp sau đây:

• kiểm tra con đường hạnh phúc để xác minh rằng các thuật toán chấp nhận một loạt các giải pháp đúng
• kiểm tra con đường hạnh phúc để xác minh rằng các thuật toán từ chối một loạt các sai giải pháp
• kiểm tra đường Sad để đảm bảo rằng các thuật toán xử lý một cách chính xác không ứng cử viên (ví dụ như một "giải pháp" với 7 nữ hoàng thay vì 8 vv)

Ở đây, "một loạt" có nghĩa là bạn muốn các giải pháp để trang trải không gian của các khả năng. Nhưng điều đó có nghĩa là bao quát không gian đó là vấn đề cụ thể. Tôi không quen thuộc với vấn đề N-queens để biết sự đa dạng tồn tại trên các giải pháp chính xác, nhưng thông tin đó sẽ hữu ích là tôi phải thực hiện các bài kiểm tra. Về các giải pháp không chính xác, bạn muốn một số liên quan đến cùng một thứ hạng, cùng một tệp, cùng một đường chéo và một kết hợp. Một số liên quan đến tiếp xúc dọc theo cạnh của hội đồng quản trị và một số liên quan đến tiếp xúc ra khỏi cạnh. Ngoài ra, nếu bạn có thông tin về phân phối giải pháp, bạn có thể ưu tiên những giải pháp có nhiều khả năng hơn, mặc dù cuối cùng bạn sẽ muốn bao gồm ngay cả những giải pháp ít có khả năng hơn vì những giải pháp đó có xu hướng phá vỡ mọi thứ trong cuộc sống thực. Ngoài ra nếu thuật toán phức tạp thì nó có ý nghĩa để phân hủy nó thành các phần và kiểm tra tính chính xác của các phần đó theo cùng một cách (phân biệt hạnh phúc với đường dẫn buồn và kiểm tra đầu vào của cả hai loại).

Answer 3

Thuật toán thực sự là những điều đơn giản nhất để kiểm tra đơn vị vì bạn không có phụ thuộc bên ngoài. Cách tiếp cận tốt nhất là sử dụng thử nghiệm theo hướng phát triển: tìm ra yêu cầu nhỏ tiếp theo bạn muốn thuật toán thực hiện, tạo kiểm tra cho nó, và sau đó viết mã để đáp ứng kiểm tra đó (và không có mã nào nhiều hơn cần thiết, ngay cả khi điều này có nghĩa là hardcoding kết quả).Sau đó, bạn tiếp tục, tái cấu trúc mã nguồn khi cần thiết để làm cho nó tổng quát hơn và chấp nhận nhiều trường hợp sử dụng hơn. Bởi thời gian tất cả các trường hợp sử dụng của bạn được bảo hiểm, bạn nên có một thực hiện vững chắc của thuật toán.

Answer 4

Bài kiểm tra đơn vị nên xác minh đầu ra của thuật toán cho nhiều đầu vào và vì nhiệm vụ này cũng phức tạp, nó phải được viết bởi một người khác (và hy vọng rằng nếu có lỗi trong mã anh ta không 't làm cùng một sai lầm)

Answer 5

Nếu bạn biết loại thuật toán nào bạn sẽ cần, thì một tùy chọn là triển khai một số phần của thuật toán đó bằng TDD. Vì vậy, khi những phần đó đã được triển khai, việc xây dựng thuật toán đầy đủ sẽ không đáng kể. Dưới đây là một ví dụ của một vấn đề (diagram of nine places) mà tôi không biết giải pháp, vì vậy viết một bài kiểm tra cho nó sẽ là khó khăn, nếu không phải là không thể, hoặc không thực tế từ quan điểm của TDD (nó sẽ có yêu cầu một bước nhảy vọt quá lớn). Tôi nhận ra nó khá giống với vấn đề Nine Queens, vì vậy tôi quyết định sử dụng một thuật toán tương tự như tôi đã sử dụng để giải quyết Nine Queens. Tôi đã sử dụng DiagramTest để kiểm tra ổ đĩa Diagram, sau đó đặt mọi thứ lại với nhau trong DiagramOfNinePlaces chỉ là một tá dòng mã. Sau khi chạy mã, tôi đã kiểm tra kết quả cuối cùng bằng tay và nó thực sự là một giải pháp cho vấn đề.

Answer 6

Bạn chỉ có thể kiểm tra hành vi mà bạn biết bạn có thể mong đợi.

Bạn có biết rằng một giải pháp tồn tại đối với một số dữ liệu thử nghiệm không? Ví dụ. bạn có thể tìm ra bằng tay rằng chắc chắn có thể đặt sáu nữ hoàng trên một bảng 8x8, hoặc bạn có thể đọc trong một cuốn sách có tồn tại ít nhất một giải pháp để đưa tám nữ hoàng trên bảng 8x8. Sau đó, bạn có thể kiểm tra xem chương trình của bạn có trả về ít nhất một giải pháp (có lẽ bạn không kiểm tra xem đó có phải là giải pháp hợp lệ) hay không.

Bạn có biết rằng không có giải pháp nào tồn tại đối với một số dữ liệu thử nghiệm khác không? Ví dụ. bạn có thể thuyết phục bản thân khá dễ dàng là không thể đặt ba nữ hoàng trên một 3x3 hoặc chín nữ hoàng trên một 8x8. Sau đó kiểm tra xem chương trình của bạn không trả về giải pháp hay ném ngoại lệ mong muốn.

Bạn có muốn kiểm tra xem giải pháp đã cho có hợp lệ không? Sau đó, bạn phải viết mã kiểm tra tính hợp lệ của nó, và bạn phải chạy mã này, cho dù nó có phức tạp thế nào đi chăng nữa. Nếu nó đủ phức tạp, hãy viết các bài kiểm tra cho nó. Nếu bạn may mắn, chương trình của bạn có thể được tái cấu trúc để bạn có thể sử dụng lại một số phần nhỏ hơn để kiểm tra giải pháp của bạn. quá).

Cuối cùng, khi bạn tìm thấy lỗi, bạn có ví dụ về nơi chương trình trả lại kết quả không mong muốn. Viết một bài kiểm tra khẳng định rằng nó không trả lại kết quả đó vào lần sau.

Bạn không thể có 100% phạm vi kiểm tra cho bất kỳ chương trình nào. Tất cả những gì bạn có thể làm là kiểm tra các trường hợp bạn biết và có thời gian để viết.

Answer 7

Có rất nhiều vấn đề khi tạo giải pháp khó hơn nhiều so với việc kiểm tra xem có giải pháp nào là chính xác hay không.

Trong trường hợp giống như vấn đề N-queens, bạn chỉ cần kiểm tra xem họ chỉ là một nữ hoàng trên mỗi hàng và đường chéo của bảng và có N nữ hoàng trên bảng trong giải pháp, biết rằng giải pháp là hợp lệ.

2:

Nếu vấn đề được biết là có các thuật toán khác mà làm việc cho một số trùng thiết lập đầu vào sau đó cố gắng mà thuật toán khác để kiểm tra thuật toán ban đầu của bạn cho bộ đầu vào cả hai đều làm việc trên.Ví dụ một tìm kiếm brute-force có thể làm việc, hoặc có thể được tính toán trước và lưu cho một phạm vi nhỏ hơn của đầu vào và được sử dụng như là các xét nghiệm. Trong một số vấn đề toán học, các câu trả lời cho một phạm vi đầu vào hạn chế (chẳng hạn như các ô vuông, hoặc các quyền hạn của 2, vv), được xác minh dễ dàng hơn. Bạn nên ít nhất là thử nghiệm cho các trường hợp thse.

Answer 8

Tôi nghĩ đây là một câu hỏi rất hay và không có viên đạn bạc. Tôi sẽ chỉ cho bạn biết về kinh nghiệm của tôi.

Tôi đã viết một thuật toán để tìm tập hợp điểm gần nhất giữa hai trụ trong không gian 3D. Đây là một vấn đề rất phức tạp và không gian đầu vào là rất lớn.

Để kiểm tra mã của mình, lúc đầu tôi vừa tạo một số trường hợp chuẩn, được căn chỉnh theo trục, sao cho kết quả "đúng" là hiển nhiên. Nhưng điều đó quá yếu.

Sau đó, tôi đã có thể "tăng cường" các trường hợp kinh điển bằng cách áp dụng các phép biến đổi ngẫu nhiên. Điều này đã giúp một chút. Sau đó tôi đã nghĩ về việc viết một thuật toán trùng lặp khác và triển khai thực hiện, nhưng điều đó rất khó, và không có cách nào để biết cả hai thuật toán có thể hiển thị cùng một lỗi hay không. Tuy nhiên, đối với một vấn đề khác, điều này có thể khả thi, chẳng hạn như với brute-force: không hiệu quả, nhưng rất đơn giản để hiểu và xác minh.

Sau đó, tôi nghĩ về các thuộc tính của bộ giải pháp. Ví dụ vector tách biệt phải là một minima cục bộ, vì vậy tôi sẽ có thể "nhìn xung quanh" từng điểm cuối của giải pháp (đối với một epsilon nhỏ) và xác định xem giải pháp có phải là một minima cục bộ hay không.

Sau đó, tôi bắt đầu nghĩ về các thuộc tính tô pô của hàm ánh xạ đầu vào đến đầu ra. Trong trường hợp này tôi biết rằng khoảng cách tách biệt sẽ thay đổi một cách trơn tru. Vì vậy, tôi đã chọn một đầu vào ngẫu nhiên và đồng bằng nhỏ, và sau đó so sánh đầu ra có và không có đồng bằng được áp dụng. Nếu thuật toán là chính xác, thì sự khác biệt về đầu ra phải nhỏ.

Bằng cách kết hợp tất cả các kỹ thuật này, tôi đã có thể nhận được sự tự tin cao trong mã.