3 ms·
Can't you use sparse arrays?
by toolslive 7y ago
Can't you use sparse arrays?
- dalke 7y agoI don't understand your question. I think you're asking if APL and/or J supports a sparse matrix representation, such that the one-liner scales as expected for the Tarjan algorithm. As I wrote, I don't know more than a trivial amount of APL, and cannot answer that question. However, I infer that if that were the case then the links I pointed to would use a sparse array implementation and simple one-liner, instead of the 30 or so lines of APL. Perhaps pavlov, as the next Supreme Dictator of Tech, could show us an appropriate whiteboard interview solution for this problem in APL?
- gmfawcett 7y agoI can't speak for APL, but J does have a standardized sparse-array format, and a verb for converting normal arrays to sparse and back. Most operations work on both kinds of arrays transparently, although (in my limited experience) many ops are quite a bit slower on sparse arrays. Perhaps the performance difference is less significant for huge arrays, but for me it was measurably slower when working with a 1000x1000 table. Having said that, the sparse format gives you direct access to its internal index (coordinate) array, as well as the value array. So algorithms that can take advantage of these data structures might benefit significantly.