-2
\$\begingroup\$

What my code try to do here is to sort items trough 2 dictionaries. If they are similar or the same, I create a new list to append them.

The test file is relatively big, around 2000 data each dictionary.

My concern is that i need to maintain a linear time complexity trough out the code and i am not sure that my code is on a linear complexity.

I would like an opinion on the complexity of this code. Is it linear? If it is not is there any way to improve it?

import pandas as pd
import string
import textdistance as td
import time
start_time = time.time()


amazon =  pd.read_csv('amazon.csv')
google = pd.read_csv('google.csv')

title1 = amazon['title']
title2 = google['name']
id1 = amazon['idAmazon']
id2 = google['id']

out_amazon = {}
out_google = {}

list_a =[]
list_b =[]
list_c =[]
list_d =[]
list_e =[]
list_f =[]
list_g =[]
list_h =[]
list_i =[]
list_j =[]
list_k =[]
list_l =[]
list_m =[]
list_n =[]
list_o =[]
list_p =[]
list_q =[]
list_r =[]
list_s =[]
list_t =[]
list_u =[]
list_v =[]
list_w =[]
list_x =[]
list_y =[]
list_z =[]
list_unknown = []
duplicate_list = []

amazon_labeled = ([(name, 'Amazon') for name in title1])
google_labeled = ([(name, 'Google') for name in title2])

amazon_dict = dict(zip(amazon.idAmazon, amazon_labeled))
google_dict = dict(zip(google.id, google_labeled))

z = {**amazon_dict, **google_dict}
keys = sorted((z.values()))

i = 0
while i < (len(keys)) - 1:
    if (keys[i][0][0]) == 'a':
        list_a.append(keys[i])
    elif (keys[i][0][0]) == 'b':
        list_b.append(keys[i])
    elif (keys[i][0][0]) == 'c':
        list_c.append(keys[i])
    elif (keys[i][0][0]) == 'd':
        list_d.append(keys[i])
    elif (keys[i][0][0]) == 'e':
        list_e.append(keys[i])
    elif (keys[i][0][0]) == 'f':
        list_f.append(keys[i])
    elif (keys[i][0][0]) == 'g':
        list_g.append(keys[i])
    elif (keys[i][0][0]) == 'h':
        list_h.append(keys[i])
    elif (keys[i][0][0]) == 'i':
        list_i.append(keys[i])
    elif (keys[i][0][0]) == 'j':
        list_j.append(keys[i])
    elif (keys[i][0][0]) == 'k':
        list_k.append(keys[i])
    elif (keys[i][0][0]) == 'l':
        list_l.append(keys[i])
    elif (keys[i][0][0]) == 'm':
        list_m.append(keys[i])
    elif (keys[i][0][0]) == 'n':
        list_n.append(keys[i])
    elif (keys[i][0][0]) == 'o':
        list_o.append(keys[i])
    elif (keys[i][0][0]) == 'p':
        list_p.append(keys[i])
    elif (keys[i][0][0]) == 'q':
        list_q.append(keys[i])
    elif (keys[i][0][0]) == 'r':
        list_r.append(keys[i])
    elif (keys[i][0][0]) == 's':
        list_s.append(keys[i])
    elif (keys[i][0][0]) == 't':
        list_t.append(keys[i])
    elif (keys[i][0][0]) == 'u':
        list_u.append(keys[i])
    elif (keys[i][0][0]) == 'v':
        list_v.append(keys[i])
    elif (keys[i][0][0]) == 'w':
        list_w.append(keys[i])
    elif (keys[i][0][0]) == 'x':
        list_x.append(keys[i])
    elif (keys[i][0][0]) == 'y':
        list_y.append(keys[i])
    elif (keys[i][0][0]) == 'z':
        list_z.append(keys[i])
    else:
        list_unknown.append(keys[i])
    i += 1

def check_based_alphabet(alphabetList, k = 0, j = 0):
    while k < len(alphabetList) - 1:
        if alphabetList[k][1] != alphabetList[j][1]:
            distance = td.jaccard(alphabetList[k][0], alphabetList[j][0])
            if distance > 0.7:
                duplicate_list.append([alphabetList[k][0], alphabetList[j][0]])
            j += 1
        else:
            j += 1
        if j == len(alphabetList):
            j = 1
            k += 1            

check_based_alphabet(list_a)
check_based_alphabet(list_b)
check_based_alphabet(list_c)
check_based_alphabet(list_d)
check_based_alphabet(list_e)
check_based_alphabet(list_f)
check_based_alphabet(list_g)
check_based_alphabet(list_h)
check_based_alphabet(list_i)
check_based_alphabet(list_j)
check_based_alphabet(list_k)
check_based_alphabet(list_l)
check_based_alphabet(list_m)
check_based_alphabet(list_n)
check_based_alphabet(list_o)
check_based_alphabet(list_p)
check_based_alphabet(list_q)
check_based_alphabet(list_r)
check_based_alphabet(list_s)
check_based_alphabet(list_t)
check_based_alphabet(list_u)
check_based_alphabet(list_v)
check_based_alphabet(list_w)
check_based_alphabet(list_x)
check_based_alphabet(list_y)
check_based_alphabet(list_z)
Improve this question
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of CR: Asking Questions for guidance on writing good question titles. Also, while it isn't exactly a mirror scenario the consensus is that questions about the complexity of code are off-topic \$\endgroup\$
    – Sᴀᴍ Onᴇᴌᴀ ♦
    May 28, 2020 at 21:25
  • \$\begingroup\$ sorted() takes O(nlog(n)) time, so not linear. \$\endgroup\$
    – Leo Adberg
    May 28, 2020 at 23:42
  • 1
    \$\begingroup\$ @Bobby Anyone that actually want to help you learn about big o wouldn't just give you the answer. Why do you think it's linear? Where are your workings out? \$\endgroup\$
    – Peilonrayz ♦
    May 29, 2020 at 6:44
  • 1
    \$\begingroup\$ If all you wanna know Is the time complexity of your code, then you've come to the wrong place. If you dont know how to determine that from the code itself, why dont you try the obvious naive solution and make some meassurements for various input sizes and see if it scales lineary? \$\endgroup\$
    – slepic
    May 29, 2020 at 17:28
  • 5
    \$\begingroup\$ I’m voting to close this question because it poses a specific question, there is no request for review. Please take a look at the help center. \$\endgroup\$
    – Mast ♦
    May 30, 2020 at 8:43

1 Answer 1

Reset to default
1
\$\begingroup\$

Even if you didn't ask, I would just go ahead and comment on the code. Please use the following so that you don't need so many lists.

Initialize a dictionary:

list_dict = {}

for i in range (97, 123):
    list_dict[chr(i)] = []

First use a dictionary:

i = 0
while i < (len(keys)) - 1:
    if 'a' <= (keys[i][0][0]) <= 'z':
        list_dict[keys[i][0][0]].append(keys[i])
    else:
        #ignore
        pass
    i += 1

And second use loop.

for alpha, ll in list_dict.items():
    check_based_alphabet(ll)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ While I agree that the code should be vastly simplified, your solution overwrites the entries instead of grouping them by their first letter. \$\endgroup\$
    – Graipher
    Jun 1, 2020 at 9:11
  • 1
    \$\begingroup\$ Thanks for pointing this out. just wrote that quickly by mistake. corrected. \$\endgroup\$
    – mangupt
    Jun 1, 2020 at 9:56

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