Memory savings with categoricals in Pandas - Time & Space Complexity

Time Complexity: Memory savings with categoricals

O(n)

Understanding Time Complexity

We want to understand how using categorical data affects the time it takes to work with data in pandas.

Specifically, how does changing data type to categorical impact the speed of operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

# Create a large DataFrame with repeated string values
n = 1000000
values = ['apple', 'banana', 'cherry', 'date']
df = pd.DataFrame({'fruit': [values[i % 4] for i in range(n)]})

# Convert the 'fruit' column to categorical type
df['fruit_cat'] = df['fruit'].astype('category')

This code creates a large list of repeated fruit names and converts the column to a categorical type.

Identify Repeating Operations

• Primary operation: Creating the list of fruit names by repeating 4 values n times.
• How many times: The list is built with n = 1,000,000 items.
• Conversion operation: Mapping each string to a category code during the type conversion.
• How many times: Each of the n items is processed once to assign a category code.

How Execution Grows With Input

As the number of rows n grows, the time to create the list and convert to categorical grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 string assignments and 10 category mappings
100	About 100 string assignments and 100 category mappings
1000	About 1000 string assignments and 1000 category mappings

Pattern observation: The work grows directly with the number of rows, so doubling rows doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert to categorical grows linearly with the number of rows in the data.

Common Mistake

[X] Wrong: "Converting to categorical makes operations instantly faster regardless of data size."

[OK] Correct: The conversion itself takes time proportional to data size because each item is processed once. The speedup happens later in some operations, not during conversion.

Interview Connect

Understanding how data type changes affect processing time helps you write efficient data code and explain your choices clearly.

Self-Check

What if we changed the number of unique values from 4 to 1000? How would the time complexity of converting to categorical change?

Practice

1.

What is the main benefit of converting a pandas column to category type?

easy

A. It sorts the data automatically

B. It saves memory by storing repeated values efficiently

C. It converts numbers to strings

D. It removes missing values

Solution

1. Step 1: Understand what category type does

   The category type stores repeated text values once and uses codes internally.

2. Step 2: Identify the main benefit

   This reduces memory usage because repeated strings are not stored multiple times.

3. Final Answer:

   It saves memory by storing repeated values efficiently -> Option B

4. Quick Check:

   Memory savings = A [OK]

Hint: Remember: categories store repeated text once [OK]

Common Mistakes:

• Thinking it sorts data automatically
• Confusing category with string conversion
• Assuming it removes missing values

2.

Which of the following is the correct way to convert a pandas DataFrame column df['color'] to a categorical type?

import pandas as pd
df = pd.DataFrame({'color': ['red', 'blue', 'red', 'green']})

easy

A. df['color'] = df['color'].astype('category')

B. df['color'] = df['color'].to_category()

C. df['color'] = pd.category(df['color'])

D. df['color'] = df['color'].convert('category')

Solution

1. Step 1: Recall pandas syntax for type conversion

   Use astype('category') to convert a column to categorical type.

2. Step 2: Check each option

   Only df['color'] = df['color'].astype('category') uses the correct astype method with 'category' string.

3. Final Answer:

   df['color'] = df['color'].astype('category') -> Option A

4. Quick Check:

   astype('category') = A [OK]

Hint: Use astype('category') to convert columns [OK]

Common Mistakes:

• Using non-existent methods like to_category()
• Trying to call pd.category() which does not exist
• Using convert() instead of astype()

3.

What will be the output of the following code?

import pandas as pd
import sys

df = pd.DataFrame({'fruit': ['apple', 'banana', 'apple', 'banana', 'cherry']})
mem_before = df['fruit'].memory_usage()
df['fruit'] = df['fruit'].astype('category')
mem_after = df['fruit'].memory_usage()
print(mem_before, mem_after)

medium

A. 112 80

B. 80 80

C. 80 112

D. 112 112

Solution

1. Step 1: Calculate memory before conversion

   Strings take more memory; here memory_usage() returns 112 bytes before conversion.

2. Step 2: Calculate memory after conversion to category

   Category stores codes and unique values separately, reducing memory to 80 bytes.

3. Final Answer:

   112 80 -> Option A

4. Quick Check:

   Memory before > after = C [OK]

Hint: Memory decreases after astype('category') [OK]

Common Mistakes:

• Assuming memory stays the same
• Thinking memory increases after conversion
• Confusing order of printed values

4.

Identify the error in the following code that tries to convert a column to categorical and save memory:

import pandas as pd
df = pd.DataFrame({'city': ['NY', 'LA', 'NY', 'SF']})
df['city'] = df['city'].astype(category)

medium

A. DataFrame creation syntax is wrong

B. astype cannot convert to category type

C. Missing quotes around 'category' in astype

D. Column 'city' does not exist

Solution

1. Step 1: Check astype argument

   The argument to astype must be a string 'category', but here category is unquoted, causing a NameError.

2. Step 2: Verify other parts

   DataFrame creation and column name are correct; astype supports 'category'.

3. Final Answer:

   Missing quotes around 'category' in astype -> Option C

4. Quick Check:

   Quotes needed for 'category' string [OK]

Hint: Always quote 'category' in astype('category') [OK]

Common Mistakes:

• Forgetting quotes around 'category'
• Thinking astype can't convert to category
• Assuming column name is wrong

5.

You have a DataFrame with a column df['status'] containing 1 million rows with only 3 unique values: 'new', 'in_progress', 'done'. How can you reduce memory usage effectively?

hard

A. Replace values with integers manually without category

B. Convert df['status'] to string type

C. Drop the df['status'] column

D. Convert df['status'] to category type

Solution

1. Step 1: Understand the data characteristics

   With only 3 unique values repeated 1 million times, storing as category saves memory by storing unique values once.

2. Step 2: Compare options

   Converting to string keeps large memory; dropping column loses data; manual integer replacement is error-prone and less efficient.

3. Final Answer:

   Convert df['status'] to category type -> Option D

4. Quick Check:

   Few unique values + large rows = category [OK]

Hint: Use category for few unique values in large data [OK]

Common Mistakes:

• Using string type which uses more memory
• Dropping column losing important data
• Manual integer replacement without category benefits