+1 vote
by
Hello all, the task is to find the longest sequence wrapped in side brackets - "< " and ">".

That is, if there are sequences of <a> и <bbb> the answer would be <bbb> .

How can I solve this problem by doing fork processes? Maybe there are some materials that can help to figure this out.
by
and no one asked if chains < > can overlap, like <aa<bb>aa> ?
by
Is it multithreading or a fork?
Fork is multiprocessing - different address spaces.
Multithreading is pthread_create() (etc.) on linux is one address space.
It is easier to solve your problem in a multithreaded version than in a multiprocessed one, because the result of calculations in each thread does not need to be passed to the control thread - it will already be known due to shared memory.

In general, the algorithm is simple enough - divide your array into N chunks (by the number of real processor cores), for each chunk find the beginning offset and the end offset (of course you must find for each chunk the first opening bracket and the last closing bracket). Run a different thread for each chunk, which will work within the allocated range.
After all the threads are finished, you only have to choose the maximum of the results of the calculations in the main thread.

For the fork variant, it is about the same, but you need to think about how to pass its range to the new process and how to return the result to the main process.

Good luck!
by
Of course, one could invent some analog of the Goldberg machine on forks to solve this problem, but why?

1 Answer

0 votes
by
 
Best answer
I take it you need to parallelize it? Look at the OpenMP - works in C/C++. Parallelization is very easy to do - insert some directives in the code, compilation keys and everything works.

How to solve the problem in parallel: Split the whole string into N (number of threads) parts and each thread separately for each part will find the answer within it. And also two quantities: The last character '<', the first character '<' and whether they are in the chunk at all. <br/>
Then the non-parallel part, which will choose the best answer out of N chunks, and also check which is the longest answer distributed over the chunks. For this you have everything - you know in each chunk which character can be the beginning <...> going into the next chunks and which can be the end. You still need to consider the case that in a given chunk the last <...> is to the left of the first > - then no segment <...> can stick out of that chunk. Otherwise, see where the leftmost segment can start. This is all implemented in one loop for N iterations. You need to keep the last < character in the previous chunks, which is not yet closed. Either close with the current chunk and compare with the answer, or break it (if the chunk starts with <) or continue the segment into the next chunk.
...