Optimized Solution to find the combination with max Values

Question

I have written the code to generate the random nested list and genrate the unique combinations and returned the result with max_Result in descending order

import random
import itertools

outer_list = []
inner_list_size = 40

for i in range(400):
    inner_list = [random.randint(-100, 100) for j in range(inner_list_size)]
    outer_list.append(inner_list)

nested_list = outer_list
n = 3

result_dict = {}
for i in range(1, n+1):
    for combination in itertools.combinations(nested_list, i):
        max_values = [max(group) for group in zip(*combination)]
        cumulative_sum = [sum(max_values[:j+1]) for j in range(min(n, len(max_values)))]
        sublist_name = ''.join([chr(65 + nested_list.index(lst)) for lst in combination])
        result_dict[sublist_name] = sum(max_values)

sorted_dict = {k: v for k, v in sorted(result_dict.items(), key=lambda item: item[1], reverse=True)}

for sublist_name, cumulative_sum in sorted_dict.items():
    print(cumulative_sum, '--->', sublist_name)

The problem with this code is it takes too long to run i want to optimize it in both space and time complexity and make this programm runnable in 4gb ram system as well and also i just need the top 100 result of the final result

Edit 1 as suggested by @KellyBundy

import random
import itertools
import heapq

outer_list = []
inner_list_size = 40

for i in range(400):
    inner_list = [random.randint(-100, 100) for j in range(inner_list_size)]
    outer_list.append(inner_list)

nested_list = outer_list
# nested_list = [[1,2,3,4],[5,4,3,2],[100,0,0,0]]
n = 3
num_top_results = 100

result_heap = []
for i in range(1, n+1):
    for combination in itertools.combinations(nested_list, i):
        max_values = [max(group) for group in zip(*combination)]
        sublist_name = ''.join([chr(65 + nested_list.index(lst)) for lst in combination])
        result_sum = sum(max_values)
        if len(result_heap) < num_top_results:
            heapq.heappush(result_heap, (result_sum, sublist_name))
        elif result_sum > result_heap[0][0]:
            heapq.heappushpop(result_heap, (result_sum, sublist_name))

sorted_results = sorted(result_heap, key=lambda x: x[0], reverse=True)
for result_sum, sublist_name in sorted_results:
    print(result_sum, '--->', sublist_name)

Edit 2 Using Numpy as suggested by @ Guimoute

import numpy as np
import heapq

outer_list = np.random.randint(-100, 100, size=(50, 4))
# outer_list = [[1,2,3,4],[5,4,3,2],[100,0,0,0]]
n = 3
num_top_results = 100

result_heap = []
for i in range(1, n+1):
    for combination in itertools.combinations(outer_list, i):
        max_values = np.max(combination, axis=0)
        cumulative_sum = np.cumsum(max_values)
        sublist_name = ''.join([chr(65 + np.where((outer_list == lst).all(axis=1))[0][0]) for lst in combination])
        result_sum = np.sum(max_values)
        if len(result_heap) < num_top_results:
            heapq.heappush(result_heap, (result_sum, sublist_name))
        elif result_sum > result_heap[0][0]:
            heapq.heappushpop(result_heap, (result_sum, sublist_name))

sorted_results = sorted(result_heap, key=lambda x: x[0], reverse=True)
for result_sum, sublist_name in sorted_results:
    print(result_sum, '--->', sublist_name)

Edit 4 :

# Imports.
import itertools
import numpy as np

# Constants.
ROWS = 40
COLUMNS = 400
N = 3
ONLY_SHOW_TOP_ITEMS = 100
RANDINT_BOUNDARIES = (-100, +100)

# Helpful functions.
def index_of_row(array, row) -> int:
    for i in range(len(array)):
        if np.array_equal(array[i], row):
            return i
    return -1
    
