fork download
copy 
  1. import heapq
  2. import bisect
  3. import random
  4. import time
  5.  
  6. def choose_first_n(num_items, targets, threshold):
  7.     for target_id, target in enumerate(targets):
  8.         if target >= threshold:
  9.             num_items -= 1
  10.             if num_items == 0:
  11.                 return target_id
  12.     return len(targets)
  13.  
  14. # 2s for optimised
  15. #num_bread = 90000
  16. #num_days = 1000000
  17. #num_people = 1000000
  18.  
  19. # 2s for unoptimized
  20. num_bread = 900
  21. num_days = 10000
  22. num_people = 10000
  23.  
  24.  
  25. targets = [random.random() for _ in range(num_people)]
  26.  
  27. result_sum = 0
  28. algo_naive_start = time.time()
  29. for threshold in range(num_days):
  30.     result = choose_first_n(num_bread, targets, threshold/num_days)
  31.     result_sum += result
  32.     #print(f"Threshold: {threshold}, Result: {result}")
  33. algo_naive_end = time.time()
  34. print(f"Result naive: {result_sum}")
  35.  
  36.  
  37. def preprocess(targets, num_items):
  38.     # our heap, will contain the first num_items smallest targets
  39.     largest_targets_heap = []
  40.  
  41.     # Our first preprocessing result, will contain the
  42.     # third large number between the first item and the current item,
  43.     # for every item.
  44.     third_largest_number_per_target = []
  45.  
  46.     # Compute the third largest previous value for every target
  47.     for target in targets:
  48.         heapq.heappush(largest_targets_heap, target)
  49.         if len(largest_targets_heap) > num_items:
  50.             heapq.heappop(largest_targets_heap)
  51.  
  52.         current_third_largest = largest_targets_heap[0]
  53.         third_largest_number_per_target.append(current_third_largest)
  54.  
  55.     # We now have the third largest number for every target.
  56.     # Now, consolidate that data into a lookup table, to prevent duplication.
  57.     # Therefore, find the first occurrence of every number
  58.     lookup_table_indices = []
  59.     lookup_table_values = []
  60.     current_value = third_largest_number_per_target[num_items - 1]
  61.  
  62.     # Push the (num_items-1)th value to account for the fact our heap wasn't filled up until the
  63.     # first num_items were processed
  64.     lookup_table_indices.append(num_items - 1)
  65.     lookup_table_values.append(current_value)
  66.  
  67.     # Fill the rest of the lookup table
  68.     for index, value in enumerate(third_largest_number_per_target):
  69.         if index < num_items - 1:
  70.             continue
  71.         if value != current_value:
  72.             lookup_table_indices.append(index)
  73.             lookup_table_values.append(value)
  74.             current_value = value
  75.  
  76.     # The lookup table we have, consisting of values, indices, a minimum and a maximum value
  77.     lookup_table = (lookup_table_values, lookup_table_indices, num_items, len(targets))
  78.  
  79.     return lookup_table
  80.  
  81.  
  82. def choose_first_n_preprocessed(lookup_table, threshold):
  83.     (lookup_table_values, lookup_table_indices, min_value, max_value) = lookup_table
  84.  
  85.     # We need to find the first (value,index) pair in lookup table where value is larger or equal to threshold
  86.     # We do this by using bisect, which is really fast. This is only possible because of our preprocessing.
  87.     position = bisect.bisect_left(lookup_table_values, threshold)
  88.  
  89.     # If we didn't find a result in the preprocessed table, we return the max value, to indicate that the
  90.     # threshold ist too high.
  91.     if position >= len(lookup_table_indices):
  92.         return max_value
  93.  
  94.     # Read the result from the table of incides
  95.     value = lookup_table_indices[position]
  96.     return value
  97.  
  98.  
  99. def baker_queue(num_loaves_per_day, people_max_waiting_time, required_baking_times):
  100.     # Create the preprocessed lookup table
  101.     lookup_table = preprocess(people_max_waiting_time, num_loaves_per_day)
  102.  
  103.     # For every day, compute the result
  104.     results = []
  105.     for today_baking_time in required_baking_times:
  106.         # Use our fast lookup based algorithm now
  107.         result = choose_first_n_preprocessed(lookup_table, today_baking_time)
  108.  
  109.         # Convert indices back to starting with 1, and 0 in error case, as
  110.         # the original format was
  111.         if result == len(people_max_waiting_time):
  112.             results.append(0)
  113.         else:
  114.             results.append(result + 1)
  115.     return results
  116.  
  117.  
  118. algo_preprocessed_start = time.time()
  119.  
  120. lookup_table = preprocess(targets, num_bread)
  121.  
  122. algo_preprocessed_mid = time.time()
  123. #print(lookup_table)
  124.  
  125. result_sum = 0
  126. for threshold in range(num_days):
  127.     result = choose_first_n_preprocessed(lookup_table, threshold/num_days)
  128.     result_sum += result
  129.     #print(f"Threshold: {threshold}, Result: {result}")
  130. algo_preprocessed_end = time.time()
  131. print(f"Result preprocessed: {result_sum}")
  132.  
  133. print(f"Time naive: {algo_naive_end - algo_naive_start} s")
  134. print(f"Time preprocessed (preprocessing step): {algo_preprocessed_mid - algo_preprocessed_start} s")
  135. print(f"Time preprocessed (evaluation step): {algo_preprocessed_end - algo_preprocessed_mid} s")
  136. print(f"Time preprocessed total: {algo_preprocessed_end - algo_preprocessed_start} s")
  137.  
Success #stdin #stdout 1.88s 12184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result naive: 30518052
Result preprocessed: 30518052
Time naive: 1.8492519855499268 s
Time preprocessed (preprocessing step): 0.005570411682128906 s
Time preprocessed (evaluation step): 0.006650686264038086 s
Time preprocessed total: 0.012221097946166992 s
https://ideone.com/2ZMBVH
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!