Bandeiras em Python

Question

Eu estou trabalhando com uma grande matriz (250x250x30 = 1.875.000 células), e eu gostaria de ter uma maneira de definir um número arbitrário de bandeiras para cada célula nesta matriz, de alguma maneira que seja fácil de usar e razoavelmente eficiente do espaço .

Meu plano original era uma matriz 250x250x30 lista, onde cada elemento foi algo como: ["FLAG1","FLAG8","FLAG12"]. Eu, então, mudou para armazenar apenas números inteiros em vez disso: [1,8,12]. Estes números inteiros são mapeados internamente por funções getter / setter para as cordas bandeira original. Isso só usa 250mb com 8 bandeiras por ponto, o que é bom em termos de memória.

A minha pergunta é: estou faltando uma outra maneira óbvia para estruturar este tipo de dados

Obrigado a todos por suas sugestões. Eu acabei rolando algumas sugestões em um, infelizmente, só posso escolher uma resposta e tem que viver com upvoting os outros:

EDIT: erm o código inicial que tive aqui (usando conjuntos como o elemento de base de uma matriz numpy 3d) usei um monte de memória. Este novo usa a versão em torno de 500MB quando cheio de randint(0,2**1000).

import numpy

FLAG1=2**0
FLAG2=2**1
FLAG3=2**2
FLAG4=2**3

(x,y,z) = (250,250,30)

array = numpy.zeros((x,y,z), dtype=object)


def setFlag(location,flag):
    array[location] |= flag
def unsetFlag(location,flag):
    array[location] &= ~flag

Answer 1

Eu geralmente usam um numpy array (presumivelmente de inteiros curtos, 2 bytes cada, desde que você pode necessidade mais de 256 valores distintos.) - que levaria menos de 4MB para os <2 milhões de células

Se por algum motivo eu não podia pagar a dependência numpy (por exemplo, no App Engine, que faz numpy não suporte), eu uso a biblioteca padrão módulo de conjunto - ele só suporta matrizes 1-dimensional, mas é apenas como o espaço-eficiente quanto numpy para grandes matrizes homogêneos, e os apanhador / definidor rotinas que você menção pode perfeitamente "linearize" a 3 itens tupla que é o seu índice natural no índice inteiro único na matriz 1-D.

Em geral, considere numpy (ou matriz) a qualquer momento que você tem grande homogênea, vetores densas ou matrizes de números - Python built-in listas são altamente desperdício de espaço neste caso de uso (devido à sua generalidade que você está não usar e não precisa aqui -.), e economia de memória traduz indiretamente a economia de tempo também (melhor cache, menos níveis de engano, etc, etc)

Answer 2

A sua solução é bom se cada célula vai ter uma bandeira. No entanto, se você está trabalhando com um conjunto de dados esparsos em que apenas uma pequena subseção de suas células terão bandeiras que você realmente quer é um dicionário. Você gostaria de configurar o dictonary assim que a chave é uma tupla para a localização da célula e o valor é uma lista de sinalizadores como você tem em sua solução.

allFlags = {(1,1,1):[1,2,3], (250,250,30):[4,5,6]}

Aqui temos o celular 1,1,1 tem as bandeiras 1,2, e 3 e a célula 250,250,30 tem as bandeiras 4,5, e 6

edit- fixo tuplas chave, graças Andre, ea sintaxe dicionário.

Answer 3

Você pode definir algumas constantes com diferentes, o poder de dois valores como:

FLAG1 = 0x01
FLAG8 = 0x02
FLAG12 = 0x04
...

E usá-los com lógica booleana para armazenar as bandeiras em apenas um número inteiro, P.E:.

flags = FLAG1 | FLAG8

Para verificar se um sinalizador está ativado, você pode usar o operador &:

flag1_enabled = flags & FLAG1

Se o sinalizador estiver habilitado, esta expressão irá retornar um valor diferente de zero, que será avaliada como verdadeira em qualquer operação booleana. Se o sinalizador estiver desativado, a expressão retornará 0, que é avaliada como False em operações booleanas.

Answer 4

Considere o uso de FLYWEIGHT para as propriedades da célula de acções:

http://en.wikipedia.org/wiki/Flyweight_pattern

Answer 5

BitSet é o que você quer, uma vez que permite que você armazene muitas bandeiras ao mesmo tempo usando Somente um número inteiro de tamanho fixo (tipo Int)

Answer 6

Tomar de Robbie sugestão mais um passo ...

flags = set()
x, y, flag = 34, 201, 3
flags.add((x, y, flag)) # set flag 3 at position (34, 201)
if (3, 2, 1) in flags: # check if flag 1 is at position (3, 2)
    # do something
else:
    # do something else

Você também pode criar uma classe auxiliar.

class Flags(object):
    def __init__(self):
        self.data = set()
    def add(self, x, y, flag):
        self.data.add((x, y, flag))
    def remove(self, x, y, flag):
        self.data.remove((x, y, flag))
    def contains(self, x, y, flag):
        return (x, y, flag) in self.data

Você também pode implementar métodos especiais do Python como __contains__ para torná-lo mais fácil de trabalhar.