论坛 › Python交流 › 如何优化此代码，当N非常大时，程序运行时间不能超过2s

我邪魅一笑 发表于 2022-10-23 16:08:16

如何优化此代码，当N非常大时，程序运行时间不能超过2s

编写程序求11/2-21/2+31/2-41/2+...+N1/2
    n=int(input())
    s=0
    i=1
    for i in range(1,n+1):
      if i%2==1:
            s+=i**0.5
      else:
            s-=i**0.5
    print(f'{s:.6f}')

jackz007 发表于 2022-10-23 16:14:21

       这个如何？
n , s , k = int(input()) , 0 , 1
for i in range(1 , n + 1) :
    s , k = s + k * i ** 0.5 , -k
print(f'{s:.6f}')

我邪魅一笑 发表于 2022-10-23 16:21:36

jackz007 发表于 2022-10-23 16:14
这个如何？

还是超了2s{:10_266:}

jackz007 发表于 2022-10-23 16:24:03

我邪魅一笑 发表于 2022-10-23 16:21
还是超了2s

      这还能有什么好办法？也许改用数学库可以快一点？
import math
n , s , k = int(input()) , 0 , 1
for i in range(1 , n + 1) :
    s , k = s + k * math . sqrt(i) , -k
print(f'{s:.6f}')

tommyyu 发表于 2022-10-23 16:25:34

这个可以么
n = int(input())
print(sum((i**0.5)*((-1)**(i+1)) for i in range(1, n+1)))

我邪魅一笑 发表于 2022-10-23 16:25:59

jackz007 发表于 2022-10-23 16:24
这还能有什么好办法？也许改用数学库可以快一点？

比刚才那个还慢了点{:10_250:}

我邪魅一笑 发表于 2022-10-23 16:30:24

jackz007 发表于 2022-10-23 16:14
这个如何？

还是超时了{:10_250:}

jackz007 发表于 2022-10-23 16:44:03

我邪魅一笑 发表于 2022-10-23 16:30
还是超时了

      用 numpy . sqrt() 试试看
import numpy as np

n , s , k = int(input()) , 0 , 1
for i in range(1 , n + 1) :
    s , k = s + k * np . sqrt(i) , -k
print('%.6f' % s)

tommyyu 发表于 2022-10-23 16:54:05

没看到要保留6位小数{:10_266:}
这个可以么n = int(input())
print("{:.6f}".format(sum((i**0.5)*((-1)**(i+1)) for i in range(1, n+1))))

傻眼貓咪 发表于 2022-10-23 17:42:57

用 C 可能比较快，Python 想优化只能从数学知识下手了

人造人 发表于 2022-10-24 10:27:08

8个9，一个是2秒多，一个是20秒多，差不多10倍

sh-5.1$ ls
main.pyn.cn.py
sh-5.1$ cat main.py
#!/usr/bin/env python
#coding=utf-8

n=int(input())
s=0
i=1
for i in range(1,n+1):
    if i%2==1:
      s+=i**0.5
    else:
      s-=i**0.5
print(f'{s:.6f}')
sh-5.1$ cat n.py
#!/usr/bin/env python
#coding=utf-8

import ctypes

dll = ctypes.cdll.LoadLibrary('./n.so')
dll.get_n.restype = ctypes.c_double
print(dll.get_n())
sh-5.1$ cat n.c
#include <stdio.h>
#include <math.h>

double get_n(void) {
    size_t n; scanf("%zu", &n);
    double s = 0;
    for(size_t i = 1; i <= n; ++i) {
      double x = pow(i, 0.5);
      s += i % 2 == 0 ? -x : x;
    }
    return s;
}
sh-5.1$ gcc -O3 -g -Wall -shared -o n.so n.c
sh-5.1$ ls
main.pyn.cn.pyn.so
sh-5.1$ file n.so
n.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID=d1b953da2900940d00f2e88bccc7030d706cf4cf, with debug_info, not stripped
sh-5.1$ time ./main.py <<EOF
> 99999999
> EOF
5000.380092

real        0m20.452s
user        0m20.384s
sys        0m0.024s
sh-5.1$ time ./n.py <<EOF
99999999
EOF
5000.380092309442

real        0m2.093s
user        0m2.077s
sys        0m0.010s
sh-5.1$

人造人 发表于 2022-10-27 02:43:24

花了几天时间，现学现卖，用64位汇编语言写了一遍
9个9，c要21秒多，汇编语言要2秒多
21.080 / 2.429 = 8.678
8.678 倍

20.384 / 2.077 = 9.814
c和python是 9.814 倍
什么概念呢？就是说汇编语言算2秒，python要算170多秒，就是这个概念，^_^
没有多次运行取平均值什么的，就是简单的看了看
汇编语言版本的是真的不好写
到此为止了，不玩了

sh-5.1$ ls
main.c        main.s        old
sh-5.1$ cat main.c
#include <stdio.h>
#include <math.h>

double get_n(void) {
    size_t n; scanf("%zu", &n);
    double s = 0;
    for(size_t i = 1; i <= n; ++i) {
      double x = pow(i, 0.5);
      s += i % 2 == 0 ? -x : x;
    }
    return s;
}

int main(void) {
    printf("%f\n", get_n());
    return 0;
}
sh-5.1$ cat main.s
    .section .text
    .global _start
_start:
    # 调用read系统调用
    # 从标准输入读取一个数字，是字符串类型的
    # 存储到buff中
    movq    $0, %rax            # sys_read
    movq    $0, %rdi            # stdin
    leaq    buff(%rip), %rsi    # buff
    movq    $1024, %rdx         # count
    syscall

    # 下面把buff中的字符串转换成数字
    decq    %rax      # '\n'
    movq    %rax, %rcx
    xorq    %rax, %rax
    movq    $10, %rdi
1:mulq    %rdi            # rax *= 10
    movzbq(%rsi), %rdx    # dl = *(%rsi)
    incq    %rsi
    subq    $'0', %rdx
    addq    %rdx, %rax
    decq    %rcx
    cmpq    $0, %rcx
    jg      1b
    movq    %rax, %r8

    # 下面计算表达式的值
    movq    $1, %rcx
    fldz
2:movq    %rcx, temp(%rip)
    fildq   temp(%rip)
    fsqrt               # i的0.5次方就是对i开方
    fst   %st(2)
    fchs
    testq   $1, %rcx
    fcmovne %st(2), %st(0)
    faddp
    incq    %rcx
    cmpq    %r8, %rcx
    jng   2b
    ffree   %st(1)

    # 下面把计算结果转换成字符串
    # 首先判断浮点数是不是负数
    # 如果是负数的话，要在字符串最前面加 '-'
    leaq    buff(%rip), %rsi
    movb    $'-', (%rsi)
    leaq    1(%rsi), %rax
    fldz
    fcomip%st(1), %st(0)
    cmovaq%rax, %rsi

    # 然后把整数部分和小数部分分开
    fld   %st(0)
    fisttpq temp(%rip)
    fildq   temp(%rip)
    fsubrp
    fabs
    fildq   temp(%rip)
    fabs

    # 接下来处理整数部分
3:fld   %st(0)
    movq    $10, temp(%rip)
    fildq   temp(%rip)
    fxch
    fprem
    fisttpq temp(%rip)
    movb    temp(%rip), %al
    addb    $'0', %al
    movb    %al, (%rsi)
    incq    %rsi
    fdivrp
    fisttpq temp(%rip)
    fildq   temp(%rip)
    cmpq    $0, temp(%rip)
    ja      3b
    fisttpq temp(%rip)

    # 上面弄出来的整数部分顺序是反的
    # 这里反序整数部分
    leaq    buff(%rip), %rbx
    leaq    1(%rbx), %rax
    cmpb    $'-', (%rbx)
    cmoveq%rax, %rbx
    leaq    -1(%rsi), %rdi
4:movb    (%rbx), %al
    movb    (%rdi), %ah
    movb    %al, (%rdi)
    movb    %ah, (%rbx)
    incq    %rbx
    decq    %rdi
    cmpq    %rbx, %rdi
    ja      4b

    # 下面处理小数部分
    # 保留小数点后15位
    movb    $'.', (%rsi)
    incq    %rsi
    movq    $15, %rcx
    movq    $10, temp(%rip)
    fildq   temp(%rip)
    fxch
5:fmul    %st(1), %st(0)
    fld   %st(0)
    fisttpq temp(%rip)
    movb    temp(%rip), %al
    addb    $'0', %al
    movb    %al, (%rsi)
    incq    %rsi
    fildq   temp(%rip)
    fsubrp
    decq    %rcx
    cmpq    $0, %rcx
    ja      5b

    # 字符串最后加一个 '\n'
    movb    $'\n', (%rsi)
    incq    %rsi

    # 调用write系统调用输出字符串
    movq    $1, %rax            # sys_write
    movq    $1, %rdi            # stdout
    movq    %rsi, %rdx
    leaq    buff(%rip), %rsi    # buff
    subq    %rsi, %rdx          # count
    syscall

    # 调用exit系统调用退出程序
    movq    $60, %rax   # sys_exit
    movq    $0, %rdi    # status
    syscall
    retq

    .section .bss
buff:   .zero 1024
temp:   .zero 8
sh-5.1$ gcc -O3 -g -Wall -o c main.c -lm
sh-5.1$ as -O3 -g -o asm.o main.s
sh-5.1$ ld -o asm asm.o
sh-5.1$ ls
asmasm.ocmain.cmain.sold
sh-5.1$ time ./c <<EOF
> 999999999
> EOF
15811.768402

real        0m20.280s
user        0m20.241s
sys        0m0.004s
sh-5.1$ time ./asm <<EOF
999999999
EOF
15811.768401701640368

real        0m2.343s
user        0m2.332s
sys        0m0.004s
sh-5.1$ time ./c <<EOF
999999999
EOF
15811.768402

real        0m21.210s
user        0m21.080s
sys        0m0.020s
sh-5.1$ time ./asm <<EOF
999999999
EOF
15811.768401701640368

real        0m2.476s
user        0m2.429s
sys        0m0.007s
sh-5.1$

