4/20/2011 9:45 AM | |
Posts: 270 Rating:
|
Hello guys, I'm kinda new to this forum and all the stuff around this and I almost literaly just finished self-studying the Simatic Step 7 courses PRO1 and PRO2 (well I got few excercises left in the later one I decided to start with some sorting algorithms. Obviously, first I made a failsort aka bubblesort and it was pretty easy, so I went down the road of quicksort. Few So, in attachement I add the code for my blocks and you can say cool story, bro and move onto another topic... THOUGH, I got few questions, some of which might be little silly and they pretty much all go around my code, so if someone has few hours spare time and/or is boring, perhaps you might continue reading, but don't say I didn't warn you. Inbefore the questions, a brief insight into mind of a crazy programmer, it's also in comments of the code, but quite chaoticaly spread, so you don't have to pick it here and there... Basicaly, I tried to simply code a standard quicksort (described i.e. on W) and it worked fine for 10 items in DB, however, when I increased it to 41, I hit some problem about too many nested FCs. Then I figured a workaround with something like tail-recursion, the FC 3 for quicksort returns the elements before/after pivot and in calling FC 2 I have a buffer in which I put values and call it as long as it's not empty. Now the "smart thing" comes, basicaly, the quicksort works as a binary tree, where each level of pivot gives us two sublevels of new pivots (unless there's just <2 elements, then it's a leaf and no longer branches). So, in order to keep the buffers as small as possible, I explore the tree to depth, following one side of branches (i.e. always right) all the way down to the leaf and then close it's parent (by also finishing right) and then it's parent etc. untill I get all they way back to the root and then proceed with the other branch (i.e. left). Given the optimal selection of pivot, this ensures, that the buffer takes actually only depth of the tree + 1 (for 101 elements it's 8 (2^7 = 128, closes bigger power of 2, plus 1). The optimal selection of pivot is important, because in case of data being in really unfortunate order, this could still take actualy much much much more space. So, I also made the FC 4, which takes care of finding of optimum pivot and putting it at the end of the current values that undergo sorting, but it's kinda lame I guess, because while it takes quite loads of time, it still doesn't do as it should optimaly (you want to find a median and that put as a pivot, but I asume it is the task as complicated as the actual sorting, so what I do is find the average value of all the values and then find the closest value to it and it's really quite time consuming... That being said, I suppose I can move onto the questions part now. 1) I keep getting some warning that if I change AR2, it can destroy some local variables... Is it really all that bad, am I supposed to use just AR1 (I definately could and later on I did, it's just some more instructions). 2) Are there actually some sort of conventions as if I touch those ARs, that I am like supposed at the beginning of my function to save them and at the end to load them back? I think I remember something like that being the case at some assembler class @ university, but it's long time since I had that subject... 3) Are there some obvious or even less obvious flaws in the code (like stuff that could be done in one instruction and I do it in 100 etc., because I really just put it the way I figured it out, didn't make much optimization so far). I wonder about parts that can be reduced or even totally omitted or replaced with something better... 4) I know there are multiple networks for the code, but I really couldn't seem to figure out a way to make the code work in two separate areas, or do I miss something about that? 5) Back to those warnings, I am also getting something like "row x, column y, degree 1: comment cannot be saved", should I care about that? 6) Is there some way to work with randomness? I don't recall anything of that in the courses, so I just wonder - reason I ask is, because probably optimal way to pivot selection is to pick few random values from the array to be sorted and then find an average/median between them and that pick as a pivot, so it doesn't take so much bloody time and it's actually pretty good time-wise too. And I suppose that's it, if someone got all the way down here, cheers, the code is in the attachement(there's a.txtin.zip file with codes from source file, idk what exactly should I add from the project) and don't you anyone hesitate to tell me what am I doing wrong or point out something I miss, etc. With regards, MM Attachmentquicksort.zip (198 Downloads) |
Last edited by: MM1234 at: 4/20/2011 11:13 AMAlso, on second thouhgt, the values stated, such as 2^x, depth of tree etc., are not 100% accurate for smaller scales (the bigger input to sort, the more accurate they are) and perhaps the +1 to depth is not the case, since I omit addition of nodes that are gonna be leaves for sure... Those could be taken as <max perhaps, but it''s more clear to explain it with those, than just rumble mumble some crazy numbers pulled out of somewhere... Last edited by: MM1234 at: 4/20/2011 9:45 AMP.S.: Sorry, for the wall of text, it''''s just me... :] |
|
Follow us on