Recent

Author Topic: Breaking or continue from nested loop  (Read 5134 times)

Flaze07

  • New Member
  • *
  • Posts: 36
Breaking or continue from nested loop
« on: June 08, 2018, 04:09:56 pm »
I need to break or continue from nested loop, I found a thread on it before, http://forum.lazarus.freepascal.org/index.php?topic=30867.0 it suggest breaking into function or procedure. Well I am using the code for https://www.codechef.com/problems/SUBINC and so I need it to be fast. ( I used Dlang before pascal, and my code was too slow ), so is using flag or goto better ? or maybe breaking it into function or procedure don't have that much overhead ?
pascal is good for learning programming language

Handoko

  • Hero Member
  • *****
  • Posts: 5122
  • My goal: build my own game engine using Lazarus
Re: Breaking or continue from nested loop
« Reply #1 on: June 08, 2018, 04:21:13 pm »
Please show us your code, we may able to help you optimize it.

Programmers usually avoid using goto nowadays, because improper use of it can make the code hard to debug and maintain.

Flaze07

  • New Member
  • *
  • Posts: 36
Re: Breaking or continue from nested loop
« Reply #2 on: June 08, 2018, 04:30:40 pm »
well...I am not that done with the code.
oh well, I am going to show two codes, Dlang and Pascal
https://www.codechef.com/viewsolution/18828694 ( this is the Dlang )
https://gist.github.com/Flaze07/2d544f82b2f06c5f91e6410e8b27e4ad ( this is Pascal, I managed to somewhat convert it, but it is still not correct )
« Last Edit: June 08, 2018, 04:37:20 pm by Flaze07 »
pascal is good for learning programming language

Flaze07

  • New Member
  • *
  • Posts: 36
Re: Breaking or continue from nested loop
« Reply #3 on: June 08, 2018, 05:03:55 pm »
I managed to convert it good, but it turned out to be slower than Dlang counterpart https://www.codechef.com/viewsolution/18831781 oh well, time to try it out with good ol' C++, or maybe there's something in the pascal version that is slowing the whole thing down ?
pascal is good for learning programming language

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: Breaking or continue from nested loop
« Reply #4 on: June 08, 2018, 05:10:25 pm »
This is a multi level exit (or, GOTO) problem. The code exists the inner-for, but also aborts the outer-for body skipping the nascending statement.

FPC has no multilevel exit except "exit' that exits a whole procedure.
Code: Pascal  [Select][+][-]
  1. procedure doinner;
  2. begin
  3.   for inner ...
  4.       begin
  5.           if something then
  6.            exit
  7.         end;
  8. nAscending:=nAscending+1;
  9. end;
  10.  
  11. begin
  12.   for outer:=....
  13.           doinner;
  14. end;

Or you could try with goto.

Flaze07

  • New Member
  • *
  • Posts: 36
Re: Breaking or continue from nested loop
« Reply #5 on: June 08, 2018, 05:14:10 pm »
well, in the end I used flag...not sure if that is good, goto seems like a good approach too though, I don't know if I want to consider using procedure as using just one function that I made seems to make the Pascal program slower than Dlang's version of the same program
pascal is good for learning programming language

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: Breaking or continue from nested loop
« Reply #6 on: June 08, 2018, 05:22:22 pm »
Don't forget to flag it as inline, and configure the compiler (lazarus menus or cmdline) to inline

As why it is slower, if you translate foreign concepts into a different language, there is a chance that it is not the best option for that language.

It might also be unrelated parts (like stdio being slower by default, or memory management being more conservative, thus growing arrays in small increments is slower).

Benchmarking is an art. Once we had a fairly major issue with a large scale FPC user saying the code was slower than Kylix/Delphi. Turned out to be that differences in the speed of random() used in the tests that created the main difference, not the algorithm/codegeneration.
(FPC has a higher quality but slower random)
« Last Edit: June 08, 2018, 05:25:28 pm by marcov »

Flaze07

  • New Member
  • *
  • Posts: 36
Re: Breaking or continue from nested loop
« Reply #7 on: June 08, 2018, 05:27:49 pm »
yeah, I suppose you are right, might try what you suggested. Also, I am not that good with figuring out new ways of doing things, but then again, I don't really expect the pascal code to be faster than the Dlang code, I expect to be about as fast
pascal is good for learning programming language

