Блог

Обновление: Программы на C (как показано ниже) были скомпилированы без дополнительных флагов, т.Е. g program.cpp . Однако повышение уровня оптимизации не меняет того факта, что перебор выполняется быстрее, чем метод запоминания (0,1 секунды ПРОТИВ 1 секунды на моей машине).

Контекст

Я пытаюсь вычислить число (< 1 миллиона) с помощью самой длинной последовательности Collatz. Я написал алгоритм грубой силы и сравнил его с предложенной оптимизированной программой (которая в основном использует запоминание).

Мой вопрос: что может быть причиной того, что грубая сила выполняется быстрее, чем предположительно оптимизированная версия (memoization) на C ?

Ниже приведены сравнения, которые у меня есть на моем компьютере (Macbook Air); время указано в начале программного кода в комментариях.

C (перебор)

 /**
 * runs in 1 second
 */

#include <iostream>
#include <vector>

unsigned long long nextSequence(unsigned long long n)
{
  if (n % 2 == 0)
    return n / 2;
  else
  {
    return 3 * n   1;
  }
}

int main()
{
  int max_counter = 0;
  unsigned long long resu<
  for (size_t i = 1; i < 1000000; i  )
  {
    int counter = 1;
    unsigned long long n = i;
    while (n != 1)
    {
      n = nextSequence(n);
      counter  ;
    }
    if (counter > max_counter)
    {
      max_counter = counter;
      result = i;
    }
  }

  std::cout << result << " has " << max_counter << " sequences." << std::endl;

  return 0;
}
  

C (запоминание)

 /**
 * runs in 2-3 seconds 
 */

#include <iostream>
#include <unordered_map>

int countSequence(uint64_t n, std::unordered_map<uint64_t, uint64_t> amp;cache)
{
  if (cache.count(n) == 1)
    return cache[n];

  if (n % 2 == 0)
    cache[n] = 1   countSequence(n / 2, cache);
  else
    cache[n] = 2   countSequence((3 * n   1) / 2, cache);

  return cache[n];
}

int main()
{
  uint64_t max_counter = 0;
  uint64_t resu<
  std::unordered_map<uint64_t, uint64_t> cache;
  cache[1] = 1;
  for (uint64_t i = 500000; i < 1000000; i  )
  {
    if (countSequence(i, cache) > max_counter)
    {
      max_counter = countSequence(i, cache);
      result = i;
    }
  }

  std::cout << result << std::endl;

  return 0;
}
  

В Python техника запоминания действительно выполняется быстрее.

Python (запоминание)

 # runs in 1.5 seconds

def countChain(n):
    if n in values:
        return values[n]
    if n % 2 == 0:
        values[n] = 1   countChain(n / 2)
    else:
        values[n] = 2   countChain((3 * n   1) / 2)
    return values[n]


values = {1: 1}
longest_chain = 0
answer = -1

for number in range(500000, 1000000):
    if countChain(number) > longest_chain:
        longest_chain = countChain(number)
        answer = number

print(answer)
  

Python (грубая сила)

 # runs in 30 seconds


def countChain(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1   countChain(n / 2)
    return 2   countChain((3 * n   1) / 2)


longest_chain = 0
answer = -1

for number in range(1, 1000000):
    temp = countChain(number)
    if temp > longest_chain:
        longest_chain = temp
        answer = number

print(answer)
  

Я понимаю, что ваш вопрос касается разницы между двумя вариантами C , а не между скопированным C и интерпретируемым python. Для решающего ответа на этот вопрос потребовалось бы скомпилировать код с включенной оптимизацией и профилировать его выполнение. И ясность в отношении того, является ли целевой файл компилятора 64 или 32 битным.

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

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

Теперь, если вы добавите следующую инструкцию сразу после инициализации кэша и непосредственно перед отображением результата, вы увидите, что происходит огромное изменение в количестве выделенных сегментов:

 std::cout << "Bucket count: "<<cache.bucket_count()<<"/"<<cache.max_bucket_count()<<std::endl; 
  

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

 std::unordered_map<uint64_t, uint64_t> cache(3000000);
  

Выполнение этого в ideone для небольшого и неформального теста сэкономило почти 50% производительности.

Но безрезультатно… Хранение и поиск объектов в unordered_map требует вычисления хэш-кодов, состоящих из множества арифметических операций. Поэтому я предполагаю, что эти операции просто тяжелее, чем выполнение вычислений методом перебора.

Доступ к основной памяти значительно медленнее вычислений, настолько, что, когда приходит время позаботиться, вы должны обрабатывать все, что занимает очень мало (зависит от модели процессора) мегабайт, как извлеченное с устройства ввода-вывода или сетевого устройства.

Даже выборка из L1 обходится дорого по сравнению с целочисленными операциями.

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

Итак, люди подсчитали операции процессора и просто предположили, что память может более или менее соответствовать.

В настоящее время это просто … не может. Штраф за промах в кэше процессора составляет сотни операций с целыми числами, и ваша хэш-карта с 16 миллионами байтовых записей практически гарантированно уничтожает не только кэши памяти процессора, но и TLB, что превращает штраф за задержку из болезненного в разрушительный.