Более быстрая реализация суммы (для теста Codility)

Ответ 1

Я не думаю, что ваша проблема связана с функцией суммирования массива, возможно, вы часто суммируете массив WAY. Если вы просто суммируете массив WHOLE один раз, а затем переходите через массив до тех пор, пока не найдете первую точку равновесия, вы должны достаточно уменьшить время выполнения.

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

    long lower = 0;
    long upper = 0;
    foreach (int i in A)
        upper += i;

    for (int i = 0; i < A.Length; i++)
    {
        upper -= A[i];
        if (upper == lower)
        {
            equi = i;
            break;
        }
        else
            lower += A[i];
    }

    return equi;
}

Ответ 2

Вот мое решение, и я набрал 100%

 public static int solution(int[] A)
    {
        double sum = A.Sum(d => (double)d);
        double leftSum=0;
        for (int i = 0; i < A.Length; i++){
            if (leftSum == (sum-leftSum-A[i])) {
                return i;
            }
            else {
                leftSum = leftSum + A[i];
            }
        }
        return -1;
    }

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

4999912596452418 → 233ms (sum)

4999912596452418 → 126ms (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;
    }

Ответ 9

Я сделал ту же самую наивную реализацию, и вот мое решение 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;
        }
    }
}

Ответ 10

Вот мысль:

private static ArrayList equi(int[] A)
{
    ArrayList answer = new ArrayList();

    //if(A == null) return -1; 
    if ((answer.Count == null))
    {
        answer.Add(-1);
        return answer;
    }

    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) answer.Add(i);
    //return i;
    }
    //return -1;
    return answer;
}

Ответ 11

В С++:

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.

Ответ 12

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

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

Ответ 13

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

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

Ответ 14

Это не поможет вам с алгоритмом 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 независимы, поэтому процессор может ускорить их выполнение. Только в самом конце они собираются вместе.

Ответ 15

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

Ответ 16

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)

Ответ 17

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, хотя - это интересная идея, но я нашел требования слишком расплывчатыми. Я думаю, я был бы более впечатлен, если бы они предоставили вам требования + набор модульных тестов, которые проверяют эти требования, а затем попросят написать код. То, как большинство TDD происходит в любом случае. Я не думаю, что делать это слепое действительно получает что-то другое, кроме как позволять им бросать в некоторые угловые случаи.

Ответ 18

Проверена 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

Ответ 19

Это обеспечило мне 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;
}

Ответ 20

Вот мой ответ с объяснениями о том, как это сделать. Он получит 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;
    }
}

Ответ 21

Я забил 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;
}

Ответ 22

Это может быть старым, но вот решение в Голанге со скоростью 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
}