Unordered_map vs array

I need help with the codes here . Since there are two codes I ain’t posting here.

Summary in short: solved a trie question using unordered_map implementation in cpp, got TLE and MLE. changed the unordered_map to array of pointers and got accepted, now I don’t understand why there is such weired behaviour in these cases.

1 Like

coz u didn’t consider constant factor
although unordered_map and arrays hav access time as O(1) the constant factor has much diff
hence this behaviour
its not weird at all

but what about memory limit ?? Won’t map’s memory be better than that of array’s ??

yup maps will hav less memory req but did u ever get MLE on codechef
well I didn’t
I guess we live in a world where we hav lot of memory but need faster solutions
hence codechef guys hav set memory such that you dont need to take care of it so much
focus on faster algos

Agreed, but bro not all contests are held on codechef ??
One needs to know why one’s code gets wrong, else one can’t get better ???

u r jst making array of size 26 per node
say u created 1m nodes(which is really bad scenerio)
char is of 1byte
so around 20mb mem will be needed
thats not too much
I wonder if u will face any prob in any contest

again as i said num of nodes will be less than 1m (around 100k)
lol i just noticed codechef dont even provide memory limit for every question
but i had read somewhere that it depends on compiler or something around 1/2 GB (not sure)

this ques N=1e5, each string len=60, so total nodes =6*1e6 (roughly), Am I correct ?? I didn’t undrstand your char point. Can you explain a little ??

forget abt the char pt
it was a mistake
i was thinking abt another implementation of trie
for ques like these theres one more variation of trie called compressed trie(am not sure if its necessary here)
btw why dont u try that prob and tell which implementation gave better result

1 Like

yeah, I’ll try and let you know .:smiley:

This might be helpful: https://codeforces.com/blog/entry/62393

1 Like

Thanks for the source, But if you go through the question link and see the third implementation, I used map and not unordered_map , so , I don’t think this is applicable there.

Remember, there are places where array will work better, at some places, policy table, at some places map, and at some places unordered_map. So try everything until you get AC :stuck_out_tongue:

1 Like

LOL…:laughing:
sounds like machine learning : try all algorithms and see which gives best results

1 Like