Timeout error for select_random_quantum_word

Hello, i get the following error message:
Screenshot (432)
I wonder if this could be caused by going through the dictionary file multiple times e.g. 4 times, or if this may have a different source?

There is a time limit to how much time a test can take. However, reaching that time limit with a correct, somewhat efficient C-implementation is unlikely. My first guess would be an infinite loop/divergence, rather than an ineffecient implementation. The time out is triggered, whenever execution takes longer than the set time limit, so theoretically a very ineffecient implementation could also cause this.

Best,
Tim

1 Like

You might want to consider to first check how many words you want to read beforehand instead of reallocating buffer everytime you reach a limit. (That is if you are working with an array of strings).

So you can basically open and close the file 2 times. First time you check the amount of words you want to read. Then you allocate an array of that size. Second time you go through and store all the words in said array. Somehow this is more efficient than reallocating repeatedly or trying to generate a selected1 (and selected2) from the Trie, where you insert the valid words in. Like this you can also easily use drand48() * word_count (-1?) to compute a random array index (twice) for selected1/2. There might be several easier solution but that’s how I did it. (I didn’t test it and this way might be a point for your own ideas).
If you look into the data folder of your project and there the text-file “english-words-full” (or something like that) you will notice, that there are words of not length k. But it contains like 30k words. Choosing a selected1/2 should be hard to do from the Trie * data structure.

Yes, you can, but we tutors recommend you don’t. Reading the file twice is rather hard to maintain, it’s easier to read the file once. This is also a better approach in general, since the file might change inbetween. realloc'ating the buffer so that its size always doubles is a good and efficient approach.

It’s actually not that difficult :stuck_out_tongue:
But it’s much easier to indeed just maintain a seperate list of all words from which you choose. Do not forget to free this list.

It’s not. It’s less efficient (though still constant-time) and “less” correct (on a real system there would be a safety bug). Reallocating so that the size doubles every time has the same complexity (amortized analysis). Reading directly into the trie and writing a function that gives the nth word of that trie (in alphabetical order) is also constant-time, but arguably easier since there’s less memory to manage. All you need to write nth is to count the number of entries per sub-trie. (Think about it if you have time, it’s kinda fun to implement)

2 Likes

Ok well, then something in my realloc implementation was scuffed. Mr. Hack mentioned the reallocation by doubling instead of incrementally increasing the buffer size, yes. The Trie entries count sound interesting. I will try it. Thanks.

Thanks a lot for the help i guess it was just as you suggested some infinite loop i accidentally implemented as the test works out for me since i rewrote the function.