Click here to Skip to main content
15,860,859 members
Please Sign up or sign in to vote.
3.00/5 (2 votes)
So I had to solve a problem :
given a file that contains N numbers I have to output the largest number that all numbers before it are less than it and all numbers after it are larger than it..if there is no such number the output is 'not found' !
so I wrote this code on pascal
program solar  ;
uses crt,dos,sysutils;

var i,k,m,j,min,max,pos:longint;
a,mi,ma:array [1..1000000] of longint;
filein,fileout:textfile;
        hours:word;
        minutes:word;
        seconds:word;
        sec100:word;
procedure startclock;
        begin
        gettime(hours,minutes,seconds,sec100);
        end;
procedure stopclock;
        var seconds_count:longint;
        c_hours:word;
        c_minutes:word;
        c_seconds:word;
        c_sec100:word;
        mil:longint;
        begin
        gettime(c_hours,c_minutes,c_seconds,c_sec100);
        seconds_count:=(c_seconds-seconds)* 100 +(c_minutes-minutes) * 6000 + (c_hours-hours)*360000;
        mil:=seconds_count+c_sec100-sec100;
        writeln(mil/100:4:2,' seconds');
        end;

  
Begin  
  startclock;
  assign(filein,'solar.in');  
  reset(filein);  
  readln(filein,m);  
  
  i:=0;  
  repeat  
  i:=i+1;  
  readln(filein,a[i]);  
  until eof(filein);  
  close(filein);  
  
  ma[1]:=a[1];  
      mi[m]:=a[m];  
     for i:=2 to m do  
  begin  
      if a[i]>ma[i-1] then  
        begin  
                        ma[i]:=a[i];  
        end  
      else  
        begin  
           ma[i]:=ma[i-1];  
        end;  
  end;  
  pos:=-1;  
  i:=m-1;  
  while i>=2 do  
  begin  
   if a[i]<mi[i+1] then  
       begin  
  
          mi[i]:=a[i];  
       end  
       else  
        begin  
         mi[i]:=mi[i+1];  
        end;  
              if (a[i]>ma[i-1])  and  (a[i]<mi[i+1]) then  
                begin  
                pos:=a[i];  
                break;  
                end;  
  i:=i-1;  
  
  
  end;  
  
  
  
    assign(fileout,'solar.out');  
       rewrite(fileout);  
    if pos=-1 then  
    writeln(fileout,'NOT FOUND')  
    else  
    writeln(fileout,pos);  
    close(fileout);  
stopclock();
readkey();
    end.  

when I run with an input of 80.000 numbersit takes 20 ms

but when I run this (c++) :

#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <ctime>


using namespace std;


int main()
{
	clock_t t1,t2;
	t1=clock();
	ifstream fin;ofstream fout;
	fin.open("solar.txt");
		int x;
		int arr[80000];int min[80000];int max[80000];
	
		int result(-1);

	fin>>x;
///	arr=new int[x-1];
//	min=new int[x-1];

//	max=new int[x-1];
	fin>>arr[0];
	max[0]=arr[0];
	for (int i=1;i<x;i++)
	{ int temp;fin>>temp;
	arr[i]=temp;
	if(temp>max[i-1]) max[i]=temp; else max[i]=max[i-1];

		}
	min[x-1]=arr[x-1];

		for (int i=x-2;i>=0;i--)
	{

		if(arr[i]<min[i+1]) min[i]=arr[i]; else min[i]=min[i+1];
	
		if(arr[i]<min[i+1] && arr[i]>max[i-1]) { result=arr[i];break;}
	}
		fout.open("solarout.txt");
		if(result==-1) fout<<"NOT FOUND"<<endl;
		else
			fout<<result<<endl;
		t2=clock();
		fin.close();fout.close();


		cout<<t2-t1<<endl;
		system("pause");


}

with the same input it takes 300 ms
also...I can't declare a static array with many cells on C++...if I try to declare a 1.000.000 size array like I did in pascal the program crashes...
my questions are :
1) why does this happen
2) why can't I declare big static arrays ?
3) are dynamic arrays (not linked lists vectors etc...just dynamic arrays declared using the NEW keyword ) slower than static ones (suppose I execute the same code)
4) Is there a more effective (effective=fast) way to solve this problem ?
what I do is : a) pass the numbers in an array, b) get the maximum number of a cell and the ones before it and save it an another same-sized array,c) get the minimum number of a cell and the ones after it,and check if the number in the cell meets the criteria...if it does I break the loop since i want the largest number and that means all other numbers before it are less than it...
thank you very much !
Posted
Updated 1-Mar-14 3:21am
v2
Comments
[no name] 1-Mar-14 19:57pm    
Your measurements are totally meaningless. The question basically says "I have two programs one in c++ and one in Pascal and they take different times to execute." This is really not a well thought out question.

The largest amount of time in your program is taken up by the input and output functions. So what you are measuring is that the input/output system of your pascal implementation is obviously much faster than the input/output system of your C implementation. That is not really surprising, because stream i/o has never been the fastest. And using other compilers and runtime systems might change the situation. You have not told us which compiler you are working with, so it is hard to comment.

As of the big static arrays, what have your tried? Could it be that you are still working with a 16-bit implementation?

And as for question (3): The access to arrays on the heap is not slower that the access to statically allocated arrays, or arrays allocated on the stack. Just their allocation / deallocation may take take up a little time.

And no, I don't see a faster method to solve this than with two linear scans.

If you want to do meaningful comparison between the two programming languages, you should limit the scope of your time measurement to the pure algorithm and exclude all i/o work.
 
Share this answer
 
v2
You asked:

2) why can't I declare big static arrays ?

1. Your two programs are not equivalent.
2. Your array definitions in the C++ code aren't static - all three are declared on the stack. That's a no-no for stuff this large for several reasons. If you want arrays that large, allocate them with operator new *or* put the 'static' keyword in front of all three definitions *or* move the array definitions outside of main().

When asking questions like this one, please provide information such as which operating system you're using and which compiler(s) you're using. You can provide more information, but less information won't get you the help you're looking for without a lecture ;-)

There are always more effective ways to implement *any* solution, but you haven't told us enough to help you in that area. You know what the task is and we don't.
 
Share this answer
 
Comments
EbolaHost 1-Mar-14 14:58pm    
I use Windows 7
c++ compiler:Visual c++ 2010
pascal compiler:FPC (free pascal compiler)
however I sent this program to someone who compiles it on linux with fpc again for pascal and gcc for c++

the task is this :given a list of numbers find the largest number A that all numbers before it are A
for example if I have this :
1
2
3
18
19
25
I must return number 19 because only the numbers 19 and 18 meet the criteria and 19 is the largest !

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900