Best way to get higest value in a matrix array in python

Question

i need to check the higest value of a array but in my case its taking to long:

My array have 3 values: X, Y , Value

[
 [1,1,36],
 [1,2,36.5],
 [1,3,36.5],
 [1,4,36.5],
 [1,5,36.5],
 [2,1,36.5],
 [2,2,36.5],
 [2,3,36.5],
 [2,4,36.5],
 [2,5,36.5],
 [3,1,36.5],
 [3,2,36.5],
 [3,3,36.5],
 [3,4,36.5],
 [3,5,36.5],
]

note that my array is a x,y value for a pixel and the last info is a float value for it.

but its a small example i. Im my real case i will have 300.000 itens in my array. Id like to get the higest value inside a starting x,y and ending x,y points.

I did a for function but its taking to long to execute.

some one can help me ?

#

i have another array now that i need to get the higest value where i only have [x,y] values and to get temperatire i must to it:

value = image_data[x,y]

in the folowing exemple by DarrylG i dont know how to change it to work in this way.

i Tryed to change this line

return max(lst[index_lo:index_hi+1], key=lambda item: item[2])

to

return max(lst[index_lo:index_hi+1], key=lambda item: lst[0,1])

but it dont worked.

Answer 1

Assumption 1

Since using {} doesn't make sense, I'm assuming your values are:

my_lst = [
 [1,1,36],
 [1,2,36.5],
 [1,3,36.5],
 [1,4,36.5],
 [1,5,36.5],
 [2,1,36.5],
 [2,2,36.5],
 [2,3,36.5],
 [2,4,36.5],
 [2,5,36.5],
 [3,1,36.5],
 [3,2,36.5],
 [3,3,36.5],
 [3,4,36.5],
 [3,5,36.5],
]

Assumption 2

The first two values (i.e. X, Y) are ordered in ascending order (as in your example data).

Assumption 3

From your comments, the real problem you're trying to solve is to find max value over a limited range of the (X, Y) values.

Solution

We can't simply use (Examples using max key):

print(max(my_lst, key=lambda x: x[2]))

Since this finds the tuple with max value over the entire list. We want to find the max over a sublist.

We need a quick method to find the start and stop index in our list of tuples.

The sublist is specified by indexes of (X, Y) start/stop locations such as: start: (2, 1), finish: (3, 4).

We use the method from here which allows a binary search to find the start and stop indexes.

from bisect import bisect_left
class KeyList(object):
    # bisect doesn't accept a key function, so we build the key into our sequence.
    def __init__(self, l, key):
        self.l = l
        self.key = key
    def __len__(self):
        return len(self.l)
    def __getitem__(self, index):
        return self.key(self.l[index])

def find_max(lst, lo, hi):
  " Finds max within sublist of lo to hi tuples "

  # Binary search to find index of lo and hi pixel tuples
  index_lo = bisect_left(KeyList(lst, lambda y: (y[0], y[1])), start)
  index_hi = bisect_left(KeyList(lst, lambda y: (y[0], y[1])), finish)

  # Use slice to get sublist
  # Max based upon key which uses 3rd element of tuples
  return max(lst[index_lo:index_hi+1], key=lambda item: item[2])

Usage

print(find_max(my_lst, (2,1), (3,4)))

Output

[2, 1, 36.5]

Additional Question

In your additional question the data is actually a 2d array or grid of points.

For this type of data we don't need binary search to find where data starts and ends.

def find_max_grid(lst, lo, hi):
  " Find max within a 2d array given starting and stopping tuples "
  def max_with_index(row):
    " Finds max in a row "
    return max(enumerate(row), key=lambda v: v[1])

  r1, c1 = lo  # Starting row & column
  r2, c2 = hi  # Ending row & column

  max_row, max_col, max_val = -1, -1, 0  # Initial
  for r, row in enumerate(lst[r1:r2+1], start = r1):
    if r == r1:
      index, val  = max_with_index(row[c1:])
    elif r == r2:
      index, val = max_with_index(row[:c2+1])
    else:
      index, val = max_with_index(row)

    if val > max_val:
      max_row = r
      max_col = index
      max_val = val

  return (max_row, max_col), max_val

Usage

image_data = [
  [11, 12, 5, 2], 
  [15, 6, 10, 11], 
  [10, 8, 12, 5], 
  [12, 15, 8, 6]
  ]

# find max from row 1, column 2
# to            row 3, column 4
# rows and columns numbered are 0, 1, 2, ...
print(find_max_grid(image_data, [1, 2], [3, 4]))

Output

((3, 1), 15)  # row 3, column 1 with value 15