1
\$\begingroup\$

I'm trying to do a non equi self join with basic python libraries on a table that has 1.7 millions rows and 4 variables. the data look like this:

product     position_min     position_max      count_pos
A.16        167804              167870              20
A.18        167804              167838              15
A.15        167896              167768              18
A.20        238359              238361              33
A.35        167835              167837              8
import csv
from collections import defaultdict
import sys
import os

list_csv=[]
l=[]
with open(r'product.csv', 'r') as file1:
    my_reader1 = csv.reader(file1, delimiter=';')
    list_csv=[row for row in my_reader1 ]
with open(r'product.csv', 'r') as file2:
    my_reader2 = csv.reader(file2, delimiter=';') 
    with open('product_p.csv', "w") as csvfile_write:
        ecriture = csv.writer(csvfile_write, delimiter=';',
                                quotechar='"', quoting=csv.QUOTE_ALL)
        for row in my_reader2:
            res = defaultdict(list)
            for k in range(len(list_csv)):
                comp= list_csv[k]
                try:
                    if int(row[1]) >= int(comp[1]) and int(row[2]) <= int(comp[2]) and row[0] != comp[0]:
                        res[row[0]].append([comp[0],comp[3]]) 
                except:
                    pass         


            if bool(res):    
                for key, value in res.items():
                    sublists = defaultdict(list)
                    for sublist in value:
                        l=[]
                        sublists[sublist[0]].append(int(sublist[1]))
                    l.append(str(key) + ";"+ str(min(sublists.keys(), key=(lambda k: sublists[k]))))
                        ecriture.writerow(l)

I should get this in the "product_p.csv" file:

'A.18'; 'A.16'
'A.15'; 'A.18'
'A.35'; 'A.18' 

What the code does is to read the same file twice, the first time completely, and convert it into a list, and the 2nd time line by line and that is to find for each product (1st variable) all the products to which it belongs by the condition on position_min and position_max and after that choose only one by keeping the product that has the minimum of count_pos .

I tried it on a sample of the original data, it works, but with 1.7 millions rows, it runs for hours without giving any results. Is there a way to do that without for loops with basic python libraries ?

Thank you in advance

\$\endgroup\$
5
  • \$\begingroup\$ with basic python libraries? No. Why would you want this? Pandas/Numpy are built for this kind of scale. \$\endgroup\$
    – Reinderien
    Jul 14 at 22:42
  • \$\begingroup\$ I have to run it in a workflow as a shell action, and for that I have to use only basic python libraries. I want to use less loopsin my code, That's why I posted here. \$\endgroup\$
    – Stella
    Jul 15 at 13:31
  • \$\begingroup\$ That doesn't seem like a good excuse? Any Python program with dependencies can be run from the shell. \$\endgroup\$
    – Reinderien
    Jul 15 at 13:38
  • \$\begingroup\$ The workflow have to be run on a hadoop cluster, that's why i need to use only basic python libraires. \$\endgroup\$
    – Stella
    Jul 16 at 13:49
  • \$\begingroup\$ Still not hearing a good reason. Other people have been down this road. \$\endgroup\$
    – Reinderien
    Jul 16 at 13:52
1
\$\begingroup\$

Double Open

There is no reason to open the product.csv file twice.

The first time you open the file, you are reading and storing the entire file in memory. Instead of opening and reading the file a second time line by line, you could simply loop over the list_csv. This:

with open(r'product.csv', 'r') as file2:
    my_reader2 = csv.reader(file2, delimiter=';') 
    with open('product_p.csv', "w") as csvfile_write:
        ecriture = csv.writer(csvfile_write, delimiter=';',
                                quotechar='"', quoting=csv.QUOTE_ALL)
        for row in my_reader2:
            ...

becomes:

with open('product_p.csv', "w") as csvfile_write:
    ecriture = csv.writer(csvfile_write, delimiter=';',
                          quotechar='"', quoting=csv.QUOTE_ALL)
    for row in list_csv:
        ...

Save your work

