2013-01-14 33 views
7

Tôi có một ứng dụng cần lấy vài triệu char * làm tham số đầu vào (thường là chuỗi nhỏ hơn 512 ký tự (trong unicode)), và chuyển đổi và lưu trữ chúng dưới dạng. chuỗi mạng.Tối ưu hóa vài triệu từ * thành chuỗi chuyển đổi

Nó hóa ra là một nút cổ chai thực sự trong việc thực hiện ứng dụng của tôi. Tôi tự hỏi nếu có một số mẫu thiết kế hoặc ý tưởng để làm cho nó hiệu quả hơn.

Có một phần quan trọng khiến tôi cảm thấy như nó có thể được cải thiện: Có rất nhiều bản sao. Nói 1 triệu đối tượng đang đến, có thể chỉ có 50 mẫu char * độc đáo.

Đối với hồ sơ, đây là thuật toán Tôi đang sử dụng để chuyển đổi char * để string (thuật toán này là trong C++, nhưng phần còn lại của dự án là trong C#)

String ^StringTools::MbCharToStr (const char *Source) 
{ 
    String ^str; 

    if((Source == NULL) || (Source[0] == '\0')) 
    { 
     str = gcnew String(""); 
    } 
    else 
    { 
     // Find the number of UTF-16 characters needed to hold the 
     // converted UTF-8 string, and allocate a buffer for them. 
     const size_t max_strsize = 2048; 

     int wstr_size = MultiByteToWideChar (CP_UTF8, 0L, Source, -1, NULL, 0); 
     if (wstr_size < max_strsize) 
     { 
     // Save the malloc/free overhead if it's a reasonable size. 
     // Plus, KJN was having fits with exceptions within exception logging due 
     // to a corrupted heap. 

     wchar_t wstr[max_strsize]; 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     } 
     else 
     { 
     wchar_t *wstr = (wchar_t *)calloc (wstr_size, sizeof(wchar_t)); 
     if (wstr == NULL) 
      throw gcnew PCSException (__FILE__, __LINE__, PCS_INSUF_MEMORY, MSG_SEVERE); 

     // Convert the UTF-8 string into the UTF-16 buffer, construct the 
     // result String from the UTF-16 buffer, and then free the buffer. 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     free (wstr); 
     } 
    } 
    return str; 
} 
+4

Có vẻ như C++/CLI hoặc C++/CX thay vì C++. Tôi không thay đổi thẻ chỉ vì tôi không biết. – bames53

+0

Vì vậy, bạn muốn kết thúc với chỉ 50 hoặc hơn C# dây và một triệu tài liệu tham khảo cho họ? –

+0

C++/CLI của nó, và có, tôi có thể có 1 triệu tài liệu tham khảo, đó là một bộ sưu tập các bài kiểm tra theo thời gian. – greggorob64

Trả lời

5

Bạn có thể sử dụng từng ký tự từ chuỗi đầu vào để cấp cấu trúc trie. Tại lá, có một đối tượng chuỗi .NET. Sau đó, khi char* xuất hiện trước đó, bạn có thể nhanh chóng tìm thấy phiên bản .NET hiện có mà không cần phân bổ bộ nhớ nào.

Pseudo-code:

  • bắt đầu với một Trie rỗng,
  • quá trình một char * bằng cách tìm kiếm Trie cho đến khi bạn có thể đi đâu xa
  • thêm các nút cho đến khi toàn bộ char của bạn * đã được mã hóa như các nút
  • nhìn vào chiếc lá, đính kèm một NET chuỗi thực tế

câu trả lời cho câu hỏi này khác SO sẽ giúp bạn có starte d: How to create a trie in c#

+0

Tôi nghĩ rằng đây sẽ là một triển khai thực hiện vững chắc, hoạt động tốt. – greggorob64

1

tôi có lẽ sẽ sử dụng một bộ nhớ đệm dựa trên cấu trúc cây bậc ba, hoặc tương tự, và tra cứu chuỗi đầu vào để xem nếu nó đã được chuyển đổi trước khi thậm chí chuyển đổi một ký tự đơn thành biểu diễn .NET.

3

Có một phần quan trọng giúp tôi cảm thấy như nó có thể được cải thiện: Có rất nhiều bản sao. Nói 1 triệu đối tượng đang đến, có thể chỉ có 50 mẫu char * độc đáo.

Nếu đây là trường hợp, bạn có thể muốn xem xét việc lưu trữ các "tìm thấy" mẫu trong một bản đồ (ví dụ như sử dụng một std::map<const char*, gcroot<String^>> [mặc dù bạn sẽ cần một Comparer cho const char*), và sử dụng để quay trở lại giá trị được chuyển đổi trước đó.

Có một phí để lưu trữ bản đồ, so sánh, vv Tuy nhiên, điều này có thể được giảm thiểu do sử dụng bộ nhớ giảm đáng kể (bạn có thể sử dụng lại các thể hiện chuỗi được quản lý), cũng như lưu cấp phát bộ nhớ (calloc) /miễn phí). Ngoài ra, sử dụng malloc thay vì calloc có thể sẽ là một cải tiến (rất nhỏ), vì bạn không cần phải loại bỏ bộ nhớ trước khi gọi MultiByteToWideChar.

+0

Tôi chắc chắn sẽ chuyển từ malloc sang calloc. Ánh xạ âm thanh khá giống với việc thực hiện cây, nhưng vì tôi có quyền truy cập vào các kiểu dữ liệu .net (C++ i được định nghĩa là C++. Net, không phải chuẩn C++), tôi có thể sử dụng các kiểu bản đồ của chúng. – greggorob64

+0

@ greggorob64 Bạn sẽ không thể dễ dàng làm việc với các bộ sưu tập .net với kiểu gốc làm khóa. Sử dụng 'std :: map' với giá trị là' gcroot 'sẽ hoạt động mà không có kiểu được xây dựng tùy chỉnh và cung cấp cho bạn cùng thời gian truy cập' log (n) 'như một trie. ;) –