# Data.
# random_numbers_matrix = np.array([[1,2,3,4],[5,4,3,2],[100,0,0,0]])
random_numbers_matrix = np.random.randint(*RANDINT_BOUNDARIES, (ROWS, COLUMNS)) 
if __name__ == "__main__":
    
    # Fill the dict.
    results_dict = {}
    for i in range(1, N+1):
        for combination in itertools.combinations(random_numbers_matrix, i):        
            name = ''.join([chr(65 + index_of_row(random_numbers_matrix, lst)) for lst in combination])
            max_values = np.max(combination, axis=0)
            sum_ = np.sum(max_values)
            results_dict[name] = max(sum_, results_dict.get(name, -np.inf)) # Support empty dict entry on the first iteration.
    
    # Print the results.
    sorted_results = {k: v for k, v in sorted(results_dict.items(), key=lambda item: item[1], reverse=True)}
    for n, (sublist_name, result_sum) in enumerate(sorted_results.items()):
        print(result_sum, '--->', sublist_name)
        if n >= ONLY_SHOW_TOP_ITEMS:
            break

Can It be optimezed any further or does it have any drawbacks now.

The first step would be to use numpy. `max`, `sum` and `cumsum` alone will be orders of magnitude faster. — Guimoute, Mar 04 '23 at 16:52
Would be good if you could say the time/memory used for the approaches. — Kelly Bundy, Mar 04 '23 at 17:02
in your first and second code, you have a list of shape (400, 40), giving `math.comb(400, 3)` = 10586800 combinations, in your third code you have a list of shape (50, 4), giving only `math.comb(50, 3)` = 19600 combinations. Which one is correct? The number of combinations seems to have the biggest impact on performance (I didn't test it) — Aemyl, Mar 04 '23 at 17:23
i had reduced the size to be little small so that other people can run it however the actual size is (400, 40) — Sachin Rajput, Mar 04 '23 at 17:39

score 0 · Answer 1 · answered Mar 04 '23 at 19:09

Based on the 4th code example in your question (which looks like it was taken from @Guimote's deleted answer), I added some optimizations:

instead of calling itertools.combinations on the matrix directly, it is called on the index space. This way, no helper function is needed
I changed the data structure of the results from dict[name, sum] to list[tuple[sum, name]]. This allows calling sorted and min without lambda expressions
the optimized code only stores ONLY_SHOW_TOP_ITEMS entries in results instead of ~math.comb(ROWS, MAX_SELECTED_ROWS) key, value pairs
I also did some renaming and other refactoring, mostly for readability reasons and personal preference

The code needs ~15MB RAM and ~3 minutes on my machine.

# coding: utf-8

from itertools import combinations
from time import perf_counter

import numpy as np

ROWS = 400
COLUMNS = 40
MAX_SELECTED_ROWS = 3
ONLY_SHOW_TOP_ITEMS = 100
RANDINT_BOUNDARIES = (-100, +100)


# random_numbers_matrix = np.array([[1, 2, 3, 4],
#                                   [5, 4, 3, 2],
#                                   [100, 0, 0, 0]])
random_numbers_matrix = np.random.randint(*RANDINT_BOUNDARIES, (ROWS, COLUMNS))


def main():
    results = []
    lowest_sum = -np.inf
    for num_selected_rows in range(1, MAX_SELECTED_ROWS+1):
        for indices in combinations(range(len(random_numbers_matrix)), num_selected_rows):
            name = ''.join([chr(65 + row_index) for row_index in indices])
            max_values = np.max(random_numbers_matrix[[indices]], axis=0)
            sum_ = np.sum(max_values)
            if len(results) < ONLY_SHOW_TOP_ITEMS:
                if sum_ < lowest_sum:
                    lowest_sum = sum_
                results.append((sum_, name))
            elif sum_ > lowest_sum:
                results.append((sum_, name))
                for i, combination in enumerate(results):
                    if combination[0] == lowest_sum:
                        break
                results.pop(i)
                lowest_sum = min(results)[0]
    
    # print the results
    for result_sum, name in sorted(results, reverse=True):
        print(result_sum, '--->', name)


if __name__ == '__main__':
    t0 = perf_counter()
    main()
    t1 = perf_counter()
    print(f"finished in {t1-t0:.1f} seconds")

Optimized Solution to find the combination with max Values

1 Answers1