Exercício 01 - Funções Xadrez

Autor: Wagner Machado do Amaral
Data: 09/03/2009

Enunciado: ia636-2009:exercicio1

Versão 1.0

Funções apresentadas em aula: varredura pixel a pixel (não aconselhável) e iameshgrid. Observe que foi calculado o tempo de execução dessas funções.

 1 def varredura(h,w):
 2   t1 = time.time()
 3   A = zeros( (h,w) )
 4   for i in range(0,h):
 5     for j in range(0,w):
 6       A[i,j] = (i+j) % 2
 7   t2 = time.time()
 8   mmshow(A, title= "varredura: Tempo = " + str(t2-t1) + "s");
 9 
10 def grid(h,w):
11   t1 = time.time()
12   J,I = iameshgrid( range(0,w), range(0,h) )
13   A = (I+J) % 2
14   t2 = time.time()
15   mmshow(A, title= "iameshgrid: Tempo = " + str(t2-t1) + "s");
16 
17 varredura(250,500)
18 grid(250,500)

varredura: Tempo = 0.0918619632721s

iameshgrid: Tempo = 0.00569701194763s

A função a seguir foi baseada na resolução de Fernando Paolieri Neto. Essa função apresenta tempo de execução inferior ao das funções acima (varredura e iameshgrid).

 1 def xadrez1(lin, col):
 2   t1 = time.time()
 3 
 4   I = zeros([lin,col])
 5   # cria um array de linhas=lin colunas=col e preenche todos os elementos com valor igual a zero
 6 
 7   I[0:lin:2,0:col:2] = 1
 8   # atribui valor 1 a todos elementos de I contidos em [0:lin:2,0:col:2], sendo que:
 9   # 0:lin:2 refere-se as linhas entre 0 e lin intercaladas a cada 2 linhas, iniciando-se em I[0,0]
10   # 0:col:2 refere-se as colunas entre 0 e col intercaladas a cada 2 colunas, iniciando-se em I[0,0]
11 
12   I[1:lin:2,1:col:2] = 1
13   # atribui valor 1 a todos elementos de I contidos em [1:lin:2,1:col:2], sendo que:
14   # 1:lin:2 refere-se as linhas entre 1 e lin intercaladas a cada 2 linhas, iniciando-se em I[1,1]
15   # 1:col:2 refere-se as colunas entre 1 e col intercaladas a cada 2 colunas, iniciando-se em I[1,1]
16 
17   t2 = time.time()
18   mmshow(I, title= "Tempo = " + str(t2-t1) + "s");
19 
20 xadrez1(250,500)

Tempo = 0.000682830810547s

A função acima utilizou o comando zeros([lin,col]) para criar a matriz inicial I. Observer abaixo que a utilização da função numpy.zeros([lin,col]) diminuiu o tempo de execução.

1 def xadrez2(lin, col):
2   t1 = time.time()
3   I = numpy.zeros([lin,col])
4   I[0:lin:2,0:col:2] = 1
5   I[1:lin:2,1:col:2] = 1
6   t2 = time.time()
7   mmshow(I, title= "Tempo = " + str(t2-t1) + "s");
8 
9 xadrez2(250,500)

Tempo = 0.000618934631348s

As funções apresentadas até o momento criam um tabuleiro de xadrez com casas do tamanho de 1 pixel. A função apresentada a seguir oferece a possibilidade de configurar o tamanho das casas do tabuleiro. Porém para implementar essa função utilizei o laço for que causou um aumento no tempo de execução da função em comparação com as demais.

 1 def xadrez3(lin, col, size):
 2   t1 = time.time()
 3   I = numpy.zeros([lin,col])
 4   i = 0
 5   for fl in range(0,size):
 6     for fc in range(0,size):
 7       i = i+1
 8       inil,inic = fl,fc
 9       I[ inil:lin:size*2 , inic:col:size*2 ] = 1
10       inil,inic = inil+size,inic+size
11       I[ inil:lin:size*2 , inic:col:size*2 ] = 1
12   t2 = time.time()
13   mmshow(array(I), title= "[ Modo Iterativo. Tempo = " + str(t2-t1) + "s, Iterações = " + str(i) + " ]" );
14 
15 xadrez3(250,500,25)

[ Modo Iterativo. Tempo = 0.00947690010071s, Iterações = 625 ]

Esse algoritmo utiliza a mesma abordagem matricial da função anterior. Porém para gerar casas maiores que 1 pixel o algoritmo é repetido n vezes, sendo n o número de pixels de cada casa.

Dessa forma o aumento do tempo causado pelo laço for não está relacionado diretamente ao tamanho da matriz, mas sim ao tamanho definido para cada casa.

Versão 2.0

