Cách nhanh nhất để tìm kiếm thông qua các chuỗi trong Objective-C là gì?

Question

Tôi đang triển khai một loại tự động hoàn tất cho ứng dụng iOS. Dữ liệu tôi đang sử dụng cho các giá trị tự động hoàn thành là tệp văn bản được phân cách bằng dấu phẩy với khoảng 100.000 chuỗi. Đây là những gì tôi đang làm bây giờ:

1. Đọc tệp văn bản và tạo NSArray với 100.000 NSString.
2. Khi người dùng, làm [array containsObject:text]

Chắc chắn có một/cách tốt hơn nhanh hơn để làm tra cứu này. Có suy nghĩ gì không?

Answer 1

Tuyệt đối, có! Nó không phải là "trong mục tiêu-C" mặc dù: rất có thể, bạn sẽ cần phải mã nó cho mình.

Ý tưởng là chuyển đổi danh sách chuỗi thành suffix tree, cấu trúc dữ liệu cho phép bạn tìm kiếm theo tiền tố rất nhanh chóng. Tìm kiếm các hoàn thành có thể có trong một cây hậu tố rất nhanh, nhưng bản thân cấu trúc không dễ xây dựng. Một tìm kiếm nhanh trên internet cho thấy rằng không có triển khai sẵn có trong Mục tiêu C, nhưng bạn có thể port an implementationin another language, use a C implementation hoặc thậm chí tự viết nếu bạn không bị ép thời gian.

Có lẽ cách tiếp cận dễ dàng hơn là sắp xếp các chuỗi theo thứ tự bảng chữ cái và chạy tìm kiếm nhị phân trên tiền tố đã được nhập cho đến thời điểm này. Mặc dù không hiệu quả như một cây hậu tố, cách tiếp cận mảng được sắp xếp sẽ được chấp nhận cho các chuỗi 100K, bởi vì bạn đến đúng vị trí trong dưới mười bảy lần kiểm tra.

Answer 2

Cách đơn giản nhất có thể là tìm kiếm nhị phân. Xem -[NSArray indexOfObject:inSortedRange:options:usingComparator:].

Đặc biệt, tôi muốn thử một cái gì đó như thế này:

• Pre-sort mảng mà bạn lưu vào tập tin
• Khi bạn tải các mảng, có thể @selector(compare:) (nếu bạn đang lo lắng về nó vô tình bị phân loại hoặc thứ tự sắp xếp Unicode thay đổi đối với một số trường hợp cạnh). Điều này sẽ là khoảng O (n) giả định mảng được sắp xếp chủ yếu rồi.
• Để tìm kết quả phù hợp đầu tiên, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
• Đi xuống mảng cho đến khi các mục nhập không còn chứa searchString làm tiền tố. Bạn có thể muốn làm trường hợp so sánh/dấu phụ/chiều rộng-insensitive để xác định xem nó là một tiền tố (NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch)

Điều này có thể không phải là "chính xác" xử lý tất cả miền địa phương (Thổ Nhĩ Kỳ nói riêng), nhưng sẽ không thay thế compare: bằng localizedCompare: và cũng sẽ không gấp ngây chuỗi. (Đó là chỉ 9 dòng dài, nhưng mất khoảng một ngày làm việc để có được quyền và có khoảng 40 dòng mã và 200 dòng thử nghiệm, vì vậy tôi có lẽ không nên chia sẻ nó ở đây.)