Thaddy

  • Hero Member
  • *****
  • Posts: 14159
  • Probably until I exterminate Putin.
Re: Breaking or continue from nested loop
« Reply #8 on: June 08, 2018, 05:29:24 pm »
The procedural approach is achievable when using inlined functions that return a boolean instead of a procedure. Depending on the boolean return value you can do further breaks/continue on higher levels.
Another (or combined) approach is to use local procedures or functions (with e.g. an assignable typed constant in the main block). You can achieve the same effect.
But technically that is also flag.
Specialize a type, not a var.

Flaze07

  • New Member
  • *
  • Posts: 36
Re: Breaking or continue from nested loop
« Reply #9 on: June 08, 2018, 05:37:03 pm »
ok, thank you for all the help, it's been helpful
pascal is good for learning programming language

ASerge

  • Hero Member
  • *****
  • Posts: 2212
Re: Breaking or continue from nested loop
« Reply #10 on: June 09, 2018, 02:17:54 pm »
well...I am not that done with the code.
oh well, I am going to show two codes, Dlang and Pascal
https://www.codechef.com/viewsolution/18828694 ( this is the Dlang )
https://gist.github.com/Flaze07/2d544f82b2f06c5f91e6410e8b27e4ad ( this is Pascal, I managed to somewhat convert it, but it is still not correct )
1. Code in Dlang  contains error:
Code: C  [Select][+][-]
  1. secondOuter : for( int j = i + 1; j <= arrLength; ++j ); // must be < allLength
2. There is no need to copy each time to a separate array for verification. It is better to do it on it, just pointing out from and to.
3. In the main question I agree with Thaddy - it is better to use a separate function, you can mark it as inline.
4. And most importantly: your solves the problem WRONG! Index j should start from i, not from i +1.
Work sample:
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3. {$MODE OBJFPC}
  4.  
  5. type
  6.   TArray = array of Cardinal;
  7.  
  8. function IsAscending(const A: TArray; AFrom, ATo: Integer): Boolean;
  9. var
  10.   i: Integer;
  11. begin
  12.   for i := AFrom + 1 to ATo do
  13.     if A[i - 1] > A[i] then
  14.       Exit(False);
  15.   Result := True;
  16. end;
  17.  
  18. function ReadArray(out A: TArray): Boolean;
  19. var
  20.   ArrLength, i: Integer;
  21. begin
  22.   Readln(ArrLength);
  23.   if ArrLength <= 0 then
  24.     Exit(False);
  25.   SetLength(A, ArrLength);
  26.   for i := Low(A) to High(A) do
  27.     Read(A[i]);
  28.   Readln; // Skip end of line
  29.   Result := True;
  30. end;
  31.  
  32. procedure DoTest;
  33. var
  34.   i, j: Integer;
  35.   Arr: TArray;
  36.   CountOfAscendings: Integer;
  37. begin
  38.   if not ReadArray(Arr) then
  39.   begin
  40.     Writeln('Bad array length');
  41.     Exit;
  42.   end;
  43.   CountOfAscendings := 0;
  44.   for i := Low(Arr) to High(Arr) do
  45.   begin
  46.     for j := i to High(Arr) do
  47.       if IsAscending(Arr, i, j) then
  48.         Inc(CountOfAscendings);
  49.   end;
  50.   Writeln(CountOfAscendings);
  51. end;
  52.  
  53. var
  54.   TestsCount: Cardinal;
  55. begin
  56.   Readln(TestsCount);
  57.   while TestsCount > 0 do
  58.   begin
  59.     DoTest;
  60.     Dec(TestsCount);
  61.   end;
  62.   Readln;
  63. end.

Thaddy

  • Hero Member
  • *****
  • Posts: 14159
  • Probably until I exterminate Putin.
Re: Breaking or continue from nested loop
« Reply #11 on: June 09, 2018, 02:24:46 pm »
@ASerge
It is always nice to see compilable examples.... compliments.  :D
Specialize a type, not a var.

 

TinyPortal © 2005-2018