Entry in source row i becomes entry in destination row j. Visit source rows in descending order and prepend, producing increasing destination column order without a sorting pass.
def transpose: SparseMatrix = {
  val out = new SparseMatrix(N)
  var i = N - 1
  while (i >= 0) {
    for ((j, x) <- rows(i)) {
      out.rows(j) = (i, x) :: out.rows(j)
    }
    i -= 1
  }
  out
}
Before processing source row i, each destination row contains exactly the contributions from source rows with index greater than i, in increasing index order. Prepending index i preserves that order, and each source position is unique. Hence the representation invariant holds and
(1)
The source sparse matrix is unchanged.

Ancestors (11)

  1. 4
  2. Imperative programming
  3. 2014
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version