6
\$\begingroup\$

I have the following code that I'm using to create combinations of elements in my dataset:

start_time = time.time()
question_pairs = []
import itertools as iter

for memberid in IncorrectQuestions.memberid.unique():
    combinations = IncorrectQuestions[IncorrectQuestions.memberid == memberid].groupby('memberid').questionid.apply(
        lambda x: list(iter.combinations(x, 2)))
    for elem in combinations:
        for el in elem:
            question_pairs.append(list(el))

print("--- %s seconds ---" % (time.time() - start_time))

the DataFrame IncorrectQuestions has about 40 Million records. Here's the sample dataset:

    memberid    created firstencodedid  questionid
0   9   2016-01-18 05:10:44 MAT.CAL.110 5696d0248e0e0869c96357d3
1   9   2016-01-18 05:10:44 MAT.CAL.110 5696cbc45aa413444ffd9973
2   9   2016-01-18 05:10:44 MAT.CAL.110 5696cf86da2cfe6f21d09879
3   34  2016-11-10 04:24:14 MAT.ARI.300 51d8cd415aa41337ec50425a
4   34  2016-11-10 04:24:14 MAT.ARI.300 559a84505aa4136cb37be676

The piece of code above takes way too long. It has been an hour and it is still running. Is there a way to optimize this piece of code so it takes less time?

The desired output would create all possible combinations of questionid for each memberid. For example, the combinations for memberid = 9 would be:

['5696d0248e0e0869c96357d3','5696cbc45aa413444ffd9973']

['5696d0248e0e0869c96357d3','5696cf86da2cfe6f21d09879']

['5696cbc45aa413444ffd9973','5696cf86da2cfe6f21d09879']

The combinations for memberid = 34 would be:

['51d8cd415aa41337ec50425a','559a84505aa4136cb37be676']

And finally, the combined output would be both the lists combined, i.e.:

['5696d0248e0e0869c96357d3','5696cbc45aa413444ffd9973']

['5696d0248e0e0869c96357d3','5696cf86da2cfe6f21d09879']

['5696cbc45aa413444ffd9973','5696cf86da2cfe6f21d09879']

['51d8cd415aa41337ec50425a','559a84505aa4136cb37be676']

I hope this makes things clearer.

Any pointers would be appreciated.

\$\endgroup\$
  • \$\begingroup\$ Could you please add an example of the desired output so that I can recommend other possible improvements ? \$\endgroup\$ – Grajdeanu Alex. Feb 28 '17 at 22:10
  • \$\begingroup\$ More, please modify the title so that it describes what the code does \$\endgroup\$ – Grajdeanu Alex. Feb 28 '17 at 22:18
  • \$\begingroup\$ @Dex'ter: Thanks a lot for your response. I've added the desired output in the question. \$\endgroup\$ – Patthebug Feb 28 '17 at 22:33
  • \$\begingroup\$ I though CR required running code, which in this case would include the creation of a sample data frame? \$\endgroup\$ – hpaulj Feb 28 '17 at 23:28
  • \$\begingroup\$ What's the size of the largest group? If you can guarantee that no group exceeds e.g. 5 rows then it's a very different problem to the case where a group could contain a million rows. \$\endgroup\$ – Peter Taylor Mar 1 '17 at 8:39
7
\$\begingroup\$

You take the combinations in a way too convoluted way. For starter, I would simplify the retrieval of "same memberid" questions:

for memberid in IncorrectQuestions.memberid.unique():
    questions = IncorrectQuestions[IncorrectQuestions.memberid == memberid].questionid

No need to groupby here since you’re already filtering by the one memberid you’re interested in. Thus producing combinations can be as simple as:

    for elem in itertools.combinations(questions, 2):
        question_pairs.append(list(elem))

Now, I don't see why you want to explicitly turn the tuples returned by itertools.combinations into lists as it adds up time and memory usage. So I suggest dropping it.

Now in the for loop, the use of unique() plus filtering on these unique values is the exact use-case for groupby. So you can rewrite it:

for member_id, questions in IncorrectQuestions.groupby('memberid'):
    for pair in itertools.combinations(questions.questionid, 2):
        question_pairs.append(pair)

I would then turn it into a function for better reusability/testing and use Python naming conventions:

def generate_combination_of_questions(dataframe):
    question_pairs = []
    for _, questions in dataframe.groupby('memberid'):
        for pair in itertools.combinations(questions.questionid, 2):
            question_pairs.append(pair)
    return question_pairs

But the combo var = [] + for loop + var.append should be turned into either a list-comprehension or a generator for better performances:

def generate_combination_of_questions(dataframe):
    return = [
        pair
        for _, questions in dataframe.groupby('memberid')
        for pair in itertools.combinations(questions.questionid, 2)
    ]

or

def generate_combination_of_questions(dataframe):
    for _, questions in dataframe.groupby('memberid'):
        yield from itertools.combinations(questions.questionid, 2)

The second version uses Python 3 syntax and is called as follow:

question_pairs = list(generate_combination_of_questions(IncorrectQuestions))

If you don't have Python 3 available, you can use the more verbose:

