Vectorization Help...I think
in [Matlab]
|
From: Jonny O'Connell on 17 Jul 2010 14:06 Hi, I'm really new to MALTAB, I only sat the module this semester, but somehow I've managed to get myself a summer project writing a parallel evolutionary algorithm in it! Anyway I've done some basic profiling on my code and found that one line is accounting for about ~45% of my run time. It's a find function, but it's pretty much a copy and paste from the help documentation (obviously adapted for my needs), but I'm not sure if I can improve it any further. From the literature I've read on MATLAB, vectorization is king, and should be used anywhere it can be for better performance. I've had some success on various parts of the program, but I'm not sure if what I have is a candidate for vectorization and I was hoping someone could cast an experienced eye over it. % Perform swapping until cycle is complete while cycleIndex ~= seedNumber; cycleIndex = find(firstParent == secondParent(currentNumber)); offspring(cycleIndex) = firstParent(cycleIndex); currentNumber = cycleIndex; end The culprit is the 'find' line, the first line in the loop. Any pointers would be good! Cheers
From: Bruno Luong on 17 Jul 2010 15:01 "Jonny O'Connell" <jonnydotoconnelldotx(a)gmail.com> wrote in message <i1sreb$6fs$1(a)fred.mathworks.com>... > Hi, > > I'm really new to MALTAB, I only sat the module this semester, but somehow I've managed to get myself a summer project writing a parallel evolutionary algorithm in it! > > Anyway I've done some basic profiling on my code and found that one line is accounting for about ~45% of my run time. It's a find function, but it's pretty much a copy and paste from the help documentation (obviously adapted for my needs), but I'm not sure if I can improve it any further. > > From the literature I've read on MATLAB, vectorization is king, and should be used anywhere it can be for better performance. I've had some success on various parts of the program, but I'm not sure if what I have is a candidate for vectorization and I was hoping someone could cast an experienced eye over it. > > % Perform swapping until cycle is complete > while cycleIndex ~= seedNumber; > cycleIndex = find(firstParent == secondParent(currentNumber)); > offspring(cycleIndex) = firstParent(cycleIndex); > currentNumber = cycleIndex; > end > Try this: [trash loc] = ismember(secondParent,firstParent); while cycleIndex ~= seedNumber; cycleIndex = loc(cycleIndex); offspring(cycleIndex) = firstParent(cycleIndex); end Bruno
From: Jonny O'Connell on 17 Jul 2010 18:14 > Try this: > > [trash loc] = ismember(secondParent,firstParent); > while cycleIndex ~= seedNumber; > cycleIndex = loc(cycleIndex); > offspring(cycleIndex) = firstParent(cycleIndex); > end > > Bruno Thank-you! I think you accidentally missed the stopping condition, but after adding that back in I did a quick test. For the whole loop originally, 320 seconds, with your alteration, the loop and the ismember line are only 145....over twice as quick! Many thanks again, Jonny
From: Roger Stafford on 17 Jul 2010 19:05 "Jonny O'Connell" <jonnydotoconnelldotx(a)gmail.com> wrote in message <i1t9vc$k9s$1(a)fred.mathworks.com>... > > Try this: > > > > [trash loc] = ismember(secondParent,firstParent); > > while cycleIndex ~= seedNumber; > > cycleIndex = loc(cycleIndex); > > offspring(cycleIndex) = firstParent(cycleIndex); > > end > > > > Bruno > > Thank-you! I think you accidentally missed the stopping condition, but after adding that back in I did a quick test. For the whole loop originally, 320 seconds, with your alteration, the loop and the ismember line are only 145....over twice as quick! > > Many thanks again, > > Jonny - - - - - - - It is difficult to give you a reliable answer without some additional information about the firstParent and secondParent arrays. For example, it would be easy to fall into an infinite loop if, say, firstParent(1) == secondParent(2) firstParent(2) == secondParent(1) Also if more than one firstParent is equal to a given secondParent element, then the find function could yield multiple values, or if no firstParent is found, it could produce empty results. I think you need to tell us more about the nature of these two arrays. The ismember function presumably uses an order n*log(n) algorithm where n is the arrays' length, whereas the find function is an order n algorithm. For Bruno's suggestion to save time with large n, it would be necessary that either a single use of the while loop is made and the number of trips through it before exiting is likely to be at least order log n, or some equivalent multiple usage of the while loop is made using the results of a single call to ismember. I think there is much more that you can tell us about the statistics of your problem that would be useful in giving you reliable advice. Roger Stafford
From: Jonny O'Connell on 17 Jul 2010 22:36
> It is difficult to give you a reliable answer without some additional information about the firstParent and secondParent arrays. For example, it would be easy to fall into an infinite loop if, say, > > firstParent(1) == secondParent(2) > firstParent(2) == secondParent(1) > > Also if more than one firstParent is equal to a given secondParent element, then the find function could yield multiple values, or if no firstParent is found, it could produce empty results. I think you need to tell us more about the nature of these two arrays. > > The ismember function presumably uses an order n*log(n) algorithm where n is the arrays' length, whereas the find function is an order n algorithm. For Bruno's suggestion to save time with large n, it would be necessary that either a single use of the while loop is made and the number of trips through it before exiting is likely to be at least order log n, or some equivalent multiple usage of the while loop is made using the results of a single call to ismember. > > I think there is much more that you can tell us about the statistics of your problem that would be useful in giving you reliable advice. > > Roger Stafford Okay I'll try and put what I'm doing into a bit of context. This function takes two permutations of size n (size normally in the range 100-500) generated using the 'randperm' function, to be the firstParent and secondParent. Lets say we have the two parents: First: 8 7 6 4 1 2 5 3 9 10 Second: 2 5 1 7 3 8 4 6 10 9 Taking a randomly selected starting point, that element from the first parent is copied into an 'offspring'. So say this algorithm chooses to start at index 3, 6 is copied into location 3 of an offspring. Offspring: - - 6 - - - - - - - The algorithm then looks at index location 3 in the second parent, and finds 1. It locates 1 in the first parent and copies that into the offspring, at its first parent index of 5. Offspring: - - 6 - 1 - - - - - It repeats, looks at index 5 in the second parent and finds 3. 3 is located in the first parent at index 8 and copied too the offspring. Offspring - - 6 - 1 - - 3 - - Now when the algorithm comes onto the next loop of the cycle, and checks index 8 of the second parent it finds 6 which is the value it started with. At this point the cycle halts and any empty spaces are filled with values from the second parent. Offspring: 2 5 6 7 1 8 4 3 10 9 My entire function to achieve this: function offspring = cycle_crossover(firstParent, secondParent) % Initilisation of starting point and output matrix seedNumber = randi(length(firstParent), 1, 1); offspring = zeros(1, length(firstParent)); offspring(seedNumber) = firstParent(seedNumber); currentNumber = seedNumber; cycleIndex = 0; % Perform swapping until cycle is complete [~, locations] = ismember(secondParent, firstParent); while cycleIndex ~= seedNumber; cycleIndex = locations(currentNumber); offspring(cycleIndex) = firstParent(cycleIndex); currentNumber = cycleIndex; end % Keep remaining items in their original location zeroLocations = ismember(offspring, 0); offspring(zeroLocations) = secondParent(zeroLocations); end I changed the 'copy remaining items' section code also based on what Bruno provided, and that too seemed to speed up significantly. For the scenario laid out, is that how you believe the code should look? Thanks again! Jonny |