Contents

LAB 04 - Representación en memoria

!wget --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/20192.L3/master/init.py
import init; init.init(force_download=False); init.get_weblink()

import init
from local.lib.rlxmoocapi import submit, session
import inspect
student = session.Session(init.endpoint).login( course_id=init.course_id, 
                                                session_id="UDEA", 
                                                lab_id="lab_04" )

LAB 04 - Representación en memoria

Ejercicio 1

Una matriz diagonal 2D es aquella en la que cualquier elemento \(m_{ij}=0 \iff i \ne j\). Trataremos solamente con matrices cuadradas, es decir \(\in \mathbb{R}^{n \times n}\).

Si asumimos que solo tenemos matrices cuadradas, podemos almacenar solo la diagonal.

Completa la siguiente función para que, dado un array numpy de entrada:

  • Lance un AssertionError si no es cuadrado o no es diagonal

  • Devuelva un vector con las posiciones de almacenamiento de su diagonal, asumiendo una posición inicial y un tamaño de dato.

Por ejemplo, para esta entrada:

[[ 1  0  0]
 [ 0  3  0]
 [ 0  0 -3]]

con init_pos=19 y size=5, la salida debería de ser:

[19, 24, 29]

def diag_store(m, init_pos=0, size=4):
    import numpy as np
    assert <... TU CODIGO AQUI ...>
    return <... TU CODIGO AQUI ...>

comprueba manualmente tu código

import numpy as np

a = np.array([[1,0,0], [0,3,0], [0,0,-3]])
print(a)
diag_store(a, init_pos=19, size=5)

registra tu solución en línea

student.submit_task(globals(), task_id="task_01");

Ejercicio 2

Una matriz triangular 2D es aquella en la que cualquier elemento \(m_{ij}=0 \iff i > j\), en donde \(i\) son las filas y \(j\) las columnas. Si asumimos que solamente trataremos con matrices cuadradas, es decir \(\in \mathbb{R}^{n \times n}\).

Completa la siguiente función para que, dado un array numpy de entrada:

  • Lance un AssertError si no es cuadrado o no es triangular superior

  • Lance un AssertError si el parámetro orientation es distinto de columns o rows

  • Devuelva un vector con las posiciones de almacenamiento de sus elementos, asumiendo una posición inicial y un tamaño de dato.

  • Tenga en cuenta el parámetro orientation q

Por ejemplo, para esta entrada:

[[ 1  0  0]
 [ 0  3  0]
 [ 0  0 -3]]

con init_pos=19 y size=5, la salida debería de ser:

[19 24 29 34 39 44]

observa que dada una matriz triangular superior \(\in \mathbb{R}^{n\times n }\), el número de elementos que hay que almacenar viene dado por:

\[\frac{n^2 - n}{2} + n\]

ya que

  • \(n^2\) es el número total de elementos de la matriz

  • \(n^2-n\) es el número de elementos excluyendo la diagonal

  • \(\frac{n^2-n}{2}\) es el número de elementos de un triángulo (superior o inferion) excluyendo la diagonal

  • \(\frac{n^2 - n}{2} + n\) es el número de elementos de un triángulo incluyendo la diagonal

def triang_store(m, init_pos=0, size=4, orientation="columns"):
    import numpy as np
    assert <... TU CODIGO AQUI ...>
    return <... TU CODIGO AQUI ...>

comprueba manualmente tu código

import numpy as np
a = np.array([[1,0,3], [0,3,1], [0,0,-3]])
print(a)
print(triang_store(a, init_pos=19, size=5))

registra tu solución en línea

student.submit_task(globals(), task_id="task_02");

Ejercicio 3

Dado:

  • una especificación de dimensiones de un array \((d_0, d_1, ... d_{n-1})\) de \(n\) dimensiones

  • una especificación de orden de almacenamiento \(\mathbb{P}[0,1,..,n-1]\) (una permutación de los elementos del \(0\) a \(n-1\))

  • una dirección de memoria de base (de inicio)

  • un tamaño de dato

obtén la matriz de posiciones de memoria de cualquier array de tales dimensiones. Tu salida ha de ser un array de numpy

Por ejemplo, para

dims = [2,2,2]
order = [0,1,2]

la salida ha de ser

[[[ 0 16]
  [ 8 24]]

 [[ 4 20]
  [12 28]]]

y para

dims = [2,3,4]
order = [2,1,0]

la salida ha de ser

