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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

编写程序求1^1/2-2^1/2+3^1/2-4^1/2+...+N^1/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}')

最佳答案

月排行榜 / 总排行榜

人造人

2022-10-27 10:27:44

sh-5.1$ ls
main.py  main.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.py  main.s  main.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$

跳转到最佳答案楼层

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

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
这还能有什么好办法？也许改用数学库可以快一点？

比刚才那个还慢了点

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

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

还是超时了

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位小数

这个可以么

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.py  n.c  n.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.py  n.c  n.py  n.so
sh-5.1$ file n.so
n.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=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
asm  asm.o  c  main.c  main.s  old
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.py  main.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.py  main.s  main.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

虽然看不懂，但是看出了你很牛

账号		自动登录	找回密码
密码			立即注册