2

这里是 Python3.3 上的代码：

import sys, re, math
str1 = str(sys.stdin.readlines())
Data = re.findall('\\b\\d+\\b', str1)

for i in reversed (Data):
    print('%.4f' % math.sqrt(float(i)))

如您所见，该程序从输入中获取数据（多行随机字符串），并搜索该字符串包含的每个数字。之后只返回它找到的每个数字的平方根。

好吧，算法有效，但不够快，我不知道如何优化它。请帮帮我。我需要做什么来优化上面的代码？

4

5 回答 5

2

这是一个负面的结果。我尝试使用一些技巧使其更快，但它只是快一点。

import sys, re, math

def find_numbers(f):
    for line in f:
        for word in line.split():
            if word.isdigit():
                yield float(word)

lst = list(find_numbers(sys.stdin))
lst.reverse()
for x in lst:
    print('%.4f' % math.sqrt(x))

我认为反转列表可能会使其变慢，但是当我只打印数字而不反转时，它并没有太大的区别。

Python 最快的解决方案是在 PyPy 中运行上述代码。

这不是一个非常困难的问题，如果您需要速度，您可能想用 C 代码编写解决方案。C 代码将尽可能快地解决这个问题。

于 2013-02-21T08:11:41.333 回答
2

您可以尝试使用 Numpy 加载和处理文件：

import numpy as np
for i in reversed(np.fromfile(sys.stdin, sep=' ')**0.5):
    print i

作为 Python 的高性能数值库，我希望它是您可用的最快的解决方案。

于 2013-02-21T08:17:23.763 回答
1

您要求使用 Python，但这可以在 C 中很好地完成。这个 C 程序不反转数字，但您可以简单地通过tac程序通过管道输出输出，这类似于cat但反转了行。

在我的测试中，这大约是 NumPy 解决方案速度的 3 倍，大约是我的 Python 解决方案或原始解决方案速度的 6 倍。

#include <ctype.h>
#include <math.h>
#include <stdio.h>

int
main()
{
    char buf[1024];
    char ch;
    float f;
    int i, n;

    for (i = 0;;)
    {
        ch = getchar();

        if (i > sizeof(buf))
        {
            fprintf(stderr, "number too long!\n");
            return 1;
        }

        if (isspace(ch) || EOF == ch)
        {
            if (i > 0)
            {
                buf[i] = '\0';
                n = atoi(buf);
                f = sqrtf(n);
                printf("%0.4f\n", f);
                i = 0;
            }

            if (EOF == ch)
                return 0;

            continue;
        }

        buf[i++] = ch;
    }
}
于 2013-02-21T09:09:27.023 回答
1

更新：为发布steveha 更早的答案的副本而道歉。大量谈论我的阅读技巧。现在仍然将这个答案留在网上，只是因为我对 i/o/buffering/runtime 效果的思考。

原帖：

我无法相信 Python 应用一个正则表达式并计算一个平方根所需的时间比从标准输入读取一行并在标准输出（或任何 I/O 上）输出结果所需的时间更长。

由于某个时间点的 I/O 将来自一个硬盘驱动器，并且会转到另一个硬盘驱动器或用户的眼睛，这应该是限制因素。

I/O 通常被缓冲以提高速度。通常一个缓冲区被突发填充，然后 cpu 在等待设备提供更多数据时空闲。

这会为您的应用程序生成一个生成器。编写一个生成器，逐行读取输入，并立即按需提供一个 sqrt 数。我怀疑这会比任何合理的现代硬件上的整体 I/O 速度慢。如果您使用的是特殊设备（如嵌入式、uController、Raspberry Pi 等，请告诉我们）

您可以做的一项优化是预编译正则表达式。当您对每个测试使用相同的正则表达式时，让我们只解析一次正则表达式。您在问题中的示例很好，因为您正在执行re.findall(). 我只是为其他读者详细说明。

import sys, re, math

pattern = re.compile(r'\b\d+\b')

def fh_numbers_to_sqrt(fh):
    for line in fh:
        for i in re.findall(pattern, line):
            yield math.sqrt(float(i))

numbers_g = fh_numbers_to_sqrt(sys.stdin)
for num in numbers_g:
    print('%.4f' % num)

这允许所有正则表达式和数学运算与 I/O 时间交错。

现在，我们根本无法真正优化和集成的一件事是reverse. 该算法必须等到最后一个元素才能反转。

所以我们可以把调用代码改成：

numbers_g = fh_numbers_to_sqrt(sys.stdin)
for num in reverse(list(numbers_g)):
    print('%.4f' % num)

并希望这比你原来拥有的更快。同样，这应该更快的唯一原因是因为我们已经将正则表达式解析和计算的运行时间隐藏在从标准输入读取数据所需的挂钟时间内。这仍应受 I/O 限制。实际上，这reverse可能不会真正增加整体运行时间，因为它可能会与标准输出上发生的 I/O 交错。看看挂钟，这个算法可能根本不会用完任何时间。:-)

To prove or negate my whole post, you could measure with time.time() how long it takes from the start of your script to just before the line Data = re.findall, and from then on to the end. If I'm correct then the data reading will take most of the time. If not, it's worthwhile to measure also the time required for all the regular expression searches. Let us know. I'm curious...

于 2013-02-22T13:32:35.787 回答
0 
import sys, re, math
str1 = str(sys.stdin.readlines())
Data = re.findall('\\b\\d+\\b', str1)

d2 = [round(math.sqrt(float(i)),4) for i in reversed (Data)]

for i in d2:
    print(i)
于 2013-02-21T08:23:50.230 回答