[[[ 0  4  8 12]
  [16 20 24 28]
  [32 36 40 44]]

 [[48 52 56 60]
  [64 68 72 76]
  [80 84 88 92]]]

Sugerencia: usa la siguiente estrategia de implementación

  1. Genera todas las posibles coordenadas de la matriz correspondiente a dims. Con esto deberías de generar un array de dimensiones \((\prod d_i)\times n\)

  2. Usa pandas.sort_values para ordenar todas las posibles coordenadas según order (usa el parámetro by)

  3. El dataframe generado anteriormente contiene en orden en el que se almacenarían en memoria los elementos de la matriz original según la especificación en dims y en order

  4. Genera una matriz de ceroz de tamaños dims y recorre secuencialmente el dataframe anterior actualizando cada coordenada.

def get_storage_positions(dims, order, size, init_pos=0):
    import pandas as pd
    import numpy as np
    import itertools  
    <... TU CODIGO AQUI ...>
    return <... TU CODIGO AQUI ...>

print(get_storage_positions(dims = [3,2], order = [0,1], size=4))

print(get_storage_positions(dims = [2,3,4], order = [0,1,2], size=4))
print("--")
print(get_storage_positions(dims = [2,3,4], order = [2,1,0], size=4))
print("--")
print(get_storage_positions(dims = [2,2,2], order = [0,1,2], size=4))
print("--")
print(get_storage_positions(dims = [2,2,2], order = [2,1,0], size=4))

registra tu solución en línea

student.submit_task(globals(), task_id="task_03");

Ejercicio 4

Dado un array de posiciones en memoria de \(n\) dimensiones queremos descubrir qué ordenación tiene en memoria. Este ejercicio es el inverso del anterior.

Por ejemplo, dada la siguiente matriz de entrada

[[[ 0  4  8 12]
  [16 20 24 28]
  [32 36 40 44]]

 [[48 52 56 60]
  [64 68 72 76]
  [80 84 88 92]]]

tu función ha de devolver la tupla

[2,1,0]

o con la siguiente matriz:

[[[ 0  4  8 12]
  [32 36 40 44]
  [64 68 72 76]]

 [[16 20 24 28]
  [48 52 56 60]
  [80 84 88 92]]]

ha de devolver la tupla

[2,0,1]

Sugerencia de implementación: para resolver este problema tienes que fijarte en el incremento en cada eje. Por ejemplo, fíjate en los dos primeros elementos de cada eje en la última matriz. Observa como el primer eje es el 2, el segundo el 0 y el último el 1.

import numpy as np
a = [2,4]
np.argsort(a)

a = [10,4,7,-1,20]
print(np.array(a))
print(np.r_[a])

print(np.argsort(a))

a = np.random.randint(10, size=(2,5,4))
a

dims = len(a.shape)
my_slices = tuple([slice(0,1,1)]*dims)
print(my_slices)
a[my_slices].flatten()

import numpy as np
r = np.array([[[ 0,  4,  8, 12],
        [32, 36, 40, 44],
        [64, 68, 72, 76]],

       [[16, 20, 24, 28],
        [48, 52, 56, 60],
        [80, 84, 88, 92]]])

print(r[:2,0,0])
print(r[0,:2,0])
print(r[0,0,:2])

ndims = 3
r = np.random.randint(100, size=[2]*ndims)
print(r)
mis_slices = tuple([slice(0,2,None)]+[0]*(ndims-1))
print("--")
print(r[mis_slices])

r[:2,0,0]

import numpy as np

a = np.r_[10,4,2,20,1]
np.sort(a)

np.argsort(a)

por tanto te sugiero una implementación en la que:

  1. Hagas un bucle por el número de dimensiones

  2. Para cada dimensión generes una lista de slices equivalentes a la notación de indexado anterior

  3. Obtengas los dos primeros elementos de cada eje

  4. Ordenes los ejes por la diferencia entre esos dos elementos

quizá la función np.argsort pueda serte de ayuda

def get_storage_order(r):
    import numpy as np
    
    return <... TU CODIGO AQUI ...>

comprueba manualmente tu código

r = np.array([[[ 0,  4,  8, 12],
        [32, 36, 40, 44],
        [64, 68, 72, 76]],

       [[16, 20, 24, 28],
        [48, 52, 56, 60],
        [80, 84, 88, 92]]])

get_storage_order(r)

registra tu solución en línea

student.submit_task(globals(), task_id="task_04");

previous

LAB 03 Matrices dispersas

next

C. Listas y árboles