Se o voso programa precisa de almacenar un conxunto no que cada elemento só pode figurar unha vez, case todas as linguaxes modernas teñen algo que podedes usar: un tipo de datos que normalmente se chama Set ou HashSet ou algo semellante. Algunhas linguaxes, porén, non teñen nada diso.
Mapa de 8 bits.
O outro día sorprendín a un dos meus compañeiros de traballo con este código:
type RequestTypes uint
const (
RequestTypeUser = RequestTypes(0x01)
RequestTypeMachine = RequestTypes(0x02)
)
func EmptyRequestTypes() RequestTypes {
return RequestTypes(0)
}
func (t RequestTypes) Contains(other RequestTypes) bool {
return uint(t) & uint(other) == uint(other)
}
func (t RequestTypes) Union(other RequestTypes) RequestTypes {
return RequestTypes(uint(t) | uint(other))
}
Minto: máis que sorprendido, o home estaba espantado.
— Que é isto? —preguntoume.
— Un conxunto —díxenlle.
— Un conxuntoooo?!?!?
— Pois claro! Implementado cun mapa de bits!
Levoulle un bo anaco convencerse de que estaba ben programado, e a min fíxome pensar en se esta non sería unha desas cousas que os programadores xa non fan pero a min, que estou afeito a mirar código de baixo nivel, me vén para a cabeza de inmediato.
Como lle dixen ao meu compañeiro, esta é unha implementación dun conxunto feita cun mapa de bits: os conxuntos van representados por un número no que cada bit corresponde a un posible elemento do conxunto. Se o bit vale 1, ese elemento está presente no conxunto; se vale 0, non está.
Con esta representación, as operacións de conxuntos funcionan en O(1): a unión é unha operación “or” binaria, a intersección é “and” e o complemento é “not”. Ademais, os conxuntos representados desta maneira ocupan moi pouco espazo: cada byte terma de ata 8 elementos.
O inconveniente desta representación é que só se pode usar se todos os elementos están definidos con antelación. Ou sexa: isto non vos serve se queredes gardar un conxunto de cadeas de texto, pero si se queredes gardar valores enumerados.
No meu programa, o conxunto RequestTypes pode ter dous elementos: un chamado RequestTypeUser, que corresponde ao bit menos significativo (ou ao número hexadecimal 0x01) e outro chamado RequestTypeMachine, que corresponde ao segundo bit menos significativo (o número 0x02).
A función EmptyRequestTypes produce un conxunto baleiro (correspondente ao número 0), a función Contains calcula a intersección entre dous conxuntos e comproba se o resultado é igual ao segundo conxunto, e a función Union calcula, como o seu nome ben indica, a unión.
É moi habitual empregar este tipo de conxuntos na programación en baixo nivel. Por exemplo, as opcións que se poden pasar á función open son elementos dun conxunto que se poden combinar cun operador “or” binario.
Este é tamén o tipo de conxunto que a linguaxe Pascal ofrece. Cando nun programa en Pascal escribimos “var Caracteres : set of char;”, a variable “Caracteres” é un mapa de 256 bits, un para cada posible carácter. Cando despois escribimos “'a' in Caracteres”, Pascal comproba se o bit correspondente (o número 97) está activo nese mapa.
Coido que vos gostaría saber que se programades en Java e usades un EnumSet, na realidade estades a usar un conxunto implementado por un mapa de bits. Non usedes un HashSet para iso, que é un desperdicio de memoria.
E vós xa sabiades disto, ou é unha desas artes perdidas como xogar á billarda ou usar un teléfono de disco?
1 comentario