Wendy, On Fri, Mar 22, 2013 at 03:34:16PM -0400, Wendy Roome wrote: > As Sebastian points out, sparse cost maps are allowed, and if the map is > sparse, it's reasonable to have a large number of PIDs. > > But there's a gotcha. Remember clients must store the cost map, and lookup > costs as needed. If the client knows the matrix is sparse, the client can > store it as a hash table, where the key is the concatenation of the source > & dest PID names. That's simple & efficient.
I agree. > Unfortunately, if the matrix ISN'T sparse, that technique is horribly > inefficient. If the matrix is full, the client should convert pid names to > index numbers (sort the PID names, use binary search to get the index), > and then store the costs in a conventional float[N][N] array. Could this be done on the fly while reading the JSON data structures from the network? ... > And, of course, that technique is wasteful for a sparse cost matrix. > > So the client has to guess how "sparse" the cost matrix really is. ... or do I have to read all the JSON stuff into a temporary buffer, then decide whether to go for a hash or an array. If the array, do pid name -> index mapping, identify the highest index, allocate array and eventually fill it? That would be 3 passes or more? Thanks Sebastian _______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
