what algorithm does array sum uses to make it much faster than some looping through?
Is it prefix sum / suffix sum or something else?
-
1I must be a linear algorithm too, but intrinsic PHP functions (i.e. all functions available in PHP directly) are executed fasterGwenc37– Gwenc372014-07-29 13:25:17 +00:00Commented Jul 29, 2014 at 13:25
-
1Basically the same algorithm that you'd implement if you wrote loop to do it, but it's executing as straight compiled C code, not PHPMark Baker– Mark Baker2014-07-29 13:27:48 +00:00Commented Jul 29, 2014 at 13:27
Add a comment
|
2 Answers
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.
1 Comment
kvanbere
You win, master ninja.
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).
