0

Here is my function:

fun quickSort(data: List<PhEntry>, maxTime: Long = 0L): List<PhEntry> {
    if (System.currentTimeMillis() > maxTime) throw Exception("")
    if (data.size < 2) return data
    val pivot = data[data.lastIndex / 2]
    val equal = data.filter { it.name == pivot.name }
    val greater = data.filter { it.name > pivot.name }
    val lesser = data.filter { it.name < pivot.name }
    return quickSort(lesser, maxTime) + equal + quickSort(greater, maxTime)
}

I call this from a time keeping function:

fun sortTimer(data: List<PhEntry>, time: Long = 0L, sortFunc: (sortedData: List<PhEntry>, time: Long) -> List<PhEntry>): Pair<List<PhEntry>?, Long> {
    val startTime = System.currentTimeMillis()
    return try{
        val result = sortFunc(data, startTime + time)
        Pair(result, System.currentTimeMillis() - startTime)
    } catch (e: Exception) {
        Pair(null, System.currentTimeMillis() - startTime)
    }
}

The data is a huge telephone directory containing a million entries. The program is supposed to try sorting the entire list within 90 seconds. If it is not possible, then it should go for a simple search of the non-sorted list.

Time values that are 90000L (90 seconds) or more causes the program to freeze. It does not throw any exception just freezes. I just tried using 1000L as the value for time and the program works fine.

Why is this happening? I want to basically terminate the recursion if time limit is reached. I can't use kotlinx libraries as I am doing a course from hyperskill and they don't allow me to modify the gradle file.

Edit 1:

On inserting a println(System.currentTimeMillis()) in the quickSort function, the function freezes when System.currentTimeMillis() exceeds maxTime. And then nothing happens. The recursion is very deep at this point, is that the reason for this behavior?

One Face
  • 417
  • 4
  • 10
  • Have you tried giving the process more heap memory?  (It's not a problem with the depth of recursion directly, as that would cause a StackOverflowError.  But each call is generating several lists, and the JVM can get very slow when the heap is about full.) – gidds Apr 29 '20 at 14:03
  • How to do this? Can you please give me a link which may explain about this? – One Face Apr 29 '20 at 14:15
  • https://stackoverflow.com/questions/6452765/how-to-increase-heap-size-of-jvm – gidds Apr 29 '20 at 14:19
  • The script does not throw `OutOfMemoryException` though. Will try this and get back. – One Face Apr 29 '20 at 14:21
  • 1
    seems an inefficient implementation of the quick sort... note that you iterate over your `data` already 3 times, just to get the 3 lists of equal, lesser and greater... you may want to replace your algorithm with just `data.sortedBy { it.name }`, which most probably already performs better... Also if you are on the JVM you may want to use an executor service where you specify a timeout when getting the value... that should be way easier than what you do now... – Roland Apr 30 '20 at 08:59

0 Answers0