StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'll play the devil's advocate here. I'll show <a href="https://stackoverflow.com/users/330565/nikita-rybak">Nikita's</a> exact algorithm written in a functional style. I'll also parallelize it, just to show it can be done.</p> <p>First, computing consecutive cells with the same number below a cell. I made a slight change by returning all values plus one compared to Nikita's proposed output, to avoid a <code>- 1</code> in some other part of the code.</p> <pre><code>def computeHeights(column: Array[Int]) = ( column .reverse .sliding(2) .map(pair => pair(0) == pair(1)) .foldLeft(List(1)) ( (list, flag) => (if (flag) list.head + 1 else 1) :: list ) ) </code></pre> <p>I'd rather use <code>.view</code> before reversing, but that doesn't work with the present Scala version. If it did, it would save repeated array creations, which ought to speed up the code a lot, for memory locality and bandwidth reasons if no other.</p> <p>Now, all columns at the same time:</p> <pre><code>import scala.actors.Futures.future def getGridHeights(grid: Array[Array[Int]]) = ( grid .transpose .map(column => future(computeHeights(column))) .map(_()) .toList .transpose ) </code></pre> <p>I'm not sure if the parallelization overhead will pay off here or not, but this is the first algorithm on Stack Overflow where it actually has a chance, given the non-trivial effort in computing a column. Here's another way of writing it, using the upcoming 2.9 features (it might work on Scala 2.8.1 -- not sure what :</p> <pre><code>def getGridHeights(grid: Array[Array[Int]]) = ( grid .transpose .toParSeq .map(computeHeights) .toList .transpose ) </code></pre> <p>Now, the meat of Nikita's algorithm:</p> <pre><code>def computeWidths(height: Int, row: Array[Int], heightRow: List[Int]) = ( row .sliding(2) .zip(heightRow.iterator) .toSeq .reverse .foldLeft(List(1)) { case (widths @ (currWidth :: _), (Array(prev, curr), currHeight)) => ( if (currHeight >= height && currWidth > 0 && prev == curr) currWidth + 1 else 1 ) :: widths } .toArray ) </code></pre> <p>I'm using pattern matching in this bit of code, though I'm concerned with its speed, because with all the sliding, and zipping and folding there's two many things being juggled here. And, speaking of performance, I'm using <code>Array</code> instead of <code>IndexedSeq</code> because <code>Array</code> is the only type in the JVM that is not erased, resulting in much better performance with <code>Int</code>. And, then, there's the <code>.toSeq</code> I'm not particular happy about either, because of memory locality and bandwidth.</p> <p>Also, I'm doing this from right to left instead of Nikita's left to right, just so I can find the upper left corner.</p> <p>However, is the same thing as the code in Nikita's answer, aside from the fact that I'm still adding one to current width compared to his code, and not printing the result right here. There's a bunch of things without clear origins here, though -- <code>row</code>, <code>heightRow</code>, <code>height</code>... Let's see this code in context -- and parallelized! -- to get the overall picture.</p> <pre><code>def getGridWidths(height: Int, grid: Array[Array[Int]]) = ( grid .zip(getGridHeights(grid)) .map { case (row, heightsRow) => future(computeWidths(height, row, heightsRow)) } .map(_()) ) </code></pre> <p>And the 2.9 version:</p> <pre><code>def getGridWidths(height: Int, grid: Array[Array[Int]]) = ( grid .toParSeq .zip(getGridHeights(grid)) .map { case (row, heightsRow) => computeWidths(height, row, heightsRow) } ) </code></pre> <p>And, for the gran finale,</p> <pre><code>def findRectangles(height: Int, width: Int, grid: Array[Array[Int]]) = { val gridWidths = getGridWidths(height, grid) for { y <- gridWidths.indices x <- gridWidths(y).indices if gridWidths(y)(x) >= width } yield (x, y) } </code></pre> <p>So... I have no doubt that the imperative version of Nikita's algorithm is faster -- it only uses <code>Array</code>, which is much faster with primitives than any other type, and it avoids massive creation of temporary collections -- though Scala <em>could</em> have done better here. Also, no closures -- as much as they help, they <em>are</em> slower than code without closures. At least until JVM grow something to help with them.</p> <p>Also, Nikita's code can be easily parallelized with threads -- of all things! -- with little trouble.</p> <p>But my point here is that Nikita's code is not particularly bad just because it uses arrays and a mutable variable here and there. The algorithm translates cleanly to a more functional style.</p> <p><strong>EDIT</strong></p> <p>So, I decided to take a shot at making an efficient functional version. It's not really fully functional because I use <code>Iterator</code>, which is mutable, but it's close enough. Unfortunately, it won't work on Scala 2.8.1, because it lacks <code>scanLeft</code> on <code>Iterator</code>.</p> <p>There are two other unfortunate things here. First, I gave up on parallelization of grid heights, since I couldn't get around having at least one <code>transpose</code>, with all the collection copying that entails. There's still at least one copying of the data, though (see <code>toArray</code> call to understand where).</p> <p>Also, since I'm working with <code>Iterable</code> I loose the ability to use the parallel collections. I do wonder if the code couldn't be made better by having <code>grid</code> be a parallel collection of parallel collections from the beginning.</p> <p>I have no clue if this is more efficient than the previous version of not. It's an interesting question...</p> <pre><code>def getGridHeights(grid: Array[Array[Int]]) = ( grid .sliding(2) .scanLeft(Array.fill(grid.head.size)(1)) { case (currHeightArray, Array(prevRow, nextRow)) => (prevRow, nextRow, currHeightArray) .zipped .map { case (x, y, currHeight) => if (x == y) currHeight + 1 else 1 } } ) def computeWidths(height: Int, row: Array[Int], heightRow: Array[Int]) = ( row .sliding(2) .map { case Array(x, y) => x == y } .zip(heightRow.iterator) .scanLeft(1) { case (currWidth , (isConsecutive, currHeight)) => if (currHeight >= height && currWidth > 0 && isConsecutive) currWidth + 1 else 1 } .toArray ) import scala.actors.Futures.future def getGridWidths(height: Int, grid: Array[Array[Int]]) = ( grid .iterator .zip(getGridHeights(grid)) .map { case (row, heightsRow) => future(computeWidths(height, row, heightsRow)) } .map(_()) .toArray ) def findRectangles(height: Int, width: Int, grid: Array[Array[Int]]) = { val gridWidths = getGridWidths(height, grid) for { y <- gridWidths.indices x <- gridWidths(y).indices if gridWidths(y)(x) >= width } yield (x - width + 1, y - height + 1) } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload