1

I am currently in the process of translating a block of Python code to C++ for speed purposes. This is the code as is (note, qsort is a quick sort I wrote myself):

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]

In essence, I am taking a few lines of input, adding them to a temporary list called hold, which holds new items and the existing output, and then my quicksort sorts the items according to their value (given as the first element/integer in the appended tuple). In Python this process is pretty simple, as I simply keep a list of tuples as hold and output, and each tuple contains three items: (1) integer used for sorting, (2) string, (3) integer. I was wondering what the best way to translate this to C++ was. Should I maintain 3 separate arrays and update all of them simultaneously, or should I use the list and tuples class. (Im trying to get my code to run as fast as it possibly can). Also, after deciding a method to use, how can I best translate the interplay between hold and output? How can I constantly effectively refresh hold at the beginning of the loop and effectively modify output at the end?

Any and all help is greatly appreciated! Cheers, mates!

4

2 回答 2

3

应该可以重写您的 Python 以使其足够快。

首先，将所有输入收集到一个列表中。

其次，使用list.sort()方法函数对列表进行排序，并带有一个key=按数字排序的参数。

你自己的排序函数会比 Python 内置的排序慢。而且我不清楚代码在做什么，但它似乎不止一次调用 sort 函数（外部 while 循环每个循环运行一次 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 不是很熟悉，也不能确切地说出你想要做什么，但这是我建议的路径。创建一个类或结构来保存在元组中找到的数据（三个成员：int、int、string）。创建一个将保存您的结构的向量，然后使用包含从输入文件读取的数据的结构填充此向量。最后，使用自定义排序函数对此向量调用排序。实现将与这个问题非常相似，但我会在这里给你一个概述。

你的结构可能看起来像这样

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);

您必须定义一个排序函数来比较结构的两个实例

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 回答