How to make this sparse matrix and trie work in tandem

Question

I have a sparse matrix that has been exported to this format:

(1, 3) = 4
(0, 5) = 88
(6, 0) = 100
...

Strings are stored into a Trie data structure. The numbers in the previous exported sparse matrix correspond to the result of the lookup on the Trie.

Lets say the word "stackoverflow" is mapped to number '0'. I need to iterate the exported sparse matrix where the first element is equals to '0' and find the highest value.

For example:

(0, 1) = 4
(0, 3) = 8
(0, 9) = 100 <-- highest value

(0, 9) is going to win.

What would be the best implementation to store the exported sparse matrix? In general, what would be the best approach (data structure, algorithm) to handle this functionality?

Answer 1

Absent memory or dynamism constraints, probably the best approach is to slurp the sparse matrix into a map from first number to the pairs ordered by value, e.g.,

matrix_map = {}  # empty map
for (first_number, second_number, value) in matrix_triples:
    if first_number not in matrix_map:
        matrix_map[first_number] = []  # empty list
    matrix_map[first_number].append((second_number, value))
for lst in matrix_map.values():
    lst.sort(key=itemgetter(1), reverse=True)  # sort by value descending

Given a matrix like

(0, 1) = 4
(0, 3) = 8
(0, 5) = 88
(0, 9) = 100
(1, 3) = 4
(6, 0) = 100,

the finished product looks like this:

{0: [(9, 100), (5, 88), (3, 8), (1, 4)],
 1: [(3, 4)],
 6: [(0, 100)]}.