Tối ưu hóa mã nguồn trong C++: copy mảng

Hi Anh Nguyen.

1. Theo mình chưa hiểu lắm A có x, y, z và B có x. Bạn tìm key trên B (So sánh thuộc tính B.x) và tìm key trên A (A.x) thì có gì khác nhau về tốc độ chứ ?.
2. “Nói chung là cache” mình không rõ lắm có phải cache không ?.khi tìm kiếm đối tượng thường thì có thể so khớp cả đối tượng (Họ tên, ngày tháng năm sinh v.v.v…) hoặc so khớp các giá trị định danh số điện thoại.
3. Tại sao bạn lại phải copy dữ liệu z từ A sang C ? (Xem lại 1).

P/S Bạm có thể nói rõ hơn phần tìm kiếm trên A không.

memcpy() hầu như là cách chuẩn để copy data, nó cũng được tối ưu hết mức có thể rồi. Nên nếu nó có vẻ chậm đối với bạn thì hoặc là nhu cầu của bạn thực sự đặc biệt, hoặc cách tổ chức dữ liệu của bạn không hiệu quả.

Nếu là #1 thì cách tốt nhất bạn có thể làm là SIMD memcpy() (SSE, AVX), copy data theo parallel, viết tay hoặc dùng library.

Câu chuyện chỉ là làm sao cho danh sách liên kết đôi chạy nhanh hơn.

Mình có 1 danh sách gốc gọi là (A) chứa data là mảng kiểu char, key, previous, next.

Thay vì để tất cả thông tin vào trong 1 nốt, mình tạo ra 1 danh sách mới (B) mà trong đó mỗi nốt chỉ chứa key, previous và next và 1 con trỏ (ptr) trỏ tới data nốt đó sẽ chứa.

Data của từng nốt thì mình copy lại từ (A) và cấp phát đâu đó trong vùng nhớ không quan trọng. Các nốt sẽ được nối với nốt tương ứng trong (B) bằng 1 con trỏ. Điều quan trọng là khi mình cần dữ liệu của nốt nào trong cái danh sách gốc (A), mình chỉ cần dùng key truyền vào so sánh với key trong (B). Nếu giống nhau thì mình lấy ra giá trị sử dụng con trỏ (ptr).

(B) là tập hợp những nốt nằm kế sát nhau giống như 1 mảng vậy đó.

Lý thuyết là như vậy. Khi so sánh tìm trên danh sách gốc (A) với cái danh sách mình mới tạo ra thì tốc độ tăng lên khoảng 10 lần (đạt yêu cầu). Nhưng có đứa ra tới 16 lần. Thời gian chuyển từ (A) ra (B) và © của mình là ~140ms, của bạn cùng lớp là dưới 100ms. Cái status thì update tự động thôi và ai cũng là anonymous.

Khi mình hỏi thì nó nói là thay đổi cách copy mảng kiểu char từ (A) qua các nốt dữ liệu. Mình thì làm memcpy. Không biết nó có làm gì đặc biệt khác không.

bạn có thể up đề lên không ?. thời gian chạy cỡ ms thì nói xuông rất khó để giải quyết được.

Việc bạn mô tả thuật toán mới thì không có gì khác biệt so với thuật toán cũ cả.
Có n phần tử, cách cũ hay cách mới bạn đều so sánh từng phần tử như vậy chi phí tốn O(n), không có sự khác biệt về chi phí thuật toán.
Cách bạn tách dữ liệu mà bảo cách mới nhanh hơn thì mình nghĩ rằng bạn dùng tham số chứ không phải tham chiếu. Không biết có đúng không nhưng mình nghĩ là bạn nên cho bọn mình xem code của bạn xử lý dữ liệu như thế nào?

Mình không có đề. Mấy cái này test được viết sẵn rồi. Mình được cho 1 cái API rồi cứ theo mấy cái test mà làm thôi. Nhưng hướng đi giống như hình này nè. Code copy của mình cũng đơn giản thôi.

A* arrayA // có data sẵn rồi

