Which cpu would be faster for grasshopper calculations?

Replies to This Discussion

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 2:36pm

This doesn't mess up the order of the string contents when measuring the distance right? Just like levenshtein distance where 0100 and 0010 would have the distance of 2 right? Brb going to corner shop to grab some energy drinks long night ahead will test it when I come back

Permalink Reply by David Rutten on July 21, 2016 at 4:18pm

If swap is enabled, that distance would be only 1, because a swap of two adjacent characters is considered a single operation.

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 2:12pm

Went to the shower realised I have worded it wrong string from the first branch has to be ran agains all of the rest branches and that repeats for 10000 times soooo. 10000x(39x10000)=3,9 billion component cycles with each checking 600 vs 600 characters. It took me 17 minutes to run 390,000 cycles. realised just now it would take me 7080 days to complete it normally. And with cuttoff value of 1 it in perfect world it would take 20 days to complete it........ Yup either my math is wrong or this calculation is impossible with this method.

Permalink Reply by David Rutten on July 21, 2016 at 4:18pm

I think your first order of business is trying to reduce the number of measurements. No matter how quick you make the comparison, there's nothing that will make it faster than turning it from O(nxm) to O(log(n) x log(m)).

What exactly are you trying to do?

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 4:30pm

Yeah I have been doing just that now I am down to 5314x43910

So what I am doing is running ladybug daylight hour simulation through my site at horizontal planes with step of 200mm I end up with 40 planes with roughly 10000 points for each plane, each point has sum of daylight hours received though out the year roughly 600 test hours and I have a third result with 0 and 1 if at that particular hour that point is sun=visible. (I get all these values in a string instead of a list to reduce the tree complexity)

And now I take the bottom plane point sun=visible branch aka branch 0;39 and run it against 0;0 to 29 one of them has to be inverted haven't got to that yet. So esentially what Is happening I am trying to find the points that could capture sunlight and I would use light tubes to tunel that light to the points that need the light at those exact hours(hence the trying to match the strings at exact order up to certain distance)

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 9:07pm

I think I found a great way to tackle this whit so called trie trees. http://stevehanov.ca/blog/index.php?id=114 found it here the second code. The way I understand is that it collapses the data that it only branches out at deviations. The author claims that it reduces the calculation time by 300 times.  It's like a smarter version of O(nxm) where "The upper bound for the runtime is O(<max word length> * <number of nodes in the trie>). For most dictionaries, considerably less than O(<number of words> * <max word length>^2)"

So I might be autistic because I haven't used real maths since the start of architecture but here it goes.
For O(nxm)
(10000*(40*10000))*(600*600)=1,440,000,000,000,000

And for trie node method O(mx(nodes))

10000(600*(600*600))=2,160,000,000,000 (the way I calculated the node amount is most likely wrong) 


And if any of this makes sense and trie method is actually applicable here could you help me port this script into grasshopper component, the whole code aspect of grasshopper components I haven't touched yet myself. :/ Thx for taking your time whit my boooshit David you da best!!!

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 10:59pm

Then there is fuzzy string matching which combines both of the methods that we have talked about trie's and cutoff value O(k * <number of nodes in the trie>), where k is the maximum cost. And I was looking at factorials in Levenshtein distance as you recommended, but as I understand its a P NP problem which is way above my second year architecture student pay grade. 

And apparently the tries are memory hungry so he continues with some DAWG's MANNNN

code: https://gist.github.com/smhanov/94230b422c2100ae4218

article: http://stevehanov.ca/blog/index.php?id=115

It's more complex but sounds like it has its benefits, such as showing the index of matches in the "dictionary"  so it would be easier for me to retrieve it later. Because I am matching these stings up but I would need same results in a whole other identical beginning structure tree aka I could just dispatch the indexes.

Anyway here is the file with all the values to give more insight!

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 11:15pm

https://drive.google.com/open?id=0BzJEuQsw2Ry0ZFFfZ1RWN0VtSGs 

Had to dodge the 5MB limit

Permalink Reply by David Rutten on July 21, 2016 at 1:39pm

GH2 isn't at the stage yet where actual components run, this is all core code being tested. But I don't think Levenshtein distance calculations can be multi-threaded because every new iteration depends on the previous one. Of course if you're calculating more than 1 distance then you can calculate each one on a different thread and gain speed in this way. This is in fact what I imagine most GH2 components will do. Unless they specifically implement a multi-threaded algorithm, they can be parallelized by running several iterations at the same time. This of course won't help if a component only computes a single outcome.

Permalink Reply by Jonas Blazinskas on July 21, 2016 at 1:43pm

Yeah I was imagining something like V-ray where each thread is running a small portion and doing its thaaaaangggg.

Permalink Reply by David Rutten on July 21, 2016 at 2:05pm

Also the algorithm I implemented isn't particularly optimized. Instead of just iterating over all the chars in both strings and testing them for equality, I first convert each string into an array of strings where each element is either a character, or a combination of a character and a diacritic, or a character surrogate pair.

I decided that correctness was more important that x-treme speed.

Permalink Reply by Jonas Blazinskas on August 3, 2016 at 12:16pm

Just wanted to say I managed to overcome my issue by inventing my own 64 bit grasshopper. Aka Opened multiple instances of rhino and grasshopper divided the paths and ran each component simultaneously :D if it works it works right? 

• ‹ Previous
• 1
• 2
• Next ›
• Page