Самый быстрый способ вычислить e^x?

Каков самый быстрый способ вычислить 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 самая быстрая, как говорится в некоторых комментариях, то может ли кто-нибудь дать представление о временной сложности и времени выполнения этой программы, короче говоря, об эффективности программы?


python optimization mathematical-optimization
person CMouse    schedule 07.06.2017    source источник
comment
В чем вопрос? math.exp действительно вычисляет e^x настолько быстро, насколько это возможно (обычно он использует ваш процессор с плавающей запятой, а затем оборачивает результат как число с плавающей запятой Python), но это, конечно, не полный пример (sum — это функция), и мы не не знаю, что терпит неудачу (тест не описан). Тогда ни с того ни с сего возник вопрос о побитовых операциях, которые редко смешиваются с операциями с плавающей запятой. Если у вас есть работающий код, вряд ли это будет тот уровень, на котором может помочь оптимизация.   -  person Yann Vernier    schedule 07.06.2017
comment
Большинство автоматических инструментов проверки кода проверяют соответствие временной сложности вашего алгоритма заданным критериям, а не абсолютному времени выполнения. Переосмыслите свой алгоритм как законченное решение, не сосредотачивайтесь на микрооптимизациях.   -  person Łukasz Rogalski    schedule 07.06.2017
comment
Вы запрашиваете на питоне, а затем говорите, что у вас нет языковых ограничений. Хм?   -  person Stefan Pochmann    schedule 07.06.2017
comment
@ ŁukaszRogalski result = -0.490631 + 0.774275 * math.exp(0.474907 * sum) - единственная логика, а result - ответ, так какова временная сложность, я полагаю, O (n), но тогда почему контрольный код помечает его как плохой?   -  person CMouse    schedule 08.06.2017
comment
Как я могу описать тест, который я не знаю? Как я уже говорил вам, онлайн-соревнования по кодированию не говорят вам обо всем этом, они просто дают вам результат как хороший, плохой, средний, ниже среднего @YannVernier   -  person CMouse    schedule 08.06.2017

Ответы (1)


arrow_upward
1
arrow_downward

Я не знаю, точна ли математика экспоненциальной кривой в этом коде, но это определенно не медленная точка.

Во-первых, вы читаете входные данные за один вызов 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).

person Yann Vernier    schedule 08.06.2017
comment
Похоже, введенные произвольные константы являются вариантом формулы Бине для чисел Фибоначчи. Исключение, закодированное в , нарушает последовательность на ранней стадии, и ограниченная точность чисел с плавающей запятой может сыграть роль, если мы ожидаем, что программа будет тестироваться на больших входных данных. - person Yann Vernier; 08.06.2017
comment
В качестве вывода ожидается целое число, поэтому используется math.ceil(). Буду признателен за оптимизированный код на выбранном вами языке - person CMouse; 08.06.2017
comment
Тогда он почти наверняка ожидает точное число. Вам следует вообще отказаться от использования операций с плавающей запятой и выполнять вычисления Фибоначчи в длинных позициях. Тем не менее, может быть полезно сделать это за меньшее количество шагов, чем сумма; одна идея - один раз на цифру с матрицами того, сколько раз F (i-n) и F (i-n-1) включены. Эту концепцию можно было бы реализовать и один раз для каждого блока, но небольшой диапазон цифр делает справочную таблицу практичной. - person Yann Vernier; 08.06.2017
comment
Я использовал mathematica, чтобы найти уравнение кривой, пожалуйста, обратитесь к ссылке, которую я использовал, чтобы найти уравнение кривой и продолжить дальнейшие действия mathematica.stackexchange.com/questions/147456/ входными данными являются значения, которые я нашел при кодировании задачи, но поскольку Я использовал в нем рекурсию, стек переполнялся, поэтому мне пришлось найти общий способ найти его для большего n. - person CMouse; 08.06.2017
comment
Спасибо, я пропустил ту часть, что набор входных данных создает ряд Фибоначчи, я нашел код для вычисления f(n) за время O(log n). - person CMouse; 08.06.2017
comment
Задача, вероятно, предполагает, что вы преобразуете эту рекурсию с двумя вызовами в итерацию с двумя переменными. - person Yann Vernier; 08.06.2017