quad 17 Report post Posted June 26, 2018 (edited) Hey, If anybody has a clue an explanation would be highly appreciated. This is a task I need to finish to apply to uni ;o We investigate the behavior of an unknown program. Different parts of program are written in different programming languages and source codes aren't equipped with any comments. We have found that one of the most important and more often executable code part is the following for (j=0; j<K; j=j+1) run_dlx(); where K is given as a fixed (integer) parameter. The procedure run_dlx() is an external procedure which can't provide any parameters when called, but only a start signal. Default value of K is 10. For K=10 the program running time is 6.534 seconds. When we changed K=20, the running time was 41.32 seconds. When we changed K=30, it seemed us that program does not finish its work at all and we terminated it. Therefore, we tested for K=25, for which the running time was 18 minutes and 41 seconds. For K=0 the running time was 6.5 seconds. Finally, we decided to test once more for K=30 and decided to wait more patiently a little bit longer - the running time was 9 hours and 54 minutes. To be sure of the results we obtained, we decided to repeat all the experiments - for all K values 0, 10, 20, 25 and 30. In all cases we got the same results (running times) as for previous trials. Tasks: Please explain, what might be the reason that for high K values the program running time is extremely long. Please explain, what we can conclude about the behavior and features of procedure run_dlx() having the above-mentioned testing data. Try to evaluate program running time for K=40 and K=50 and additionally for K=15. Thanks! Edited June 26, 2018 by quad Quote Share this post Link to post Share on other sites
Mii 19 Report post Posted June 26, 2018 Wrong section, off-topic as it it not pko/top-related. Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue. 1 Quote Share this post Link to post Share on other sites
quad 17 Report post Posted June 26, 2018 (edited) 50 minutes ago, Mii said: Wrong section, off-topic as it it not pko/top-related. Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue. I have removed tags. Also, description clearly states 'questions and discussions related to programming', for the record, it does not say a word that my question has to be top-related. And, I have never tagged you, so I'm not sure why you're being aggressive, as it couldn't even bother you. Besides, I can notice a couple more questions with zero relation to this game, so you might consider leaving some comments out there, too. In case anyone's interested, the above mentioned program was used to brute force. Topic can be closed. Have a good day, MI :) Edited June 26, 2018 by quad Quote Share this post Link to post Share on other sites
V3ct0r 2,117 Report post Posted June 26, 2018 13 hours ago, Mii said: Wrong section, off-topic as it it not pko/top-related. Also you may want to refrain from tagging several people that have no relation to this and not try to "force" their attention to your issue. And what is the problem? Can not help - walk past 1 Quote Some useful links / Полезные ссылки Tips for making a topic in 'Questions & Help' / Рекомендации по созданию тем в разделе "Помощь" Server Advertising Section Rules / Правила раздела "Реклама серверов" Available e-mail domains for registration / Допустимые e-mail домены для регистрации User groups / Группы пользователей User ranks / Звания пользователей "Broken" pictures on the forum / "Битые" изображения на форуме Beware of scammers! / Осторожно, мошенники! My developments / Мои разработки Mods for client and server / Моды для клиента и сервера PKOdev.NET website for Tales of Pirates Server / PKOdev.NET веб-обвязка для сервера Пиратии I do not provide any help in private messages and outside the forum. Use 'Questions & Help' section please. Thank you for understanding! Я не оказываю какую-либо помощь в личных сообщениях и вне форума. Пожалуйста, используйте раздел "Пиратия: Помощь". Благодарю за понимание! Share this post Link to post Share on other sites
deguix 64 Report post Posted June 27, 2018 (edited) I didn't study in university, but you should definitely read about https://en.wikipedia.org/wiki/Memory_leak, one of the most common mistakes in programming. About brute-force... well... it would make sense, except why then would K=10 be almost the same time as K=0? Edited June 27, 2018 by deguix 1 Quote Share this post Link to post Share on other sites
Mii 19 Report post Posted June 27, 2018 (edited) 9 hours ago, V3ct0r said: And what is the problem? Can not help - walk past No problem at all. Was simply pointing out some people may not want to be tagged to every possible thread(in general not specifically just by quad) out of consideration. I wasn't being aggressive/toxic or trying to offend anyone but sorry if it bothered you. Anyways,so as to not go off-topic any further and walk past~ Have a good day :) Edited June 27, 2018 by Mii 1 Quote Share this post Link to post Share on other sites
quad 17 Report post Posted June 27, 2018 (edited) 3 hours ago, deguix said: I didn't study in university, but you should definitely read about https://en.wikipedia.org/wiki/Memory_leak, one of the most common mistakes in programming. About brute-force... well... it would make sense, except why then would K=10 be almost the same time as K=0? Hey there, I'm really unsure since no parameters are passed and idk how it would brute force without knowing what length to use. They should reply soon with the answers and I'll post them here, might be interesting for someone perhaps. Edited June 27, 2018 by quad Quote Share this post Link to post Share on other sites
MonkeyCode 453 Report post Posted June 30, 2018 @quad we study the time and cost of executions by using a notation called "O-Notation". 1 Quote Share this post Link to post Share on other sites
MonkeyCode 453 Report post Posted June 30, 2018 This is also the exact reason why we have various sorting algorithm, if we would sort a small list, say consisting of 4 entries, an "insertion" sort would be suitable, but once the list too big, as suggested by your question, perhaps we can use some other algorithm to solve the sorting of the giant list to save cost and time. try "Bubble" sort. In your question above, we try to scale the number of execution by a fixed amount regardless how many entries are in the list. This is how one would try to optimize their programs. 1 Quote Share this post Link to post Share on other sites
MouradMS 4 Report post Posted July 14, 2018 As a fellow university student, this is how I would answer this question. With no further information about run_dlx(), this is my conclusion: - run_dlx() is dependent on the variable K, which is probably global. - run_dlx() doesn't scale well with the variable K, and thus runs on an inefficient algorithm. - Plotting the given time costs against the values of K will easily reveal its exponential complexity and should allow you whether algebraically/geometrically to find a relation to approximate these values. Also a side-note is that in Donald Knuth's Bibles, DLX refers to his implementation of Algorthim X using the Dancing Links Approach with a complexity of O(N^N^2), so that's something for yall to taste! 3 Quote Share this post Link to post Share on other sites