B* arrayB = new B[array_length];

C* arrayC = new C[array_length];

A* temp = arrayA.getFirstNode();

while(temp != NULL)

{

arrayB->x = temp ->x;

arrayC->y = temp ->y;

memcpy(arrayC->z, temp ->z, strlen (arrayA->z) + 1);  

temp = temp->next;
arrayB++;
arrayC++;

}

Hi Anh Nguyen.

1. Theo mình không cần thiết copy ra C. Trong B có một con trỏ trỏ thẳng đến A là được. Hoặc đến A->data. (Mất công copy ra tăng gấp đôi ram rồi chỉ dùng mộ mà có nguy cơ dị bội dữ liệu.).
2. Tuy nhiên nhìn lại vấn đề thì nếu như thế thì còn dùng danh sách liên kết làm gì nữa khi cả x, y đều được lưu trên mảng ? Chuyển A sang dang vector phần data của A vấn được cấp phát động bình thường riêng phần id, và con trỏ đến data được lưu trong vector (Một dạng mảng của C++ tự nhân dôi kích thước).

Hi Anh Nguyen
Mình thấy hơi có vần đề với cách giải quyết này của bạn. Theo mình tối ưu code có 2 loại : tối ưu vi mã (những đoạn mã nhỏ như các phép nhân chia công trừ hay copy mảng) nó không là thay đổi thiết kế của hệ thống, tối ưu thiết kế (áp dụng các loại thuật toán mới dữ liệu mới) là thay đổi kiến trúc của hệ thống hoặc một phần.
Quay lại vấn đề của bạn cần hiểu rõ hai lọa dữ liệu là danh sách liên kêt và mảng. Dều là cấu trúc lưu trữ dữ liệu cũng kiểu.

1. Danh sách liên kết dùng khi các dữ liệu ít ổn định tối ưu cho việc thêm xóa tại vi trí bất kỳ (VD bài toán quản lý trứng trong một lò ấp)
2. Mảng dùng cho các loại dữ liệu ổn định chủ yếu là truy cập ít thêm xóa. (VD danh shách học sinh trong lớp thường ít thay đổi trong một học kỳ).
   Như hiện tại người thiết kế đang dùng danh sách liên kết và bạn chuyển nó sang mảng. Việc đó có thể tối ưu tìm kiếm nhưng nó là việc thêm, xóa, sửa kém hiệu quả hơn. (Khi thêm một phần tử lại phải mở rộng mảng cạche) nếu đa phần các thao tác là thêm xóa thì thực sự bạn làm cho hệ thống chạy chậm đi.

P/S Việc phân biết dữ liệu ổn định hay không, không thực sự rõ ràng. Cái đó phụ thuộc vào yêu cầu bài toán. Bạn có thể thêm các phần tử vào danh sách liên kết theo quy tắc tăng dần (cái này khá nhanh) và tạo mảng index cho cứ 100 phần tử một.

Post thứ nhất:
Xin lỗi mình không nói rõ yêu cầu.

Yêu cầu:

1. Làm cho danh sách liên kết chạy nhanh hơn.
2. Nốt cần tìm sẽ nằm đâu đó cuối danh sách liên kết. Không được sắp xếp lại danh sách liên kết theo bất cứ thứ tự nào. Muốn tìm thấy nốt đó thì phải chạy hết danh sách không bỏ cái nào.
3. Muốn làm gì trên danh sách liên kết thì phải đi từng nốt một bằng cách gọi hàm nextNode(). Mặc dù B được khởi tạo giống mảng nhưng phải coi như nó là 1 danh sách liên kết. Nối từng nốt lại với nhau bằng địa chỉ. Muốn dùng các nốt trong B thì phải dùng nextNode().
4. Không được sử dụng STL: mấy cái như vector bạn vừa kể không được dùng.
5. Khai báo trong các lớp A, B, C thế nào thì để y chang vậy. Không thay đổi.

Câu hỏi của mình: làm sao tạo một con trỏ trỏ thẳng đến dữ liệu trong A được? Cái này mình không rành. Dữ liệu trong A và C được khai báo như sau: char textData[size];

