nhanh so sánh chuỗi trong C

Question

Tôi hiện có loại vòng lặp

while(1) 
{ 
    generate_string(&buffer); 

    for(int i = 0; i < filelines; i++) 
    { 
     if(strcmp(buffer,line[i]) == 0) 
     { 
      /* do something */ 
     } 
    } 
} 

Tôi có một tập tin với một vài triệu chuỗi (mà hy vọng sẽ được cắt giảm một nửa sometime sớm), số lượng của tất cả các chuỗi là được lưu trữ trong filelines

dòng [i] về cơ bản là nơi bản thân chuỗi được lưu trữ.

Hiện tại, do so sánh các triệu chuỗi này, hàm generate_string (& bộ đệm); được thực hiện khoảng 42 lần mỗi giây. Có cách nào nhanh hơn để so sánh chuỗi trong C?

Answer 1

strcmp thường được tối ưu hóa bởi tất cả các nhà cung cấp. Tuy nhiên, nếu bạn không hài lòng với điều này bạn có thể thử:

• Lookup Burst Tries
• Sử dụng một cây hậu tố để so sánh chuỗi nhanh - xem this bài viết
• Tùy thuộc vào kích thước của chuỗi trong ứng dụng của bạn bạn có thể viết một bộ so sánh chuỗi tùy chỉnh. Ví dụ: GNU libc được sử dụng để có tối ưu hóa này cho các chuỗi nhỏ nơi chúng thử nghiệm chuỗi nhỏ hơn năm byte dưới dạng số nguyên. MS cl cũng có một số tối ưu hóa cho các chuỗi nhỏ (tìm kiếm nó).

Nhưng quan trọng hơn là đảm bảo strcmp bạn thực nút cổ chai.

Answer 2

Tôi không biết rằng có một cách nhanh hơn gọi strcmp để làm so sánh chuỗi, nhưng bạn có lẽ thể tránh gọi strcmp rất nhiều. Sử dụng bảng băm để lưu trữ các chuỗi của bạn và sau đó bạn có thể kiểm tra xem chuỗi trong buffer có nằm trong bảng băm hay không. Nếu chỉ mục của lần truy cập là quan trọng khi bạn "làm điều gì đó", bảng có thể ánh xạ chuỗi để lập chỉ mục.

Answer 3

Bạn có thể thử thứ gì đó 'rẻ' giống như sàng lọc dựa trên char đầu tiên. Nếu các ký tự đầu tiên không khớp, các chuỗi không thể bằng nhau. Nếu chúng khớp nhau, sau đó gọi strcmp để so sánh toàn bộ chuỗi. Bạn có thể muốn xem xét một thuật toán tốt hơn nếu đó là thích hợp cho tình hình của bạn; các ví dụ sẽ phân loại tệp/dòng và thực hiện tìm kiếm nhị phân, sử dụng bảng băm hoặc các kỹ thuật bảng chuỗi tương tự.

Answer 4

bạn có thể nhận được bằng so sánh nhị phân trong trường hợp này bởi vì chương trình của bạn không thực sự là sắp xếp, nhưng so sánh bình đẳng.

bạn cũng có thể cải thiện tốc độ so sánh tại đây bằng cách xác định độ dài trước (miễn là tất nhiên chúng thay đổi đủ). khi độ dài không khớp ở đây, do something sẽ không xảy ra.

Tất nhiên, băm ở đây sẽ là một xem xét khác tùy thuộc vào số lần bạn đọc giá trị được băm.

Answer 5

Nếu tôi nhận được câu hỏi của bạn một cách chính xác, bạn cần phải kiểm tra xem một chuỗi có nằm trên tất cả các dòng được đọc cho đến thời điểm này hay không. Tôi sẽ đề xuất sử dụng TRIE hoặc thậm chí tốt hơn là Patricia tree từ các dòng tệp.Bằng cách này thay vì đi trên tất cả các dòng bạn có thể kiểm tra tuyến tính nếu chuỗi của bạn là hiện tại (và với một nỗ lực nhiều hơn nữa - ở đâu).

Answer 6

Bạn đã biên dịch với tối ưu hóa, đúng không?

Nếu bạn có cấu trúc dữ liệu Trie hoặc hashtable nằm xung quanh địa điểm, sẵn sàng sử dụng, thì bạn nên làm như vậy.

Không làm điều đó, một thay đổi khá dễ dàng có thể tăng tốc mọi thứ là sắp xếp mảng của bạn line một lần, trước khi bạn bắt đầu tạo chuỗi để tìm kiếm. Sau đó tìm kiếm nhị phân cho buffer trong mảng được sắp xếp. Thật dễ dàng vì hai chức năng bạn cần là tiêu chuẩn - qsort và bsearch.

Tìm kiếm nhị phân thành mảng được sắp xếp chỉ cần thực hiện về các lần so sánh chuỗi (filelines), thay vì về filelines. Vì vậy, trong trường hợp của bạn, đó là so sánh chuỗi 20 cái gì đó cho mỗi cuộc gọi đến generate_string thay vì một vài triệu. Từ những con số bạn đã đưa ra, tôi nghĩ rằng bạn có thể mong đợi nó đi nhanh hơn 20-25 lần, mặc dù tôi không hứa gì cả.

Answer 7

Tôi có thể đảm bảo với bạn, chức năng strcmp là TUYỆT ĐỐI KHÔNG phải là nút cổ chai. Thông thường, strcmp được tối ưu hóa tốt và có thể so sánh 32 hoặc 64 bit đối với các chuỗi dài hơn 4/8 byte tùy thuộc vào kiến ​​trúc. Cả newlib và GNU libc đều làm điều này. Nhưng ngay cả khi bạn đã xem xét từng byte trong cả hai chuỗi 20 lần, nó không quan trọng nhiều như algo & các lựa chọn cấu trúc dữ liệu được tạo ở đây.

