более быстрое выполнение суммы (для теста Codility)

Question

Как следующая простая реализация sum может быть быстрее?

private long sum( int [] a, int begin, int end ) {
    if( a == null   ) {
        return 0;
    }
    long r = 0;
    for( int i =  begin ; i < end ; i++ ) {
       r+= a[i];
    }
    return r;
}

РЕДАКТИРОВАТЬ

Фон в порядке.

Читая последнюю запись об ужасах кодирования, я зашел на этот сайт: http://codility.com, в котором есть этот интересный программный тест.

Во всяком случае, я получил 60 из 100 в моем представлении, и в основном (я думаю), потому что это реализация суммы, потому что те части, где я потерпел неудачу, являются частями производительности. Я получаю TIME_OUT_ERROR

Итак, мне было интересно, возможна ли оптимизация алгоритма.

Итак, никакие встроенные функции или сборка не будут разрешены. Это может быть сделано в C, C ++, C #, Java или почти в любом другом.

РЕДАКТИРОВАТЬ

Как обычно, ммерс был прав. Я профилировал код и увидел, что большую часть времени потратил на эту функцию, но я не понял, почему. Так что я сделал, чтобы отбросить мою реализацию и начать с новой.

На этот раз у меня есть оптимальное решение [согласно Сан Хасинто O (n) - см. Комментарии к MSN ниже -]

На этот раз у меня 81% на Codility, что я считаю достаточно хорошим. Проблема в том, что я не взял 30 минут. но около 2 часов. но я думаю, это оставляет меня все еще хорошим программистом, потому что я мог бы работать над проблемой, пока не нашел оптимальное решение:

Вот мой результат.

Я никогда не понимал, что это за "комбинации ..." и как тестировать "extreme_first"

Answer 1

Это может быть старым, но вот решение на Голанге со 100% пропуском:

package solution

func Solution(A []int) int {
    // write your code in Go 1.4
    var left int64
    var right int64
    var equi int

    equi = -1
    if len(A) == 0 {
        return equi
    }

    left = 0
    for _, el := range A {
        right += int64(el)
    }

    for i, el := range A {
        right -= int64(el)
        if left == right {
            equi = i
        }
        left += int64(el)
    }

    return equi
}

Answer 2

В C ++ следующее:

int* a1 = a + begin;
for( int i = end - begin - 1; i >= 0 ; i-- )
{
    r+= a1[i];
}

может быть быстрее. Преимущество в том, что мы сравниваем с нулем в цикле.

Конечно, с действительно хорошим оптимизатором не должно быть никакой разницы.

Другая возможность будет

int* a2 = a + end - 1;
for( int i = -(end - begin - 1); i <= 0 ; i++ )
{
    r+= a2[i];
}

здесь мы проходим предметы в том же порядке, только не по сравнению с end.