Last active
August 18, 2023 09:16
-
-
Save lucasmonstrox/03f85a26002724d643cd7e06593a63e2 to your computer and use it in GitHub Desktop.
collatz fastest way
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const longestCollatzSequence = limit => { | |
| var numberWithHighestSequence = 3; | |
| var highestSequenceIndex = 8; | |
| /** | |
| * "Uint32Array" automatically fill with "zeros" - avoid copyWithin/loop/map to set array with zero values | |
| * | |
| * Save between 20~25 ms | |
| */ | |
| var arrayOfSequences = new Int32Array(limit); | |
| arrayOfSequences[1] = 1; | |
| arrayOfSequences[2] = 2; | |
| /** | |
| * Double step i += 2 to gain performance and avoid 1 iteration | |
| * | |
| * Save between 1~3 ms | |
| */ | |
| for (var number = 3; number < limit; number += 2) { | |
| /** | |
| * === comparison is fastest than casting condition to boolean | |
| * | |
| * The saving is insignificant but is possible to see the difference for a big limit | |
| */ | |
| if (arrayOfSequences[number] === 0) { | |
| var numberToTransform = number; | |
| /** | |
| * Using "new Array()" is fastest than "[]" | |
| * | |
| * Save between 5~10 ms | |
| */ | |
| var arrayOfNumbers = new Array(); | |
| do { | |
| /** | |
| * "array.push(value)" is fastest than "array[i] = value" | |
| * Link: https://stackoverflow.com/questions/614126/why-is-array-push-sometimes-faster-than-arrayn-value | |
| */ | |
| arrayOfNumbers.push(numberToTransform); | |
| /** | |
| * Caculate by "numberToTransform & 1" is fastest than "numberToTransform % 2 === 1" | |
| * Calculate by "numberToTransform >>> 1"(bitwise) is fastest than division | |
| * (numberToTransform << 1) + (numberToTransform << 0) is a fastest than 3 * numberToTransform | |
| * | |
| * Save 30~40 ms | |
| */ | |
| numberToTransform = | |
| numberToTransform & 1 | |
| ? (((numberToTransform << 1) + (numberToTransform << 0) + 1) << | |
| 0) >>> | |
| 1 | |
| : numberToTransform >>> 1; | |
| /** | |
| * === comparison is fastest than casting condition to boolean | |
| * "arrayOfSequences[numberToTransform] === undefined" is most probably to occur than "arrayOfSequences[numberToTransform] === 0" | |
| * | |
| * The saving is insignificant but is possible to see the difference for a big limit | |
| */ | |
| } while ( | |
| arrayOfSequences[numberToTransform] === undefined || | |
| arrayOfSequences[numberToTransform] === 0 | |
| ); | |
| /** | |
| * This strategy automatically resolves the next numbers and automatically gets cached. | |
| * | |
| * Save 250~300 ms | |
| */ | |
| var j = arrayOfNumbers.length; | |
| while (j-- > 0) { | |
| // Ignore numbers greather than limit. This prevents the array from getting big | |
| if (arrayOfNumbers[j] < limit) { | |
| arrayOfSequences[arrayOfNumbers[j]] = | |
| arrayOfNumbers.length - j + arrayOfSequences[numberToTransform]; | |
| } | |
| } | |
| if (arrayOfSequences[number] > numberWithHighestSequence) { | |
| numberWithHighestSequence = arrayOfSequences[number]; | |
| highestSequenceIndex = number; | |
| } | |
| } | |
| } | |
| return highestSequenceIndex; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment