более быстрое выполнение суммы (для теста 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% правильности и работоспособности этого кода проверено

Private Function equi(ByVal A() As Integer) As Integer
        Dim index As Integer = -1
        If A.Length > 0 And Not IsDBNull(A) Then
            Dim sumLeft As Long = 0
            Dim sumRight As Long = ArraySum(A)
            For i As Integer = 0 To A.Length - 1
                Dim val As Integer = A(i)

                sumRight -= val
                If sumLeft = sumRight Then
                    index = i
                End If
                sumLeft += val
            Next
        End If

        Return index
    End Function

Answer 2

100% O (n) раствор в C

int equi ( int A[], int n ) {

    long long sumLeft = 0;
    long long sumRight = 0;
    int i;

    if (n <= 0) return -1;

    for (i = 1; i < n; i++)
        sumRight += A[i];
    i = 0;

    do {
        if (sumLeft == sumRight)
            return i;

        sumLeft += A[i];

        if ((i+1) < n)
            sumRight -= A[i+1];
        i++;
    } while (i < n);

    return -1;
}

Вероятно, не идеален, но он все равно проходит свои испытания:)

Не могу сказать, что я большой поклонник Codility - это интересная идея, но я нашел требования слишком расплывчатыми. Я думаю, я был бы более впечатлен, если бы они дали вам требования + набор модульных тестов, которые проверяют эти требования, и затем попросили вас написать код. Так происходит в большинстве случаев. Я не думаю, что делать это вслепую действительно выигрывает что-то кроме разрешения бросать в некоторых угловых случаях.

Answer 3

Я набрал 100% за это:

int equi (int[] A)
{
    if (A == null) return -1;

    long sum0 = 0, sum1 = 0;

    for (int i = 0; i < A.Length; i++) sum0 += A[i];

    for (int i = 0; i < A.Length; i++)
    {
        sum0 -= A[i];
        if (i > 0)
        {
            sum1 += A[i - 1];
        }          
        if (sum1 == sum0) return i;      
    }        
    return -1;
}

Answer 4

private static int equi ( int[] A ) {
    if (A == null || A.length == 0)
     return -1;
 long tot = 0;
 int len = A.length;
 for(int i=0;i<len;i++)
     tot += A[i];
 if(tot == 0)
     return (len-1);
 long partTot = 0;
 for(int i=0;i<len-1;i++)
 {
  partTot += A[i];
  if(partTot*2+A[i+1] == tot)
   return i+1;
 }
 return -1;

}

Я рассматривал массив как баланс, поэтому, если индекс равновесия существует, то половина веса находится слева. Поэтому я сравниваю только partTot (частичное общее) x 2 с общим весом массива. Alg принимает O (n) + O (n)

Answer 5

{In Pascal + Assembly}
{$ASMMODE INTEL}
function equi (A : Array of longint; n : longint ) : longint;
var c:Longint;
    label noOverflow1;
    label noOverflow2;
    label ciclo;
    label fine;
    label Over;
    label tot;
Begin
 Asm
    DEC n
    JS over
    XOR ECX, ECX   {Somma1}
    XOR EDI, EDI   {Somma2}
    XOR EAX, EAX
    MOV c, EDI
    MOV ESI, n
  tot:
    MOV EDX, A
    MOV EDX, [EDX+ESI*4]
    PUSH EDX
    ADD ECX, EDX
    JNO nooverflow1
    ADD c, ECX
    nooverflow1:
    DEC ESI
  JNS tot;
    SUB ECX, c
    SUB EDI, c
  ciclo:
    POP EDX
    SUB ECX, EDX
    CMP ECX, EDI
    JE fine
    ADD EDI, EDX
    JNO nooverflow2
    DEC EDI
    nooverflow2:
    CMP EAX, n
    JA over
    INC EAX
    JMP ciclo
    over:
      MOV EAX, -1
    fine:
  end;
End;

Answer 6

Если вы используете C или C ++ и разрабатываете для современных настольных систем и хотите изучить некоторый ассемблер или узнать о внутренних особенностях GCC, вы можете использовать SIMD инструкции .

Эта библиотека является примером того, что возможно для массивов float и double, аналогичные результаты должны быть возможны для целочисленной арифметики, поскольку в SSE также есть целочисленные инструкции.

Answer 7

Вот мой ответ с объяснениями, как это сделать. Это даст вам 100%

class Solution
{
    public int solution(int[] A)
    {
        long sumLeft = 0;       //Variable to hold sum of elements to the left of the current index
        long sumRight = 0;      //Variable to hold sum of elements to the right of the current index
        long sum = 0;           //Variable to hold sum of all elements in the array
        long leftHolder = 0;    //Variable that holds the sum of all elements to the left of the current index, including the element accessed by the current index

        //Calculate the total sum of all elements in the array and store it in the sum variable
        for (int i = 0; i < A.Length; i++)
        {
            //sum = A.Sum();
            sum += A[i];
        }
        for (int i = 0; i < A.Length; i++)
        {
            //Calculate the sum of all elements before the current element plus the current element
            leftHolder += A[i];
            //Get the sum of all elements to the right of the current element
            sumRight = sum - leftHolder;
            //Get the sum of all elements of elements to the left of the current element.We don't include the current element in this sum
            sumLeft = sum - sumRight - A[i];
            //if the sum of the left elements is equal to the sum of the right elements. Return the index of the current element
            if (sumLeft == sumRight)
                return i;
        }
        //Otherwise return -1
        return -1;
    }
}

Answer 8

Просто подумал, не уверен, что прямой доступ к указателю будет быстрее

    int* pStart = a + begin;
    int* pEnd = a + end;
    while (pStart != pEnd)
    {
        r += *pStart++;
    }

Answer 9

Это дало мне 100% в Javascript:

function solution(A) {
    if (!(A) || !(Array.isArray(A)) || A.length < 1) {
        return -1;
    }

    if (A.length === 1) {
        return 0;
    }

    var sum = A.reduce(function (a, b) { return a + b; }),
        lower = 0,
        i,
        val;

    for (i = 0; i < A.length; i++) {
        val = A[i];
        if (((sum - lower) - val) === (lower)) {
            return i;
        }
        lower += val;
    }

    return -1;
}

Answer 10

Это не поможет вам с алгоритмом O (n ^ 2), но вы можете оптимизировать свою сумму.

В предыдущей компании к нам приходила Intel и давала советы по оптимизации. У них был один неочевидный и несколько крутой трюк. Заменить:

long r = 0; 
for( int i =  begin ; i < end ; i++ ) { 
   r+= a[i]; 
} 

с

long r1 = 0, r2 = 0, r3 = 0, r4 = 0; 
for( int i =  begin ; i < end ; i+=4 ) { 
   r1+= a[i];
   r2+= a[i + 1];
   r3+= a[i + 2];
   r4+= a[i + 3];
}
long r = r1 + r2 + r3 + r4;
// Note: need to be clever if array isn't divisible by 4

Почему это быстрее: В исходной реализации ваша переменная r является узким местом. Каждый раз в цикле вы должны извлекать данные из массива памяти a (который занимает пару циклов), но вы не можете выполнять несколько операций извлечения параллельно, потому что значение r в следующей итерации цикла зависит от значения г в этой итерации цикла. Во второй версии r1, r2, r3 и r4 являются независимыми, поэтому процессор может гипертить их выполнение. Только в самом конце они собираются вместе.