Post thứ hai:
Mục tiêu hiện tại chỉ là tìm kiếm và lấy ra dữ liệu thôi.
B vẫn là danh sách liên kết đó chứ. Có điều thay vì tạo nốt rồi để nó nằm tùy ý trong bộ nhớ rồi nối tụi nó lại thì mình tạo các nốt đó nằm sát nhau như 1 cái mảng để tăng cach hit rate. Cách làm thì tạo 1 mảng trước rồi copy key , xong 1 nốt thì cứ array+1 để tới địa chỉ tiếp theo tạo nốt mới, cuối cùng thì nối lại.
Thực sự nếu cho dùng mảng và sắp xếp lại rồi mới tìm thì nó rất đơn giản.

Hi Anh Nguyen
Vậy cái này nó giống một bài thi hơn. Và chỉ cho A là một danh sách liên kết. Yêu cầu tìm phần tử trong A nhanh nhất mà không xắp xếp lại A ? Phần B và C là bạn tự nghĩ ra hay là cho luôn cả B và C.

P/S Thực sự việc tạo B là một mảng nhưng sau đó truy cập như một danh sách có nhanh hơn không ?

Ah, B và C là cho luôn vì muốn tránh tình trạng sử dụng pointer trỏ vào mấy cái mảng chả trong A. Do đó mình bắt buộc phải copy mảng char từ A qua C bằng memcpy.

Có đứa bảo nếu viết tay lại hàm copy chỉ sử dụng cho 1 mục đích này thì sẽ nhanh hơn memcpy. Một cách nữa là dùng overload operator nhưng mình mới học nên bó tay.

Thật sự là nó nhanh hơn. Nếu kiếm bằng cấu trúc cũ A là 8 giây. Cấu trúc mới có 1 giây hơn. Test có timer luôn nên mình biết kết quả.

Lý do là vì nó để sát nhau, thứ 2 nữa là những trường trong B chỉ phục vụ tìm kiếm nên được giữ trong cache. Đó là lý do mình nói dữ liệu của C nằm đâu không quan trọng. Những cái cần để xác định dữ liệu nằm ở nốt nào thì B đã có. Nếu tìm đúng thì nhảy qua C lấy, không cứ chạy tiếp.

Cái này không phải bài thi. Thực hành cho vui thôi coi như điểm danh.

Hi Anh Nguyen

1. B và C buộc phải là index và data à hay chỉ là 2 danh sách chung chung thôi.
2. Mình không chắc khi để xát nhau thì bạn có truy cập nhanh hơn không khi thực tế vấn phải lấy địa chỉ rồi truy cập một vòng.
3. Thay copy mảng thì lấy luôn địa chỉ a nhét vào đó là OK.

Mình mới edit lại cái post trước đó. Bạn đọc lại nha chứ mình thấy viết 1 cái 2 lần nhìn kì nên ko viết lại.

Hi Anh Nguyen.
Có lẽ do mình hơi chậm hiểu nhưng bạn không muốn sử dụng con trỏ để trỏ vào mảng char trong A bằng cách copy nó ra một chỗ khác rồi dùng một con trỏ (Vâng mảng thì vần là con trỏ) để trỏ vào chỗ mới vừa tạo thế thì có gì khác nhau ?

test.png800x600 5.01 KB

Cái đó mình biết nhưng không hiểu tại sao mình viết:
C->randomData = A->randomData thì visual không cho. Nó nói lvalue must be modifiable thì phải.

Hi Anh Nguyen.
Cái đó là hạn chế về ngôn ngữ lập trình của bạn. Thử tìm trên stack xem. Mình thấy nó có vẻ là lỗi kiểu dữ liệu thôi.

Vậy C->randomData là mảng chứ không phải con trỏ mà gán ngang như vậy (nếu được) nghĩa là shallow copy dữ liệu vẫn nằm trong A.

Bingo. Chắc cách tốt nhất là overload = thôi.