LC stalls in a long process.

Anything beyond the basics in using the LiveCode language. Share your handlers, functions and magic here.

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller

Post Reply
dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9582
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

LC stalls in a long process.

Post by dunbarx » Wed Mar 18, 2015 4:57 pm

This was a challenge posted on the use-list. I bring it here to report a problem with LC and long processes. The OP wanted to find methods of determining, among a list of 26 populations, which combination would equal 100,000,000. I did it brute force, using a combinatorial handler in the MasterLibrary. But this handler never finished with 26 elements, so I kluged an even more brute-force gadget on top of that function, so that it needed only to work the first twelve, and then the remaining 14 were "added on".

Anyway, the thing works fine. In the abbreviated example here with 18 lines, to find the sum of 26978865,the answer is lines 1,9 and 18. This is still 262,000-odd combinations, and I chose it so that it finishes in just a short while. But beyond 22 lines, LC stalls and the handler quits. I wrote on the use-list:
Houston, we have an issue with LC.

I used the "combinatorial" function in the "MasterLibrary" for the 26 lines in the list, but the process was too slow. I made a kluge, so that a shorter call to that function was then processed by an even more brute-force routine. It works fine, but it also does not work.

LC stalls if the number of elements is greater than 22. I assume this is some sort of memory issue, unless LC just gets bored with the whole thing.

The following handlers pull an arbitrary value to test, and the gadget does indeed find the appropriate components.

Code: Select all

on mouseUp
   --FIELD 1 HAS THE LIST OF POPULATIONS
   --1,9,18 ARE AN ARBITRARY TARGET SUM
   -- THIS IS A SHORTER TEST FOR 18 LINES TO PROVE CONCEPT, AND FINISH IN A SHORT TIME

   get line 1 of fld 1 & "," & line 9 of fld 1 & "," & line 18 of fld 1
   put sum(it) into magicNumber --29335150
   
   put fld 1 into tList
   put combinatorial(12) into accum
   repeat with y = 13 to 18 --FAILS WITH A VALUE OF 26, THE ACTUAL NUMBER OF LINES IN THE LIST
      put accum into tempAccum
      repeat for each line tLine in tempAccum
         put tLine & comma & y & return after finalAccum
      end repeat
      put accum & return & finalAccum into accum
      put y after accum
      put "" into finalAccum
   end repeat
   
   repeat for each line tLine in accum
      repeat for each item tItem in tLine
         put line tItem of tList & "," after temp
      end repeat
      if sum(temp) = magicNumber then
         answer tLine
         exit to top
      else
         put "" into temp
      end if
   end repeat
end mouseUp

function combinatorial n 
   put the cursor into tCursor
   put 1 into tCursorCtr
   if n >= 15 then -- make sure you know what you're in for!
      answer n && "objects will result in" && (2^15 -1) && "subsets" with "Continue" or "Cancel"
      if it is "Cancel" then exit to top
   end if
   put 1 into subsetsVar -- initialize variable
   repeat until x = n -- this repeats (2^n - 2) times, which is one less than the numer of possible subsets
      Add 1 to tCursorCtr
      if tCursorCtr > 5000 then
         set the cursor to busy
         put 0 into tCursorCtr
      end if
      put the last line in subsetsVar into x -- each subset is used as input to compute the next subset
      put the number of items in x into noItems
      if item noItems of x = n then
         add 1 to item (noItems -1) of x -- increment 2nd to last item if last item = n
         delete the last item of x -- get rid of last item if it = n
         put return & x after subsetsVar -- add another subset to list of subsets
      else
         put ((item noItems of x) + 1) into item (noItems + 1) of x -- increment last item
         put return & x after subsetsVar -- add another subset to list of subsets
      end if
   end repeat
   set the cursor to tCursor
   return subsetsVar -- return the list of all possible subsets
end combinatorial
-- Population LIST:

18897109
12828837
9461105
6371773
5965343
5946800
5582170
5564635
5268860
4552402
4335391
4296250
4224851
4192887
3439809
3279833
3095313
2812896
2783243
2710489
2543482
2356285
2226009
2149127
2142508
2134411
I did not try this with an array, first to see if it is faster, but also to see if it can handle the larger list. Anyone have any insight?

Craig Newman
Last edited by dunbarx on Wed Mar 18, 2015 6:48 pm, edited 1 time in total.

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: LC stalls in a long process.

Post by FourthWorld » Wed Mar 18, 2015 5:50 pm

How will the output be used?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9582
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: LC stalls in a long process.

Post by dunbarx » Wed Mar 18, 2015 6:45 pm

Richard.

I think it is just an exercise. The OP said he did it in Python, and wanted to know what plans of attack might be considered in LC.

Craig

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: LC stalls in a long process.

Post by FourthWorld » Wed Mar 18, 2015 6:58 pm

Where is the original discussion?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9582
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: LC stalls in a long process.

Post by dunbarx » Wed Mar 18, 2015 6:59 pm

"how many different methods can we find for this question"

by fareastern23

Craig

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: LC stalls in a long process.

Post by FourthWorld » Wed Mar 18, 2015 7:20 pm

There is no link there, and that thread isn't in this month's archive. I suppose I could go hunting for it. but if you happen to know where it is that would be helpful. Thanks.

EDIT: Searching a couple different ways on Google finally got me to that thread in Nabble:
http://runtime-revolution.278305.n4.nab ... 90279.html

But oddly enough it doesn't appear in the master archive for the mailing list:
http://lists.runrev.com/pipermail/use-l ... /date.html

Seems not everyone got that email, including the listserve software itself. That might explain why there's been no post from Alex Tweedly with a one-line solution using arrays. :)
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9582
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: LC stalls in a long process.

Post by dunbarx » Wed Mar 18, 2015 10:35 pm

Richard.
That might explain why there's been no post from Alex Tweedly with a one-line solution using arrays
I bet there is. But my main concern is with the handler stall.

Craig

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: LC stalls in a long process.

Post by FourthWorld » Wed Mar 18, 2015 10:43 pm

I was going to run the script, but it expect a "field 1". What's in field 1? Is there a complete stack somewhere?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

WaltBrown
Posts: 466
Joined: Mon May 11, 2009 9:12 pm
Location: NE USA

Re: LC stalls in a long process.

Post by WaltBrown » Thu Mar 19, 2015 4:12 am

Craig

In combinatorial, you have "repeat until x = n" but later have "put the number of items in x into noItems" How does a list of items equaling an integer terminate a repeat loop? Should that be "repeat until the number of items in x = n"?

Walt
Walt Brown
Omnis traductor traditor

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9582
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: LC stalls in a long process.

Post by dunbarx » Thu Mar 19, 2015 5:23 am

@Richard, The "fld 1" in my handler is just to contain the 26 lines of numbers, The first line in that handler describes it.

@ Walt. I did not look deeply into the combinatorial handler, but it works fine. This comes from the "MasterLibrary" stack, a very nice repository of tools.

I will post the stack tomorrow, when I get back to work. If it matters at all, I believe that there is no combination of values that adds up to exactly 100,000,000. I had to make yet another kluge to figure that out, since I could not go beyond all the combinations of 23 elements. That kluge is in the stack.

I will also try a much simpler handler that deals with millions of lines in a variable, and try to see if that breaks as well, and in about the same places.

Craig

Post Reply

Return to “Talking LiveCode”