Em mới tiếp cận với lập trình ứng dụng , thấy một số cấu trúc khá hay như : thread,multithread,link list,… Và e băn khoăn rằng không biết nên dùng những thứ này trong giải toán tin hay không ?? Nếu có thì tốc độ có cải thiện so với bình thường không ạ ???
Có nên sử dụng thread, multithread, link list trong việc giải toán tin
bạn thử giải một bài tập đơn giản nào đó bằng những cái bạn nêu lên chưa? tại sao không bỏ vài giờ để trải nghiệm và tự đánh giá
5 Likes
Thread API thì low-level thấp, bạn chủ yếu vọc để biết sự tồn tại của nó thôi.
Về ứng dụng thì bạn nên tiếp cận theo data parallelism hoặc task parallelism hơn (dù nó vẫn là low-level)
Ví dụ như các giải thuật ensemble learning, người ta sẽ sử dụng các naive nonlinear model, chạy song song nó, rồi dùng scheduler nhận output của các naive model, đưa ra output cuối cùng (theo cơ chế voting, weight average,…) . Kết quả là có một strong model mạnh hơn. Mấy trò ensemble learning thích hợp để chơi competitive programming kiểu Kaggle, nhưng chạy real product thì không xài được.
5 Likes
Cái này là tùy bạn chứ sao lại có nên hay không nên.
Tuy nhiên các bài toán tin chủ yếu nặng về thuật toán, việc tối ưu thuật toán là điều quan trọng hơn dùng sức trâu vì vậy sẽ ít bài dùng đến multithread
6 Likes
Linked list là CTDL nên dùng cũng chẳng sao 
Mình nghĩ dùng lập trình bất đồng bộ trong một bài toán tin là một cách “gian lận hợp pháp”. Nó có hiệu quả, chẳng ai cấm. Nhưng vốn dĩ, mục tiêu chung khi làm những bài toán tin là tạo ra một thuật toán chạy được và tối ưu.
Nếu thuật toán của bạn tối ưu quá kém thì dù có chạy chục luồng cũng không bằng thuật toán của người ta chỉ chạy đơn luồng 
4 Likes
trong tất cả những cuộc thi mà mình đã thi, từ tin học trẻ hay olympic 30/4 hay thi tin học đến vòng quốc gia, mình chưa thấy có bài nào có thể xài được multithread (tất nhiên là cố ý thì vẫn được, nhưng không có ý nghĩa gì ngoài việc làm cho code phức tạp hơn)
lý do là vì những giải thuật dựa trên sự tính toán tuần tự, và sự phụ thuộc kết quả của những bước trước, nên không có chỗ cho multithread hay tính toán song song
những cái gọi là “tài nguyên” cũng chỉ là những biến/bộ nhớ thì không thể có 2 cái cùng sử dụng (read/write) mà không biết rõ trước sau được
trong thực tế, người ta xài multithread dành cho những tác vụ có thể chạy độc lập mà không ảnh hưởng những tác vụ khác, đó là một trong những điều kiện để quyết định sử dụng multithread, tận dụng sức mạnh không phải là điều kiện đủ để ra quyết định việc đó được
còn nếu nói về linklist, học nó chủ yếu là biết rèn luyện mà thôi, thực tế đã có những cái implement sẵn và như stack, queue hay vector cũng có đủ các tính năng rồi
đa số vấn đề năm ở thời gian chạy như hầu như về bộ nhớ thì mình chưa thấy (vì dung lượng bộ nhớ cho phép khá lớn, nếu khai báo mảng mà full bộ nhớ cho phép thì thời gian duyệt sẽ rất lâu, mình cũng chưa gặp case nào tạch vì thiếu bộ nhớ 
5 Likes
To @vn_deaths:
Bạn có thể dùng linked list nhưng không cần phải cài lại vì C++ STL hỗ trợ sẵn cho bạn rồi.
Các máy chấm competitive programming có thể không cho phép thí sinh sử dụng 1 số thư viện hay xài 1 số lệnh (ví dụ các câu lệnh liên quan đến system). Bạn có thể dùng multithread trong code của bạn, nhưng máy chấm có thể phát hiện ra bạn gọi thư viện không được phép, đến lúc đó bài của bạn có bị 0 điểm thì cũng không oan
Có 1 số bài cho limit của n lớn (tầm 2 triệu), trong code lại phải khai báo tầm 2-3 mảng, có khi cài segment tree nữa nên thành ra memory lại hạn chế. Một số online judge muốn thử thách thí sinh nên chỉ cho memory rất hạn chế (tầm 64-128 MB). Bạn may mắn chưa gặp case tạch vì thiếu bộ nhớ, còn mình là trùm dính Memory Limit Exceeded Tất nhiên bị MLE cũng do thuật toán dởm hoặc quá naive nữa.
Mình đào lại nick codeforces cũ của mình thì thấy có bài này, đến test 88 rồi còn chết vì thiếu mem và bài này đến giờ mình vẫn chưa Accepted.
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?