Каков самый быстрый способ вычислить e ^ x, если x может быть значением с плавающей запятой.
Прямо сейчас я использовал математическую библиотеку Python для вычисления этого, ниже приведен полный код, где result = -0.490631 + 0.774275 * math.exp(0.474907 * sum) - это основная логика, остальное - это код обработки файлов, который требует вопрос.
import math
import sys
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n // 10
return r
def _print(string):
fo = open("output.txt", "w+")
fo.write(string)
fo.close()
try:
f = open('input.txt')
except IOError:
_print("error")
sys.exit()
data = f.read()
num = data.split('\n', 1)[0]
try:
val = int(num)
except ValueError:
_print("error")
sys.exit()
sum = sum_digits(int(num))
f.close()
if (sum == 2):
_print("1")
else:
result = -0.490631 + 0.774275 * math.exp(0.474907 * sum)
_print(str(math.ceil(result)))
Значение result - это уравнение кривой (которое является решением задачи программирования), которое я получил из wolfarm-mathematica, используя свой собственный набор данных.
Но это, похоже, не соответствует критериям оценки!
Я также пробовал способ Ньютона-Рафсона, но сходимость для больших x вызывает проблему, кроме этого, вычисление натурального журнала ln(x) снова является проблемой!
У меня нет языковых ограничений, поэтому приемлемо любое решение. Кроме того, если математическая библиотека Python самая быстрая, как говорится в некоторых комментариях, то может ли кто-нибудь дать представление о временной сложности и времени выполнения этой программы, короче говоря, об эффективности программы?
Ответ 1 · рейтинг 1 · Yann Vernier
Я не знаю, точна ли математика экспоненциальной кривой в этом коде, но это определенно не медленная точка.
Во-первых, вы читаете входные данные за один вызов read. Его нужно прочитать, но это загружает весь файл. Следующий шаг занимает только первую строку, поэтому будет более уместно использовать readline. Само это разделение равно O(n), где n - это как минимум размер файла, который может включать данные, которые вы игнорировали, поскольку обрабатываете только одну строку.
Во-вторых, вы конвертируете эту строку в int. Это, вероятно, требует поддержки длинных целых чисел Python, но операция может быть O (n) или O (n ^ 2). Алгоритм с одним проходом будет умножать накопленное число на 10 для каждой цифры, каждый раз выделяя одно или два новых (более длинных) значения long.
В-третьих, sum_digits снова разбивает это длинное целое на цифры. Он делает это с помощью дорогостоящего деления и двух операций, а не с помощью divmod. Это O(n^2), потому что каждое деление должно обрабатывать каждую старшую цифру для каждой цифры. И это необходимо только из-за преобразования, которое вы только что сделали.
Суммирование цифр, найденных в строке, вероятно, проще сделать с помощью чего-то вроде sum(int(c) for c in l if c.isdigit()), где l - это строка ввода. Это не особенно быстро, так как при преобразовании цифр возникает довольно много накладных расходов, и сумма может вырасти большой, но это делает один проход с довольно узким циклом; это где-то между O (n) и O (n log n), в зависимости от длины данных, потому что сумма может вырасти сама по себе.
Что касается неизвестной экспоненциальной кривой, настораживает наличие исключения для небольшого числа. Вероятно, есть какой-то другой вариант, который быстрее и точнее, если ответ в любом случае является целым числом.
Наконец, у вас есть как минимум четыре различных формата выходных данных: error, 2, 3.0, 3e+20. Вы знаете, что из этого ожидается? Возможно, вам следует использовать форматированный вывод, а не str для преобразования ваших чисел.
Одно дополнительное замечание: если данные действительно большие, их обработка по частям определенно ускорит процесс (вместо нехватки памяти, необходимости обмена и т. д.). Поскольку вы ищете сумму цифр, сложность вашего размера может быть уменьшена с O (n) до O (log n).
