Sắp xếp sao cho tối ưu

tuhocvba

Administrator
Thành viên BQT
Bước khởi đầu của code là chạy đúng yêu cầu.
Tiếp theo, chúng ta mong muốn là làm sao để vượt qua kỳ vọng của yêu cầu, tức là chương trình nên có tốc độ chấp nhận được.

Vẫn liên quan tới chủ đề này:
Hôm nay lại có một câu chuyện nữa muốn chia sẻ với các bạn. Đó là vấn đề tốc độ xử lý. Tôi thực sự đã đau đầu về nó trong suốt một tuần qua.

Giả sử ta có dãy số 1,2,3,5,2000.
Lần đầu cần chèn số tự nhiên vào dãy trên, mong muốn chèn số 4. Do giữa 3 và 5 có khoảng trống. Lúc này ta có dãy: 1,2,3,4,5,2000.
Lần tiếp theo cần chèn số tự nhiên vào dãy 1,2,3,4,5,2000 thì mong muốn chèn số 6. Lúc này ta có dãy: 1,2,3,4,5,6,2000.
Lần tiếp theo là 7...
....
Chèn số 2001. Lúc này ta có dãy: 1,2,3,4,5,...2000,2001.
Chèn số 2002. Lúc này ta có dãy: 1,2,3,4,5,...2000,2001,2002.
Như vậy thuật toán chèn số vào dãy, mọi người đã hình dung được.
Tuy nhiên ban đầu ta có một dãy số bla bla. Do đó chúng ta phải sắp xếp dãy số theo thứ tự tăng dần.
Tới đây ta hình dung ra hai lệnh For.
Giả sử dãy có n phần tử, n càng lớn, thì máy tính cần chạy số lần tiệm cận với : \[ n^2 \]
Ngay cả thuật toán nổi bọt cũng vậy.
Nếu chỉ một câu lệnh For, số lần chạy chỉ là 1 tới n, tức là n. Chúng ta không hề mong muốn là \[ n^2 \] .

1. Tôi dùng hai lệnh For, và test với dãy khoảng 2000 phần tử, quả nhiên là lâu không tưởng. Dù đã ghi ra mảng để xử lý.
Tôi nghĩ, tôi có thể dùng SortedList, đó là công cụ mạnh. Nhưng điểm yếu duy nhất là nó yêu cầu máy người dùng phải cài Net Framework. Đây là điều tôi không muốn, vì nó gây phiền hà cho người dùng.

2. Nếu tạo một workbook temp, ghi dữ liệu lên đó và dùng sort thì sao?
Tốc độ không cải thiện. Chúng ta biết rằng mỗi lần tạo ra một workbook, là một lần mất thời gian.

3. Tôi nghĩ là cần phải có một thuật toán mới, tuy nhiên bên phía yêu cầu nói rằng khó có thể thay đổi logic vì dữ kiện đầu vào không hề lý tưởng, có khả năng bla bla, do đó việc sắp xếp lại là cần thiết.
Tôi muốn lợi dụng khả năng sắp xếp của Microsoft Excel, nhưng tôi không muốn khởi tạo workbook mới mô phỏng thao tác sort bằng tay. Vì vậy tôi nghĩ chúng ta còn giải pháp nữa là worksheetfunction.
Và chúng ta có Small.

Cuối cùng thì tốc độ cũng đã được cải thiện rất nhiều. Đây là điều tôi muốn chia sẻ cho các bạn.
 

PeterVu

Thành viên mới
Bước khởi đầu của code là chạy đúng yêu cầu.
Tiếp theo, chúng ta mong muốn là làm sao để vượt qua kỳ vọng của yêu cầu, tức là chương trình nên có tốc độ chấp nhận được.

Vẫn liên quan tới chủ đề này:
Hôm nay lại có một câu chuyện nữa muốn chia sẻ với các bạn. Đó là vấn đề tốc độ xử lý. Tôi thực sự đã đau đầu về nó trong suốt một tuần qua.

