• Hans de Great (unregistered)

    Cannot recist to be frist

  • Hansoff Mahjunk (unregistered)

    Frist is no better than sicint

  • (nodebb)

    This is the new meaning of "went up exponentially", meaning just "a lot". The algorithm is O(n-cubed) for n = the number of switches, and O(m-squared) or so for m = the number of ports per switch, so O(n-cubed times m-squared), rather than O(2 to the n power).

    (Can you tell that I don't trust the forum software on this site to handle asterisks correctly? And by "correctly" I mean, of course, "the way I want".)

  • Rev. Creflo Baller (unregistered) in reply to Steve_The_Cynic

    You sure about that? I think it's perhaps worse than (truly) exponential. Because of the nesting it feels like a permutation of combinations (or vice-versa) or maybe even a combination of permutations of combinations. It's building an array of all ports on an array of all switches but one for an array of every switch on the network and there appears to be no check on whether a given path has already been checked from the opposite side.

    It's so awful I may be misunderstanding due to a fail-safe in my brain preventing me from comprehending how truly disgusting it is.

  • (nodebb) 
            int portCounter = 0;
        int macCounter = 0;
        for each port {
            ports[portCounter] = port;
            portIndexes[portCounter] = macCounter;
            for each MAC on port {
                 allMACs[macCounter++] = MAC;
            }
        }

    Shouldn't portCounter be being incremented somewhere in there?

  • Chronomium (unregistered) in reply to Rev. Creflo Baller

    It's still to a fixed power though; if m=n then it's n^5, while if m=n^2 it's n^7. It gets pretty bad, but ultimately any fixed power isn't as bad as truly exponential.

  • Herby (unregistered)

    I am reminded about a memory test I wrote for a microprocessor. It did all sorts of bit tests and addressing tests, and soon grew into factorial space when counting the iterations. I realized after attempting to run the thing, and looking at the progress after a minute or two that it MIGHT finish in a couple of years time to complete the test. I pared it down to a few simplified tests that while functional, weren't as exhaustive in their scope.

    Lesson learned!

  • Ulysses (unregistered)

    Y'all should be grateful it used iteration rather than recursion!

  • Rev. Creflo Baller (unregistered) in reply to Chronomium

    I think it's factorial not fixed power. On a hypothetical network, if you change from 8-port switches to 16-port it's not building arrays with twice the additional members, nor just 2 to the 8th power additional members, but because of the recursion I think it has to have 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 = 518918400 additional members, on top of the 8! it already would've had to do. I think.

    And the recursion, I think in this pseudo code, is recursed? So that factorial is multiplied by the number of switches, factorial. Minus one for not counting the current switch.

  • Rev. Creflo Baller (unregistered)

    Or am I failing to read the example correctly...?

  • Jeremy (unregistered) in reply to Chronomium

    But since power and exponent are synonyms I think exponential is appropriate when raising to any power, even if it's a constant power.

  • Tim (unregistered) in reply to Jeremy

    Exponential growth means M^N where N is the varying value e.g. 2^2; 2^3; 2^4; ... It's the opposite of logarithmic growth, and is truly horrendous.

    Raising to a non-varying positive power N^M e.g. 2^2; 3^2; 4^2 is bad (especially as M increases) and for small values of N can be worse than exponential growth, but in the long run is not as bad as exponential growth.

  • nasch (unregistered) in reply to Tim

    So if exponential growth is where the power increases, what is it called when the base increases? It's not linear, pretty sure not geometric.

  • compsci (unregistered) in reply to nasch

    Polynomial time, of course. Here https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time

  • Notorious Nitpicker (unregistered)

    I think i once owned a set of Psuedo.

  • Hans de Great (unregistered)

    It looks to me as a simplified Traveling Salesman problem (not wigthed) . Would then mean O(n!)

  • RandomStranger (unregistered) in reply to Notorious Nitpicker

    Don't step on my Blue Psuedo Shoes

  • (nodebb) in reply to Tim

    This is a really clear explanation, thanks. I've often thought business people were technically wrong when they talk about "exponential" growth when they mean vaguely non-linear, but I've forgotten most of my high school maths and never bothered to re-acquaint with exponential, geometric, polynomial, etc.

  • PedantsRUs (unregistered)

    Any algorithm that has a finite upper bound runs in constant time. O(1). Even if that bound relies on the maximum array size for a language raised to an absurd value.

  • Captain Oblivious (unregistered) in reply to WTF

    The future of the field...

  • Anonymous (unregistered)

    Is "Array[]" an array of integers or an array of arrays? Or is this R?

  • (nodebb) in reply to PJH

    Oh, this treasure trove of WTF just keeps going

    int startIndex; int endIndex; for (int ictr = 0; ictr < ports.length; ictr++) { if (ports[ictr] == port) { startIndex = portIndexes[ictr]; endIndex = portIndexes[ictr + 1]; } }

    So, on the last iteration through the loop, we reference a non-existent member, The correct limit (portCounter) is out of scope (or in some other scope), depending upon how this particular Verkakt language works.

    for (int ictr = startIndex; ictr < endIndex - 1; ictr++) {

    Less than (endIndex - 1)? So we arbitrarily drop the last mac address for every single port. If a port has only one mac address, we return an array with nothing resembling a mac address.

    I wonder how efficient it would be if it actually was playing with a full deck, and not so many invalid values.

    Of course, "exponential growth" really just means anything that doesn't scale well. n log n might be tolerable, because if you can really assess an algorithm is n log n, you've probably made it perform as well as you can. Polynomial or worse usually won't fly unless you can restrict the problem space.

    Addendum 2017-01-11 23:16: Your formatting kung fu is better than mine. <bow/>

  • (nodebb) in reply to Crunger

    Interesting use of formatting there...

  • WP (unregistered)

    This is still fine. I just found something obfuscated in my project's codebase which is O(n^n) that just got reduced to O((log(n))^n), because it is too messy, crap and live, I could not allocate time for rewriting the entire module.

  • Someguy Inoz (unregistered)

    I once had the joy of rewriting a permission management system built by someone who liked linear searches. He'd do linear searches on sorted arrays after bubble sorting them. I suppose at least he understood the code he'd written. And his code worked really well on the test dataset, where he had 3 or 4 users in 2 groups who could be granted 2 or 3 different permissions on 5 or 6 objects in a very simple tree. It was pretty flawless and all his snazzy treeviews and smart navigation was pretty snappy.

    Then we pointed it at the real system, with a few thousand users, 20 or so permissions ("can view but not modify data owned by my group") and thousands of objects in a fairly deep hierarchy. Somehow the very first screen, with all the trees closed down to a single top node, didn't load. Well, one core of the CPU went to 100% and we waited. And waited. After lunch we waited some more. Eventually we decided it didn't work.

    I was given the rewrite and a three week deadline. Not just for the user interface, but for "the other bit" as well... using that permission tree to decide what data to display to a given user, and which bits they could modify.

    Looking at thee source code I gave up counting the O(N) complexity after about 30. To draw a single permission in the "permissions this user has" tree, he'd linear search the array of permissions for each object, carefully recursing through the tree of objects to find out what permissions it inherited from objects above it, every time. Then he'd look for the next un-drawn permission, using a linear search through the already-drawn objects to see if each permission in the master list had been drawn yet. I cried.

    I made it work, basically by not doing iterations except where I had to, like linking tree nodes to their parent object directly and a few other tricks.

  • Paul Neumann (unregistered)

    Be careful with that much Pseudo -- Cross any major borders and you'll be doing hard time

Leave a comment on “Mapping Every Possibility”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article