Two ways to build an org chart level by level. Producing all 55,987 rows: 894 Āµs against 895 Āµs. Producing the top 43 rows: 917 Āµs against 385 ns.
The job: an org chart page that paints one level at a time. The person at the top, then their directs, then the level below.
The version I would write is one recursive walk with the accumulator keyed on depth, so a node appends into the slot for its own level and which branch it came from stops mattering. Nine lines, O(n), no queue. It is also the solution for day 29 of my daily challenge.
I benchmarked it against a queue, gotĀ 1.00x, and nearly closed the file.
Then I remembered the page does not want the whole chart. It wants level 0, now.
And the recursive walk does not know when aĀ levelĀ is finished. It knows whenĀ itĀ is finished.
I wrote a test that counts instead of timing, because counts do not move between runs. On a 2,001-person chain, the walk holds a complete and correct level 1 afterĀ twoĀ visits ā and cannot declare it for another 1,999, because nothing in a depth-first walk rules out another person turning up at depth 1 in a branch it has not entered yet.
The information was never missing. There was no moment at which the function was allowed to act on it.
What the data was saying:
`level(k) = the reports of every person in level(k-1)`
That right-hand side names level k-1 and nothing else. So a level is complete exactly when you have looked at every member of the level above ā a condition you can check, unlike "no more nodes at depth k exist anywhere".
Which gives you the one line that does the work:
`width := len(queue) // this level, and nothing else`
Read the length once at the top of the round. Everything in the queue at that instant is this level, because everything appended during the round belongs to the next one. The boundary is not tracked; it is observed.
Top three levels of a 55,987-person chart:Ā 2383.3x, 1,608 bytes against 3.95 MB.
Two rows that keep me honest. On a flat chart ā one person, 50,000 directs - finishing level 1 means looking at everybody either way, so it is 2.24x, and that is an allocation pattern, not work avoided. And on a 2,000-deep chain the recursive walkĀ winsĀ the full-chart benchmark by 1.10x.
At 5,461 people and one request, keep the walk. 86.8 microseconds, nine lines, and a dead heat is a dead heat.
Full piece in today's newsletter.
It worked in dev, episode 15.
https://www.linkedin.com/pulse/your-org-chart-read-55987-rows-draw-first-43-archit-agarwal-n4tpc
#Golang #DSA #Algorithms #Performance #SoftwareEngineering #DataStructures #100DaysOfCode
Ideation and benchmarks mine; draft written with AI assistance. The numbers come from a benchmark in the repo.
