Speeding up macro process (Graph algorithm stuff)

Hi, i'm working on floyd algorithm macro for a project,
problem is, the spreadsheet matrix is huge, it's a 1043 x 1043 spreadsheet
And this is taking wayyy too long, i've been waiting for almost 2 days already..
here's the file :
http://ifile.it/6v2j39f
(You start the macro using "run" command in "input" sheet)

So is there any way to speed it up?
Or if anyone got a supercomputer, could you help me process this? :p

I'm thinking about changing the 10^5 value into infinite value, but i can't find a way to display infinite value..

And here's some reference for Floyd's algorithm,
http://ifile.it/12p5zle

I have tried to split the algorithm to make it process one iteration at a time, but i've been waiting like 2 hours with no result,
and that's for 1 iteration, can't imagine how long it takes for 1043 iterations
You can do this by deleting the ' on this code

Please Login or Register  to view this content.

I'd really appreciate any help.. thanks.

Hi,

I just wanted to check whether this line is correct in the 'Copy Weights to output sheet' section:

Please Login or Register  to view this content.

Referencing row 3 of that sheet causes the column header to be entered into the table, is this the intended behaviour?

After reading up some on Floyd's Algorythm, I've realised I don't understand why you have 3 matrices.
The way I understand it Floyd's will calculate the least cost route between 2 nodes, identified by the row & column vertices of the matrix.
Do you not just need the input matrix, and then the resulting Output Matrix? (or am I missing something? )

Thanks

EDIT Not to worry, I now see that one matrix is used to give the 'cost' and one gives the 'route'

Out of interest what is the spec of the PC you are running this on?

I have just performed some test runs on my machine:

Intel Core 2 Duo 6300 @ 1.86GHz
3.50 GB of RAM

Floyd's Algorithm takes t * n^3 to run, where t is the time taken for a single vertices and n is the number of vertices.
Based on tests of 50, 100 and 150 vertices my computer takes 47.12 micro seconds per vertices.

Calculating this out based on your data of 1043 vertices:

0.00004712 * 1043^3 = approx. 15 hours.

It might be worth you running your code and setting the number of vertices to say 100 and timing how long it takes. We can then calculate how long you should EXPECT the full dataset to take.

As an ammendment to the above post I forgot that timing was with various debug options enabled.

With that removed on my PC the whole set should be done in around 7 hours.

The modified code that I have been using is shown below. Note that I am specifying the number of Vetices in the red line of code, rather than reading it from the cell, this is purely to allow for easy testing with different quantities of Vertices.

To 'estimate' the total time that will be taken do these steps:
1) Set n = 100
2) Run the macro and take a note of the time in seconds reported (t)
3) A rough estimate of the time for the full dataset of 1043 vertices is given by:

Please Login or Register  to view this content.

Floyd's Algorithm Function:

Please Login or Register  to view this content.

Hi,

Yeah, there is quite a bit of difference between your original code and the modified code that I posted, namely the use of ranges to initialise the original matrices, which saves quite a lot of time.

I'm not convinced that changing the 10^5 on teh input sheet to infinity would make much difference to be honest, as they only have to represent 'infinity' based on your other data. You could try using 10^8 just to be sure that your data can't reach that level, but I don't think it is a problem at the moment.

The actual processing of the algorithm if done in the for k... for i... for j... style will always take n^3 time to complete, so all you can try and do is accelerate the speed that the function inside the loop runs at;

Please Login or Register  to view this content.

Looking at it though, I can't see anyway that would make a significant enough difference to make it faster.

A couple of thoughts I had earlier though;

* Is your input matrix always undirectional, that is mirrored around the diagonal zero line? If so it might be possible to speed up the computation by just calculating half of the resulting matrix and then reflecting that back into the corrresponding cells. I have not thought about this in any detail though, so that might not be possible.

* Do you HAVE to use Floyd's Algorithm?
For a sparce graph, (ie. like yours with few connecting vertices compared to the number that are infinite cost), Johnson's Algorithm is supposed to be faster. However in my brief internet search on this topic I found the information on this method to be sparse to, and it may well take longer to research and code the Johnson's method than it would to just let the Floyd's method run, especially if you are only going to be doing this one time. If of course you are running this calculation more than once then the research might be worthwhile. I don't know where you got your original Floyd's Algorithm word file of information from, but it might be worth checking that source for anything on Johnson's too. If you do get any useful information feel free to post it and I will see if we can work that into your code.

I am quite interested in this project now that I have looked into Floyd's so would be interested to see an example of how Johnson's is implemented. The examples I have seen so far have been very poor.

Reading the data into arrays and operating on it there might be faster.

Aha, I do that on many other projects, not sure why I didn't think of it here
Thanks Shg, I'll give it a go and report back

Give this a go, it would seem to be the dog's doo-dahs based on the timings I am getting from it

Thanks to Shg for the 'reminder' regarding Arrays

