Okay, here's how a client can handle large cost maps whether they're
sparse or full.
First, get a sparse matrix class. It must handle square matrices with
numeric indexes, 0 to N-1, for a fixed N. The class should be efficient
(in space and time) whether the matrix is full or sparse.
I couldn't find a good sparse matrix class in java, so I wrote my own.
Also, it's difficult for me to use an open-source package. My employer
wants me to clear the license with our lawyers, to make sure it doesn't
restrict our right to use it in a product. And if I have to choose between
spending a day with a lawyer or a day writing code ....
Then get a on-the-fly parser class for JSON. Typically this has a base
scanner that calls abstract methods when it encounters a new list, an item
in a list, a new dictionary, an item in a dictionary, etc. I couldn't find
one of those either. Fortunately JSON is simple, so it's not hard to write
one.
Then write a class to convert the PID names to index numbers (given a
network map, save the PID names in an array, sort, then lookup name via
binary search).
Finally extend the on-the-fly parser to read a cost map response. When it
gets a cost, it converts the src & dest pid names to numbers and sets that
element in the sparse matrix.
So a client can read a possibly sparse matrix in one pass. But it requires
extra effort to write those classes, or locate ones that are acceptable.
Simple techniques will work fine for small ALTO servers, but then fail
miserably when confronted with a large server.
- Wendy Roome
On 03/25/2013 05:42, "Scharf, Michael (Michael)"
<[email protected]> wrote:
>> > 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? ...
>
>Is there an existing JSON parser libary that supports such "on-the-fly"
>parsing (stream-like)?
>
>The libraries I have looked at so far typically parse a buffer with the
>whole JSON data.
>
>> > 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?
>
>Out of my head, I'd think that multiple passes will be needed when using
>standard JSON libraries. Obviously, an ALTO implementation can implement
>own JSON parsing logic, but we'd better not assume this.
_______________________________________________
alto mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/alto