+0

@Reed: cố gắng là 'O (1)' đối với số chuỗi, không phải 'O (lg n)'. –

2

Tôi nghĩ tối ưu hóa đầu tiên bạn có thể thực hiện ở đây là thực hiện lần gọi đầu tiên MultiByteToWideChar bắt đầu bằng bộ đệm thay vì con trỏ rỗng. Vì bạn đã chỉ định CP_UTF8, MultiByteToWideChar phải đi qua toàn bộ chuỗi để xác định độ dài mong đợi.Nếu có một số chiều dài dài hơn phần lớn các chuỗi của bạn, bạn có thể xem xét phân bổ một cách tối ưu bộ đệm có kích thước đó trên ngăn xếp; và nếu điều đó không thành công, sau đó chuyển sang phân bổ động. Tức là, hãy di chuyển nhánh đầu tiên nếu khối if/else của bạn bên ngoài số if/else.

Bạn cũng có thể tiết kiệm thời gian bằng cách tính toán độ dài của chuỗi nguồn một lần và chuyển nó một cách rõ ràng - theo cách đó MultiByteToWideChar không phải thực hiện strlen mỗi lần bạn gọi.

Điều đó nói rằng, có vẻ như nếu phần còn lại của dự án của bạn là C#, bạn nên sử dụng thư viện lớp .NET BCL được thiết kế để thực hiện việc này thay vì có lắp ráp bên cạnh trong C++/CLI. dây. Đó là những gì System.Text.Encoding dành cho.

Tôi nghi ngờ bất kỳ loại cấu trúc dữ liệu bộ nhớ đệm nào bạn có thể sử dụng ở đây sẽ tạo ra bất kỳ sự khác biệt đáng kể nào.

Ồ, và đừng bỏ qua kết quả của MultiByteToWideChar - không chỉ bạn không nên bỏ bất cứ điều gì đến void, bạn đã có hành vi không xác định trong trường hợp MultiByteToWideChar không thành công.

+0

Tôi sẽ xem xét các không gian tên system.text.encoding. Khi chúng tôi lần đầu tiên bắt đầu sử dụng .net, chúng tôi chỉ sử dụng các chuỗi contstuctor tiêu chuẩn: chuỗi mới (char * đầu vào). Điều này bị loại bỏ khá nhanh với các ký tự rộng, đó là lý do tại sao tìm thấy việc thực hiện được đề cập ở trên và sử dụng điều đó. Các giải pháp chính xác chắc chắn là sử dụng hốc thư viện givent. – greggorob64

Các vấn đề liên quan