Giả sử ta có dãy số 1,2,3,5,2000.
Lần đầu cần chèn số tự nhiên vào dãy trên, mong muốn chèn số 4. Do giữa 3 và 5 có khoảng trống. Lúc này ta có dãy: 1,2,3,4,5,2000.
Lần tiếp theo cần chèn số tự nhiên vào dãy 1,2,3,4,5,2000 thì mong muốn chèn số 6. Lúc này ta có dãy: 1,2,3,4,5,6,2000.
Lần tiếp theo là 7...
....
Chèn số 2001. Lúc này ta có dãy: 1,2,3,4,5,...2000,2001.
Chèn số 2002. Lúc này ta có dãy: 1,2,3,4,5,...2000,2001,2002.
Như vậy thuật toán chèn số vào dãy, mọi người đã hình dung được.
Tuy nhiên ban đầu ta có một dãy số bla bla. Do đó chúng ta phải sắp xếp dãy số theo thứ tự tăng dần.
Tới đây ta hình dung ra hai lệnh For.
Giả sử dãy có n phần tử, n càng lớn, thì máy tính cần chạy số lần tiệm cận với : \[ n^2 \]
Ngay cả thuật toán nổi bọt cũng vậy.
Nếu chỉ một câu lệnh For, số lần chạy chỉ là 1 tới n, tức là n. Chúng ta không hề mong muốn là \[ n^2 \] .

1. Tôi dùng hai lệnh For, và test với dãy khoảng 2000 phần tử, quả nhiên là lâu không tưởng. Dù đã ghi ra mảng để xử lý.
Tôi nghĩ, tôi có thể dùng SortedList, đó là công cụ mạnh. Nhưng điểm yếu duy nhất là nó yêu cầu máy người dùng phải cài Net Framework. Đây là điều tôi không muốn, vì nó gây phiền hà cho người dùng.

2. Nếu tạo một workbook temp, ghi dữ liệu lên đó và dùng sort thì sao?
Tốc độ không cải thiện. Chúng ta biết rằng mỗi lần tạo ra một workbook, là một lần mất thời gian.

3. Tôi nghĩ là cần phải có một thuật toán mới, tuy nhiên bên phía yêu cầu nói rằng khó có thể thay đổi logic vì dữ kiện đầu vào không hề lý tưởng, có khả năng bla bla, do đó việc sắp xếp lại là cần thiết.
Tôi muốn lợi dụng khả năng sắp xếp của Microsoft Excel, nhưng tôi không muốn khởi tạo workbook mới mô phỏng thao tác sort bằng tay. Vì vậy tôi nghĩ chúng ta còn giải pháp nữa là worksheetfunction.
Và chúng ta có Small.

Cuối cùng thì tốc độ cũng đã được cải thiện rất nhiều. Đây là điều tôi muốn chia sẻ cho các bạn.
Tôi xin được tiếp admin bằng hiệu suất đo được thực tế.
Còn tùy thuộc vào cấu hình máy để cho ra kết quả nhanh hay chậm.
Nhưng cấu hình nào cũng sẽ cho ra phần tăng hiệu suất tương tự.
Dưới đây là 2 phép thử đơn giản cho chúng ta thấy kết quả và hiệu suất trước và sau khi cải thiện.
STTVùng testPhạm vi điềnVị trí điềnThời gian chạy trước khi cải thiện
(Giây)
Thời gian chạy sau khi cải thiện (Giây)Tăng hiệu suất (%)
1​
Database không có dữ liệuA -> ZZ
702​
129​
49​
62%​
2​
Database có sẵn dữ liệu
A -> KK & SE->ZZ
KL -> SD
200​
81.6​
22.9​
72%​
 

thanhphong

Thành viên mới
Không xử lý trực tiếp trên excel, xử lý bằng mảng, là đã cải thiện tốc độ rồi.
Sau đấy còn cải thiện được tiếp như thế này, thật kinh hồn.
Bạn cần đăng nhập để thấy hình ảnh
 

vbano1

Admin
Thành viên BQT
STTVùng testPhạm vi điềnVị trí điềnThời gian chạy trước khi cải thiện
(Giây)
Thời gian chạy sau khi cải thiện (Giây)Tăng hiệu suất (%)
1​
Database không có dữ liệuA -> ZZ
702​
129​
49​
62%​
2​
Database có sẵn dữ liệu
A -> KK & SE->ZZ
KL -> SD
200​
81.6​
22.9​
72%​
Công thức tính hiệu suất có gì đó sai sai. Tôi nghĩ tốc độ đã tăng gấp đôi hoặc hơn, thì hiệu suất không thể chỉ vài chục phần trăm (dưới 50%).
 
Top