Announcement

Collapse
No announcement yet.

Random Sorting Function

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Random Sorting Function

    I want to share a thought and see if this would be a good candidate for a built-in Miva function. Quick backstory: On product pages, my Related Products are displayed in a slider, so although all of them are always on the page, not all of them are seen unless the user scrolls through the list. As such, I wanted to randomize the list to give each item equal exposure. I didn't find a built-in sorting method to randomize an array, so I explored ways to create this manually.

    A quick Google search shows that there is a very established algorithm for random sorting called the Fisher–Yates shuffle. I found a website that shows it implemented in basically every programming language under the sun (except Mivascript, of course), which helped me figure out how it actually works and adapt it to Miva SMT code for my PROD page.

    Code:
    <mvt:assign name="g.i" value="miva_array_elements(l.settings:related_products:products)"/>
    
    
    <mvt:while expr="g.i GT 0">
    	<mvt:assign name="g.random" value="random(g.i - 1)"/>
    	<mvt:assign name="g.random" value="g.random + 1"/>
    	<mvt:assign name="g.null" value="miva_array_copy(l.settings:related_products:products,g.i,1,g.temparray,1)"/>
    	<mvt:assign name="g.null" value="miva_array_copy(l.settings:related_products:products,g.random,1,l.settings:related_products:products, g.i)"/>
    	<mvt:assign name="g.null" value="miva_array_copy(g.temparray,1,1,l.settings:related_products:products,g.random)"/>
    	<mvt:assign name="g.i" value="g.i - 1"/>
    </mvt:while>
    I only need this in one place so far, so I didn't both with a module. However, I know that Miva has a few built-in sorting functions already, and I thought something like this would be a good candidate for inclusion in a future release. Random sorting is pretty handy, and I haven't found anything in Miva so far to accomplish this.

    What do you think? Is this something that would be useful enough to include in the engine or even a function in Merchant? Is there anything built in that I've overlooked to accomplish similar results?


    Josh

    #2
    Re: Random Sorting Function

    This in an interesting problem and an interesting solution, however, yours is likely to have duplicate items show in the list, and in fact the randomness will be skewed toward the low end.

    The formula random(g.i - 1) + 1 is reducing the range of numbers on each pass, so the chance of generating lower and lower numbers is increased. (e.g. first pass, chance of getting a 1 is 1/100 in the, 50th pass its 1/50, 99 pass its 1/2)

    Also, rather than randomizing and copying the entire array, you only need a to randomize a list of indexes to the array so that you are not actually copying array elements. That will be faster to generate. So if the array has 100 elements you need a non-repeating list of random numbers from 1 to 100.

    Once you have generated a randomList if numbers, you can display the items like this.

    Code:
    <mvt:foreach iterator="index" array="randomList">
        <mvt:assign name="l.settings:product" value="l.settings:related_products:products[l.settings:index]" />
        
        Product Code: &mvt:product:code;<br>
    </mvt:foreach>
    Not to be self promoting but if you have Toolbelt, it has a command for this:
    <mvt:item name="ry_toolbelt" param="random_numbers|return_array|size_exprsn|lim it_exprsn" />

    Example: Return return 7 random numbers for a deck of 52 cards
    <mvt:item name="ry_toolbelt" param="random_numbers|l.all_settings:shuffle_cards |7|52" />

    If you want to try your hand at it, here is the Javascript version of the code
    Note: There are more efficient ways to do this, but for under a few hundred items, it's pretty fast.
    https://en.wikipedia.org/wiki/Fisher...3Yates_shuffle

    Code:
    Non repeating sequence of "size" randomly generated numbers between 1 and limit. 
    
    function rndseqence(size,limit) {
          if (size > limit) {
            alert("The size of the list can not exceed the upper number limit");
            return null;
          } else {
            var numlist=new Array(size);
            var i=0; var j=0; var n=0;
            while (i<numlist.length) {
              n=Math.random();
              n=Math.round(n*limit);
              while (n==0) {
                n=Math.random();
                n=Math.round(n*limit);
              }
              pass=true;
              if (i>0) {
                for (j=0;j<i;j++) {
                  if (numlist[j]==n) {
                    pass=false;
                  }
                }
              }
              if (pass) {
                numlist[i]=n;
                i++;
              }
            }
            return numlist;
          }
    }
    Last edited by RayYates; 08-03-15, 09:50 AM.
    Ray Yates
    "If I have seen further, it is by standing on the shoulders of giants."
    --- Sir Isaac Newton

    Comment


      #3
      Re: Random Sorting Function

      Hi Ray,
      Thanks for your response. I think I should clarify a bit how the code snippet I posted works, because it's a bit different than you described. Also, I take no credit for this method. I merely implemented it using Miva functions.

      On each iteration through the loop, the element at the g.random position is swapped with the element at the g.i position, so even though g.random can repeat itself and is generated from an incrementally smaller range, the values of the elements it chooses are always unique. The g.i variable really just defines the last element in the array that has not yet been selected in the new random order. It works backwards, building the new array order from last to first. Hopefully I'm explaining that well.

      My goal was to randomize the array so it could be called in a standard foreach loop, but I'm intrigued by your idea of applying this to the indexes and not the full array directly. As you pointed out, it seems like it would be faster since the values being copied are smaller. The downside would be that it can't just drop into existing template code without modifying all of the variables within the loop as well, but I'll experiment and report back.

      Thanks again for your feedback.


      Josh

      Comment


        #4
        Re: Random Sorting Function

        Ahhh I see that now. After you make a temp copy the last record, the random record is copied to the end of the list, then the copy of the last record is put in its place. You decrement the pointer to the last record and repeat. Brilliant.

        This is infinitely better than the Javascript method I posted, which scans the list to avoid repeats.

        Due to my obsessive need for speed, after some study, I replaced the underlying function in Toolbelts Random_Numbers command with the function below. It's able to generate a sequence of 1,000,000 non repeating random numbers in about 8 seconds.
        Now I must smack myself and get back to work...
        Code:
        <MvFUNCTION NAME="rndseqence2" PARAMETERS="size, limit, numlist VAR" STANDARDOUTPUTLEVEL="">    <MvCOMMENT>
                Non repeating sequence of "size" randomly generated numbers between 1 and limit.
                https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method
        
        
                Returns size of numlist
                l.numlist populated with results
            </MvCOMMENT>
        
        
            <MvIF EXPR="{ l.size GT l.limit }">
                <MvASSIGN NAME="g.rndseqence2_error" VALUE="Error rndseqence2(): Size exceeds limit.">
                <MvFUNCTIONRETURN VALUE = "">
            </MvIF>
        
        
            <MvIF EXPR="{ l.size LT 1 }">
                <MvASSIGN NAME="g.rndseqence2_error" VALUE="Error rndseqence2(): Size is less than 1.">
                <MvFUNCTIONRETURN VALUE = "">
            </MvIF>
        
        
            <MvIF EXPR="{ l.limit LT 2 }">
                <MvASSIGN NAME="l.numlist[1]" VALUE="{ 1 }">
                <MvFUNCTIONRETURN VALUE = "{ 1 }">
            </MvIF>
        
        
            <MvCOMMENT> Create Scratchpad array of l.limit numbers</MvCOMMENT>
            <MvASSIGN NAME="l.ndx" VALUE="{ 1 }">
            <MvWHILE EXPR="{ l.ndx LE l.limit }">
                <MvASSIGN NAME="l.scratchpad" INDEX="{ l.ndx }" VALUE="{ l.ndx }">
                <MvASSIGN NAME="l.ndx" VALUE="{ l.ndx + 1 }">
            </MvWHILE>
        
        
            <MvASSIGN NAME="l.ndx" VALUE="{ 1 }">
            <MvWHILE EXPR="{ l.limit GE 0 }">
                <MvASSIGN NAME="l.ptr" VALUE="{ random(l.limit - 1) + 1 }">
                <MvCOMMENT> Get a number from the list </MvCOMMENT>
                <MvASSIGN NAME="l.numlist" INDEX="{ l.ndx }" VALUE="{ l.scratchpad[l.ptr] }">
                <MvIF EXPR="{ l.ptr LT l.limit }">
                    <MvCOMMENT> Exchange this number with the last on the list </MvCOMMENT>
                    <MvASSIGN NAME="l.scratchpad" INDEX="{ l.ptr }" VALUE="{ l.scratchpad[l.limit] }">
                </MvIF>
                <MvIF EXPR="{ l.ndx EQ l.size}">
                    <MvWHILESTOP>
                </MvIF>
                <MvASSIGN NAME="l.ndx" VALUE="{ l.ndx + 1 }">
                <MvASSIGN NAME="l.limit" VALUE="{ l.limit - 1 }">
            </MvWHILE>
        
        
            <MvFUNCRETURN VALUE="{ miva_array_max(l.numlist) }">
        </MvFUNCTION>
        Last edited by RayYates; 08-04-15, 07:24 AM.
        Ray Yates
        "If I have seen further, it is by standing on the shoulders of giants."
        --- Sir Isaac Newton

        Comment

        Working...
        X