Оптимизация на огромном наборе ввода
Мне нужно найти ПОДВЕДЕНИЕ из Si * Ci (для i в диапазоне от 1 до n).
Ниже приведены ограничения:
1 ≤ n ≤ 10 ^ 6
1 ≤ si ≤ 10 ^ 6
1 ≤ ci ≤ 10 ^ 6
Вот мой код
<?php
for($i = 0; $i < $n; $i++){
$total += ($s[$i] * $c[$i]);
}
?>
Однако в коде не хватает времени для высоких входных значений (до 10 ^ 6).
Как добавить такие огромные числа с правильными методами оптимизации, не превышая время выполнения.
Решение
Вы можете увеличить максимальное время выполнения, используя set_time_limit
Узнайте больше здесь: http://php.net/manual/en/function.set-time-limit.php
set_time_limit — ограничивает максимальное время выполнения
bool set_time_limit (int $ секунд)
Если вы установите его на ноль, он будет работать вечно, пока скрипт не завершит выполнение или не прервется вручную. Поместите это вверху вашего скрипта, чтобы сделать это:
set_time_limit(0);
Обновить:
Используйте язык, отличный от PHP.
Другие решения
Есть несколько аспектов, о которых вы должны позаботиться:
Эти операции могут занять много времени, поэтому вам нужно изменить ограничение времени запроса:
set_time_limit(0);
PHP предлагает некоторые функции отображения / уменьшения для таких операций. Один array_map() а другой array_reduce()
function multiply($s, $c) {
return $s * $c;
}
function sum($carry, $item)
{
$carry += $item;
return $carry;
}$result = array_reduce(array_map('multiply', $s, $c), 'sum');
Конечно, вы можете использовать анонимные функции в качестве обратных вызовов.
В зависимости от ваших данных вы должны позаботиться о проблемах производительности / точности. В этом случае взгляните на bcmath расширение и bcmul() bcadd() функции.