Planned Economy Bakery - Trying to scale a nested loop with a heap

Question

Let's say you are living in a controlled economy where there is a baker in town, and every day he bakes a random number of loaves of bread (sometimes the oven breaks, or he has less ingredients). The people in the town queue up to buy a loaf of bread (you can only buy one loaf) based on a pre-assigned ticketing system. Your position in the queue is constant every single day.

There are more people in the queue than loaves of bread available. The bread is ready at different times each day, and some people in the queue need to be at work. If the bread isn't ready before they have to leave for work, they leave the queue and the next person in line takes their place. But they still have their original queue ticket. The values in the people list are the number of hours before the person in the queue has to leave for work

I want to know what is the number on the last ticket given to the baker each day before he runs out of loaves of bread.

I can get my existing code to work for relatively small numbers of people, but if there are millions of people, lots of days (planned economies plan for 5 years ahead), you get the picture.

def BakerQueue(loaves, people, bake_time):
    got_some_bread = []
    for b in bake_time:
        counter = 0
        for p in range(len(people)):
            if people[p] >= b:
                counter += 1
                if counter == loaves:
                    got_some_bread.append(p + 1)
                    counter = 0
                    break
                elif p == len(people) - 1:
                    got_some_bread.append(0)
                    break
            elif counter < loaves and p == len(people) - 1:
                got_some_bread.append(0)
                counter = 0
    return got_some_bread

You can use this to run the code: in this example, there are 3 loaves, 19 people in the queue [list], and different bake times [list] for each of the days in a week, so on the first day, ticket 1, 2, 3 get loaves, on the second day 2,3,4 get loaves because 1 went to work as the bread wasn't ready in time, on the third day, 7, 9 and 15 get loaves because the bread took 5 hours to be ready and those people went to work. I only care about who gets the last loaf on each day which is what the function is returning.

BakerQueue(3, [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],[1, 2, 5, 4, 5, 4, 7])

This will return as expected

[3, 4, 15, 7, 15, 7, 19]

So I thought about implementing a priority queue using the heapq library, however, I need to maintain the original ticket order, so I thought to create a list of tuples with the values and the index and convert to a heap and pop the top person off of the heap if they have gone to work or if they have gotten a loaf of bread and there are still loaves available. This is the point where I begin to fail. I only care which ticket number got the last loaf of bread each day

Answer 1

I think I understood your problem.

Problem description

Given:

• num_items - the number of available items
• targets - a list of potential targets, each having a value
• threshold - a cutoff limit

Task:

• Choose the first num_items elements of targets, whose values are above or equal to threshold.
• Return the array index of the last chosen element from targets (starting with 1), or 0 if not enough targets are available. (Odd decision, I would have gone with indices starting at 0 and return len(targets) if none found, but fine)
• Optimize for speed. targets and num_items are identical every time, threshold is the only value that changes.

---

Example

num_items = 3
targets = [5,3,4,1,3,3,7,4]
threshold = 4

Chosen targets would be the ones at the positions [0,2,6], with the values [5,4,7], as those are the first 3 values that are above or equal to threshold. We only search the index of the last one, which in this case would be 6.

---

Approach

Your original idea was to iterate through all the people which is very fast if the threshold is very low, but becomes really slow if the threshold is higher, as we need to iterate through all the people until we find a candidate.

I rewrote your original idea to iterate through all of them, as I wasn't able to understand your code:

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 + 1
    return 0

def baker_queue(num_loaves_per_day, people_max_waiting_time, required_baking_times):
    results = []
    for today_baking_time in required_baking_times:
        results.append(choose_first_n(num_loaves_per_day, people_max_waiting_time, today_baking_time))
    return results

print(baker_queue(3,
                  [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],
                  [1, 2, 5, 4, 5, 4, 7]))
# Returns: [3, 4, 15, 7, 15, 7, 19], as in the original code.

Using a heap is an interesting idea, but I don't think we benefit from that in any way. Heaps are only really fast for item removal/insertion, which we don't do. We just iterate over them.

The fastest way that I could think of is to pre-process the threshold list into something more efficient, as if, create an 'index' of the last target.

Demonstration: We use our previous code, and look at the results based on the threshold value:

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 + 1
    return 0

targets = [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8]
num_items = 3

for threshold in range (10):
    result = choose_first_n(num_items, targets, threshold)
    print(f"Threshold: {threshold}, Result: {result}")

