5 ms·
> Try transposing a 4-megabyte matrix before the week is out on a machine with 32KiB of RAM and two 5-megabyte hard drives. Transposing is just copying bytes f
by chrisseaton 6y ago
> Try transposing a 4-megabyte matrix before the week is out on a machine with 32KiB of RAM and two 5-megabyte hard drives.
Transposing is just copying bytes from one place to another, isn't it? There's no maths involved, is there?
To have that run in a week with the most naive approach possible you'd only need a machine that can copy seven words a second. Are there real relevant machines that can't do that? What algorithms could help you anyway? Something to do with cache and the order in which you read and write? And you've got plenty of space as you can trivially do it in-place.
- smallnamespace 6y agoThe RAM here is essentially a cache. You’ll want to transpose a block at a time, something like 150 x 150 blocks, so it all fits. Each block is not contiguous on disk, so you’ll want to load blocks in the right order to avoid extra seeks.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- chrisseaton 6y agoI suspect, since the poster mentioned having two hard drives, that really they're confusing transposition with inversion. These aren't the same things.
- dekhn 6y agoTransposing is copying bytes, but changing the stride order of the array. So a lot of the work is extremely non-local. The poster meant that to do this efficiently, you'll use blocks and stage data between the drives while working. You can also transpose in place: https://en.wikipedia.org/wiki/In-place_matrix_transposition https://en.wikipedia.org/wiki/In-place_matrix_transposition see some of the commentary on efficiency there.