C++ Cách nhanh nhất để quét các phần tử nhất định trong mảng char chưa ký và một véc tơ chữ ký không dấu là gì?

Question

Tôi có một câu hỏi nhỏ, cách nhanh nhất để quét các phần tử nhất định trong một mảng char chưa được ký hiệu LARGE và một vectơ chỉ chứa các phần tử char chưa ký là gì? Câu trả lời thẳng sẽ là tuyệt vời, nhưng câu trả lời chi tiết chuyên sâu sẽ là tuyệt vời. Tôi có ý gì bằng cách nhanh chóng? Về cơ bản, để tìm kiếm các ký tự nhất định trong vòng ít nhất một giây. Tôi biết rằng đó không phải là định nghĩa được giáo dục ...

Lưu ý: Mảng không được sắp xếp.

Tuyên bố chung:

unsigned char* Array = new unsigned char[ 50000 ]; 
std::vector< unsigned char > Vec(50000); 
/* 
* Fill Array & Vec with random bytes 
*/ 

phép nói rằng, tôi muốn tìm kiếm những chữ 'a' trong Array, tôi sẽ chỉ đơn giản là viết vòng lặp này để tìm kiếm cho nó:

Lưu ý: quá trình tìm kiếm sẽ tìm kiếm nhiều hơn một phần tử. Chủ yếu, 256. Do đó, bạn có thể khai thác số ma thuật đó.

Đối với phương pháp lặp:

unsigned int Count = 0; 
for (unsigned int Index = 0; Index != 50000; ++ Index) 
    if(Array[ Index ] == 'a') Count ++; 

std :: count phương pháp:

unsigned int Count = std::count (Array, Array + 50000, 'a'); 

Có cách nào nhanh hơn để tìm kiếm các yếu tố nhất định trong mảng?

Một số IDEAS - Xin vui lòng không cho tôi một dấu hiệu cho điều này! Nó chỉ là một ý tưởng. Tôi muốn một số ý kiến.

Sorting

tốc độ sẽ được tốt hơn nếu chúng ta làm một bản sao của mảng và sắp xếp nó? Tại sao tạo một bản sao? Vâng, bởi vì chúng ta cần giữ nội dung gốc. Mục đích là để quét cơ bản và đếm sự xuất hiện của một nhân vật. Hãy nhớ rằng, vấn đề tốc độ. Điều đó có nghĩa, quá trình sao chép phải nhanh.

Answer: No and its not worth it! 

Tại sao? Vâng, cho phép đọc:

@Kiril Kirov:

Phụ thuộc. Nếu bạn có kế hoạch tìm kiếm một đơn char - thì hoàn toàn không. Sao chép mảng là một hoạt động tốn kém. Sắp xếp nó - thậm chí còn đắt hơn.

Vâng, nếu bạn sẽ chỉ có một mảng và bạn dự định tìm kiếm, giả sử, 100 ký tự khác nhau, thì phương pháp này có thể cung cấp cho bạn hiệu suất tốt hơn. Bây giờ, điều này thực sự phụ thuộc vào cách sử dụng của bạn. Và không ai có thể cung cấp cho bạn câu trả lời hoàn toàn đúng cho trường hợp này. Bạn cần phải chạy nó và hồ sơ.

* Cuộn xuống bài viết cung cấp thông tin của @Kiril Krov để biết thêm.

Trả lời: Cho đến nay, không có một chất rắn hoặc một câu trả lời, bởi vì không có một phương pháp thực sự "nhanh" để đạt được mục tiêu này, đặc biệt là khi nó không sắp xếp. Tuy nhiên, chủ đề có thể là giải pháp khả thi. Nhưng, xem ra cho CPU của chúng tôi!Điều này được dựa trên câu trả lời được gửi của @ Andrea (cuộn xuống một chút để biết thêm thông tin) - Tôi hy vọng tôi đọc nó đúng.

Answer 1

Khi người khác viết, độ phức tạp của thuật toán tốt nhất là O(n), đặc biệt là vì mảng của bạn không được sắp xếp.

Để thực hiện tìm kiếm nhanh hơn, bạn có thể chia nhỏ mảng và quét từng phần riêng lẻ trong các chuỗi riêng biệt. Điều này sẽ mở rộng tuyến tính với số lõi CPU bạn có sẵn trên máy của bạn.

Nếu, ví dụ, bạn có bốn lõi có sẵn, sau đó sinh ra bốn luồng và để cho mỗi luồng quét một phần tư của mảng.

Có lẽ cuộc thảo luận này có thể giúp: Using threads to reduce array search time

---

Trong mọi trường hợp (và điều này là đúng đối với bất kỳ vấn đề liên quan đến hiệu suất), bạn nên cấu hình mã của bạn. Tạo một trường hợp thử nghiệm cho phương pháp bạn có, đo thời gian cần thiết và thực hiện điều này như là một đường cơ sở. Sau đó, đối với mỗi sửa đổi bạn thực hiện, hãy làm lại phép đo để kiểm tra xem nó có thực sự cải thiện thời gian thực hiện hay không. Ngoài ra, hãy đảm bảo thực hiện từng phép đo nhiều lần (trong cùng một trường hợp thử nghiệm) và tính trung bình, để giảm bộ nhớ đệm và các hiệu ứng làm ấm khác (lý tưởng, thực thi mã ít nhất một lần trước khi bắt đầu phép đo đầu tiên).

này được Java liên quan, nhưng đưa ra một số thông tin phản hồi tốt mà nó không trong mọi trường hợp có ý nghĩa với parallelize: A Beginner´s Guide to Hardcore Concurrency

Answer 2

Thuật toán tốt nhất là O(n), trong đó n là số phần tử.

Khi bạn cần kiểm tra từng phần tử, bạn phải trải qua toàn bộ mảng.

Cách dễ dàng tôi có thể nghĩ đến, đã được viết bằng câu trả lời của riêng bạn.

Và không có cách nào nhanh hơn để thực hiện việc này - bộ nhớ liên tục, mảng không được sắp xếp, bạn cần phải "chạm" từng phần tử. Đó là giải pháp nhanh nhất có thể.

---

Về chỉnh sửa của bạn: sử dụng std::count và "theo cách thủ công" lặp qua mảng sẽ cho bạn hiệu suất tương tự.

---

Có cách nào nhanh hơn để tìm kiếm các yếu tố nhất định trong mảng

Vâng, nếu mảng được sắp xếp. Sau đó, bạn có thể đạt được tối đa O(log(n)). Sau đó, bạn sẽ cần một số thuật toán tìm kiếm hiện có, chẳng hạn như tìm kiếm nhị phân.

---

có tốc độ tốt hơn nếu chúng tôi thực hiện một bản sao của mảng và sắp xếp nó

Phụ thuộc. Nếu bạn có kế hoạch tìm kiếm một char đơn lẻ - tuyệt đối không. Sao chép mảng là một hoạt động tốn kém. Sắp xếp nó - thậm chí còn đắt hơn.

Vâng, nếu bạn sẽ chỉ có một mảng và bạn dự định tìm kiếm, giả sử, 100 ký tự khác nhau, thì phương pháp này có thể cung cấp cho bạn hiệu suất tốt hơn. Bây giờ, điều này thực sự phụ thuộc vào cách sử dụng của bạn. Và không ai có thể cung cấp cho bạn câu trả lời hoàn toàn đúng cho trường hợp này. Bạn cần phải chạy nó và hồ sơ.

Answer 3

Dou bạn có ý nghĩa gì bởi "nhanh"?

Nhanh như trong sự phức tạp, hoặc như là một sự cải tiến bởi một hằng số? Bạn không thể đạt được độ phức tạp cao hơn với mảng chưa được phân loại. Tuy nhiên, nếu bạn thay đổi mảng rất hiếm khi và tìm kiếm nó rất thường xuyên, bạn có thể xem xét sắp xếp nó sau mỗi thay đổi hoặc tốt hơn, sử dụng cấu trúc dữ liệu khác (như multimap hoặc set).

