Translating Python to C++: lists and tuples

Question

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!

Answer 1

It should be possible to rewrite your Python so that it is fast enough.

First, collect all the input to one list.

Second, sort the list using the list.sort() method function, with a key= argument to sort by the number.

Your own sorting function is going to be slower than the built-in Python sort. And I'm not clear on what the code is doing but it seems to call the sort function more than once (the outer while loop runs your sort function once per loop). Rewrite as I suggested and it should be very fast.

EDIT: Does this code do approximately the same thing as your original code?

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

Answer 2

I'm not very familiar with python, and can't tell exactly what you're trying todo, but here's the path I'd suggest. Create a class or struct to hold the data found in your tuple (three members: int, int, string). Create a vector that will hold your structures, and then populate this vector with structs containing data read in from the input file. Finally, call sort on this vector using a custom sort function. The implementation would be very similar to this question, but I'll give you an overview here.

Your struct could look like this

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

Your vector would be defined like this

vector<mystruct> myvector;

You'd load up your vector with code similar to this

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

You'll have to define a sort function to compare two instances of your struct

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

And then use std::sort to sort your vector

std::sort(myvector.begin(),myvector.end(),compareStructs);