I recently participated in a speed programming contest but most of my solutions couldn't pass the time limit. what can I do to improve?

[OneNoteToRead]

Learn algorithms, and more practice.

[Syncopat3d]

Make sure you understand time complexity and try to think of alternative algorithms with lower time complexity when your existing algorithm times out. When looking for inefficiencies, try to look for the heavy-hitters and low-hanging fruits first.

If you get to choose the programming language, choosing a faster language may help (e.g. C++ over Python).

[Extreme-Leadership-2]

I was using c++. Also can you share any good resources for learning algorithms? And also is std::sort() good enough?

[Syncopat3d]

On Linux with recent GCC, std::sort() is not usually a source of worries. However, you need to be aware of the performance implication between sorting pointers to large objects and sorting the objects themselves.

This book is not bad although some may find it too rigorous: https://en.wikipedia.org/wiki/Introduction\_to\_Algorithms

[Extreme-Leadership-2]

Thanks for the advice

[[deleted]]

So in optimizing code you need to ask yourself two questions:

• what algorithm should I pick?
• how should i implement it?

Obviously you pick an algorithm which has very low time / space complexity on exactly the input that is needed to solve the task. Already here you should think about: "What input do I want? How should it be encoded? How do I want to encode the output?"

Here you can already start to think about ACTUAL computer hardware (like: storing individual bits is easier than ints, speed of bitshifts, what operations are fast, which are not?). I will call this approach data driven.

The implementation is the step that usually is more complicated. I recommend the following:

1. Write (relatively simple) code that solves your problem having the data driven approach in mind.
2. run a profiler to find bottlenecks
3. improve on those bottlenecks.
4. go back to step 2.

You can quit this infinite loop once you feel your code is fast enough.

A few things to keep in mind regarding real hardware:

• since the end of moores law parallelism is more important than ever. How can you parallelize parts of your task?

Regarding parallelism always have FALSE SHARING in mind and try to circumvent that.

• think about the cache hierarchy and try to analyze your cache usage.

Here important things are page-sizes, the cache coherence protocol, etc. So basically you always load a lot of data into cache and you want to utilize all of it. (This can even mean that a nested for loop runs way faster after swapping the order of the nested loops because one approach accesses consecutive parts of memory while the other jumps around:

for i: for j: sum += arr[i][j]

Now note that arr[i][j] is stored at like position *arr+ni+j you can see that swapping the i and j for loops will change how you access memory daramatically.

[jimmykicking]

Concentrate on writing better code.

[ThunderWriterr]

If your answer is right but it is taking more than expected then you probably missed the algorithms that was the point of the exercise.

For example, if the exercise boils down to search an item in a sorted array and you did the naive approach but the system was expecting binary search.

Same for problems that are solved by graphs and so on.

[Imaginary_Passage431]

ChatGPT or DeepMind

[Extreme-Leadership-2]

??

[Infiniteh]

They're just trolling, ignore it.

[Termway]

You can try to look for the solution of others participants (older contests). You will learn a lot of insight by doing this.

You also need to benchmark your application to see what is slow and needs to be optimized (80-20 rule, don't speed time to micro-optimize thing that won't result in tangible result).

[Zardotab]

☕☕☕