Nếu bạn có ý định có hằng số tốt hơn trong O(n), có một số thủ thuật gọn gàng sử dụng/lạm dụng bộ nhớ cache của CPU của bạn. Nếu bạn tìm kiếm nhiều phần tử, nó nhanh hơn để tìm kiếm hàng trăm phần tử mảng đầu tiên cho mỗi ký tự, sau đó vài trăm tiếp theo, và tiếp tục quét toàn bộ mảng cho từng cụm từ tìm kiếm của bạn. Những cải tiến này không phức tạp, do đó hiệu ứng thường sẽ không tuyệt vời như vậy. Trừ khi tìm kiếm này xảy ra tại nút cổ chai của bạn lặp đi lặp lại sâu bên trong một số thuật toán khác, tôi sẽ không khuyên bạn nên sử dụng nó. Vì vậy, trừ khi nó bên trong một thuật toán dựng hình, hoặc một trình điều khiển thiết bị, hoặc cho một kiến ​​trúc cụ thể, vv nó có lẽ là không có giá trị nó. Tuy nhiên, trong những trường hợp hiếm hoi mà nó có thể thích hợp, tôi đã thấy những cải thiện tốc độ từ 3x - 4x trở lên bằng cách sử dụng lắp ráp nội tuyến và lạm dụng chache CPU.

EDIT:

Cảm nhận của bạn idicated nó có thể là một ý tưởng tốt để bao gồm một giới thiệu ngắn gọn về cấu trúc dữ liệu.

• mảng, vector: truy cập nhanh nhất, tìm kiếm chậm, thêm chậm/xóa nếu không được nối vào cuối.
• danh sách: việc truy cập chậm, tìm kiếm chậm, thêm nhanh nhất/loại bỏ
• cây, bảng băm, vv: tìm kiếm tốt nhất (! Một số phép O(0) tìm kiếm), thay đổi chậm (phụ thuộc vào loại)

Tôi khuyên bạn nên tìm hiểu về các cấu trúc dữ liệu khác nhau (vectơ, danh sách, bản đồ, multimap, tập hợp, nhiều thứ, vv) trong C++, vì vậy bạn có thể sử dụng cấu trúc phù hợp nhất với nhu cầu của mình.

Giới thiệu về bộ nhớ cache CPU: có vẻ như việc chọn cấu trúc dữ liệu phù hợp tốt hơn và tổ chức mã quan trọng hơn nhiều. Tuy nhiên, tôi bao gồm điều này vì lợi ích của sự hoàn chỉnh. Nếu bạn tìm kiếm mảng trong các đoạn ngắn hơn là toàn bộ mảng cùng một lúc, phần đó của mảng được thêm vào bộ nhớ cache của CPU của bạn và việc truy cập bộ nhớ cache nhanh hơn nhiều so với việc truy cập RAM. Vì vậy, bạn có thể làm việc trên đoạn dữ liệu nhỏ hơn của mình (ví dụ: tìm kiếm nhiều phần tử), sau đó chuyển sang đoạn dữ liệu tiếp theo, v.v. Điều này có nghĩa, ví dụ,

search "a" in elements 1..100 
search "b" in elements 1..100 
search "c" in elements 1..100 
search "a" in elements 101..200 
search "b" in elements 101..200 
search "c" in elements 101..200 
... 
search "c" in elements 999901 .. 1000000 

có thể nhanh hơn

search "a" in elements 1..1000000 
search "b" in elements 1..1000000 
search "c" in elements 1..1000000 

Nếu số lượng tìm kiếm các yếu tố (a, b, c, ..) là đủ lớn. Tại sao? Vì trong trường hợp kích thước bộ nhớ cache là 100, trong ví dụ đầu tiên, dữ liệu được đọc 10.000 lần từ RAM, trong ví dụ thứ hai, 30000 lần.

