LiveCode Forums.

Posted: **Fri Jun 15, 2012 7:37 pm**

I am trying to find the number of inversions in a random list of 100,000 numbers using merge sort. My code works fine for a small list of numbers, but takes forever with the large list. It seems to get stuck on this line:
repeat with m = 1 to 100000
I've heard that "repeat for each" is faster, but I don't know how I would use that here.

Code: Select all

on mouseUp

   #input original array
   put specialFolderPath("documents") & "/IntegerArray.txt" into tFilePath
   put url ("file:" & tFilePath) into tArray
   
#this is the smaller list that worked fine
   --   put "9,10,8,1,4,7,6,2,5,3" into tBeg
   --   set itemdelimiter to comma
   --   repeat with i=1 to 10
   --      put item i of tBeg & cr after tArray
   --   end repeat
   
   put 1 into  i
   put 1 into j
   put tArray into t1
   
   repeat with tWhole = 2 to 131072--groups from 2 to n
      put tWhole/2 into tHalf
      repeat with m = 1 to 100000--each level
         if tHalf=1 then
            put line m of t1 into tLeft
            put line m+1 of t1 into tRight
         else
            put line m to m+tHalf-1 of t1 into tLeft
            put line m+tHalf to m+tWhole-1 of t1 into tRight
         end if
         repeat with k = 1 to tWhole--each run
            if line j of tRight = empty or\
            i<tHalf+1 and\
            line i of tLeft < line j of tRight or\
            j>tHalf then
               put line i of tLeft & cr after t2
               add 1 to i
            else 
               put line j of tRight & cr after t2
               add 1 to j
               if i<tHalf+1 then
                  add tHalf - i + 1 to tInv
               end if
            end if
         end repeat
         put 1 into i
         put 1 into j
         add tWhole-1 to m
      end repeat
      put tWhole*2-1 into tWhole
      put t2 into t1
      put empty into t2
   end repeat
   
   put tInv into field 11
end mouseUp

Posted: **Sat Jun 16, 2012 6:51 pm**

Hi.

"Repeat for" can be thousands of times faster, especially with large amounts of data. Sometimes it is essential to be able to reference explicitly the elements of the repeat, though, and so the "repeat with" structure is often indispensible.

But you can also set up a counter, and use that in place of the automatic indexing of the "repeat with" variable. I really have not read your code, but suggest that you see if this is possible. In a simple example, I loaded a field with 100,000 numbers. Then tried these two scripts in a button:

Code: Select all

on mouseup
   get fld "testField"
   put the ticks into temp
   repeat for  each line tLine in it
      add 1 to tLine
   end repeat
   answer the ticks - temp
end mouseup

on mouseup
   get fld "testField"
   put the ticks into temp
   repeat with y = 1 to the number of lines of it
      add 1 to line y of it
   end repeat
   answer the ticks - temp
end mouseup

The first handler worked in two ticks. The second took months.

See if you can rewrite your script with this expedient.

Craig Newman

Posted: **Sun Jun 17, 2012 11:42 pm**

Thanks. I think I've solved it. The problem seemed to be with the second repeat loop. If I tried any version of repeat other than 'repeat until,' the second loop took forever. Interestingly, 'repeat with' in the first loop was 1 tick faster than 'repeat for each '

Code: Select all

on mouseup
   
   #input original array
   put empty into tArray
   put empty into tFirst
   
   put specialFolderPath("documents") & "/IntegerArray.txt" into tFilePath
   put url ("file:" & tFilePath) into tArray
   
   put the ticks into temp
   get tArray
   put 1 into j
   repeat for  each line tLine in it
      --   repeat with i=1 to 100000
      repeat until j=100000
         add 1 to j
      end repeat
      add 1 to i
   end repeat
   answer the ticks - temp
end mouseUp

LiveCode Forums.

Super-Slow Repeat With...

Super-Slow Repeat With...

Re: Super-Slow Repeat With...

Re: Super-Slow Repeat With...