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

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 に答える
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 に答える
1

更新: steveha の以前の回答の複製を投稿したことをお詫びします。私の読書スキルについて多くを語っています。i/o/バッファリング/ランタイム効果についての私の考えのためだけに、今のところこの回答をオンラインのままにしておきます。

元の投稿:

Python が 1 つの正規表現を適用して 1 つの平方根を計算するのに、標準入力から 1 行を読み取って結果を標準出力 (またはその他の I/O) に出力するのにかかる時間よりも長いとは思えません。

ある時点での I/O はハードドライブから発生し、別のハードドライブまたはユーザーの目のいずれかに移動するため、それが制限要因になるはずです。

I/O は通常、高速化のためにバッファリングされます。通常、バッファはバーストでいっぱいになり、デバイスがさらにデータを提供するのを待っている間、CPU はアイドル状態になります。

これは、アプリケーションのジェネレーターにつながります。入力を 1 行ずつ読み取り、必要に応じて平方数を即座に提供するジェネレータを作成します。これが、合理的な最新のハードウェアの全体的な I/O 速度よりも遅くなるとは思えません。特別なデバイス (組み込み、uController、Raspberry Pi など) を使用している場合はお知らせください)

実行できる最適化の 1 つは、正規表現をプリコンパイルすることです。各テストで同じ正規表現を使用しているため、正規表現の解析は 1 回だけ行います。を行っているため、質問の例は問題ありません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 とインターリーブする可能性があるため、実行時間全体に実際には追加されない可能性があります。壁掛け時計を見ると、このアルゴリズムは時間をまったく使用しない可能性があります。:-)

私の投稿全体を証明または否定するために、スクリプトの開始から行の直前まで、そしてそこから最後までtime.time()にかかる時間を測定できます。Data = re.findall私が正しければ、データの読み取りにはほとんどの時間がかかります。そうでない場合は、すべての正規表現検索に必要な時間も測定する価値があります。我々に教えてください。私は興味がある...

于 2013-02-22T13:32:35.787 に答える
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 に答える
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 に答える