Почему статическая инициализация значительно улучшает время выполнения по сравнению с инициализацией конструктора в C ++ ⇐ C++

[Anonymous]

Я реализовал две версии решения для следующей задачи LeetCode:
максимальные и минимальные суммы при последующих размерах k < br/>
Учитывая целочисленные массивы nums и положительное целое число k , верните сумму максимальных и минимальных элементов всех последствий Nums с максимума k элементы. Поскольку результат может быть большим, вернуть It Modulo 10^9 + 7 .

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

[*] code 1 (инициализация на основе конструктора) занимает ~ 2000 мс. < /p>
< /li>

Код 2 (статическая инициализация) занимает только ~ 30 мс (~ 66x ускорение). < /P>
< /li>
< /ul>
код 1: на основе конструктора Инициализация (~ 2000 мс) < /h3>
class Solution {
private:
const int mod = 1e9 + 7;
const int MX = 1e5 + 1;
vector F, REC_F;

public:
Solution() {
F.resize(MX);
REC_F.resize(MX);
F[0] = 1;
for (int i = 1; i < MX; ++i) {
F = F * i % mod;
}
REC_F[MX - 1] = power(F[MX - 1], mod - 2);
for (int i = MX - 2; i >= 0; --i) {
REC_F = REC_F[i + 1] * (i + 1) % mod;
}
}

int minMaxSums(vector& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long ans = 0, s = 1;

for (int i = 0; i < n; ++i) {
ans = (ans + s * (nums + nums[n - 1 - i])) % mod;
s = (2 * s - comb(i, k - 1) + mod) % mod;
}
return ans;
}

long long comb(int n, int m) {
return n < m ? 0 : F[n] * REC_F[m] % mod * REC_F[n - m] % mod;
}

long long power(long long x, int n) {
long long ans = 1;
for (; n > 0; n /= 2) {
if (n % 2) ans = (ans * x) % mod;
x = (x * x) % mod;
}
return ans;
}
};

< /code>
код 2: статическая инициализация (~ 30 мс, ~ 66x быстрее) < /h3>
const int mod = 1'000'000'007;
const int MX = 100'000;
long long F[MX]; // Factorial
long long REC_F[MX]; // Inverse Factorial

long long power(long long x, int n) {
long long ans = 1;
for (; n > 0; n /= 2) {
if (n & 1) ans = (ans * x) % mod;
x = (x * x) % mod;
}
return ans;
}

auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; ++i) {
F = F * i % mod;
}
REC_F[MX - 1] = power(F[MX - 1], mod - 2);
for (int i = MX - 2; i >= 0; --i) {
REC_F = REC_F[i + 1] * (i + 1) % mod;
}
return 0;
}();

class Solution {
public:
int minMaxSums(vector& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long ans = 0, s = 1;

for (int i = 0; i < n; ++i) {
ans = (ans + s * (nums + nums[n - 1 - i])) % mod;
s = (2 * s - comb(i, k - 1) + mod) % mod;
}
return ans;
}

long long comb(int n, int m) {
return n < m ? 0 : F[n] * REC_F[m] % mod * REC_F[n - m] % mod;
}
};

< /code>

наблюдения и вопросы < /h3>

код 1 (инициализация на основе конструктора на основе конструктора ) значительно медленнее (~ 2000 мс).

код 2 (статическая инициализация) на ~ 66x быстрее (~ 30 мс).
< /li>
< /ul>
Однако на моей локальной машине (VS Compiler) оба запускаются примерно за 30 секунд с тестовыми данными: < /p>
vector nums(1e5, 1e9);
int k = 70;
< /code>
Почему LeetCode показывает огромную разницу, но локально время выполнения аналогичны? P> Я хотел бы понять, почему такая радикальная разница происходит между LeetCode и My Local Machine: < /p>

LeetCode создает несколько решений < /код > экземпляры для тестового примера? >
< /li>
Есть ли модель оптимизации или выполнения компилятора, которая вызывает такое поведение? < /p>

Оптимизирует ли компилятор LeetCode статическую инициализацию по -разному? /p>

Статические переменные сохраняются в тестовых случаях. Может ли это повысить эффективность на LeetCode? < /Li>
< /ul>
< /li>
< /ol>
Модели выполнения влияют на производительность времени выполнения в C ++.

Подробнее здесь: https://stackoverflow.com/questions/793 ... -construct