The previous "Floyds" routine that I posted takes around 30 seconds to run with 100 vertices (on this PC, I have moved to my sloooow laptop )
The new "Floyds_Arrays" routine reports a time of 0.5 seconds!
Please let me know how you get on

Note that the number of vertices is now entered via the use of an input box which defaults to 100, (line highlighted in red)

Please Login or Register  to view this content.

How many vertices were you running?
My clapped out old laptop managed to do 255 with no problem so I am intrigued what value your's failed at?
Does it work ok at 255 for instance?

Ok, that is seriously confusing then

Can you try it on the attached spreadsheet? Bearing in mind this is a subset of your data as my Excel 2003 can only handle worksheets up to 256 columns, so the largest vertices that you can do is 255.

Well it works.. but i'm not sure if it's faster, it's 2038.18 sec
thats almost 1 sec per vertice right? 2038/255?

FYI, the number of vertice input must always be the same with the number of matrix , so we can just refer it to
n = Worksheets("Input").Cells(1, 8)

When you say "it works" what do you mean by "it" ?

The new macro in your existing workbook?
The new macro in the subset workbook that I posted?
Something else?
How many Vertices have you specified?

I realise that the number of vertices is supposed to be the same as the size of the matrix, however when the processing was taking a long time it was useful to be able to tell it to only work on the first 10x10 or 50x50 or 100x100 of the input matrix to make sure all was working correctly.
In final run you will of course need to run it over the entire matrix.

Ah i see, on that part the original code i posted was correct actually :p
It's for filling up route vertices with the 'node' values (T23, G4,etc)

Please Login or Register  to view this content.

And the latest one you gave me definitely slower than the one that doesn't use arrays though..
I tested both with 100 matrix :
the one you posted on first page only took 59.86 sec while the one with arrays gave me 144.66 sec

I am now thoroughly confused!
The most recent code I posted DOES fill the route vertices with the destination node values...
After running the code the route table looks like the attached LCR.jpeg, if that is not correct then please explain how it should be.
Perhaps Excel 2007 is dealing with arrays differently...

Just so that we can be sure we are singing from the same sheet as it were can you try the following.
I have attached my test workbook.
Please run the 'Floyds' macro with 100 Vertices entered into the inputbox.
This gives me the following time report:

Time to clear: 05.19 seconds
Time to init: 05.19 seconds
Time to run: 21.48 seconds

Then run the 'Floyds_Arrays' macro, again with 100 Vertices.
This gives me the following time report:

Time to clear: 05.25 seconds
Time to init: 05.25 seconds
Time to run: 00.33 seconds
Time to txfer from Array to range: 00.03 seconds

PLEASE post the timings you get from your computer as a comparison.

Perhaps someone else can shed some light on why Excel 2007 seems to be so much slower dealing with the arrays than 2003 if that does prove to be the case.

The following code is already in the example workbook attached, but is presented here also for completeness:

Using Worksheets (no arrays)

Please Login or Register  to view this content.

Using Arrays

Please Login or Register  to view this content.

You are correct with your timings, now they are making more sense to me
You can see now that the array version is much faster to process the algorithm.

You do need to add the additional times to it, but even so the array version should be considerably faster.

Looking at your post;

Floyd :
Time to clear : 06.55
Time to Init : 06.55
Time to run : 26.22

So the whole thing took 6.55 + 6.55 + 26.22 seconds = 39.32 seconds

Floyd Array :
Time to clear : 06.52
Time to Init : 06.52
Time to run : 00.50
Time to txfer from Array to range : 00.03 sec

So the whole thing took 6.52 + 6.52 + 0.5 seconds + 0.03 = 13.57 seconds

The thing to note here is that the 'time to clear' will be constant as it is clearing the ENTIRE data area no matter the qty of input vertices.
So it should only be the last 3 timings that change.

I would definitly recommend re-running it using the Array version on your full dataset.

To fix the 'Route' situation make the following change to the macro:

WAS:

Please Login or Register  to view this content.

CHANGED TO:

Please Login or Register  to view this content.

Fingers crossed for you. Please let me know how you / it gets on

Perhaps.
In Excel 2003 the largest Input matrix I can use from the worksheet is 255x255 as all columns after that are truncated.
Perhaps having two 1044x1044 arrays in memory is just too much for Excel to cope with, not having a copy of 2007 available I can't shed any more light on it than that

Do you get an option to 'Debug' when you get that error come up? If so what line is highlighted Yellow when the debug screen opens?

Weird, so it is at the point when it is trying to clear the Output worksheet...

Can you try this for me please, (whether it fixes the problem or not it is faster )

Change:

Please Login or Register  to view this content.

To be:

Please Login or Register  to view this content.

I haven't switched calculation to manual because we are performing no calculations on the worksheet itself.
I've just tried it here just in case and it made no difference to the timings on 255 vertices.

All together now...

HOORAY!