Tuy nhiên, hiệu quả của việc này (và lựa chọn kích thước dữ liệu của bạn) phụ thuộc nhiều vào kiến ​​trúc của bạn và chỉ được khuyến nghị nếu bạn thực sự chắc chắn rằng đây là nút cổ chai thực sự của bạn. Thường thì không.

Answer 4

Tùy thuộc vào quá trình quét một lần hoặc nhiều lần. Việc sắp xếp sẽ giúp ích rất nhiều về tốc độ quét, bạn luôn có thể thu hẹp quá trình quét bằng cách tìm kiếm. Và sự phức tạp có thể là O (log (n)).

Hoặc nếu bạn có thể bắt đầu chèn và tạo mảng sẽ quét, bạn có thể sử dụng cây đỏ-đen chậm chèn, nhưng luôn được sắp xếp.

Cuối cùng nhưng không kém phần quan trọng, đối với câu hỏi của bạn mà bạn đang quét "mảng char chưa ký", trong đó số lượng phần tử bị giới hạn. Bạn có thể thực hiện quét một lần, nhưng cần nhiều bộ nhớ hơn: sử dụng giá trị của mỗi phần tử bên trong mảng char chưa ký của bạn làm chỉ mục của một mảng khác được sử dụng để lưu trữ kết quả quét.

Nếu bạn muốn vị trí của mọi phần tử, mảng kia có thể là: int scanresult [256] [n], trong đó n là số lớn nhất cho số lượng char nhất định.

Nếu bạn chỉ cần đếm số lượng 'a' trong mảng, mảng kia có thể là: int scanresult [256], lấy ví dụ này, Độ phức tạp là O (n), nhưng chỉ cần chạy một lần :

unsigned char* Array = new unsigned char[ 50000 ]; 
/* Fill Array */ 
int scanresult[256]; 
for (int i=0;i<256;++i) { scanresult[i]=0; } 
for (unsigned int Index = 0; Index != 50000; ++ Index) 
    scanresult[Array[Index]]++; 

Answer 5

Đừng quên, unsigned char> 0 & & unsigned char < = 256 ...

#define MAX 50000 

unsigned char* Array = new unsigned char[ MAX ]; 
unsigned int Logs[ 256 ]; 

// Fill Array 

::memset(&Logs, 0, sizeof(Logs) * 256); 
for(unsigned int Index = 0; Index != MAX; ++ Index) 
    Logs[ Array[ Index ] ] ++; 

delete [] Logs; 

Answer 6

Đối với một tìm kiếm ký tự đơn, std::count có lẽ là càng nhanh như bạn sẽ nhận được. Và đối với các bộ dữ liệu nhỏ (và 50000) là nhỏ, bạn không thể nhận thấy thời gian. Trong số , đối với một ký tự đơn, hầu như mọi thuật toán hợp lý sẽ mất ít thời gian hơn để đọc dữ liệu. (std::count trên 50000 yếu tố trong một vector hoặc một phong cách C mảng sẽ được gần gũi với tức thời trên một máy hiện đại. Đơn đặt hàng của độ richter Uner bạn "ít nhất một giây", ở mức nào.)

Nếu bạn muốn để đi nhanh hơn, giải pháp là không tạo mảng để bắt đầu, nhưng để thực hiện quá trình xử lý khi đang di chuyển, trong khi bạn đang đọc dữ liệu (hoặc để nhận mảng ngay lập tức, qua mmap). Và nếu bạn cần dữ liệu cho nhiều hơn một ký tự ... chỉ cần tạo bảng tần số ký tự khi bạn đọc dữ liệu. Và tìm cách nhanh nhất để đọc dữ liệu (gần như chắc chắn là mmap trong Linux, ít nhất theo một số biện pháp tôi đã thực hiện gần đây). Sau đó, chỉ cần lập chỉ mục vào bảng này khi bạn muốn đếm. Đọc dữ liệu sẽ là O (n) (và không có cách nào xung quanh), nhưng sau đó, nhận được số lượng là O (1), với một, rất rất nhỏ yếu tố contant cũng (dưới một nano giây trên một rất nhiều máy móc).