<jupyter_start><jupyter_text>Building Fast Queries on a CSVSkills: Object Oriented Programming, Time and Space Complexity AnalysisWe will imagine that we own an online laptop store and want to build a way to answer a few different business questions about our inventory.<jupyter_code># Open and explore the dataset
import csv
with open('laptops.csv') as file:
    read_file = csv.reader(file)
    laptop_prices = list(read_file)
    
header = laptop_prices[0]
rows = laptop_prices[1:]
print(header)
print(rows)
# Create a class with the csv filename as input to read the file

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
            
new_class = Inventory('laptops.csv')

print(new_class.header)
print(len(new_class.rows))
# Improve the class to get laptop given laptop id as input

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
            
new_class = Inventory('laptops.csv')

print(new_class.get_laptop_from_id('3362737'))
print(new_class.get_laptop_from_id('3362736'))
# To reduce time complexity of this algorithm, we will use preprocessing the data to create dict
# where the keys are the IDs and the values are the rows.

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
        self.id_to_row = {}
        for row in self.rows:
            self.id_to_row[row[0]] = row
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
       
    def get_laptop_from_id_fast(self, laptop_id):
        for row in self.rows:
            if laptop_id in self.id_to_row:
                return row
            else:
                return None
    
new_class = Inventory('laptops.csv')

print(new_class.get_laptop_from_id_fast('3362737'))
print(new_class.get_laptop_from_id_fast('3362736'))
# Let's compare the performance of those two methods

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
        self.id_to_row = {}
        for row in self.rows:
            self.id_to_row[row[0]] = row
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
       
    def get_laptop_from_id_fast(self, laptop_id):
        for row in self.rows:
            if laptop_id in self.id_to_row:
                return row
            else:
                return None
    
import time
import random

ids = [str(random.randint(1000000,9999999)) for _ in range(10000)]

new_class = Inventory('laptops.csv')

total_time_no_dict = 0
for each in ids:
    start = time.time()
    new_class.get_laptop_from_id(each)
    end = time.time()
    total_time_no_dict += (end-start)
    
total_time_dict = 0
for each in ids:
    start = time.time()
    new_class.get_laptop_from_id_fast(each)
    end = time.time()
    total_time_dict += (end-start)
    
print(total_time_no_dict, total_time_dict)
# Let's implement preprocessing of data to make our code of check_promotion_dollars() run faster.

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
        self.id_to_row = {}
        self.prices = set()
        for row in self.rows:
            self.id_to_row[row[0]] = row
            self.prices.add(row[-1])
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
       
    def get_laptop_from_id_fast(self, laptop_id):
        for row in self.rows:
            if laptop_id in self.id_to_row:
                return row
            else:
                return None
    
    def check_promotion_dollars(self, dollars):
        for row in self.rows:
            if row[-1] == dollars:
                return True
        for i in self.rows:
            for j in self.rows:
                if i[-1] + j[-1] == dollars:
                    return True
        return False
    
    def check_promotion_dollars_fast(self, dollars):
        if dollars in self.prices:
            return True
        for i in self.prices:
            for j in self.prices:
                if i + j == dollars:
                    return True
        return False
    
new_class = Inventory('laptops.csv')

print(new_class.check_promotion_dollars_fast(1000))
print(new_class.check_promotion_dollars_fast(442))
# Let's compare the performance of the last two functions that we wrote

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
        self.id_to_row = {}
        self.prices = set()
        for row in self.rows:
            self.id_to_row[row[0]] = row
            self.prices.add(row[-1])
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
       
    def get_laptop_from_id_fast(self, laptop_id):
        for row in self.rows:
            if laptop_id in self.id_to_row:
                return row
            else:
                return None
    
    def check_promotion_dollars(self, dollars):
        for row in self.rows:
            if row[-1] == dollars:
                return True
        for i in self.rows:
            for j in self.rows:
                if i[-1] + j[-1] == dollars:
                    return True
        return False
    
    def check_promotion_dollars_fast(self, dollars):
        if dollars in self.prices:
            return True
        for i in self.prices:
            for j in self.prices:
                if i + j == dollars:
                    return True
        return False

import random
import time

prices = [random.randint(100,5000) for _ in range(100)]

new_class = Inventory('laptops.csv')

total_time_no_set = 0
for price in prices:
    start = time.time()
    new_class.check_promotion_dollars(price)
    end = time.time()
    total_time_no_set += (end-start)
    
total_time_set = 0
for price in prices:
    start = time.time()
    new_class.check_promotion_dollars_fast(price)
    end = time.time()
    total_time_set += (end-start)
    
print(total_time_no_set, total_time_set)
# We want to write a method that efficiently answers the query: Given a budget of D dollars, find all laptops
#  whose price it at most D.

class Inventory():
    def __init__(self, csv_filename):
        with open(csv_filename) as file:
            list_file = list(csv.reader(file))
        self.header = list_file[0]
        self.rows = list_file[1:]
        for row in self.rows:
            row[-1] = int(row[-1])
        self.id_to_row = {}
        self.prices = set()
        for row in self.rows:
            self.id_to_row[row[0]] = row
            self.prices.add(row[-1])
        def row_price(row):
            return row[-1]
        self.rows_by_price = sorted(self.rows, key=row_price)
            
    def get_laptop_from_id(self, laptop_id):
        for row in self.rows:
            if row[0] == laptop_id:
                return row
        return None
       
    def get_laptop_from_id_fast(self, laptop_id):
        for row in self.rows:
            if laptop_id in self.id_to_row:
                return row
            else:
                return None
    
    def check_promotion_dollars(self, dollars):
        for row in self.rows:
            if row[-1] == dollars:
                return True
        for i in self.rows:
            for j in self.rows:
                if i[-1] + j[-1] == dollars:
                    return True
        return False
    
    def check_promotion_dollars_fast(self, dollars):
        if dollars in self.prices:
            return True
        for i in self.prices:
            for j in self.prices:
                if i + j == dollars:
                    return True
        return False
    
    def find_first_laptop_more_expensive(self, price):
        range_start = 0
        range_end = len(self.rows_by_price) - 1
        
        while range_start < range_end:
            range_middle = (range_end + range_start) // 2
            lap_price = self.rows_by_price[range_middle][-1]
            if lap_price == price:
                return range_middle + 1
            elif lap_price < price:
                range_start = range_middle + 1
            else:
                range_end = range_middle - 1
                
        lap_price = self.rows_by_price[range_start][-1]
        if lap_price < price:
            return -1
        return range_start+1
    
new_class = Inventory('laptops.csv')

print(new_class.find_first_laptop_more_expensive(1000))
print(new_class.find_first_laptop_more_expensive(10000))<jupyter_output>683
-1
{'fraction_non_alphanumeric': 0.08787189878422458, 'fraction_numerical': 0.01433231195018286, 'mean_word_length': 1.8983099398453165, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '32786', 'license': 'MIT', 'n_tokens_mistral': 3263, 'n_tokens_neox': 3093, 'n_words': 833, 'path': 'fast-queries/fast_queries.ipynb', 'repo_name': 'shanizalh/portfolio', 'size': '10117'}