Threshold: 0, Result: 3
Threshold: 1, Result: 3
Threshold: 2, Result: 4
Threshold: 3, Result: 4
Threshold: 4, Result: 7
Threshold: 5, Result: 15
Threshold: 6, Result: 15
Threshold: 7, Result: 19
Threshold: 8, Result: 19
Threshold: 9, Result: 0

You can see that if the threshold goes up, the result goes up. There is a steadily increasing relationship between the threshold and the result.

If we can compute the values at which the result changes, we can compute the result directly via a divide-and-conquer search, which is a LOT faster than iterating through the list. (O(logn) instead of O(n), in case you are familiar with Big-O notation)

One thing to note here is that the last result is 0, which breaks that scheme. That is the reason why it is benefitial to let the indices start with 0 instead of 1, and have the 'error' case be len(targets) instead of 0.

Preprocessing

The hardest thing is the preprocessing to get to that mapping.

Let's look at it from the other way round.

For the sake of simplicity, let's say num_items is 3, and we have 10 targets. Will the chosen targets be within the first 5 targets?

The answer is: yes, IF at least 3 of the first 5 targets are above or equal to the threshold. Or in other words, the 3rd largest number in the list is the deciding factor. If the threshold is above the 3rd largest number, the first 5 targets will not provide all the chosen targets.

Therefore, for all items, we need to compute the 3rd largest number. Funnily, this is actually where a heap WILL come in handy ;)

Implementation

import heapq
import bisect

def preprocess(targets, num_items):
    # Special case if we have more items than targets, would break later.
    # Return an empty lookup table with len(targets) as fallback, so the
    # result will always be len(targets)
    if num_items > len(targets):
        lookup_table = ([], [], len(targets))
        return lookup_table

    # 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 and a maximum value
    lookup_table = (lookup_table_values, lookup_table_indices, len(targets))

    return lookup_table

def choose_first_n_preprocessed(lookup_table, threshold):
    (lookup_table_values, lookup_table_indices, 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

print(baker_queue(3,
                  [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],
                  [1, 2, 5, 4, 5, 4, 7]))
# [3, 4, 15, 7, 15, 7, 19]

Theoretical Analysis

This should now be a LOT faster, especially for a large number of days, but also for a large number of people.

The complexity of the naive implementation was

O(days * people)

The complexity of the preprocessed implementation is

O(people * log(bread) + days * log(people))

This doesn't sound a lot different, but it is. It basically says if the limiting factor is the people, it doesn't matter how many days, and if the limiting factor is the days, it doesn't matter how many people.

Benchmarking Results

Setup was:

• 900 bread per day
• 10,000 people
• 10,000 days

Result:

• Naive: 2.13 seconds
• Preprocessed: 0.012 seconds

I then tried to push the algorithm so far that it also takes 2 seconds, and got those numbers:

• 90,000 bread per day
• 1,000,000 people
• 1,000,000 days

I didn't run those numbers on the naive algorithm, but the math says it would have taken about 20,000 seconds, or 5.5 hours.

The benchmark code can be found at https://ideone.com/2ZMBVH or here:

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):
    # Special case if we have more items than targets, would break later.
    # Return an empty lookup table with len(targets) as fallback, so the
    # result will always be len(targets)
    if num_items > len(targets):
        lookup_table = ([], [], num_items, len(targets))
        return lookup_table

    # 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")

Well that took a while, I hope it was worth it ;)

I think this was my biggest post yet, it was a really interesting task!

I hope you appreciate it.

Greetings

Answer 2

@Finomnis offers an excellent theoretical and algorithmic analysis. As is my wont, I'll take a different approach and examine your usage of Python.

                counter = 0
                break

does not need the counter assignment at all. You're breaking, so you will return to the top of the outer loop where this assignment is done the first time; it needn't be repeated.

This is a classic example of the need for enumerate:

    for p in range(len(people)):
        if people[p] >= b:

In other words,

for p, person in enumerate(people):
    if person >= b:

The entire method can be well-expressed as a generator rather than using successive list concatenation:

def baker_queue(loaves, people, bake_time):
    for b in bake_time:
        counter = 0
        for p, person in enumerate(people):
            if person >= b:
                counter += 1
                if counter == loaves:
                    yield p + 1
                    break
                elif p == len(people) - 1:
                    yield 0
                    break
            elif counter < loaves and p == len(people) - 1:
                yield 0
                counter = 0