более быстрая реализация суммы (для теста 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's

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

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

EDIT

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

На этот раз я получил оптимальное решение [в соответствии с San Jacinto O (N) -смом комментариев к MSN ниже -]

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

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

my result on codility http://img534.imageshack.us/img534/6804/codility.png

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

Answer 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; 
} 

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.

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

4999912596452418 -> 233ms (сумма)

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

Answer 10

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

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

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

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

Answer 11

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

Answer 12

Это не поможет вам с O алгоритма (п^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 

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

Answer 13

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

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; 

}

Я рассматривал массив как Bilance так, если индекс равновесия существует, то половина веса находится на левой стороне. Поэтому я сравниваю только partTot (частичное полное) x 2 с общим весом массива. АЛГ занимает O (N) + O (п)

Answer 15

Я набрал 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 16

Вот это мысль:

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

Answer 17

100% O (п) решение в 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. Я не думаю, что делать это слепое действительно получает что-то другое, кроме как позволить им бросить в некоторые угловые случаи.

Answer 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 

Answer 19

Вот мое решение, и я набрал 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; 
    } 

Answer 20

Это у меня на 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 21

Вот мой ответ с объяснениями о том, как это сделать. Это поможет вам 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 22

Это может быть старым, но здесь решение в Golang со скоростью пропускания 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 
}