人造人 发表于 2022-10-27 10:27:44

sh-5.1$ ls
main.pymain.s
sh-5.1$ cat main.py
#!/usr/bin/env python
#coding=utf-8

import ctypes

dll = ctypes.cdll.LoadLibrary('./main.so')
dll.main()
print('ok')
sh-5.1$ cat main.s
    .section .text
    .global _start
_start:
    callq   main

    # 调用exit系统调用退出程序
    movq    $60, %rax   # sys_exit
    movq    $0, %rdi    # status
    syscall
    retq

    .global main
main:
    # 调用read系统调用
    # 从标准输入读取一个数字，是字符串类型的
    # 存储到buff中
    movq    $0, %rax            # sys_read
    movq    $0, %rdi            # stdin
    leaq    buff(%rip), %rsi    # buff
    movq    $1024, %rdx         # count
    syscall

    # 下面把buff中的字符串转换成数字
    decq    %rax      # '\n'
    movq    %rax, %rcx
    xorq    %rax, %rax
    movq    $10, %rdi
1:mulq    %rdi            # rax *= 10
    movzbq(%rsi), %rdx    # dl = *(%rsi)
    incq    %rsi
    subq    $'0', %rdx
    addq    %rdx, %rax
    decq    %rcx
    cmpq    $0, %rcx
    jg      1b
    movq    %rax, %r8

    # 下面计算表达式的值
    movq    $1, %rcx
    fldz
2:movq    %rcx, temp(%rip)
    fildq   temp(%rip)
    fsqrt               # i的0.5次方就是对i开方
    fst   %st(2)
    fchs
    testq   $1, %rcx
    fcmovne %st(2), %st(0)
    faddp
    incq    %rcx
    cmpq    %r8, %rcx
    jng   2b
    ffree   %st(1)

    # 下面把计算结果转换成字符串
    # 首先判断浮点数是不是负数
    # 如果是负数的话，要在字符串最前面加 '-'
    leaq    buff(%rip), %rsi
    movb    $'-', (%rsi)
    leaq    1(%rsi), %rax
    fldz
    fcomip%st(1), %st(0)
    cmovaq%rax, %rsi

    # 然后把整数部分和小数部分分开
    fld   %st(0)
    fisttpq temp(%rip)
    fildq   temp(%rip)
    fsubrp
    fabs
    fildq   temp(%rip)
    fabs

    # 接下来处理整数部分
3:fld   %st(0)
    movq    $10, temp(%rip)
    fildq   temp(%rip)
    fxch
    fprem
    fisttpq temp(%rip)
    movb    temp(%rip), %al
    addb    $'0', %al
    movb    %al, (%rsi)
    incq    %rsi
    fdivrp
    fisttpq temp(%rip)
    fildq   temp(%rip)
    cmpq    $0, temp(%rip)
    ja      3b
    fisttpq temp(%rip)

    # 上面弄出来的整数部分顺序是反的
    # 这里反序整数部分
    leaq    buff(%rip), %rbx
    leaq    1(%rbx), %rax
    cmpb    $'-', (%rbx)
    cmoveq%rax, %rbx
    leaq    -1(%rsi), %rdi
4:movb    (%rbx), %al
    movb    (%rdi), %ah
    movb    %al, (%rdi)
    movb    %ah, (%rbx)
    incq    %rbx
    decq    %rdi
    cmpq    %rbx, %rdi
    ja      4b

    # 下面处理小数部分
    # 保留小数点后15位
    movb    $'.', (%rsi)
    incq    %rsi
    movq    $15, %rcx
    movq    $10, temp(%rip)
    fildq   temp(%rip)
    fxch
5:fmul    %st(1), %st(0)
    fld   %st(0)
    fisttpq temp(%rip)
    movb    temp(%rip), %al
    addb    $'0', %al
    movb    %al, (%rsi)
    incq    %rsi
    fildq   temp(%rip)
    fsubrp
    decq    %rcx
    cmpq    $0, %rcx
    ja      5b

    # 字符串最后加一个 '\n'
    movb    $'\n', (%rsi)
    incq    %rsi

    # 调用write系统调用输出字符串
    movq    $1, %rax            # sys_write
    movq    $1, %rdi            # stdout
    movq    %rsi, %rdx
    leaq    buff(%rip), %rsi    # buff
    subq    %rsi, %rdx          # count
    syscall
    retq

    .section .bss
buff:   .zero 1024
temp:   .zero 8
sh-5.1$ as -O3 -g -o main.o main.s
sh-5.1$ ld -shared -o main.so main.o
sh-5.1$ ls
main.o        main.pymain.smain.so
sh-5.1$ time ./main.py <<EOF
> 999999999
> EOF
15811.768401701640368
ok

real        0m2.360s
user        0m2.348s
sys        0m0.007s
sh-5.1$

我邪魅一笑 发表于 2022-10-27 15:57:32

人造人 发表于 2022-10-27 10:27


虽然看不懂，但是看出了你很牛{:10_275:}

查看完整版本: 如何优化此代码，当N非常大时，程序运行时间不能超过2s