Skip to content

Instantly share code, notes, and snippets.

@frankandrobot
Last active July 20, 2016 03:43
Show Gist options
  • Save frankandrobot/2511f29af9d66df4c8f62eb3f7ee48be to your computer and use it in GitHub Desktop.
Save frankandrobot/2511f29af9d66df4c8f62eb3f7ee48be to your computer and use it in GitHub Desktop.
Recursive Flatten vs Tail-Recursive Flatten
.gradle/
.idea/
build/
*.iml
gradle/

flatten

In the absence of a product manager, I assumed either use case could happen:

  • a reasonable number of nested levels in the array (and performance doesn't matter too much).
  • an arbitrary number of nested levels in the array.

A reasonable number of nested levels in the array

In this approach, a simple solution using standard recursion is appropriate (#flatten1). The solution is simple to understand and is very maintainable.

An arbitrary number of nested levels in the array

In this approach, I used tail recursion (which is equivalent to a for loop). See #flatten2 Unfortunately, as will be made clear below, the tail recursive solution requires that you manually re-create the stack---hence, it can handle more complex arrays (than #flatten1) at the cost of potentially being bogged down by the GC.

flatten2

The idea is that the array is a tree. Integers are leaves and child arrays are nodes. In order to "flatten" the array, all you need to do is a depth-first traversal of the tree representation---at each leaf adding its value to a result array.

Unfortunately, because the array is not a tree you either need to:

  • pre-convert the array into a tree (this can be done in linear time, using linear memory). OR
  • convert items into "nodes" dynamically (as #flatten2 does).

Approach 1 potentially runs out of memory.

Approach 2 can handle larger, more complex arrays. However, you need to keep track of parent nodes, and so memory can still be a problem. Also, because objects get recycled, the GC can also be an issue.

Running

Run unit tests

gradle test

Run speed tests

gradle speedTests
group 'com.frankandrobot'
version '1.0.0'
apply plugin: 'org.junit.platform.gradle.plugin'
apply plugin: 'kotlin'
apply plugin: 'idea'
buildscript {
ext.kotlin_version = '1.0.3'
repositories {
jcenter()
mavenCentral()
}
dependencies {
classpath "org.jetbrains.kotlin:kotlin-gradle-plugin:$kotlin_version"
classpath 'org.junit.platform:junit-platform-gradle-plugin:1.0.0-M1'
}
}
repositories {
jcenter()
mavenCentral()
maven {
url "https://jetbrains.jfrog.io/jetbrains/spek-snapshots"
}
}
junitPlatform {
engines {
include 'spek'
}
}
dependencies {
testCompile 'com.natpryce:hamkrest:1.1.0.0'
testCompile 'org.jetbrains.spek:spek-api:1.0.0-SNAPSHOT'
testRuntime 'org.jetbrains.spek:spek-junit-engine:1.0.0-SNAPSHOT'
compile "org.jetbrains.kotlin:kotlin-stdlib:$kotlin_version"
}
sourceSets {
main {
kotlin {
srcDir './'
exclude 'test*'
}
}
test {
kotlin {
srcDir './'
}
}
}
task speedTestFlatten1(dependsOn: [classes], type: JavaExec) {
classpath = sourceSets.main.runtimeClasspath
main = "com.frankandrobot.flatten.System_test_flatten1_speed_specKt"
}
task speedTestFlatten2(dependsOn: [classes], type: JavaExec) {
classpath = sourceSets.main.runtimeClasspath
main = "com.frankandrobot.flatten.System_test_flatten2_speed_specKt"
}
task speedTests(dependsOn: [speedTestFlatten1, speedTestFlatten2]) {}
package com.frankandrobot.flatten
import java.util.*
val emptyList = ArrayList<Any>()
val flattenedArray = arrayListOf(0, 1, 2, 3, 4, 5)
val nestedArrayLevel1 = arrayListOf<Any>(0, arrayListOf(1, 2), 3, arrayListOf(4, 5))
val nestedArrayLevel2 = arrayListOf<Any>(0, arrayListOf(1, arrayListOf(2, 3), arrayListOf(4)), arrayListOf(5))
val nestedArrayLevel5 = arrayListOf<Any>(0, arrayListOf(1, arrayListOf(2, arrayListOf(3, arrayListOf(4, arrayListOf(5))))))
val systemTestLoop = 10000000
package com.frankandrobot.flatten
import java.util.*
fun flatten1(arr : ArrayList<Any>) : ArrayList<Int> {
val result = ArrayList<Int>(arr.size)
var i = -1
var elem : Any
while(++i < arr.size) {
elem = arr[i]
if (elem is Int) { result.add(elem) }
else { result.addAll(flatten1(elem as ArrayList<Any>)) }
}
return result
}
package com.frankandrobot.flatten
import java.util.*
internal data class Node(var array : ArrayList<Any>,
var start : Int = 0,
var parent : Node? = null) {
inline fun hasNextChild() = start < array.size
inline fun nextChild() = array[start++]
}
internal data class Visitor(val size : Int) {
val result = ArrayList<Int>(size)
inline fun visit(value : Int) = result.add(value)
}
internal tailrec fun traverse(visitor : Visitor, node: Node) {
var updatedNode: Node? = node
while (updatedNode!!.hasNextChild() == false && updatedNode.parent != null) {
updatedNode = updatedNode.parent
}
if (updatedNode!!.hasNextChild() == true) {
val elem = updatedNode.nextChild()
if (elem is Int) {
visitor.visit(elem)
}
else {
updatedNode = Node(array = elem as ArrayList<Any>, parent = updatedNode)
}
traverse(visitor, updatedNode)
}
}
/**
* The idea is that the array is a tree. Integers are leaves and child arrays are
* nodes. In order to "flatten" the array, all you need to do is a depth-first
* traversal of the tree representation---at each leaf adding its value to a
* `result` array.
*/
fun flatten2(arr : ArrayList<Any>) : ArrayList<Int> {
val visitor = Visitor(arr.size)
traverse(visitor, Node(arr))
return visitor.result
}
#!/usr/bin/env bash
##############################################################################
##
## Gradle start up script for UN*X
##
##############################################################################
# Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script.
DEFAULT_JVM_OPTS=""
APP_NAME="Gradle"
APP_BASE_NAME=`basename "$0"`
# Use the maximum available, or set MAX_FD != -1 to use that value.
MAX_FD="maximum"
warn ( ) {
echo "$*"
}
die ( ) {
echo
echo "$*"
echo
exit 1
}
# OS specific support (must be 'true' or 'false').
cygwin=false
msys=false
darwin=false
case "`uname`" in
CYGWIN* )
cygwin=true
;;
Darwin* )
darwin=true
;;
MINGW* )
msys=true
;;
esac
# Attempt to set APP_HOME
# Resolve links: $0 may be a link
PRG="$0"
# Need this for relative symlinks.
while [ -h "$PRG" ] ; do
ls=`ls -ld "$PRG"`
link=`expr "$ls" : '.*-> \(.*\)$'`
if expr "$link" : '/.*' > /dev/null; then
PRG="$link"
else
PRG=`dirname "$PRG"`"/$link"
fi
done
SAVED="`pwd`"
cd "`dirname \"$PRG\"`/" >/dev/null
APP_HOME="`pwd -P`"
cd "$SAVED" >/dev/null
CLASSPATH=$APP_HOME/gradle/wrapper/gradle-wrapper.jar
# Determine the Java command to use to start the JVM.
if [ -n "$JAVA_HOME" ] ; then
if [ -x "$JAVA_HOME/jre/sh/java" ] ; then
# IBM's JDK on AIX uses strange locations for the executables
JAVACMD="$JAVA_HOME/jre/sh/java"
else
JAVACMD="$JAVA_HOME/bin/java"
fi
if [ ! -x "$JAVACMD" ] ; then
die "ERROR: JAVA_HOME is set to an invalid directory: $JAVA_HOME
Please set the JAVA_HOME variable in your environment to match the
location of your Java installation."
fi
else
JAVACMD="java"
which java >/dev/null 2>&1 || die "ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH.
Please set the JAVA_HOME variable in your environment to match the
location of your Java installation."
fi
# Increase the maximum file descriptors if we can.
if [ "$cygwin" = "false" -a "$darwin" = "false" ] ; then
MAX_FD_LIMIT=`ulimit -H -n`
if [ $? -eq 0 ] ; then
if [ "$MAX_FD" = "maximum" -o "$MAX_FD" = "max" ] ; then
MAX_FD="$MAX_FD_LIMIT"
fi
ulimit -n $MAX_FD
if [ $? -ne 0 ] ; then
warn "Could not set maximum file descriptor limit: $MAX_FD"
fi
else
warn "Could not query maximum file descriptor limit: $MAX_FD_LIMIT"
fi
fi
# For Darwin, add options to specify how the application appears in the dock
if $darwin; then
GRADLE_OPTS="$GRADLE_OPTS \"-Xdock:name=$APP_NAME\" \"-Xdock:icon=$APP_HOME/media/gradle.icns\""
fi
# For Cygwin, switch paths to Windows format before running java
if $cygwin ; then
APP_HOME=`cygpath --path --mixed "$APP_HOME"`
CLASSPATH=`cygpath --path --mixed "$CLASSPATH"`
JAVACMD=`cygpath --unix "$JAVACMD"`
# We build the pattern for arguments to be converted via cygpath
ROOTDIRSRAW=`find -L / -maxdepth 1 -mindepth 1 -type d 2>/dev/null`
SEP=""
for dir in $ROOTDIRSRAW ; do
ROOTDIRS="$ROOTDIRS$SEP$dir"
SEP="|"
done
OURCYGPATTERN="(^($ROOTDIRS))"
# Add a user-defined pattern to the cygpath arguments
if [ "$GRADLE_CYGPATTERN" != "" ] ; then
OURCYGPATTERN="$OURCYGPATTERN|($GRADLE_CYGPATTERN)"
fi
# Now convert the arguments - kludge to limit ourselves to /bin/sh
i=0
for arg in "$@" ; do
CHECK=`echo "$arg"|egrep -c "$OURCYGPATTERN" -`
CHECK2=`echo "$arg"|egrep -c "^-"` ### Determine if an option
if [ $CHECK -ne 0 ] && [ $CHECK2 -eq 0 ] ; then ### Added a condition
eval `echo args$i`=`cygpath --path --ignore --mixed "$arg"`
else
eval `echo args$i`="\"$arg\""
fi
i=$((i+1))
done
case $i in
(0) set -- ;;
(1) set -- "$args0" ;;
(2) set -- "$args0" "$args1" ;;
(3) set -- "$args0" "$args1" "$args2" ;;
(4) set -- "$args0" "$args1" "$args2" "$args3" ;;
(5) set -- "$args0" "$args1" "$args2" "$args3" "$args4" ;;
(6) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" ;;
(7) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" ;;
(8) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" "$args7" ;;
(9) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" "$args7" "$args8" ;;
esac
fi
# Split up the JVM_OPTS And GRADLE_OPTS values into an array, following the shell quoting and substitution rules
function splitJvmOpts() {
JVM_OPTS=("$@")
}
eval splitJvmOpts $DEFAULT_JVM_OPTS $JAVA_OPTS $GRADLE_OPTS
JVM_OPTS[${#JVM_OPTS[*]}]="-Dorg.gradle.appname=$APP_BASE_NAME"
exec "$JAVACMD" "${JVM_OPTS[@]}" -classpath "$CLASSPATH" org.gradle.wrapper.GradleWrapperMain "$@"
@if "%DEBUG%" == "" @echo off
@rem ##########################################################################
@rem
@rem Gradle startup script for Windows
@rem
@rem ##########################################################################
@rem Set local scope for the variables with windows NT shell
if "%OS%"=="Windows_NT" setlocal
@rem Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script.
set DEFAULT_JVM_OPTS=
set DIRNAME=%~dp0
if "%DIRNAME%" == "" set DIRNAME=.
set APP_BASE_NAME=%~n0
set APP_HOME=%DIRNAME%
@rem Find java.exe
if defined JAVA_HOME goto findJavaFromJavaHome
set JAVA_EXE=java.exe
%JAVA_EXE% -version >NUL 2>&1
if "%ERRORLEVEL%" == "0" goto init
echo.
echo ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH.
echo.
echo Please set the JAVA_HOME variable in your environment to match the
echo location of your Java installation.
goto fail
:findJavaFromJavaHome
set JAVA_HOME=%JAVA_HOME:"=%
set JAVA_EXE=%JAVA_HOME%/bin/java.exe
if exist "%JAVA_EXE%" goto init
echo.
echo ERROR: JAVA_HOME is set to an invalid directory: %JAVA_HOME%
echo.
echo Please set the JAVA_HOME variable in your environment to match the
echo location of your Java installation.
goto fail
:init
@rem Get command-line arguments, handling Windows variants
if not "%OS%" == "Windows_NT" goto win9xME_args
if "%@eval[2+2]" == "4" goto 4NT_args
:win9xME_args
@rem Slurp the command line arguments.
set CMD_LINE_ARGS=
set _SKIP=2
:win9xME_args_slurp
if "x%~1" == "x" goto execute
set CMD_LINE_ARGS=%*
goto execute
:4NT_args
@rem Get arguments from the 4NT Shell from JP Software
set CMD_LINE_ARGS=%$
:execute
@rem Setup the command line
set CLASSPATH=%APP_HOME%\gradle\wrapper\gradle-wrapper.jar
@rem Execute Gradle
"%JAVA_EXE%" %DEFAULT_JVM_OPTS% %JAVA_OPTS% %GRADLE_OPTS% "-Dorg.gradle.appname=%APP_BASE_NAME%" -classpath "%CLASSPATH%" org.gradle.wrapper.GradleWrapperMain %CMD_LINE_ARGS%
:end
@rem End local scope for the variables with windows NT shell
if "%ERRORLEVEL%"=="0" goto mainEnd
:fail
rem Set variable GRADLE_EXIT_CONSOLE if you need the _script_ return code instead of
rem the _cmd.exe /c_ return code!
if not "" == "%GRADLE_EXIT_CONSOLE%" exit 1
exit /b 1
:mainEnd
if "%OS%"=="Windows_NT" endlocal
:omega
rootProject.name = 'flatten'
package com.frankandrobot.flatten
import java.util.*
fun testFlatten(count : Int, testArray : ArrayList<Any>, flatten: (ArrayList<Any>) -> ArrayList<Int>) {
val startTime = System.currentTimeMillis()
(1..count).forEach { flatten(testArray) }
val totalTime = System.currentTimeMillis() - startTime
println("Total time for size ${count}: ${totalTime}")
}
package com.frankandrobot.flatten
fun main(args : Array<String>) {
println("flatten1 speed test")
testFlatten((systemTestLoop / 3.0).toInt(), nestedArrayLevel5, ::flatten1)
testFlatten((systemTestLoop / 3.0 * 2.0).toInt(), nestedArrayLevel5, ::flatten1)
testFlatten((systemTestLoop).toInt(), nestedArrayLevel5, ::flatten1)
}
package com.frankandrobot.flatten
fun main(args : Array<String>) {
println("flatten2 speed test")
testFlatten((systemTestLoop / 3.0).toInt(), nestedArrayLevel5, ::flatten2)
testFlatten((systemTestLoop / 3.0 * 2.0).toInt(), nestedArrayLevel5, ::flatten2)
testFlatten((systemTestLoop).toInt(), nestedArrayLevel5, ::flatten2)
}
package com.frankandrobot.flatten
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.jetbrains.spek.api.Spek
import org.jetbrains.spek.api.dsl.describe
import org.jetbrains.spek.api.dsl.it
import java.util.*
class Flatten1Spec : Spek({
describe("#flatten1") {
it("should work on empty array") {
assertThat<Any>(emptyList, equalTo<Any>(flatten1(emptyList)))
}
it("should work on regular array") {
assertThat(flattenedArray, equalTo(flatten1(flattenedArray as ArrayList<Any>)))
}
it("should work on a nested array of level 1") {
assertThat(flattenedArray, equalTo(flatten1(nestedArrayLevel1)))
}
it("should work on a nested array of level 2") {
assertThat(flattenedArray, equalTo(flatten1(nestedArrayLevel2)))
}
it("should work on a nested array of level 5") {
assertThat(flattenedArray, equalTo(flatten1(nestedArrayLevel5)))
}
}
})
package com.frankandrobot.flatten
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.jetbrains.spek.api.Spek
import org.jetbrains.spek.api.dsl.describe
import org.jetbrains.spek.api.dsl.it
import java.util.*
class Flatten2Spec : Spek({
describe("#flatten1") {
it("should work on empty array") {
assertThat<Any>(emptyList, equalTo<Any>(flatten2(emptyList)))
}
it("should work on regular array") {
assertThat(flattenedArray, equalTo(flatten2(flattenedArray as ArrayList<Any>)))
}
it("should work on a nested array of level 1") {
assertThat(flattenedArray, equalTo(flatten2(nestedArrayLevel1)))
}
it("should work on a nested array of level 2") {
assertThat(flattenedArray, equalTo(flatten2(nestedArrayLevel2)))
}
it("should work on a nested array of level 5") {
assertThat(flattenedArray, equalTo(flatten2(nestedArrayLevel5)))
}
}
})
@frankandrobot
Copy link
Author

Start with the README.
Code is in flatten1.kt and flatten2.kt.
Tests start with system and test.
Best way to run this code is by cloning this gist and either running gradle speedTests or gradle test.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment