Recursive Flatten vs Tail-Recursive Flatten

.gitignore

.gradle/
.idea/
build/
*.iml
gradle/

README.md

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

build.gradle

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]) {}

constants.kt

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

flatten1.kt

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
}

flatten2.kt

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
}

gradlew

#!/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 "$@"

gradlew.bat

@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

settings.gradle

rootProject.name = 'flatten'

system.test.flatten.speed.spec.kt

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}")
}

system.test.flatten1.speed.spec.kt

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)
}

system.test.flatten2.speed.spec.kt

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)
}

test.flatten1.spec.kt

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)))
        }
    }
})

test.flatten2.spec.kt

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)))
        }
    }
})

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.