'Zero fuera' una matriz con Python -- python campo con python-3.x campo con unit-testing campo con matrix campo con complexity camp codereview Relacionados El problema

'Zero out' a matrix using Python


2
vote

problema

Español

A continuación se muestra mi código para una solución intentada para agrietar la entrevista de codificación Ejercicio 1.8 Escrito en Python 3.5. La declaración del problema es:

Escriba un algoritmo de modo que si un elemento en una matriz MXN es 0, toda su fila y columna se establecen en 0.

Miré los consejos para este problema, así que sé que mi solución no es la más eficiente posible. Creo que la complejidad del tiempo del código a continuación es $ O (m * n) $ y la complejidad del espacio es $ O (M + N) $. Escribí pequeñas pruebas de unidad para probar mi código. Buscando comentarios sobre lo que se debe mejorar, especialmente en términos de lectura.

  import unittest   def locate_zero_rows(matrix: list) -> list:     """Given an NxM matrix find the rows that contain a zero."""     zero_rows = [False for _ in range(len(matrix))]     for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if element == 0:                 zero_rows[row_num] = True     return zero_rows   def locate_zero_cols(matrix: list) -> list:     """Given an NxM matrix find the columns that contain a zero."""     zero_cols = [False for _ in range(len(matrix[0]))]     for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if element == 0:                 zero_cols[col_num] = True     return zero_cols   def zero_out(matrix: list) -> list:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_rows, zero_cols = locate_zero_rows(matrix), locate_zero_cols(matrix)      for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if zero_rows[row_num] or zero_cols[col_num]:                 matrix[row_num][col_num] = 0     return matrix   class MyTest(unittest.TestCase):     def test_locate_zero_rows(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zero_rows = [False, True, True]         self.assertSequenceEqual(locate_zero_rows(matrix), zero_rows)      def test_locate_zero_cols(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zero_cols = [True, True, False, True]         self.assertSequenceEqual(locate_zero_cols(matrix), zero_cols)      def test_zero_out(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zeroed_out_matrix = [[0, 0, 2, 0],                              [0, 0, 0, 0],                              [0, 0, 0, 0]]         self.assertSequenceEqual(zero_out(matrix), zeroed_out_matrix)   if __name__ == '__main__':     unittest.main()   
Original en ingles

Below is my code for an attempted solution to cracking the coding interview exercise 1.8 written in python 3.5. The problem statement is:

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

I looked at the hints for this problem so I do know that my solution is not the most space efficient possible. I believe the time complexity of the code below is \$O(M*N)\$ and the space complexity is \$O(M + N)\$. I wrote small unit tests to test my code. Looking for feedback on what needs to be improved, especially in terms of readability.

import unittest   def locate_zero_rows(matrix: list) -> list:     """Given an NxM matrix find the rows that contain a zero."""     zero_rows = [False for _ in range(len(matrix))]     for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if element == 0:                 zero_rows[row_num] = True     return zero_rows   def locate_zero_cols(matrix: list) -> list:     """Given an NxM matrix find the columns that contain a zero."""     zero_cols = [False for _ in range(len(matrix[0]))]     for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if element == 0:                 zero_cols[col_num] = True     return zero_cols   def zero_out(matrix: list) -> list:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_rows, zero_cols = locate_zero_rows(matrix), locate_zero_cols(matrix)      for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if zero_rows[row_num] or zero_cols[col_num]:                 matrix[row_num][col_num] = 0     return matrix   class MyTest(unittest.TestCase):     def test_locate_zero_rows(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zero_rows = [False, True, True]         self.assertSequenceEqual(locate_zero_rows(matrix), zero_rows)      def test_locate_zero_cols(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zero_cols = [True, True, False, True]         self.assertSequenceEqual(locate_zero_cols(matrix), zero_cols)      def test_zero_out(self):         matrix = [[5, 3, 2, 1],                   [-3, 0, 5, 0],                   [0, -1, 2, 6]]         zeroed_out_matrix = [[0, 0, 2, 0],                              [0, 0, 0, 0],                              [0, 0, 0, 0]]         self.assertSequenceEqual(zero_out(matrix), zeroed_out_matrix)   if __name__ == '__main__':     unittest.main() 
              
   
   

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

El gran problema que puedo ver es que busca en todos los elementos. No necesita hacer esto, solo necesita verificar si 0 está en cualquier lugar de esa fila o columna. Puede usar la operación 99887766655443311 para probar esto. Se encuentra un cortocircuito después de que se encuentra el primer 0 , evitando tener que buscar en toda la fila o la columna. Esto no reducirá la complejidad del tiempo, sino que mejorará considerablemente el rendimiento del mejor caso.

segundo, puede usar zip para cambiar entre filas y columnas.

Tercero, puede reducir ese cheque a una simple comprensión de la lista, la expresión del generador o la función del generador.

cuarto, puede usar ~all para detectar si hay ceros en una secuencia dada. Esto es ligeramente más rápido que in .

Finalmente, ya que está realizando los cambios en el lugar, no necesita devolver la matriz modificada.

Así que aquí está mi versión:

  import unittest   def locate_zero_rows(matrix: list) -> list:     """Given an NxM matrix find the rows that contain a zero."""     return [i for i, row in enumerate(matrix) if not all(row)]   def locate_zero_cols(matrix: list) -> list:     """Given an NxM matrix find the columns that contain a zero."""     return locate_zero_rows(zip(*matrix))   def zero_out(matrix: list) -> None:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_rows = locate_zero_rows(matrix)     zero_cols = locate_zero_cols(matrix)     ncol = len(matrix[0])     for rowi in zero_rows:         matrix[rowi] = [0]*ncol     for coli in zero_cols:         for row in matrix:             row[coli] = 0   class MyTest(unittest.TestCase):     def test_locate_zero_rows(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zero_rows = [1, 2]         self.assertSequenceEqual(locate_zero_rows(matrix), zero_rows)      def test_locate_zero_cols(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zero_cols = [0, 1, 3]         self.assertSequenceEqual(locate_zero_cols(matrix), zero_cols)      def test_zero_out(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zeroed_out_matrix = [[0, 0, 2, 0],                             [0, 0, 0, 0],                             [0, 0, 0, 0]]         zero_out(matrix)         self.assertSequenceEqual(matrix, zeroed_out_matrix)   if __name__ == '__main__':     unittest.main()   

Puede mejorar esto más al hacer la lista de la lista de columnas una expresión. Creo que esto le dará a esto un O(M) Espacio complejidad:

  def zero_out(matrix: list) -> None:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_cols = (i for i, col in enumerate(zip(*matrix)) if not all(col))     zero_rows = [i for i, row in enumerate(matrix) if not all(row)]     ncol = len(matrix[0])     for coli in zero_cols:         for row in matrix:             row[coli] = 0     for rowi in zero_rows:         matrix[rowi] = [0]*ncol   

No puede hacer ambas comprensiones con esta estructura porque los cambios a uno se reflejarían en el otro.

Es posible hacer ambas comprensiones usando itertools.zip_longest , pero no obtiene ninguna complejidad espacial (al menos para Matrices donde in0 y in1 Son similares), y duele su rendimiento.

Si puede usar NOMPY, esto se puede simplificar enormemente:

  in2  

Editar: Añadido in3 . Editar 2: Agregar adormecida Editar 3: Use in4 en lugar de in5

 

The big issue I can see is that you search every element. You don't need to do this, you only need to check if 0 is anywhere in that row or column. You can use the in operation to test this. It will short-circuit after the first 0 is found, avoiding having to search the entire row or column. This won't reduce the time complexity, but will improve the best-case performance considerably.

Second, you can use zip to switch between rows and columns.

Third, you can reduce that check to a simple list comprehension, generator expression, or generator function.

Fourth, you can use ~all to detect if there are any zeros in a given sequence. This is slightly faster than in.

Finally, since you are making the changes in-place, you don't need to return the modified matrix.

So here is my version:

import unittest   def locate_zero_rows(matrix: list) -> list:     """Given an NxM matrix find the rows that contain a zero."""     return [i for i, row in enumerate(matrix) if not all(row)]   def locate_zero_cols(matrix: list) -> list:     """Given an NxM matrix find the columns that contain a zero."""     return locate_zero_rows(zip(*matrix))   def zero_out(matrix: list) -> None:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_rows = locate_zero_rows(matrix)     zero_cols = locate_zero_cols(matrix)     ncol = len(matrix[0])     for rowi in zero_rows:         matrix[rowi] = [0]*ncol     for coli in zero_cols:         for row in matrix:             row[coli] = 0   class MyTest(unittest.TestCase):     def test_locate_zero_rows(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zero_rows = [1, 2]         self.assertSequenceEqual(locate_zero_rows(matrix), zero_rows)      def test_locate_zero_cols(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zero_cols = [0, 1, 3]         self.assertSequenceEqual(locate_zero_cols(matrix), zero_cols)      def test_zero_out(self):         matrix = [[5, 3, 2, 1],                 [-3, 0, 5, 0],                 [0, -1, 2, 6]]         zeroed_out_matrix = [[0, 0, 2, 0],                             [0, 0, 0, 0],                             [0, 0, 0, 0]]         zero_out(matrix)         self.assertSequenceEqual(matrix, zeroed_out_matrix)   if __name__ == '__main__':     unittest.main() 

You can improve this further by making the column list comprehension a expression. I think this will give this a O(M) space complexity:

def zero_out(matrix: list) -> None:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_cols = (i for i, col in enumerate(zip(*matrix)) if not all(col))     zero_rows = [i for i, row in enumerate(matrix) if not all(row)]     ncol = len(matrix[0])     for coli in zero_cols:         for row in matrix:             row[coli] = 0     for rowi in zero_rows:         matrix[rowi] = [0]*ncol 

You can't make both comprehensions with this structure because changes to one would be reflected in the other.

It is possible to make both comprehensions using itertools.zip_longest, but you don't gain any space complexity (at least for matrices where N and M are similar), and it hurts your performance.

If you can use numpy, this can be simplified enormously:

import numpy as np import unittest   def zero_out(matrix: np.array) -> None:     """Given an NxM matrix zero out all rows and columns that contain at least one zero."""     zero_cols = ~matrix.all(axis=0)     zero_rows = ~matrix.all(axis=1)     matrix[:, zero_cols] = 0     matrix[zero_rows, :] = 0   class MyTest(unittest.TestCase):     def test_zero_out(self):         matrix = np.array([[5, 3, 2, 1],                            [-3, 0, 5, 0],                            [0, -1, 2, 6]])         zeroed_out_matrix = np.array([[0, 0, 2, 0],                                       [0, 0, 0, 0],                                       [0, 0, 0, 0]])         zero_out(matrix)         np.testing.assert_array_equal(matrix, zeroed_out_matrix)   if __name__ == '__main__':     unittest.main() 

Edit: added ~all. Edit 2: Add numpy Edit 3: use not all instead of ~all

 
 
     
     
1
 
vote

Repetición

Escribiría solo una función para localizar ceros:

  in6  

y úsalo en in7 como este:

  in8  

Tipo Sugerencias

Dado que mencionó específicamente Python 3.5 y que ya tiene algo así, le gusta sugerencias de tipo en sus funciones, le sugiero que vaya hasta MyPy Sugerencias de tipo compatible.

  in9  

De esta manera, puede verificar de manera estática su código tiene los tipos correctos, como en los idiomas de tipos de forma nativa estáticamente, y darle a la información mucho más detallada en los tipos.

 

Repetition

I would write only one function to locate zeros:

def locate_zeros(matrix: IntegerMatrix) -> Iterable[Position]:     """Given an NxM matrix find the positions that contain a zero."""     for row_num, row in enumerate(matrix):         for col_num, element in enumerate(row):             if element == 0:                 yield (col_num, row_num) 

And use it in zero_out like this:

    if row_num in (x[1] for x in zeros_positions) or col_num in (x[0] for x in zeros_positions):         matrix[row_num][col_num] = 0 

Type hints

Given that you specifically mentioned Python 3.5 and that you already have something like type hints on your functions, I suggest you go all the way with mypy compatible type hints.

from typing import List, Any,  Iterable, Tuple  Position = Tuple(int, int) IntegerMatrix = List[List[int]]  def locate_zeros(matrix: IntegerMatrix) -> Iterable[Position]:  def zero_out(matrix: IntegerMatrix) -> IntegerMatrix: 

This way you can statically check your code has the correct types like in natively statically types languages and give the user much more detailed information on the types.

 
 
     
     

Relacionados problema

2  Optimización del código para la secuencia A064604  ( Optimizing code for sequence a064604 ) 
Estoy implementando a064604 - oeis para enteros positivos de hasta 10 mil millones. Estoy encontrando a los divisores en $ o ( sqrt n) $. Por lo tanto, ...

2  Tiempo de alta ejecución en el programa de partición numérico en Python 2.7  ( High execution time on number partitioning program in python 2 7 ) 
Estoy escribiendo un programa para contar solo las particiones de un número con distinta partes . Estoy usando un enfoque de abajo hacia arriba para la progr...

4  Tour de Knights - Algo que estoy haciendo mal  ( Knights tour something i am doing wrong ) 
Tengo una tarea para escribir un programa de backtracking de Knights Tour en Java donde dice el profesor a: Eliminar el tiempo de retroceso por: Find the...

4  Python Encuentra todos los subconjuntos adyacentes del conjunto de monedas que tienen una minoría de colas  ( Python find all adjacent subsets of set of coins which have a tails minority ) 
Dada una secuencia de cabezas y colas, quiero encontrar cuántas subsiguientes significativas hay en esta secuencia donde el número de cabezas no es menor que ...

7  Compruebe la consistencia de una lista de declaraciones, con coincidencia de rima difusa  ( Check consistency of a list of statements with fuzzy rhyme matching ) 
Hice un programa hoy que resuelve lo siguiente problema en un sitio de competencia de programación (Open.Kattis.com) : verifique si todas las declaraciones c...

5  Números psicosicos y ordinarios  ( Psycho and ordinary numbers ) 
La declaración del problema se puede encontrar aquí . En resumen, aquí es cuál es el problema sobre: ​​ Se le da un conjunto de números y necesita encontra...

7  Un algoritmo de partición para enteros positivos  ( A partition algorithm for positive integers ) 
He encontrado el siguiente problema que encontré muy interesante para resolver: Dada una matriz de enteros positivos {A1, A2, ..., A} Se requiere para pa...

-1  Encontrar la distancia desde cada elemento de matriz a la entrada cero más cercana  ( Finding the distance from each array element to the nearest zero entry ) 
Escribí un programa, que obtiene una cierta matriz y reemplaza cada valor en la matriz con la distancia de ella al valor cero más cercano. La complejidad del ...

7  Encontrar trillizos únicos agregando hasta 0  ( Finding unique triplets adding up to 0 ) 
Estoy trabajando en un problema "3Sum", en el que, dado una matriz var lastName = Request.Params["lastName"] ?? ""0 de var lastName = Request.Params["lastN...

2  HackerRank: Rotación de la matriz izquierda en Python  ( Hackerrank left array rotation in python ) 
Aquí está el problema en Hackerrank . Quiero saber cómo puedo mejorar este código. Estoy tratando principalmente de mejorar las siguientes habilidades: la do...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos