Оптимизировать функцию C ++ для генерации комбинаций - PullRequest
Новая
       4

Оптимизировать функцию C ++ для генерации комбинаций

0 голосов
/ 05 апреля 2020

Я пытаюсь получить функцию для генерации всех возможных комбинаций чисел, но моя проблема в слишком большом времени разработки. Так что я думаю, что должен оптимизировать это. Проблема: Сгенерируйте весь набор размера «r» с элементами от 1 до n, не повторяя его в обратном порядке (1,2 равно 2, 1).

Пример: 

n = 3 //elements: 1,2,3
r = 2 //size of set

Output:
2 3
1 3
1 2

Код, который я использую, следующий: 

    void func(int n, int r){
        vector <vector <int>> reas;
        vector<bool> v(n);
        fill(v.end() - r, v.end(), true);

        int a = 0;
        do {
            reas.emplace_back();
            for (int i = 0; i < n; ++i) {
                if (v[i]) {
                    reas[a].push_back(i+1);
                }
            }
            a++;
        } while (next_permutation(v.begin(), v.end()));
    }

Если n = 3 и r = 2, результат будет таким же, как в примере с верхом. Моя проблема в том, что если я поставлю n = 50 и r = 5, время разработки будет слишком большим, и мне нужно работать с диапазоном n = 50 ... 100 и r = 1..5; Есть ли способ оптимизировать эту функцию?

Спасибо большое

1 Ответ

1 голос
/ 05 апреля 2020

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

Учитывая это, вот вещи, которые вы можете улучшить, не переписывая полностью весь ваш алгоритм.

Сначала : Местонахождение кэша

A vector<vector<T>> не будет смежным. Вложенный вектор довольно мал, поэтому даже с предварительным распределением это всегда будет плохо, и итерация по нему будет медленной, потому что каждый новый субвектор (а их много ), вероятно, вызовет промах кеша.

Следовательно, используйте один vector<T>. Ваше k -ое подмножество будет тогда находиться не в местоположении k, а в k*r. Но это значительное ускорение на моей машине.

Второе: используйте дружественный процессору вектор перестановки

Ваша идея использовать next_permutation неплоха. Но тот факт, что вы используете vector<bool>, делает это чрезвычайно медленным. Как это ни парадоксально, использование vector<size_t> на намного быстрее, потому что легче загрузить size_t и проверить его, чем сделать то же самое с bool.

Так , если вы соберете их вместе, код будет выглядеть примерно так: 

  auto func2(std::size_t n, std::size_t r){
    std::vector<std::size_t> reas;
    reas.reserve((1<<r)*n);
    std::vector<std::size_t> v(n);
    std::fill(v.end() - r, v.end(), 1); 

    do {
      for (std::size_t i = 0; i < n; ++i) {
        if (v[i]) {
          reas.push_back(i+1);
        }
      }   
    } while (std::next_permutation(v.begin(), v.end()));
    return reas;
  }

В-третьих: не помещайте весь результат в один огромный буфер

Используйте обратный вызов для обработки каждого подмножества , Тем самым вам не нужно возвращать один огромный вектор. Вместо этого вы вызываете функцию для каждого отдельного подмножества, которое вы нашли. Если вам действительно нужно иметь один огромный набор, этот обратный вызов может по-прежнему помещать sh подмножеств в вектор, но он также может работать с ними на месте. 

  std::size_t func3(std::size_t n, std::size_t r, 
                    std::function<void(std::vector<std::size_t> const&)> fun){
    std::vector<std::size_t> reas;
    reas.reserve(r);
    std::vector<std::size_t> v(n);
    std::fill(v.end() - r, v.end(), 1);

    std::size_t num = 0;
    do {
      reas.clear(); // does not shrink capacity to 0
      for (std::size_t i = 0; i < n; ++i) {
        if (v[i]) {
          reas.push_back(i+1);
        }
      }
      ++num;
      fun(reas);
    } while (std::next_permutation(v.begin(), v.end()));
    return num;
  }

Это дает ускорение более чем в 2 раза в моих экспериментах. Но скорость возрастает с ростом скорости n и r.

Также: используйте оптимизацию компилятора

Используйте параметры компилятора, чтобы ускорить компиляцию настолько, насколько возможный. В моей системе переход от -O0 к -O1 ускоряется более чем в 10 раз. Переход к -O3 с -O1 намного меньше, но все еще существует (около x1,1).

Не имеет отношения к производительности, но все еще актуально: Почему «используется пространство имен std;» считается плохой практикой?

...