Glad it worked for you. 603.15, so whats that, a little over 10 minutes?
Wow, that is some improvement over the '2 days' figure that we had when we originally started along this 'path'.
Thankyou for presenting such an interesting problem, that has increased my knowledge of VBA and also has stirred up some interesting 'side-threads' along the way

Edit: HOORAY!

Wow, there's some reading in this thread!

KB24, can you please post the final version for curious sods like me?
(I'm not sure if it's in the latest version, but I did notice the use of the status bar in the code of one post - if this is removed, the macro will be even faster (perhaps not "significantly" though).)

Nice work Phil (with the reminder from Shg)

As you said, it does stir up some interesting side threads... I've been looking into the use of arrays for faster processing of large data sets too and have come across some issues to be aware of (transpose limits, array length limits etc). On the small chance that you are interested, I've decided to post the below links (copied straight from my notes file but unsorted for total relevance here) which provide some light reading on arrays:

'array explanations sourced from:
'http://www.dailydoseofexcel.com/arch...ays-explained/
'http://www.pcreview.co.uk/forums/thread-1001986.php (transpose limit of 5461 items)
'http://support.microsoft.com/kb/177991
'http://support.microsoft.com/?scid=kb;EN-US;153090 (basic principle of principle of Array to Range - out of date & doesn't refer to limits)
'http://support.microsoft.com/?scid=kb;en-us;843145 (general array explanations)
'http://babelfish.yahoo.com/translate_url?doit=done&tt=url&intl=1&fr=bf-res&trurl=http%3A%2F%2Fwww.xlam.ch%2Fxlimits%2Farrays.htm&lp=de_en&btnTrUrl=Translate (translated link to lots of Array related info)
'http://www.dailydoseofexcel.com/arch...nge-using-vba/ (links to the next 2 URL's)
'http://support.microsoft.com/kb/818808 ("correctly" states if (an item of the array, not entire array!) is greater than 911 characters (1/2 x 1,823))
'http://support.microsoft.com/kb/832136 (includes 1,823 character info on Excel 2003 & 8,023 characters in 2007)
'http://support.microsoft.com/kb/166342/ (some Excel array limits - not the char length limit though)
'unused example from Jindon http://www.ozgrid.com/forum/showthread.php?t=57877
'http://www.ozgrid.com/forum/showthread.php?t=65585 (another Jindon example & also Erase for arrays to free memory)
'http://support.microsoft.com/kb/843145 (descrip of arrays in subs)
'http://newtonexcelbach.wordpress.com...es-and-arrays/
'http://stackoverflow.com/questions/3...hats-the-point
'(Tushar's examples of writing to a range) http://www.mrexcel.com/forum/showthread.php?t=55175, http://www.mrexcel.com/forum/showthread.php?t=14194
'http://www.codingforums.com/archive/...p/t-82649.html, http://www.experts-exchange.com/Soft..._24458794.html (typed arrays filled by looping)
'http://support.microsoft.com/kb/184178/en-us (XL98: Variant Array of Dates Is Transferred to Worksheet)
'http://www.xtremevbtalk.com/archive/...p/t-79722.html
'http://blogs.msdn.com/excel/archive/...l.aspx#9472363
'http://www.utteraccess.com/forums/sh...Number=1146152
'http://www.experts-exchange.com/Prog..._20572066.html
PROBABLE WINNER! = http://www.experts-exchange.com/Soft..._21804560.html


Rob

Rob,

Here is the latest version of the macro code. You can try commenting out the StatusBar parts, but as I only implemented it in the outer (k) loop it seems to have negligable effect from what I can tell. (Testing 255 vertices I can detect no difference over several runs with it present or removed).
However on my PC at least, when doing a large number of vertices it seems like it suffers from the "Status bar not updating" problem anyway, so could be removed if it is of no use.
It might be useful if KB24 could post the entire workbook though, as I only have it in '2003 format' now, which truncates his 1044x1044 dataset down to 255x1044 due to Excel's limitations, which then means the largest array you can process from the data is 255x255.

Please Login or Register  to view this content.

Thanks Phil,

I'm in the same boat as you with no current access to Excel 2007 so I can't test this in further - but then, even if I could test, it may not be worth it, because you've already done a fantastic job!

I tried a few alternative approaches (Select Case instead of If, the below With clause, precalculating the addition of the output_matrix) to see if I could make it any faster but using the simple timer & only running for 255x255 didn't show any favourable differences*. On the other hand, I was surprised to find some small negative impacts for the latter two approaches (ignoring effects of any other concurrent processes).

When I next have the chance to play in Excel 2007 I may remember to come back to this thread with some more detailed timing results of a larger matrix using a high performance timer (search for GetTickCount or see http://www.j-walk.com/ss/excel/eee/eee005.txt).

Please Login or Register  to view this content.

In fact, just out of curiosity, I'm going to try looping through the code to get average times in Excel 2000 & will probably post my comparison file tomorrow...

Rob