import heapq
import bisect
import random
import time
def choose_first_n(num_items, targets, threshold):
for target_id, target in enumerate(targets):
if target >= threshold:
num_items -= 1
if num_items == 0:
return target_id
return len(targets)
# 2s for optimised
#num_bread = 90000
#num_days = 1000000
#num_people = 1000000
# 2s for unoptimized
num_bread = 900
num_days = 10000
num_people = 10000
targets = [random.random() for _ in range(num_people)]
result_sum = 0
algo_naive_start = time.time()
for threshold in range(num_days):
result = choose_first_n(num_bread, targets, threshold/num_days)
result_sum += result
#print(f"Threshold: {threshold}, Result: {result}")
algo_naive_end = time.time()
print(f"Result naive: {result_sum}")
def preprocess(targets, num_items):
# our heap, will contain the first num_items smallest targets
largest_targets_heap = []
# Our first preprocessing result, will contain the
# third large number between the first item and the current item,
# for every item.
third_largest_number_per_target = []
# Compute the third largest previous value for every target
for target in targets:
heapq.heappush(largest_targets_heap, target)
if len(largest_targets_heap) > num_items:
heapq.heappop(largest_targets_heap)
current_third_largest = largest_targets_heap[0]
third_largest_number_per_target.append(current_third_largest)
# We now have the third largest number for every target.
# Now, consolidate that data into a lookup table, to prevent duplication.
# Therefore, find the first occurrence of every number
lookup_table_indices = []
lookup_table_values = []
current_value = third_largest_number_per_target[num_items - 1]
# Push the (num_items-1)th value to account for the fact our heap wasn't filled up until the
# first num_items were processed
lookup_table_indices.append(num_items - 1)
lookup_table_values.append(current_value)
# Fill the rest of the lookup table
for index, value in enumerate(third_largest_number_per_target):
if index < num_items - 1:
continue
if value != current_value:
lookup_table_indices.append(index)
lookup_table_values.append(value)
current_value = value
# The lookup table we have, consisting of values, indices, a minimum and a maximum value
lookup_table = (lookup_table_values, lookup_table_indices, num_items, len(targets))
return lookup_table
def choose_first_n_preprocessed(lookup_table, threshold):
(lookup_table_values, lookup_table_indices, min_value, max_value) = lookup_table
# We need to find the first (value,index) pair in lookup table where value is larger or equal to threshold
# We do this by using bisect, which is really fast. This is only possible because of our preprocessing.
position = bisect.bisect_left(lookup_table_values, threshold)
# If we didn't find a result in the preprocessed table, we return the max value, to indicate that the
# threshold ist too high.
if position >= len(lookup_table_indices):
return max_value
# Read the result from the table of incides
value = lookup_table_indices[position]
return value
def baker_queue(num_loaves_per_day, people_max_waiting_time, required_baking_times):
# Create the preprocessed lookup table
lookup_table = preprocess(people_max_waiting_time, num_loaves_per_day)
# For every day, compute the result
results = []
for today_baking_time in required_baking_times:
# Use our fast lookup based algorithm now
result = choose_first_n_preprocessed(lookup_table, today_baking_time)
# Convert indices back to starting with 1, and 0 in error case, as
# the original format was
if result == len(people_max_waiting_time):
results.append(0)
else:
results.append(result + 1)
return results
algo_preprocessed_start = time.time()
lookup_table = preprocess(targets, num_bread)
algo_preprocessed_mid = time.time()
#print(lookup_table)
result_sum = 0
for threshold in range(num_days):
result = choose_first_n_preprocessed(lookup_table, threshold/num_days)
result_sum += result
#print(f"Threshold: {threshold}, Result: {result}")
algo_preprocessed_end = time.time()
print(f"Result preprocessed: {result_sum}")
print(f"Time naive: {algo_naive_end - algo_naive_start} s")
print(f"Time preprocessed (preprocessing step): {algo_preprocessed_mid - algo_preprocessed_start} s")
print(f"Time preprocessed (evaluation step): {algo_preprocessed_end - algo_preprocessed_mid} s")
print(f"Time preprocessed total: {algo_preprocessed_end - algo_preprocessed_start} s")