In this post let us explore a simple problem of finding the second largest number of an integer array using JavaScript. We will discuss different approaches that can be followed and their pros and cons.
We will explore the following approaches,
Sort and pick using the inbuilt JavaScript functions.
Loop and pick without using the inbuilt JavaScript functions.
At the first glance of the problem, the obvious way to pick the second largest element of the array would be, sorting the array in descending order and picking the 1st index element of the array (Array index starts from zero).
Sort and pick using the inbuilt JavaScript functions
In this approach we will be using the following steps,
Convert the Array in to a Set, this is to remove duplicate entries from the array.
Convert the Set again back to an Array, since set is not an ordered abstract data structure we can't sort the elements of a set. We need to sort the elements in descending order.
Sort the derived array in the descending order, this is a bit tricky.
Pick the element from the first index (Second largest)
Please find the complete source file below,
In this example we will be using Node JS, a server side Javascript language to run the above code. To execute the above NodeJS script, we need to create an input file which can be provided as the standard input.
I will be using the following ArrayInput.txt file as the input file which contains the array of numbers. First line of the input file contains the number of elements in the corresponding array and the second line contains the elements of the array.
Now, let us run the script against the above input file using the below command,
node SecondLargestNumber.js < ArrayInput.txtOutput will look like below,
Let us now explore the getSecondLargest() function and see the inbuilt functions that are used within.
nums => Is a numeric array passed to the function.
var numSet = new Set(nums) => Creates a new number set called "numSet" from the "nums" array. A set data structure doesn't contain any duplicates, so here we are converting the "nums"array to a set to remove duplicates.
var numArray = [...numSet] => Creates a new number array called "numArray" from the "numSet". This is a shorthand notation to convert a set to an array.
var numArray = numArray.sort(function(a,b){return b-a}) => Sorts the "numArray" in descending order.
Converting a Map/Set to Array
There are multiple ways of converting a Map/Set to an Array in JavaScript.
Using Array.from(arrayLike object) method : This static method creates a new, shallow-copied Array instance from an array-like or iterable object like Map, Set, etc. Ex : var numArray = Array.from(numSet); Refer to the link for further details.
Using the spread operator: Spread separator allows to expand iterable objects like arrays and sets in places where zero or more arguments (for function calls) or elements (for array literals) are expected. Spread operator is denoted as "..." We can use the spread operator to spread the elements of the set and create an array copy of the set as below, Ex : var numArray = [...numSet]; Refer to the link for further details.
Using the forEach function: Iterate through the set using the forEach loop and add the elements of the set to the array.
Sorting the array is bit tricky with JavaScript.
JavaScript Sort( ) method by default sorts values considering as Strings.
Because of this, the sort() method will produce incorrect result when sorting numbers unless a compare function is provided.
Please refer to the following links for further details on JavaScript array sort
If we use the Sort() function without the compare function the elements of the "numArray" will be considered as Strings and the values will be sorted in alphabetical order (not according to the numerical values). This will result in wrong results.
For example, consider the following array of elements,
var Array = [9, 4, 6, 1, 2, 10]
Array.sort() => [ 1, 10, 2, 4, 6, 9 ] (Sorted in Alphabetical Order)
Array.sort(function(a,b){return a-b}) => [1, 2, 4, 6, 9, 10]
(Sorted in Numerical Ascending Order)
As we can see the sort function without the compare function yields wrong results for number arrays. The compare function used in the above sample will guarantee the array will be sorted in the descending order.
We pick the second element from the sorted array which gives us the second largest element.
Loop and pick without using the inbuilt JavaScript functions
In this approach instead of using the inbuilt JavaScript functions, we will loop through the given array once while maintaining two variables largestNum and secondLargestNum to hold the largest number and second largest number. Finally after going through all the elements of the array we will return the variable contains second largest number.
Logic behind this approach
We will only loop through the array once
While looping through the array, at any point we will maintain the largestNum and secondLargestNum variables to hold the values of the largest and second largest elements of all the explored elements up to that point.
I have modified the source of the SecondLargestNumber.js NodeJS script by adding the getSecondLargestLoop(nums) function as below,
Modified complete source code can be found at https://gist.github.com/Seralahthan/87849e4394bc1b4fdd6f794c28b5830a
As you can see the main function is modified to log the execution time taken by both the above requested approaches.
Measuring the performance of both approaches
In order to compare the performance of the Inbuilt function based approach and the loop based approach we need to measure the execution time of the functions getSecondLargest() and getSecondLargestLoop().
Performance of a JavaScript function depends on the total time taken to execute event loop cycle with various phases.
For example, apart from the time taken for the computation logic, a function might have the following event loop phases which can add additional execution delays.
Timers
IO Callbacks
IO Polling
We don't have any of these event loop phases in any both of our functions.
Node.js has built-in modules that make this process of measuring the execution time easier.
The Node.js API provides us with Performance Timing API which helps in collection of high resolution performance metrics.
In this post we will be using the performance hooks module to get the relevant performance statistics.
perf_hooks.performance is an object that can be used to collect performance metrics from the current Node.js instance. It is similar to window.performance in browsers.
Please refer to the following link for further details on performance hooks
We need to import he perf_hooks.performance object as below,
const { PerformanceObserver, performance } = require('perf_hooks');perf_hooks.performance object has multiple inbuilt functions to get performance statistics in different scenarios. We will be using the performance.now() function.
performance.now() =>
Returns the current high resolution millisecond timestamp, where 0 represents the start of the current node process. Refer to the following documentation for further details and usage of performance.now() function.
https://nodejs.org/api/perf_hooks.html#perf_hooks_performance_now
Please refer to the following link for further details on other available functions in performance.
main function is modified as below to log the execution time of both functions,
We will measure the performance against the following input arrays,
PerfTestArrayInput100.txt => 100 unique random integers, taken from the [1,1000] PerfTestArrayInput1000.txt => 1000 unique random integers, taken from the [1,10000] PerfTestArrayInput5000.txt => 5000 unique random integers, taken from the [1,10000]
Input files can be found below,
Execution time statistics of PerfTestArray100
The loop based approach outperformed the Sort based approach.
Execution time statistics of PerfTestArray1000
The loop based approach outperformed the Sort based approach.
Execution time statistics of PerfTestArray5000
The loop based approach outperformed the Sort based approach.
From the results we can see that the Loop based approach is very fast and outperforms the Sort based approach. Also we can notice that execution time of the Sort based approach significantly increases with the array size.
Loop based approach outperforms the Sort based approach due to the following drawbacks in the Sort based approach,
Converting the input Array to Set Consumes additional heap memory, elements need to be copied which includes additional computation.
Set converted back to Array Consumes additional memory space, elements need to be copied which includes additional computation.
Sorting the Array
Sorting the Array
Time complexity of sorting the array is determined by the underlying sorting algorithm used by Array.sort() and the array size.
ECMAscript standard doesn't specify a particular sorting algorithm for JS. Different browsers use different sorting algorithms depending on the JS Runtime Engine.
For example, Mozilla uses Merge sort. Chrome's v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays.
JS runtime engine selects the sorting algorithm considering the following aspects,
Data size
Data type
Node JS JavaScript runtime is built on Chrome's V8 JavaScript engine.
Chrome's V8 JavaScript engine uses a combination of Insertion Sort and Quick Sort algorithm to implement the Array.sort(). Insertion Sort for arrays with length less than 10 and Quick Sort otherwise.
In our test cases since the array is big (>10) the Quick Sort will be used. Average case time complexity (Big O notation) of Quick Sort algorithm is θ(n log(n)).
In the loop based approach time complexity is traversing once through the entire array which is θ(n).
O(n) < O(n log n), so the time taken for sorting in the Sort based approach is greater than the whole time complexity of the Loop based approach.
Due to these reasons the Loop based approach outperforms the Sort based approach.
Thank you for Reading!
Cheers!!!
Commenti