2

what algorithm does array sum uses to make it much faster than some looping through?

Is it prefix sum / suffix sum or something else?

Alma Do
  • 37,009
  • 9
  • 76
  • 105
Ajeet Singh
  • 417
  • 7
  • 23
  • 1
    I must be a linear algorithm too, but intrinsic PHP functions (i.e. all functions available in PHP directly) are executed faster – Gwenc37 Jul 29 '14 at 13:25
  • 1
    Basically the same algorithm that you'd implement if you wrote loop to do it, but it's executing as straight compiled C code, not PHP – Mark Baker Jul 29 '14 at 13:27

3 Answers3

5

Algorithm is plain: just iterate through array and produce summation of elements. That's it. In terms of algorithm there's nothing more that could be said about it. Obviously, you'll have complexity as O(n) for it.

However, PHP array_sum() is a compiled C code, thus, is will be faster than user-land function. Also, if you're interested in how it works internally, you may check array_sum() implementation:

for (zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(input), &pos);
    zend_hash_get_current_data_ex(Z_ARRVAL_P(input), (void **)&entry, &pos) == SUCCESS;
    zend_hash_move_forward_ex(Z_ARRVAL_P(input), &pos)
) {
    if (Z_TYPE_PP(entry) == IS_ARRAY || Z_TYPE_PP(entry) == IS_OBJECT) {
        continue;
    }
    entry_n = **entry;
    zval_copy_ctor(&entry_n);
    convert_scalar_to_number(&entry_n TSRMLS_CC);
    fast_add_function(return_value, return_value, &entry_n TSRMLS_CC);
}

(I've left only loop part itself). There's also fast_add_function() asm optimization, you can check out it's implementation here.

Alma Do
  • 37,009
  • 9
  • 76
  • 105
1

It uses the same algorithm as if you were to write a loop in PHP (that is, the O(n) linear solution), except in most cases since it's native code (written in i.e. C) and not interpreted, it runs directly on the CPU instead of via a virtual machine (which is between 10 and 100 times slower).

kvanbere
  • 3,289
  • 3
  • 27
  • 52
0

It uses Big-O O(n) optimization. You might want to look at this excellent answer here. Also you can check most of this yourself by using software like Eureqa

Community
  • 1
  • 1
raidenace
  • 12,789
  • 1
  • 32
  • 35