Finding Top Ten From Large Object With TypeScript

Sami Nieminen

Sep 9

2 min read

This example uses X / Twitter hashtags as an example but the same method generalizes to any data where you have keys and each key can occur more than once. This solution takes no stance on the following:

How to query the data from a DB—we assume the data is provided from an API.
If it would be more optimal to perform the count computation directly in DB rather than on the backend.

Solution

type HashtagCount = [string, number] //[hashtag, count]

type TopHashtags = Array<HashtagCount>

type HashtagCounts = {
    [key: string]: number
}

//this is mock example, in reality there may be 1,000,000 entries
const hashtagCounts: HashtagCounts = {}

const topTenHashtags: TopHashtags = []

for(const key of Object.keys(hashtagCounts)) {
    const count = hashtagCounts[key]

    //optimize performance to avoid going through all array elements
    if(topTenHashtags.length === 10 && topTenHashtags[9][1] > count) {
        continue
    }

    const firstSmallerIdx = topTenHashtags.findIndex(t => t[1] < count)

    if(firstSmallerIdx > -1) {
        //insert at the desired location
        topTenHashtags.splice(firstSmallerIdx, 0, [key, count])
    } else if(topTenHashtags.length < 10) {
        //push to the end if there is room and the array is smaller than 10 and firstSmallerIndex did not return anything
        topTenHashtags.push([key, count])
    }

    if(topTenHashtags.length > 10) {
        //V8 engine (Node.js and Chrome) auto-throw away any elements that are beyond length 10
        topTenHashtags.length = 10
        //alternatively you can use array pop-method here.
    }

}

Mistakes To Avoid and Tips

Do not pre-populate the top ten array with junk data

This will cause the case to fail if hashtagCounts < 10.
Unless you add weird manual clean-up at the end to remove junk data.
You'd have a happy PM if top 10 most popular section shows some weird junk data like 'birthdayCakes123DevDay' in top 10 most popular products or hashtags of the day

Do not use linked lists

searching, inserting/shifting and memory overhead are all worse with a linked list than an array for this case

JavaScript arrays (object under the hood) are dynamic

You need to manually clean up any entries when the array is > 10 either with length method or pop-method depending on your environment

Remember to check the last array element before full findIndex method use

This will start saving compute cycles once the loop has been ran a few times

Prefer for-method over .forEach here for large array performance optimization

Object.keys(hashtagCounts).forEach() is valid but has a greater callback overhead and it is less optimized for V8 engine than for(const of X).

Remember to handle the cases where the loop has ran less than ten times

Solution

Mistakes To Avoid and Tips

Comments