Looping is better, right?



  •  Couldn't figure out why IE was taking so long to validate input on this big .NET 1.1 form I just inherited. 

     Figured it out (all the validations are written like this):

     

    function AnyCodeSelected() {
        var index;
        var selectedCode;
        for (index = 0; index < document.forms(0).elements.length; index++) {
            switch (document.forms(0).elements(index).name) {
                case "ucStatusCodeControl$cbStatusCode":
                    selectedCode = document.forms(0).elements(index).value
                    break;
            }
        }
        if (selectedCode.replace(/^\s*|\s*$/g, "") == "") {
            alert('Please select a Status Code.');
            return false;
        }
        else {
            return true;
        }
    }



  • @grinthar said:

     Couldn't figure out why IE was taking so long to validate input on this big .NET 1.1 form I just inherited....

    If only there were some way to use the document to get the Element By using it's Name attribute. If only...

    Out of morbid curiousity, just how big was the form that it would take a long time to loop through all of its elements?



  • @dohpaz42 said:

    Out of morbid curiousity, just how big was the form that it would take a long time to loop through all of its elements?
     

    Agreed. The code above really shouldn't take more than a few hundred milliseconds, even on huge forms.

     

    Unless AnyCodeSelected was called many times a second in an abused event.



  • Well, the form has around 80 - 100 fields (varying types of controls)... and each one is validated in the manner you just saw.

     Here's another (just rinse and repeat):

     function AnyPlantSelected() {
        var index;
        var selectedPlant;
        for (index = 0; index < document.forms(0).elements.length; index++) {
            switch (document.forms(0).elements(index).name) {
                case "ucPlantControl$cbPlantName":
                    selectedPlant = document.forms(0).elements(index).value
                    break;
            }
        }
        if (selectedPlant.replace(/^\s*|\s*$/g, "") == "") {
            alert('Please select a Plant.');
            return false;
        }
        else {
            return true;
        }
    }



  •  Ahh, it's O(n^2) validation.



  • @dhromed said:

     Ahh, it's O(n^2) validation.

     

     

    Yes. And, as a bonus, each field is its own user control.



  • @dhromed said:

    Ahh, it's O(n^2) validation.

    I'll bet the original coder thought the break would break out of the loop, too. Optimization WTF FTW!



  • I thought that was the worst of it. I guess not. This is used almost everywhere.

     

     function FindControlOnClientSide(controlID, elementType)
    {
        var index;
        var documentElements = document.all.tags(elementType);
        
        for(index = 0; index < documentElements.length; index++)
        {
            if(documentElements[index].id.indexOf(controlID) >= 0)
            {
                return documentElements[index];
            }
        }
    }

    function FindExactControlOnClientSide(controlID, elementType)
    {
        var index;
        var documentElements = document.all.tags(elementType);
        
        for(index = 0; index < documentElements.length; index++)
        {
            if(documentElements[index].id == controlID)
            {
                return documentElements[index];
            }
        }
    }



  • @grinthar said:

    return documentElements[index];
     

    At least this one exits early, resulting in a worst case of  n^2, rather than a guaranteed case of n^2

    My knowledge of O is limited so I don't know how to note that the O will be somwhere between n and n^2.

    If it checks all fields sequentially with this break-early loop, does that mean O((n^2) / 2) ?

    Or O( ((n^2) / 2) - n )?



  • You take out constants... if it's bound by O((n^2)/2), it's just bound by O(n^2)



  • @Sutherlands said:

    You take out constants... if it's bound by O((n^2)/2), it's just bound by O(n^2)
     

    But in this case I know exactly how long it's going to take, so n^2 would just be... wrong, no?



  • @dhromed said:

    @Sutherlands said:

    You take out constants... if it's bound by O((n^2)/2), it's just bound by O(n^2)
     

    But in this case I know exactly how long it's going to take, so n^2 would just be... wrong, no?

    No.  Basically what Big O is saying is... O(f(n)) means that there is some constant k for which kf(n) is > g(n) for all n.  If g(n) is n^2 or g(n) is .5n^2 just changes the k, but it still requires a quadratic f(n) to ensure that k*f(n) is larger than g(n) for all n.



  • @dhromed said:

    @Sutherlands said:

    You take out constants... if it's bound by O((n^2)/2), it's just bound by O(n^2)
     

    But in this case I know exactly how long it's going to take, so n^2 would just be... wrong, no?

    Nope. For any algorithm slower than O(n), you can always make n big enough so that all constant terms become so small they don't matter. An O((n^2)/2) algorithm would be slower than an O(n^1.9) algorithm and faster than an O(n^2.1) algorithm for any large enough value of n (in my example, this happens at n=1024, assuming that O((n^2)/2) means the algorithm finishes in half the time as the other two when n=1).



  • @Jaime said:

    Nope. For any algorithm slower than O(n), you can always make n big enough so that all constant terms become so small they don't matter.
    Er, well, no.  n^2 is never bigger than 2 n^2, no matter how big you make the n.  The point is that you can choose whatever k you want.  No matter what k you choose, n^2 will become bigger than kn, so n^2 is not O(n).  But you can always put something in front of n^2 + 10000n so that it is smaller than kn^2.


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.