Cổ chai thực sự là thuật toán tìm kiếm O (N). Một pass O (N log N) duy nhất tại file có thể được sử dụng ở cấu trúc dữ liệu thích hợp (cho dù đó là BST bình thường, một trie hay chỉ là một mảng được sắp xếp đơn giản) để thực hiện tra cứu O (log N).

Hãy theo tôi ở đây - rất nhiều bài toán sau. Nhưng tôi nghĩ đây là cơ hội tốt để minh họa tại sao lựa chọn thuật toán & cấu trúc dữ liệu đôi khi FAR quan trọng hơn so với phương pháp so sánh chuỗi. Steve chạm vào điều này, nhưng tôi muốn giải thích nó sâu hơn một chút.

Với N = 1e6, nhật ký (1e6, 2) = 19.9, do đó, làm tròn tối đa 20 so sánh trên cấu trúc dữ liệu lý tưởng.

Hiện tại bạn đang thực hiện tìm kiếm trường hợp xấu nhất của các hoạt động O (N) hoặc 1e6.

Vì vậy, giả sử bạn chỉ xây dựng một cây đỏ đen với thời gian chèn O (log N) và bạn chèn N mục, đó là thời gian O (N log N) để tạo cây. Vì vậy, đó là hoạt động 1e6 x 20 hoặc 20e6 cần thiết để xây dựng cây của bạn.

Trong phương pháp hiện tại của bạn, xây dựng cấu trúc dữ liệu là hoạt động O (N) hoặc 1e6, nhưng thời gian tìm kiếm trường hợp xấu nhất của bạn là O (N). Vì vậy, vào thời điểm bạn đọc các tập tin và làm chỉ 20 hoạt động tìm kiếm, bạn đang lên đến một trường hợp lý thuyết tồi tệ nhất của 21.000.000 hoạt động. Bằng cách so sánh, trường hợp xấu nhất của bạn với một cây đỏ đen và 20 tìm kiếm là 20.000.400 hoạt động, hoặc 999.600 hoạt động TỐT hơn so với tìm kiếm O (N) trên một mảng chưa được sắp xếp. Vì vậy, tại 20 tìm kiếm, bạn đang ở điểm đầu tiên mà một cấu trúc dữ liệu phức tạp hơn thực sự trả hết. Nhưng hãy xem điều gì xảy ra ở 1000 tìm kiếm:

Mảng không phân loại = khởi tạo + 1000 x thời gian tìm kiếm = O (N) + 1000 * O (N) = 1.000.000 + 2.000.000.000 = 2,001.000.000 hoạt động.

Đỏ đen = khởi tạo + 1000 x thời gian tìm kiếm = O (N log N) + 1000 * O (nhật ký N) = 20.000.000 + 20.000 = 20,020.000 hoạt động.

2,001.000.000/20,020,000 ~ = 100x như nhiều thao tác cho tìm kiếm O (N).

Tại 1e6 tìm kiếm, đó là (1e6 + 1e6 * 1e6)/(20e6 + 1e6 * 20) = 25.000x là nhiều thao tác.

Giả sử máy tính của bạn có thể xử lý hoạt động 40e6 'cần thiết để thực hiện tìm kiếm nhật ký N trong 1 phút. Sẽ mất 25.000 phút hoặc 17 NGÀY để thực hiện cùng một công việc với thuật toán hiện tại của bạn. Hoặc một cách khác để xem xét là thuật toán tìm kiếm O (N) chỉ có thể xử lý 39 tìm kiếm trong thời gian thuật toán O (log N) có thể thực hiện 1.000.000. Và càng có nhiều tìm kiếm bạn thực hiện thì càng tệ hơn.

Xem câu trả lời từ Steve và dirkgently cho một số lựa chọn tốt hơn về cấu trúc dữ liệu & thuật toán. Thận trọng duy nhất của tôi là qsort() được đề xuất bởi Steve có thể có độ phức tạp xấu nhất của O (N * N), xa hơn rất nhiều so với O (N log N) mà bạn nhận được với heapsort hoặc cấu trúc giống cây.

Answer 8

Optimization of Computer Programs in C

Bạn có thể tiết kiệm một ít thời gian bằng cách kiểm tra các ký tự đầu tiên của chuỗi trong câu hỏi trước khi thực hiện cuộc gọi. Rõ ràng, nếu các ký tự đầu tiên khác nhau, không có lý do gì để gọi strcmp để kiểm tra phần còn lại. Do sự phân phối không đồng nhất của các chữ cái trong các ngôn ngữ tự nhiên, khoản tiền thưởng không phải là 26: 1 nhưng giống như là 15: 1 cho dữ liệu chữ hoa.

#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \ 
    (int) ((unsigned char) *(a) - \ 
     (unsigned char) *(b)) : \ 
    strcmp((a), (b))) 

Nếu Các từ điển của từ bạn đang sử dụng được xác định rõ ràng (có nghĩa là bạn không nhớ giá trị trả về hình thức strcmp nhưng 0 == bình đẳng), ví dụ, một tập hợp các đối số dòng lệnh bắt đầu với cùng một tiền tố, ví dụ: tcp-accept, tcp-reject so với bạn có thể viết lại macro và thực hiện số học con trỏ để so sánh không phải số thứ nhất mà là số thứ N, trong trường hợp này là số thứ 4, ví dụ:

#define QUICKIE_STRCMP(a, b, offset) \ 
      (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))