def generate_combination_of_questions(dataframe):
    for _, questions in dataframe.groupby('memberid'):
        for pair in itertools.combinations(questions.questionid, 2):
            yield pair

Your timing procedure can also be enhanced by the use of either time.perf_counter() or, better, the timeit module

Example code with timeit:

import itertools


def generate_combination_of_questions(dataframe):
    for _, questions in dataframe.groupby('memberid'):
        yield from itertools.combinations(questions.questionid, 2)


if __name__ == '__main__':
    import timeit
    setup = """\
import pandas as pd
from __main__ import generate_combination_of_questions
incorrect = pd.read_csv(<...>)"""

    print(timeit.timeit(
        'list(generate_combination_of_questions(incorrect))',
        setup=setup, number=1))

Reading at the various comments about the size of your dataset, you definitely want the generator version (the one with yield instead of return) as it will allow you to iterate over the results one by one and not store all of them in memory before. Otherwise, the list will fill up all your memory.

For instance, writing each pair into a file might look like:

import itertools
import csv
import pandas as pd


def generate_combination_of_questions(dataframe):
    for _, questions in dataframe.groupby('memberid'):
        yield from itertools.combinations(questions.questionid, 2)


def main(file_in, file_out):
    incorrect_questions = pd.read_csv(file_in)
    with open(file_out, 'w') as output:
        writer = csv.writer(output)
        for pair in generate_combination_of_questions(incorrect_questions):
            writer.writerow(pair)


if __name__ == '__main__':
    main(<path1>, <path2>)

But you're obviously free to do any form of processing while iterating over the generator; writing to a file is just the simplest example.

\$\endgroup\$
  • 1
    \$\begingroup\$ Given that OP has just answered my question in comments stating that the average size of a group is about 20 elements, there are going to be on the order of 400 million pairs, and each pair of 24-element strings uses at least 50 bytes. So we're talking on the order of 20 gigabytes of memory with a list. Generators all the way. \$\endgroup\$ – Peter Taylor Mar 1 '17 at 16:34
  • \$\begingroup\$ @PeterTaylor: You are absolutely right. I tried this solution (which is extremely well written, Thanks to @MathiasEttinger) and it hogged all the memory and left my system in a somewhat unresponsive state. I'm clearly not a Python developer and don not really know how to code up generators. So I'm going to have to research more in that area. \$\endgroup\$ – Patthebug Mar 1 '17 at 16:43
  • \$\begingroup\$ Ahh, I see. Thanks a lot for your advice. I was thinking about doing that, without necessarily knowing that that's what a generator is. Thanks for confirming, and also for the amazing, and extremely detailed answer :). \$\endgroup\$ – Patthebug Mar 1 '17 at 16:52
  • \$\begingroup\$ Here's what I finally wrote: for memberid in IncorrectQuestions['memberid'].unique(): for pair in generate_combination_of_questions(IncorrectQuestions[IncorrectQuestions['memberid']==memberid]): writer.writerow(pair) \$\endgroup\$ – Patthebug Mar 1 '17 at 17:29
  • \$\begingroup\$ @Patthebug try for pair in generate_combination_of_questions(IncorrectQuestions): writer.writerow(pair) instead. \$\endgroup\$ – Mathias Ettinger Mar 1 '17 at 17:49
4
\$\begingroup\$

First thing first:

  • there's an existing built-in named iter, so doing import itertools as iter might create some confusion. Just leave it as import itertools or if you really need an alias for it, name it in another way.
  • you need to change combinations for PEP8 compliance. As stated above, you can name it a bit different. Think what would happen if you'd do: from itertools import combinations; combinations = ...lambda x: list(combinations(x, 2))
  • the imports should really stay at the top. Related to this, you should've add the import time too.
  • use list comprehensions:

    for elem in combinations:
        for el in elem:
            question_pairs.append(list(el))
    

    Can be rewriten as a list comprehension like this:

    question_pairs = [[el] for elem in combinations for el in elem]
    

A list comprehension is usually a bit faster than the precisely equivalent for loop (that actually builds a list), most likely because it doesn't have to look up the list and its append method on every iteration.

But, keep in mind that using a list comprehension in place of a loop that doesn't build a list, nonsensically accumulating a list of meaningless values and then throwing the list away, is often slower because of the overhead of creating and extending the list. List comprehensions aren't magic that is inherently faster than a good old loop (the explanation is from this SO answer).

I'm afraid I don't have any other ideas regarding this. I'm waiting fot the OP to add more context and some examples to the posted code.

The final code (so far) would look like:

import time
import itertools


def generate_pairs():
    for memberid in IncorrectQuestions.memberid.unique():
        combs = (IncorrectQuestions[IncorrectQuestions.memberid == memberid]
                 .groupby('memberid')
                 .questionid
                 .apply(lambda x: list(itertools.combinations(x, 2))))
        question_pairs = [[el for el in elem] for elem in combs]


def main():
    start_time = time.time()
    generate_pairs()
    print("--- %s seconds ---" % (time.time() - start_time))


if __name__ == '__main__':
    main()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.