C使用与index对应的值初始化(非常)大整数数组

Question

Edit3:通过将数组的初始化限制为仅奇数来优化.谢谢@Ronnie!

编辑2:谢谢大家,似乎没有什么可以做的了.

编辑:我知道Python和Haskell是用其他语言实现的,并且或多或少地执行我所遵循的相同操作,并且编译的C代码将在任何一天击败它们.我只是想知道标准C(或任何库)是否具有内置函数来更快地执行此操作.

我正在使用Eratosthenes的算法在C中实现一个主筛,并且需要初始化从0到n的任意大小n的整数数组.我知道在Python中你可以这样做:

integer_array = range(n)

就是这样.或者在Haskell:

integer_array = [1..n]

但是,我似乎无法找到在C中实现的类似方法.我已经提出的解决方案初始化数组然后迭代它,在该点将每个值分配给索引,但它感觉非常低效.

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;
}

有一个更好的方法吗？(不,显然没有!)

Answer 1

我提出的解决方案初始化数组然后迭代它,在那一点将每个值分配给索引,但它感觉非常低效.

您可以减少代码行数,但我认为这与"效率"无关.

虽然在Haskell和Python中只有一行代码,但在幕后发生的事情与C代码的作用相同(在最好的情况下;根据它的实现方式,它可能会执行得更糟).

有标准的库函数来填充具有常量值的数组(并且可以想象它们可以表现得更好,尽管我不打算这样做),但这不适用于此.

Answer 2

在优化分配方面,更好的算法可能是更好的选择: -

1. 通过利用您只需要在筛子中测试奇数的事实将int_array_ptr的大小减半
2. 通过一些车轮因子分解运行数字3,5,7,以便将后续比较减少70%+

这应该加快速度.