1

現在、高速化のために Python コードのブロックを C++ に変換中です。これはそのままのコードです (注、qsort は私が自分で書いたクイック ソートです):

base = sys.stdin.readline().split()
n = int(base[0])
m = int(base[1])
mult = m * 10
count = 1
output = []

while count != (n+1):

    hold = output + []
    if (n - count) + 1 >= mult:
        rev = mult
    else:
        rev = n - count + 1

    while rev != 0:
        temp = sys.stdin.readline().split()
        hold.append((int(temp[0])*count,temp[1], count))
        count += 1
        rev -= 1

    hold = qSort(hold,len(hold))
    output = hold[:m]

本質的に、私は数行の入力を取り、新しいアイテムと既存の出力を保持する hold と呼ばれる一時リストにそれらを追加し、クイックソートはそれらの値に従ってアイテムをソートします (最初の要素/整数として与えられます追加されたタプル)。Python では、タプルのリストをホールドおよび出力として保持するだけなので、このプロセスは非常に単純です。各タプルには、(1) ソートに使用される整数、(2) 文字列、(3) 整数の 3 つの項目が含まれます。これを C++ に変換する最善の方法は何かと考えていました。3 つの個別の配列を維持し、それらすべてを同時に更新する必要がありますか、またはリストとタプル クラスを使用する必要があります。(コードを可能な限り高速に実行しようとしています)。また、使用する方法を決定した後、ホールドと出力の間の相互作用をどのように最適に変換できますか? 常に効果的にするにはどうすればよいですかループの開始時に保持を更新し、最後に出力を効果的に変更しますか?

どんな助けでも大歓迎です！乾杯、仲間！

4

2 に答える 2

3

十分に高速になるようにPythonを書き直すことができるはずです。

まず、すべての入力を1つのリストに収集します。

次に、list.sort()メソッド関数を使用してリストをkey=並べ替えます。引数は数値で並べ替えます。

独自の並べ替え関数は、組み込みのPythonの並べ替えよりも遅くなります。また、コードが何をしているのかはわかりませんが、sort関数を複数回呼び出しているようです（外側のwhileループは、ループごとに1回sort関数を実行します）。私が提案したように書き直してください、そしてそれは非常に速いはずです。

編集：このコードは元のコードとほぼ同じことをしますか？

from operator import itemgetter
import sys

with sys.stdin as f:
    base = f.readline().split()
    n = int(base[0])
    m = int(base[1])

    hold = []
    for i, line in enumerate(f, 1):
        lst = line.split()
        weight = int(lst[0]) * i
        tup = (weight, lst[1], i)
        hold.append(tup)

hold.sort(key=itemgetter(0))
output = hold[:m]

for tup in output:
    print(tup[1])
于 2013-01-24T02:09:24.897 に答える
1

私は python に詳しくないので、何をしようとしているのか正確にはわかりませんが、私が提案する方法は次のとおりです。タプルで見つかったデータを保持するクラスまたは構造体を作成します (3 つのメンバー: int、int、string)。構造体を保持するベクトルを作成し、入力ファイルから読み取ったデータを含む構造体をこのベクトルに入力します。最後に、カスタム sort 関数を使用して、このベクターで sort を呼び出します。実装はこの質問と非常に似ていますが、ここで概要を説明します。

あなたの構造体は次のようになります

struct mystruct{
  int int1;
  int int2;
  string str1;
  public mystruct(int i1, int i2, string s1){int1 = i1; int2 = i2; str1 = s1;}
}

ベクトルは次のように定義されます

vector<mystruct> myvector;

これに似たコードでベクトルをロードします

mystruct ms(1,1,"text");
myvector.push_back(ms);

構造体の 2 つのインスタンスを比較するには、並べ替え関数を定義する必要があります。

bool compareStructs(mystruct i,mystruct j) { return (i.int1<j.int1); }

次に、 std::sort を使用してベクトルを並べ替えます

std::sort(myvector.begin(),myvector.end(),compareStructs);
于 2013-01-24T02:00:34.127 に答える