Re: What's the best data structure for this job?
This is a MIME GnuPG-signed message. If you see this text, it means that
your E-mail or Usenet software does not support MIME signed messages.
The Internet standard for MIME PGP messages, RFC 2015, was published in 1996.
To open this message correctly you will need to install E-mail or Usenet
software that supports modern Internet standards.
--=_mimegpg-commodore.email-scan.com-20844-1243207774-0001
Content-Type: text/plain; format=flowed; charset="US-ASCII"
Content-Disposition: inline
Content-Transfer-Encoding: 7bit
Rui Maciel writes:
I'm writing a class that processes SI units, which represents each unit as a vector of unit/exponent pairs.
According to my current implementation plan, the force units (the Newton) would be represented as [N,1] or,
after converting to the SI base units, [kg,1],[m,1],[s,-2]. To avoid wasting space with redundant
information, the unit in the unit/exponent pair is a reference index to a hash table that stores the unit's
name and symbol.
So, according to this scenario, what would be the best data structure for this job? Currently I'm using
nothing more than the STL containers for the data stuctures and the GNU MP bignum library for the exponent.
More precisely, I'm storing the SI units as:
std::vector< std::pair<unsigned int, mpq_t> > expression;
The SI unit list is being stored as:
std::map<unsigned int, std::pair<std::string, std::string> > units;
Nonetheless, I feel that this solution is far from perfect, not to mention a bit overwhelming. Moreover,
the static and global nature of a SI unit list leads me to believe that there must be a simpler solution
than a singleton wrapper class on a simple standard map.
So, what's your take on this issue? How would you implement a data structure for this task?
Have you considered using a unified list of base and compound SI units?
There's a variety ways of implementing it:
class si_info {
public:
std::string symbol;
std::string name;
std::vector<unsigned int> base_units;
};
typedef std::map<unsigned int, si_info> units;
A compount SI unit, like a newton, would have a three-element base_units
vector, containing the index of the kg, m, and s base units. An SI base unit
is represented with the base_units vector containing one element, the index
of the SI base unit itself.
You now have a uniform reference for either a base or a compount unit, the
single unsigned int handle. To be even more pedantic, rather than using
unsigned int explicitly as a handle, use a symbolic typedef:
typedef unsigned int si_handle_t;
class si_info {
public:
std::string symbol;
std::string name;
std::vector<si_handle_t> base_units;
};
typedef std::map<si_handle_t, si_info> units;
This is considered a more elegant design, and it adds additional flexibility
later down the road.
The value of an SI unit is then reduced to a single vector:
class si_value {
public:
si_handle_t si_unit;
std::vector<mpq_t> si_values;
};
si_unit gives the key to the units map. You can also use a simple
std::pair<si_unit, std::vector<mpq_t> > typedef, here.
You'll have to enforce two restrictions with this design:
1) All elements of the base_units vector in the SI map must reference only
other elements whose base_units vector is of size 1, and contain the same
si_handle_t value as the element itself -- that is, the element is either a
base element, or consists of only other base elements.
2) The size of your mpq_t vector must match the size of the base_units
vector in the si_info map. The nth element of the mpq_t vector gives the
value for the SI unit given by the nth element of the base_units vector.
Seems to me that with this design you can proceed and write code that
uniformly deals with base SI units and compount SI units, using the same
logic.
--=_mimegpg-commodore.email-scan.com-20844-1243207774-0001
Content-Type: application/pgp-signature
Content-Transfer-Encoding: 7bit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iEYEABECAAYFAkoZ2F4ACgkQx9p3GYHlUOLoowCeNQcM2Bjg+SRTz/5hnsadBtvX
DdUAnj8uXc64zxkYngFTqSF107+d1vhg
=nGD0
-----END PGP SIGNATURE-----
--=_mimegpg-commodore.email-scan.com-20844-1243207774-0001--