C khởi tạo một mảng số nguyên lớn (rất) với các giá trị tương ứng với chỉ mục

Question

Edit3: Tối ưu hóa bằng cách giới hạn việc khởi tạo mảng thành chỉ số lẻ. Cảm ơn bạn @Ronnie!

Chỉnh sửa2: Cảm ơn tất cả, có vẻ như tôi không thể làm gì được nữa.

Chỉnh sửa: Tôi biết Python và Haskell được triển khai bằng các ngôn ngữ khác và ít nhiều hoạt động giống như tôi đã từng làm, và mã C tuân thủ sẽ đánh bại chúng bất kỳ ngày nào. Tôi chỉ tự hỏi nếu tiêu chuẩn C (hoặc bất kỳ thư viện) có tích hợp chức năng để làm điều này nhanh hơn.

Tôi đang thực hiện một rây thủ trong C sử dụng thuật toán Eratosthenes' và cần phải khởi tạo một mảng số nguyên kích thước tùy ý n 0- n. Tôi biết rằng trong Python bạn có thể làm:

integer_array = range(n) 

và thế là xong. Hoặc trong Haskell:

integer_array = [1..n] 

Tuy nhiên, tôi dường như không thể tìm thấy một phương pháp tương tự như thực hiện trong C. Các giải pháp tôi đã đi lên với khởi sự lặp mảng và sau đó qua nó, gán mỗi giá trị cho chỉ số tại thời điểm đó, nhưng nó cảm thấy vô cùng hiệu quả.

int init_array() 
{ 
    /* 
    * assigning upper_limit manually in function for now, will expand to take value for 
    * upper_limit from the command line later. 
    */ 
    int upper_limit = 100000000; 
    int size = floor(upper_limit/2) + 1; 

    int *int_array = malloc(sizeof(int) * size); 
    // debug macro, basically replaces assert(), disregard.  
    check(int_array != NULL, "Memory allocation error"); 

    int_array[0] = 0; 
    int_array[1] = 2; 

    int i; 

    for(i = 2; i < size; i++) { 
     int_array[i] = (i * 2) - 1; 
    } 

    // checking some arbitrary point in the array to make sure it assigned properly. 
    // the value at any index 'i' should equal (i * 2) - 1 for i >= 2 
    printf("%d\n", int_array[1000]); // should equal 1999 
    printf("%d\n", int_array[size-1]); // should equal 99999999 

    free(int_array); 

    return 0; 

error: 
    return -1; 
} 

Có cách nào tốt hơn để thực hiện việc này không? (không, dường như không có!)

Answer 1

Dưới đây là một thuật toán tốt hơn có lẽ là một cược tốt hơn trong điều kiện tối ưu hóa việc phân bổ: -

1. Halve các int_array_ptr kích thước bằng cách tận dụng thực tế là bạn sẽ chỉ cần để kiểm tra số lẻ trong sàng
2. Run này thông qua một số phân tích nhân tử bánh xe cho số 3,5,7 để giảm so sánh tiếp theo 70% +

điều đó sẽ đẩy mọi thứ lên.

Answer 2

Giải pháp tôi đã đưa ra khởi tạo mảng và sau đó lặp lại nó, gán từng giá trị cho chỉ mục tại thời điểm đó, nhưng nó cảm thấy vô cùng kém hiệu quả.

Bạn có thể cắt giảm số dòng mã, nhưng tôi không nghĩ rằng việc này có liên quan đến "hiệu quả".

Trong khi chỉ có một dòng mã trong Haskell và Python, những gì xảy ra dưới mui xe giống như mã C của bạn (trong trường hợp tốt nhất; nó có thể hoạt động tồi tệ hơn tùy thuộc vào cách nó được triển khai).

Có chức năng thư viện chuẩn để điền vào một mảng với giá trị không đổi (và chúng có thể hoạt động tốt hơn, mặc dù tôi không đặt cược vào đó), nhưng điều này không áp dụng ở đây.