Cấu trúc dữ liệu Skiplist, từng được xem là một công cụ hẹp trong khoa học máy tính, đang có một ứng dụng đột phá trong lĩnh vực kiểm thử phần mềm. Công ty khởi nghiệp Antithesis đã sử dụng một phiên bản mở rộng của Skiplist để giải quyết một vấn đề nan giải trong quá trình chạy hàng triệu lượt kiểm thử phần mềm tự động.

Giải pháp cho dữ liệu khổng lồ

Antithesis chạy phần mềm của khách hàng hàng triệu lần với các lựa chọn ngẫu nhiên khác nhau để tìm lỗi, tạo ra một "cây thời gian" phân nhánh khổng lồ. Lượng dữ liệu sinh ra quá lớn, khiến việc truy vấn và phân tích trở nên cực kỳ tốn kém. Bằng cách áp dụng một phiên bản tổng quát của Skiplist, họ có thể thực hiện các thao tác như truy ngược lịch sử sự kiện một cách hiệu quả, giảm đáng kể độ phức tạp tính toán từ O(n) xuống còn O(log n).

Điều này có ý nghĩa thiết thực: nó cho phép các công ty phát triển phần mềm tìm và sửa lỗi nhanh hơn, rẻ hơn, từ đó tạo ra những sản phẩm ổn định và an toàn hơn cho người dùng cuối. Đây là một minh chứng cho thấy những công nghệ cơ bản vẫn có thể tái sinh và trở thành chìa khóa cho các bài toán công nghệ hiện đại.