kết quả từ 1 tới 7 trên 7

Cải thiện tốc độ chương trình?

  1. #1
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 367092
    Giới tính: Nam
    Bài gửi
    7

    Cải thiện tốc độ chương trình?

    - Đề bài: cho t số nguyên dương n ( 1 <= n <= 1 000 000 000). Tính số chữ số 0 của n! (n giai thừa).
    - Ví dụ:
    INPUT:
    Mã:
    6
    3
    60
    100
    1024
    23456
    8735373
    OUTPUT:
    Mã:
    0
    14
    24
    253
    5861
    2183837
    Đây là code của mình.
    Mã:
    #include <iostream>
    
    using namespace std;
    
    
    int main()
    {
    
        int t, n, count;
    
        cin >> t;
    
        for(int i = 0; i < t; i++)
        {
            count = 0;
            cin >> n;
            
            while(n >= 1)
            {
                n /= 5;
                count += n;
            }
            
            cout << count << endl;
        }
        
    }
    Vậy muốn hỏi mọi người xem có cách nào cải thiện tốc độ không? Mình làm test trên trang SPOJ thì tốc độ 0.14 với C++ 4.3.2 trong khi có nhiều thánh 0.00...
    http://www.spoj.com/problems/FCTRL/
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Cải thiện tốc độ chương trình?

    Thuật toán bạn dùng đã có độ phức tạp là O(log5(n)) rồi. Lúc test trên server thì có thể may mắn gặp lúc server trống thì chương trình sẽ chạy nhanh. Mình viết hàng trăm bài trên leetcode thì có nhiều khi cùng 1 đoạn code, ko sửa gì cả, mà submit lần nữa tự nhiên thời gian cực thấp, hơn toàn bộ những ng` khác. Thời gian thật không phải là chuẩn mực để đo đạc tốc độ nhanh chậm của thuật toán.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.462

    Reply: Cải thiện tốc độ chương trình?

    Trích Nguyên văn bởi tengiday Xem bài viết
    Thuật toán bạn dùng đã có độ phức tạp là O(log5(n)) rồi. Lúc test trên server thì có thể may mắn gặp lúc server trống thì chương trình sẽ chạy nhanh. Mình viết hàng trăm bài trên leetcode thì có nhiều khi cùng 1 đoạn code, ko sửa gì cả, mà submit lần nữa tự nhiên thời gian cực thấp, hơn toàn bộ những ng` khác. Thời gian thật không phải là chuẩn mực để đo đạc tốc độ nhanh chậm của thuật toán.
    Anh có rảnh rỗi chỉ em về C/C++ được không ạ
    Hãy Support theo cách của bạn
    Hãy thank theo cách của tôi



  5. Đã cảm ơn 365 Designer:


  6. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Cải thiện tốc độ chương trình?

    Trích Nguyên văn bởi Suu Programer Xem bài viết
    Anh có rảnh rỗi chỉ em về C/C++ được không ạ
    Nếu bạn có gì không hiểu có thể post bài trên 4rum; mình rỗi thì cũng sẽ vào xem (mình thích tin học mặc dù đó ko hề là chuyên ngành của mình).

  7. Đã cảm ơn tengiday:


  8. #5
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 367092
    Giới tính: Nam
    Bài gửi
    7

    Reply: Cải thiện tốc độ chương trình?

    Trích Nguyên văn bởi tengiday Xem bài viết
    Thuật toán bạn dùng đã có độ phức tạp là O(log5(n)) rồi. Lúc test trên server thì có thể may mắn gặp lúc server trống thì chương trình sẽ chạy nhanh. Mình viết hàng trăm bài trên leetcode thì có nhiều khi cùng 1 đoạn code, ko sửa gì cả, mà submit lần nữa tự nhiên thời gian cực thấp, hơn toàn bộ những ng` khác. Thời gian thật không phải là chuẩn mực để đo đạc tốc độ nhanh chậm của thuật toán.
    Cám ơn bạn đã trả lời.
    Nếu được, bạn có thể tư vấn cho mình một số cách để cải thiện tốc độ chương trình khi thuật toán đã tối ưu rồi được không? Mình khá kém khoản này.
    Giả như bài vừa nãy, mình có thể giảm tốc độ chạy xuống 0.10 khi thêm dòng
    Mã:
    ios::sync_with_stdio(false);
    Hoặc xuống đến 0.02 khi thay cin, cout bằng printf và scanf.

  9. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Cải thiện tốc độ chương trình?

    Mình không có chú ý tới vấn đề này bởi vì cái bạn nói phụ thuộc vào compiler, OS, (và kinh nghiệm viết)... Nếu bạn học lớp về compiler thì sẽ được dạy mấy cái này: ví dụ như ++i mà ko nên dùng i++, hay như lúc viết function thì nên đưa reference object thay vì theo như luật "dùng & nếu object đó sẽ bị thay đổi" (cái này nó cải thiện tốc độ rất lớn), dùng std::string trong C++ đôi khi sẽ nhanh hơn char *,...
    Tuy nhiên nếu compiler đã tối ưu rồi thì mấy chi tiết nhỏ không ảnh hưởng gì vì bản thân compiler có thể tối ưu giúp người dùng trong quá trình compile. Thuật toán quan trọng hơn nhiều. Khi đi xin việc, mình toàn bị test thuật toán bởi vì mấy công ty lớn có người/chương trình làm mấy cái này hết. Nó còn quan trọng chỗ viết sao để hạn chế memory leak nữa.

    PS: Bạn hỏi cái này để tham gia cuộc thi lập trình tính thời gian à?

  10. 2 thành viên đã cảm ơn tengiday:


  11. #7
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 367092
    Giới tính: Nam
    Bài gửi
    7

    Reply: Cải thiện tốc độ chương trình?

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình không có chú ý tới vấn đề này bởi vì cái bạn nói phụ thuộc vào compiler, OS, (và kinh nghiệm viết)... Nếu bạn học lớp về compiler thì sẽ được dạy mấy cái này: ví dụ như ++i mà ko nên dùng i++, hay như lúc viết function thì nên đưa reference object thay vì theo như luật "dùng & nếu object đó sẽ bị thay đổi" (cái này nó cải thiện tốc độ rất lớn), dùng std::string trong C++ đôi khi sẽ nhanh hơn char *,...
    Tuy nhiên nếu compiler đã tối ưu rồi thì mấy chi tiết nhỏ không ảnh hưởng gì vì bản thân compiler có thể tối ưu giúp người dùng trong quá trình compile. Thuật toán quan trọng hơn nhiều. Khi đi xin việc, mình toàn bị test thuật toán bởi vì mấy công ty lớn có người/chương trình làm mấy cái này hết. Nó còn quan trọng chỗ viết sao để hạn chế memory leak nữa.

    PS: Bạn hỏi cái này để tham gia cuộc thi lập trình tính thời gian à?
    OK cám ơn bạn đã giải đáp.
    Trả lời cho cái PS: Không. Mình tò mò muốn thử thôi. Nhưng có thể trong tương lai.