Bandiere in Python

Question

Sto lavorando con una grande matrice (250x250x30 = 1.875.000 cellule), e mi piacerebbe un modo per impostare un numero arbitrario di bandiere per ogni cella in questa matrice, in qualche modo che è facile da usare e ragionevolmente efficiente dello spazio .

Il mio piano originale era di una matrice di 250x250x30 lista, in cui ogni elemento era qualcosa di simile: ["FLAG1","FLAG8","FLAG12"]. Ho poi cambiato a memorizzare solo numeri interi, invece: [1,8,12]. Questi numeri interi sono mappati internamente da funzioni getter / setter alle corde bandiera originale. Questo utilizza solo 250 MB con 8 bandiere per punto, che va bene in termini di memoria.

La mia domanda è:? Mi sto perdendo un altro modo ovvio per strutturare questo tipo di dati

Grazie a tutti per i vostri suggerimenti. Ho finito per rotolare alcuni suggerimenti in una sola, purtroppo posso scegliere una sola risposta e devono vivere con upvoting gli altri:

EDIT: ERM il codice iniziale avevo qui (usando insiemi come elemento di base di una matrice NumPy 3d) usato un sacco di memoria. Questa nuova versione utilizza circa 500 MB quando si riempie di 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

Sono in genere utilizzare un NumPy matrice (presumibilmente di brevi int, 2 byte ciascuno, dal momento che si può bisogno di più di 256 valori distinti) -. che avrebbe preso meno di 4 MB per i <2 milioni di cellule

Se per qualche motivo non potevo permettermi la dipendenza NumPy (ad esempio su App Engine, che non supporta NumPy), mi piacerebbe utilizzare la libreria standard modulo di serie - supporta solo gli array 1-dimensionali, ma è altrettanto spazio-efficiente come NumPy per grandi array omogenei, e le getter / setter voi routine menzione può benissimo "linearizzare" a 3 elementi tupla che è il tuo indice di naturale nella indice intero singolo nella matrice 1-D.

In generale, si consideri NumPy (o array) ogni volta che si dispone di grandi, vettori o matrici di numeri densi omogenei - Python elenchi predefiniti sono altamente spreco di spazio in questo caso d'uso (a causa della loro generalità che sei non usare e non è necessario qui -!.), e salvare la memoria si traduce indirettamente al risparmio di tempo troppo (meglio caching, un minor numero di livelli di riferimento indiretto, ecc, ecc)

Answer 2

La soluzione va bene se ogni singola cellula sta per avere una bandiera. Tuttavia, se si sta lavorando con un gruppo di dati rada dove solo una piccola sottosezione di cellule avrà bandiere ciò che si vuole veramente è un dizionario. Si consiglia di impostare il dictonary così la chiave è una tupla per la posizione della cella e il valore è un elenco di bandiere, come avete nella vostra soluzione.

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

Qui abbiamo la cella di 1,1,1 hanno le bandiere 1,2, e 3 e la cella di 250,250,30 hanno le bandiere di 4,5, e 6

Modifica- fisso tuple chiave, grazie Andre, e la sintassi dizionario.

Answer 3

È possibile definire alcune costanti con diversi, potenza di due valori:

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

e li usa con la logica booleana per memorizzare le bandiere in una sola intero, p.e:.

flags = FLAG1 | FLAG8

Per verificare se è abilitata una bandiera, è possibile utilizzare l'operatore di &:

flag1_enabled = flags & FLAG1

Se è attivata la bandiera, questa espressione restituirà un valore diverso da zero, che sarà valutata come vera in ogni operazione booleana. Se il flag è disattivato, l'espressione tornerà 0, che viene valutata come False nelle operazioni booleane.

Answer 4

Si consiglia di utilizzare modello mosca per condividere proprietà della cella:

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

Answer 5

BitSet è ciò che si vuole, in quanto permette di memorizzare molte bandiere contemporaneamente utilizzando solo una dimensione numero intero fisso (tipo Int)

Answer 6

Facendo un passo ulteriore suggerimento di Robbie ...

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

È anche possibile creare una classe di supporto.

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

Si potrebbe anche implementare i metodi speciali di Python come __contains__ per rendere più facile lavorare con.