With one million rows in your file, your \$O(N^2)\$ algorithm is visiting one trillion row pairings. With each row pairing, you convert strings to integers up to 4 times with int(row[1]) >= int(comp[1]) and int(row[2]) <= int(comp[2]). That is four trillion string-to-integer conversions!

Yeouch!

If instead, as you read the file the first time, you convert the three strings into integer values and stored the already converted values in list_csv, validating in the process, your later code would cleaner and faster.

with open(r'product.csv', 'r') as file1:
    my_reader1 = csv.reader(file1, delimiter=';')
    list_csv = []
    for row in my_reader1:
        try:
            product = row[0]
            pos_min, pos_max, count_pos = map(int, row[1:])
            list_csv.append((product, pos_min, pos_max, count_pos))
        except ValueError:
            pass

    # No int(...) or try-except required beyond this point

Bare Except

try: ... except: pass is bad, bad, bad.

What exception is expected? except ValueError: is better. It lets the reader know what type of exception might occur, giving context.

It is also for your benefit. What if you accidentally wrote ... int(cmp[2]) ... inside try: ... except: pass? You would get one trillion NameError exceptions raised and suppressed. After a long, long period of time, the program would complete and write an empty result file, leaving you with no clue what went wrong. Narrowing the type of exception caught to a ValueError would immediately reveal the issue.

It would be much better to actually handle the error, instead of suppressing it. Print out a message explaining what the problem was: what row failed to convert properly. If there are known valid reasons why the conversion might fail, check that the failure was expected, and report if the failure was not of the expected variety.

Named Tuples

Giving names to your data structure elements can help readability.

What is comp[1]? row[2]? comp[3]? It is very difficult to tell from the code.

Consider instead:

...
from typing import NamedTuple

class Product(NamedTuple):
    product: str
    pos_min: int
    pos_max: int
    count_pos: int

...

with open(r'product.csv', 'r') as file1:
    my_reader = csv.reader(file1, delimiter=';')
    products = []
    for row in my_reader:
        try:
            product = row[0]
            pos_min, pos_max, count_pos = map(int, row[1:])
            products.append(Product(product, pos_min, pos_max, count_pos))
        except ValueError:
            pass

    for row in products:
        ...
        for comp in products:
            if row.pos_min >= comp.pos_min and row.pos_max <= comp.pos_max and row.product != comp.product:
                res[row.product].append([comp.product, comp.count_pos])

        ...

This is immediately more readable. We're not comparing some arbitrary thing at indices 1, 2, and 0; we're comparing named things.

Speaking of names ...

I've changed list_csv to products. It was read from a CSV file, but the elements are no longer comma-separated-values. The commas are long gone. Its just a list of products.

row and comp could use better names too.

I've also replaced:

            for k in range(len(list_csv)):
                comp= list_csv[k]

with loop directly over the values of the list. There is no need for the k index variable.

Algorithm

With the above changes, your algorithm is still the same, which means it is still \$O(N^2)\$.

Can we improve it? Sorting is \$O(N \log N)\$ which is better than \$O(N^2)\$, so is an easy thing to try. What can we sort on? Would sorting on position_min help us?

Yes, it would, but we need to be careful.

With products sorted on position_min, then row.pos_min >= comp.pos_min would be true for all comp items occurring earlier than row in the products list. We might be tempted to loop for row_idx in range(len(products)), and for comp_idx in range(row_idx), but we'd introduce a bug:

Several items sorted after row might still have an pos_min equal to row.pos_min, so we can't just loop up to the current row. But we can stop when we reach the first min_pos value larger than row.pos_min.


sort(products, key=...)

for row in products:
    limit = row.min_pos
    for comp in products:
        if comp.min_pos > limit:
            break
        if row.max_pos <= comp.max_pos and row.product != comp.product:
            res[row.product].append([comp.product, comp.count_pos])

    ...

One trillion row-pairings just dropped to one-half trillion row-pairings. It is still \$O(N^2)\$, but we cut the time in half.

\$\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.