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

Я проделал ту же простую реализацию, и вот мое решение O (n). Я не использовал метод IEnumerable Sum, потому что он не был доступен в Codility. Мое решение по-прежнему не проверяет переполнение, если входные данные имеют большие числа, поэтому он не проходит этот конкретный тест на Codility.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new[] {-7, 1, 5, 2, -4, 3, 0};
            Console.WriteLine(equi(list));
            Console.ReadLine();
        }

        static int equi(int[] A)
        {
            if (A == null || A.Length == 0)
                return -1;

            if (A.Length == 1)
                return 0;

            var upperBoundSum = GetTotal(A);
            var lowerBoundSum = 0;
            for (var i = 0; i < A.Length; i++)
            {
                lowerBoundSum += (i - 1) >= 0 ? A[i - 1] : 0;
                upperBoundSum -= A[i];
                if (lowerBoundSum == upperBoundSum)
                    return i;
            }
            return -1;
        }

        private static int GetTotal(int[] ints)
        {
            var sum = 0;
            for(var i=0; i < ints.Length; i++)
                sum += ints[i];
            return sum;
        }
    }
}

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

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

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

Вероятно, самое быстрое, что вы могли бы получить, - это выровнять 16-байтовый массив int, разделить 32 байта на две __ m128i переменных (VC ++) и вызвать _mm_add_epi32 (опять же, VC ++ intrinsic) на кусках. Повторно используйте один из фрагментов, чтобы продолжать добавлять в него, а на последнем фрагменте извлеките четыре целых и добавьте их старомодным способом.

Более важный вопрос заключается в том, почему простое добавление является достойным кандидатом для оптимизации.

Редактировать: Я вижу, что это в основном академическое упражнение. Возможно, я попробую завтра и опубликую результаты ...

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

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

В 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.

В C# 3.0, моем компьютере и моей ОС это происходит быстрее до тех пор, пока вы можете гарантировать, что 4 последовательных числа не переполнят диапазон int, вероятно, потому что большинство сложений выполняется с использованием 32-битной математики. Однако использование лучшего алгоритма обычно дает большее ускорение, чем любая микрооптимизация.

Время для массива из 100 миллионов элементов:

4999912596452418 -> 233мс (sum)

4999912596452418 -> 126мс (sum2)

    private static long sum2(int[] a, int begin, int end)
    {
        if (a == null) { return 0; }
        long r = 0;
        int i = begin;
        for (; i < end - 3; i+=4)
        {
            //int t = ;
            r += a[i] + a[i + 1] + a[i + 2] + a[i + 3];
        }
        for (; i < end; i++) { r += a[i]; }
        return r;
    }

Это не поможет вам с алгоритмом 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 в следующей итерации цикла зависит от значения r в этой итерации цикла. Во второй версии r1, r2, r3 и r4 независимы, поэтому процессор может выполнять гиперпоточное выполнение. Только в самом конце они объединяются.

Некоторые советы:

• Используйте профилировщик, чтобы определить, на что вы проводите много времени.

• Напишите хорошие тесты производительности, чтобы вы могли точно определить эффект каждого внесенного вами изменения. Делайте аккуратные записи.

• Если выясняется, что узким местом является проверка того, что вы разыменовываете юридический адрес внутри массива, и вы можете гарантировать, что начало и конец фактически находятся внутри массива, то подумайте о том, чтобы исправить массив, сделав указатель на массив и выполнение алгоритма в указателях, а не в массивах. Указатели небезопасны; они не тратят время на проверку, чтобы убедиться, что вы все еще внутри массива, поэтому они могут быть несколько быстрее. Но вы берете на себя ответственность за то, чтобы не повредить каждый байт памяти в адресном пространстве.

Если это основано на реальной задаче-образце, ваша проблема не в сумме. Ваша проблема в том, как вы вычисляете индекс равновесия. Наивная реализация - это O(n^2). Оптимальное решение намного лучше.

Этот код достаточно прост, если только a довольно маленький, вероятно, он будет ограничен в первую очередь пропускной способностью памяти. Таким образом, вы, вероятно, не можете надеяться на какой-либо значительный выигрыш, работая над самой частью суммирования (например, разворачивая цикл, обратный отсчет вместо увеличения, выполнение сумм параллельно - если только они не находятся на отдельных процессорах, каждый со своим собственный доступ к памяти). Самый большой выигрыш, вероятно, будет получен от выполнения некоторых инструкций предварительной загрузки, поэтому большая часть данных уже будет в кеше к тому времени, когда вам это понадобится. Остальное просто (в лучшем случае) заставит ЦП поторопиться, так что он будет ждать дольше.

Редактировать: Похоже, что большая часть того, что выше, не имеет ничего общего с реальным вопросом. Он небольшой, поэтому его трудно читать, но я попытался просто использовать std :: accumulate () для начального добавления, и мне показалось, что все в порядке:

{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;

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)