С++: самый быстрый способ проверить, равны ли все элементы массива

Ответ 1

int check(const int a[], int n)
{   
    while(--n>0 && a[n]==a[0]);
    return n!=0;
}

Ответ 2

Как только вы обнаружите несоответствующий элемент, вы можете выйти из цикла:

bool check(const int array[], int n)
{   
    for (int i = 0; i < n - 1; i++)      
    {         
        if (array[i] != array[i + 1])
            return true;
    }
    return false;
}

Если это критически важно для производительности, его можно немного оптимизировать, например:

bool check(const int array[], int n)
{   
    const int a0 = array[0];

    for (int i = 1; i < n; i++)      
    {         
        if (array[i] != a0)
            return true;
    }
    return false;
}

Ответ 3

Вот твердое решение, которое действительно С++ 11. Преимущества в том, что вам не нужно вручную играть с индексами или итераторами. Лучше всего использовать

предпочитает вызов алгоритмов для рукописных циклов [Herb Sutter - стандарты кодирования С++]

Я думаю, что это будет столь же эффективно, как и решение Paul R.

bool check(const int a[], int n)
{
      return !std::all_of(a, a+n, [a](int x){ return x==a[0]; });
}

Ответ 4

Восстановите массив до более крупного типа данных. Например, работайте на 64-битных ints или используйте SSE или AVX-функции для работы с 128 или 256 бит. Например, собственный SSE2 - _mm_cmpeq_epi32, результат которого вы будете использовать с _mm_or_si128. Проверьте результат с повторным применением _mm_srli_si128 и _mm_cvtsi128_si32. Проверьте результат каждые несколько сотен итераций для раннего выхода.

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

Ответ 5

Мы будем в основном выполнять операцию O (n), чтобы вы не могли сделать намного лучше, чем у вас, кроме того, что не доставляли флаг и просто return false; при первом сбое и return true; после итерации.

Ответ 6

bool check(int array[],int n)
{       
  // here 1st element is checked with others. This decreases the number of iteration by 1.
  // also it returns immediately. 
  // The requirement is to check if all the elements are equal. 
  // So if 1st element is equal to others then all elements are equal. 
  // Otherwise the  elements are not equal.
  for(int i=1;i<n;i++)      
  {         
    if(array[0]!=array[i])
      return false;
  }        
  return true;
}

Ответ 7

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

Ниже перечислены некоторые доступные библиотеки:

http://parallel-for.sourceforge.net/parallelfor.html

Или, возможно, вы можете использовать параллизм, который предлагают многие GPU.

Ответ 8

В теории я бы предложил следующее:

bool check_single(const int a[], int n)
{
    for (int i = 1; i < n; ++i) {
        if (a[0] != a[n]) { return false; }
    }
    return true;
}

По сравнению с другими (уже предложенными) версиями:

• a[0] будет выведен за пределы цикла компилятором, что означает доступ к одному массиву в цикле
• мы зацикливаем от 0 до n, что лучше (с точки зрения доступа), чем загрузка a[0], а затем цикл из a[n]

Очевидно, он по-прежнему проверяет N элементов и, следовательно, O (N).

Ответ 9

Для эффективности программиста вы можете попробовать следующее в одной строке.

vector<int> v{1, 1, 1, 1};
all_of(v.cbegin(), v.cend(), [&r=v[0]](int value){ return value == r; }->bool);

Я не тестировал этот код, сообщите мне, есть ли синтаксическая ошибка.

Ответ 10

bool check_identity (int a[], int b[], const int size)
{
    int i;
    i = 0;
    while ((i < size-1) && (a[i] == b[i]))   i++;

    return (a[i] == b[i]);

}