более быстрое выполнение суммы (для теста Codility) - PullRequest
11 голосов
/ 26 февраля 2010

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

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

my result on codility

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

Ответы [ 22 ]

6 голосов
/ 26 февраля 2010

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

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;
}
6 голосов
/ 12 июня 2015

Вот мое решение, и я набрал 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;
    }
5 голосов
/ 26 февраля 2010

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

5 голосов
/ 26 февраля 2010

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

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

Codility Results

3 голосов
/ 26 февраля 2010

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

3 голосов
/ 26 февраля 2010

Несколько советов:

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

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

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

2 голосов
/ 26 февраля 2010

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

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

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

1 голос
/ 26 февраля 2010

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

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

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

4999912596452418 -> 126 мс (сумма2)

    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;
    }
1 голос
/ 26 февраля 2010

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

Codility Results

1 голос
/ 15 февраля 2011

Вот мысль:

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;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...