{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Guided Project Solution: Building Fast Queries on a CSV"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Reading the Inventory\n",
"\n",
"Use the `csv` module to read the `laptops.csv` file and separate the header from the rows."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['Id', 'Company', 'Product', 'TypeName', 'Inches', 'ScreenResolution', 'Cpu', 'Ram', 'Memory', 'Gpu', 'OpSys', 'Weight', 'Price']\n",
"['6571244', 'Apple', 'MacBook Pro', 'Ultrabook', '13.3', 'IPS Panel Retina Display 2560x1600', 'Intel Core i5 2.3GHz', '8GB', '128GB SSD', 'Intel Iris Plus Graphics 640', 'macOS', '1.37kg', '1339']\n",
"['7287764', 'Apple', 'Macbook Air', 'Ultrabook', '13.3', '1440x900', 'Intel Core i5 1.8GHz', '8GB', '128GB Flash Storage', 'Intel HD Graphics 6000', 'macOS', '1.34kg', '898']\n",
"['3362737', 'HP', '250 G6', 'Notebook', '15.6', 'Full HD 1920x1080', 'Intel Core i5 7200U 2.5GHz', '8GB', '256GB SSD', 'Intel HD Graphics 620', 'No OS', '1.86kg', '575']\n",
"['9722156', 'Apple', 'MacBook Pro', 'Ultrabook', '15.4', 'IPS Panel Retina Display 2880x1800', 'Intel Core i7 2.7GHz', '16GB', '512GB SSD', 'AMD Radeon Pro 455', 'macOS', '1.83kg', '2537']\n",
"['8550527', 'Apple', 'MacBook Pro', 'Ultrabook', '13.3', 'IPS Panel Retina Display 2560x1600', 'Intel Core i5 3.1GHz', '8GB', '256GB SSD', 'Intel Iris Plus Graphics 650', 'macOS', '1.37kg', '1803']\n"
]
}
],
"source": [
"import csv\n",
"\n",
"with open('laptops.csv') as f:\n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" header = rows[0]\n",
" rows = rows[1:]\n",
" \n",
"print(header)\n",
"for i in range(5):\n",
" print(rows[i])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Inventory Class\n",
"\n",
"Start implementing a class to represent the inventory. It get the name of the CSV file as argument and reads it into `self.header` and `self.rows`."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['Id', 'Company', 'Product', 'TypeName', 'Inches', 'ScreenResolution', 'Cpu', 'Ram', 'Memory', 'Gpu', 'OpSys', 'Weight', 'Price']\n",
"1303\n"
]
}
],
"source": [
"class Inventory(): # step 1\n",
" \n",
" def __init__(self, csv_filename): # step 2\n",
" with open(csv_filename) as f: # step 3\n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] # step 4\n",
" self.rows = rows[1:]\n",
" for row in self.rows: # step 5\n",
" row[-1] = int(row[-1])\n",
"\n",
"inventory = Inventory('laptops.csv') # step 6\n",
"print(inventory.header) # step 7\n",
"print(len(inventory.rows)) # step 8"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Finding a Laptop From the Id\n",
"\n",
"Implement a `get_laptop_from_id()` function that given a laptop identifier find the row corresponding to that laptop."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"import csv \n",
"\n",
"class Inventory(): \n",
" \n",
" def __init__(self, csv_filename):\n",
" with open(csv_filename) as f: \n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] \n",
" self.rows = rows[1:]\n",
" for row in self.rows: \n",
" row[-1] = int(row[-1])\n",
" \n",
" def get_laptop_from_id(self, laptop_id): # step 1\n",
" for row in self.rows: # step 2\n",
" if row[0] == laptop_id:\n",
" return row\n",
" return None # step 3"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['3362737', 'HP', '250 G6', 'Notebook', '15.6', 'Full HD 1920x1080', 'Intel Core i5 7200U 2.5GHz', '8GB', '256GB SSD', 'Intel HD Graphics 620', 'No OS', '1.86kg', 575]\n",
"None\n"
]
}
],
"source": [
"inventory = Inventory('laptops.csv') # step 4\n",
"print(inventory.get_laptop_from_id('3362737')) # step 5\n",
"print(inventory.get_laptop_from_id('3362736')) # step 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Improving Id Lookups\n",
"\n",
"Improve the time complexity of finding a laptop with a given id by precomputing a dictionary that maps laptop ids to rows."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"import csv \n",
"\n",
"class Inventory(): \n",
" \n",
" def __init__(self, csv_filename):\n",
" with open(csv_filename) as f: \n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] \n",
" self.rows = rows[1:]\n",
" for row in self.rows: \n",
" row[-1] = int(row[-1])\n",
" self.id_to_row = {} # step 1\n",
" for row in self.rows: # step 2\n",
" self.id_to_row[row[0]] = row \n",
" \n",
" def get_laptop_from_id(self, laptop_id):\n",
" for row in self.rows: \n",
" if row[0] == laptop_id:\n",
" return row\n",
" return None \n",
" \n",
" def get_laptop_from_id_fast(self, laptop_id): # step 3\n",
" if laptop_id in self.id_to_row: # step 4\n",
" return self.id_to_row[laptop_id]\n",
" return None"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Test the code:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['3362737', 'HP', '250 G6', 'Notebook', '15.6', 'Full HD 1920x1080', 'Intel Core i5 7200U 2.5GHz', '8GB', '256GB SSD', 'Intel HD Graphics 620', 'No OS', '1.86kg', 575]\n",
"None\n"
]
}
],
"source": [
"inventory = Inventory('laptops.csv') # step 5\n",
"print(inventory.get_laptop_from_id_fast('3362737')) # step 6\n",
"print(inventory.get_laptop_from_id_fast('3362736')) # step 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Comparing Performance\n",
"\n",
"Compare the performance of both function for id lookup."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.5494911670684814\n",
"0.002789735794067383\n"
]
}
],
"source": [
"import time # step 1\n",
"import random # step 2\n",
"\n",
"ids = [str(random.randint(1000000, 9999999)) for _ in range(10000)] # step 3\n",
"\n",
"inventory = Inventory('laptops.csv') # step 4\n",
"\n",
"total_time_no_dict = 0 # step 5\n",
"for identifier in ids: # step 6\n",
" start = time.time() # step 6.1\n",
" inventory.get_laptop_from_id(identifier) # step 6.2\n",
" end = time.time() # step 6.3\n",
" total_time_no_dict += end - start # step 6.4\n",
" \n",
"total_time_dict = 0 # step 7\n",
"for identifier in ids: # step 8\n",
" start = time.time() # step 8.1\n",
" inventory.get_laptop_from_id_fast(identifier) # step 8.2\n",
" end = time.time() # step 8.3\n",
" total_time_dict += end - start # step 8.4\n",
" \n",
"print(total_time_no_dict) # step 9\n",
"print(total_time_dict)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Analysis\n",
"\n",
"We got:\n",
"\n",
"```text\n",
"0.5884554386138916\n",
"0.0024595260620117188\n",
"```\n",
"\n",
"We can see a significant improve in performance. If we divide _0.588_ by _0.002_ we see that the new method is about _294_ times faster for this input size."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Two Laptop Promotion\n",
"\n",
"Write a method that finds whether we can spend a given amount of money by purchasing either one or two laptops."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"import csv \n",
"\n",
"class Inventory(): \n",
" \n",
" def __init__(self, csv_filename):\n",
" with open(csv_filename) as f: \n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] \n",
" self.rows = rows[1:]\n",
" for row in self.rows: \n",
" row[-1] = int(row[-1])\n",
" self.id_to_row = {} \n",
" for row in self.rows: \n",
" self.id_to_row[row[0]] = row \n",
" \n",
" def get_laptop_from_id(self, laptop_id):\n",
" for row in self.rows: \n",
" if row[0] == laptop_id:\n",
" return row\n",
" return None \n",
" \n",
" def get_laptop_from_id_fast(self, laptop_id): \n",
" if laptop_id in self.id_to_row: \n",
" return self.id_to_row[laptop_id]\n",
" return None\n",
"\n",
" def check_promotion_dollars(self, dollars): # step 1\n",
" for row in self.rows: # step 2\n",
" if row[-1] == dollars:\n",
" return True\n",
" for row1 in self.rows: # step 3\n",
" for row2 in self.rows:\n",
" if row1[-1] + row2[-1] == dollars:\n",
" return True\n",
" return False # step 4"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"False\n"
]
}
],
"source": [
"inventory = Inventory('laptops.csv') # step 5\n",
"print(inventory.check_promotion_dollars(1000)) # step 6\n",
"print(inventory.check_promotion_dollars(442)) # step 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Optimizing Laptop Promotion\n",
"\n",
"Create a faster version of the promotion method by using the techniques we've learned in the course."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"import csv \n",
"\n",
"class Inventory(): \n",
" \n",
" def __init__(self, csv_filename):\n",
" with open(csv_filename) as f: \n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] \n",
" self.rows = rows[1:]\n",
" for row in self.rows: \n",
" row[-1] = int(row[-1])\n",
" self.id_to_row = {} \n",
" for row in self.rows: \n",
" self.id_to_row[row[0]] = row\n",
" self.prices = set() # step 1\n",
" for row in self.rows: # step 2\n",
" self.prices.add(row[-1])\n",
" \n",
" def get_laptop_from_id(self, laptop_id):\n",
" for row in self.rows: \n",
" if row[0] == laptop_id:\n",
" return row\n",
" return None \n",
" \n",
" def get_laptop_from_id_fast(self, laptop_id): \n",
" if laptop_id in self.id_to_row: \n",
" return self.id_to_row[laptop_id]\n",
" return None\n",
"\n",
" def check_promotion_dollars(self, dollars): \n",
" for row in self.rows: \n",
" if row[-1] == dollars:\n",
" return True\n",
" for row1 in self.rows: \n",
" for row2 in self.rows:\n",
" if row1[-1] + row2[-1] == dollars:\n",
" return True\n",
" return False \n",
" \n",
" def check_promotion_dollars_fast(self, dollars): # step 3\n",
" if dollars in self.prices: # step 4\n",
" return True\n",
" for price in self.prices: # step 5\n",
" if dollars - price in self.prices:\n",
" return True\n",
" return False # step 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Test the code:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"False\n"
]
}
],
"source": [
"inventory = Inventory('laptops.csv') # step 7\n",
"print(inventory.check_promotion_dollars_fast(1000)) # step 8\n",
"print(inventory.check_promotion_dollars_fast(442)) # step 9"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Comparing Promotion Functions\n",
"\n",
"Compare the performance of both methods for the promotion."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.7781209945678711\n",
"0.0003719329833984375\n"
]
}
],
"source": [
"prices = [random.randint(100, 5000) for _ in range(100)] # step 1\n",
"\n",
"inventory = Inventory('laptops.csv') # step 2\n",
"\n",
"total_time_no_dict = 0 # step 3\n",
"for price in prices: # step 4\n",
" start = time.time() # step 4.1\n",
" inventory.check_promotion_dollars(price) # step 4.2\n",
" end = time.time() # step 4.3\n",
" total_time_no_dict += end - start # step 4.4\n",
" \n",
"total_time_dict = 0 # step 5\n",
"for price in prices: # step 6\n",
" start = time.time() # step 6.1\n",
" inventory.check_promotion_dollars_fast(price) # step 6.2\n",
" end = time.time() # step 6.3\n",
" total_time_dict += end - start # step 6.4\n",
" \n",
"print(total_time_no_dict) # step 7\n",
"print(total_time_dict)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Analysis\n",
"\n",
"We got:\n",
"\n",
"```text\n",
"0.7781209945678711\n",
"0.0003719329833984375\n",
"```\n",
"\n",
"We can see a significant improve in performance. If we divide _0.7781_ by _0.0002_ we see that the new method is about _2593_ times faster for this input size."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Finding Laptops Within a Budget\n",
"\n",
"Implement a method for finding the range of indexes of laptops that fall within a budget."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"683\n",
"-1\n"
]
}
],
"source": [
"import csv \n",
"\n",
"def row_price(row):\n",
" return row[-1]\n",
"\n",
"class Inventory(): \n",
" \n",
" def __init__(self, csv_filename):\n",
" with open(csv_filename) as f: \n",
" reader = csv.reader(f)\n",
" rows = list(reader)\n",
" self.header = rows[0] \n",
" self.rows = rows[1:]\n",
" for row in self.rows: \n",
" row[-1] = int(row[-1])\n",
" self.id_to_row = {} \n",
" for row in self.rows: \n",
" self.id_to_row[row[0]] = row\n",
" self.prices = set() \n",
" for row in self.rows: \n",
" self.prices.add(row[-1])\n",
" self.rows_by_price = sorted(self.rows, key=row_price) # Step 1\n",
" \n",
" def get_laptop_from_id(self, laptop_id):\n",
" for row in self.rows: \n",
" if row[0] == laptop_id:\n",
" return row\n",
" return None \n",
" \n",
" def get_laptop_from_id_fast(self, laptop_id): \n",
" if laptop_id in self.id_to_row: \n",
" return self.id_to_row[laptop_id]\n",
" return None\n",
"\n",
" def check_promotion_dollars(self, dollars): \n",
" for row in self.rows: \n",
" if row[-1] == dollars:\n",
" return True\n",
" for row1 in self.rows: \n",
" for row2 in self.rows:\n",
" if row1[-1] + row2[-1] == dollars:\n",
" return True\n",
" return False \n",
" \n",
" def check_promotion_dollars_fast(self, dollars):\n",
" if dollars in self.prices: \n",
" return True\n",
" for price in self.prices: \n",
" if dollars - price in self.prices:\n",
" return True\n",
" return False \n",
" \n",
" def find_laptop_with_price(self, target_price):\n",
" range_start = 0 \n",
" range_end = len(self.rows_by_price) - 1 \n",
" while range_start < range_end:\n",
" range_middle = (range_end + range_start) // 2 \n",
" value = self.rows_by_price[range_middle][-1]\n",
" if value == target_price: \n",
" return range_middle \n",
" elif value < target_price: \n",
" range_start = range_middle + 1 \n",
" else: \n",
" range_end = range_middle - 1 \n",
" if self.rows_by_price[range_start][-1] != target_price: \n",
" return -1 \n",
" return range_start\n",
" \n",
" def find_first_laptop_more_expensive(self, target_price): # Step 2\n",
" range_start = 0 \n",
" range_end = len(self.rows_by_price) - 1 \n",
" while range_start < range_end:\n",
" range_middle = (range_end + range_start) // 2 \n",
" price = self.rows_by_price[range_middle][-1]\n",
" if price > target_price:\n",
" range_end = range_middle\n",
" else:\n",
" range_start = range_middle + 1\n",
" if self.rows_by_price[range_start][-1] <= target_price: \n",
" return -1 \n",
" return range_start\n",
"\n",
"inventory = Inventory('laptops.csv') # Step 3 \n",
"print(inventory.find_first_laptop_more_expensive(1000)) # Step 4\n",
"print(inventory.find_first_laptop_more_expensive(10000)) # Step 5\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}