Conforme sugestão do professor Lotufo, desenvolvi uma função para gerar um tabuleiro de xadrez com o tamanho das casas configurável e que não utiliza laço de repetição for.

Esse método utiliza as propriedades da multiplicação de matrizes. Segue abaixo:

 1 # essa função retorna uma linha com valores zero e um intercalados
 2 # Parametros de entrada
 3 #   * vetor : vetor 1-D que deve possui valores sequenciais e possuir
 4 #             tamanho igual ao tamanho desejado para o tabuleiro de xadrez
 5 #   * size  : tamanho desejado para as casas do tabuleiro (em pixel)
 6 #   * ini   : 0 ou 1, indica se a sequencia de valores binários a ser
 7 #             retornada começara em 0 ou 1
 8 # Retorno
 9 #   * vetor com valores binários (zero e um) intercalados
10 def linhabinaria(vetor,size,ini):
11     elemento = vetor/size # informa qual casa do tabuleiro o elemento do vetor está
12     if (vetor%size) > 0:
13       elemento = elemento + 1
14 
15     # define se a sequencia iniciara em zero ou um
16     if ini==0:
17       el1=0
18       el2=1
19     else:
20       el1=1
21       el2=0
22 
23     # intercala o valor zero e um, conforme elemento
24     if elemento%2 > 0 :
25       return el1
26     else:
27       return el2
28 vectfunc = vectorize(linhabinaria)
29 
30 #####################################################
31 ################# TESTANDO A FUNÇÃO #################
32 #####################################################
33 
34 
35 ## TESTE 1
36 #####################################################
37 
38 print "TESTE 1"
39 
40 # O conceito desse método resume-se em criar matrizes com valores
41 # zero e um dispostos de forma que a multiplicação dessas matrizes gere
42 # uma matriz quadrada na forma de um tabuleiro de xadrez
43 
44 n = 10  # tamanho desejado para o tabuleiro (pixels)
45 size_casa = 2 # tamanho das casas do tabuleiro
46 B0 = vectfunc([arange(1,n)],size_casa,0) # vetor binário que inicia em 0
47 B1 = vectfunc([arange(1,n)],size_casa,1) # vetor binário que inicia em 1
48 B = concatenate((B0,B1))
49 
50 # sendo n o tamanho desejado para o tabuleiro:
51 # B é uma matriz n,2
52 
53 A = B.transpose()
54 
55 # A é uma matriz 2,n (transposta de B)
56 
57 print "A"
58 print array(A)
59 
60 print "B"
61 print array(B)
62 
63 C = dot(A,B)
64 
65 # C é a multiplicação de A com B.
66 # Devido a forma como os valores zero e um foram atribuidos
67 # aos elementos de A e B, a matriz C resultou em um tabuleiro de xadrez
68 
69 print "C"
70 print array(C)
71 
72 ## TESTE 2
73 #####################################################
74 
75 t1 = time.time()
76 
77 n = 1000
78 size_casa = 200
79 B0 = vectfunc([arange(1,n)],size_casa,0)
80 B1 = vectfunc([arange(1,n)],size_casa,1)
81 B = concatenate((B0,B1))
82 
83 A = B.transpose()
84 
85 C = dot(A,B)
86 
87 t2 = time.time()
88 
89 mmshow(array(C), title= "[ Modo Matricial(novo). Tempo = " + str(t2-t1) + "s ]");
90 
91 # Função anterior (iterativa com laço for)
92 xadrez3(n,n,size_casa)
TESTE 1
A
[[0 1]
 [0 1]
 [1 0]
 [1 0]
 [0 1]
 [0 1]
 [1 0]
 [1 0]
 [0 1]]
B
[[0 0 1 1 0 0 1 1 0]
 [1 1 0 0 1 1 0 0 1]]
C
[[1 1 0 0 1 1 0 0 1]
 [1 1 0 0 1 1 0 0 1]
 [0 0 1 1 0 0 1 1 0]
 [0 0 1 1 0 0 1 1 0]
 [1 1 0 0 1 1 0 0 1]
 [1 1 0 0 1 1 0 0 1]
 [0 0 1 1 0 0 1 1 0]
 [0 0 1 1 0 0 1 1 0]
 [1 1 0 0 1 1 0 0 1]]
Warning: downcasting image from int32 to uint16 (may lose precision)
Warning: downcasting image from double to uint16 (may lose precision)

[ Modo Matricial(novo). Tempo = 0.0216879844666s ]

[ Modo Iterativo. Tempo = 1.04759287834s, Iterações = 40000 ]

O tempo de execução foi menor do que o obtido através da função anterior (iterativa).

Obs: Esse método possui a restrição de que o tabuleiro deve possuir lagura igual à altura.