5

Edit3：通过将数组的初始化限制为仅奇数进行优化。谢谢@罗尼！

Edit2：谢谢大家，看来我对此无能为力了。

编辑：我知道 Python 和 Haskell 是用其他语言实现的，并且或多或少地执行我下面的相同操作，并且编译的 C 代码将在任何一天击败它们。我只是想知道标准 C（或任何库）是否具有更快地执行此操作的内置函数。

我正在使用 Eratosthenes 的算法在 C 中实现一个素筛，并且需要初始化一个任意大小的整数数组n从 0 到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;
}

有一个更好的方法吗？（不，显然没有！）

4

2 回答 2

10

我提出的解决方案初始化数组，然后对其进行迭代，将每个值分配给该点的索引，但感觉非常低效。

您也许可以减少代码行数，但我认为这与“效率”无关。

虽然在 Haskell 和 Python 中只有一行代码，但在底层发生的事情与您的 C 代码所做的事情是一样的（在最好的情况下；根据实现方式，它的性能可能会更差）。

有一些标准库函数可以用常量值填充数组（可以想象它们的性能会更好，尽管我不会打赌），但这不适用于这里。

于 2013-07-23T02:21:16.020 回答
9

在优化分配方面，这里更好的算法可能是更好的选择：-

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

那应该加快速度。

于 2013-07-23T02:30:46.003 回答