Computer Science Canada

structs :shock:

Author:  bugzpodder [ Sat Mar 26, 2005 1:19 pm ]
Post subject:  structs :shock:

code:
struct BigInteger{
       
        int sz,start,maxsize, *arr;
        BigInteger(){start=0;maxsize=1;sz=1; arr=new int[1];}
             BigInteger(int val){BigInteger(); arr[0]=val;}
}


I dont know what the heck the problem is with the code above, but whenever I call BigInteger using the second constructor, sz is always 0!!

this can be seen from:

code:
#include<iostream>
using namespace std;
struct BigInteger{
       
        int sz,start,maxsize, *arr;
        BigInteger(){start=0;maxsize=1;sz=1; arr=new int[1]; cout<<sz<<endl;}
             BigInteger(int val){BigInteger(); cout<<sz<<endl; arr[0]=val;}
};

int main(){
        BigInteger u(20);
        return 0;

}

in which you'll see a 1 and 0 outputted. why on earth is that happening?


And also, for something like:

code:

pair<BigInteger,int> div(BigInteger &v1, int v2){
             .......
        cout<<ret.first.arr[0]<<endl;
        return ret;
}
            ....
        p=div(v,1e9);  //although 1e9 is a double rather than an int, it is not causing the problmes
        cout<<p.first.arr[0]<<endl;


and this produce totally different outputs!!!
I am completely lost as to whats going on...

Author:  rizzix [ Sat Mar 26, 2005 1:34 pm ]
Post subject: 

try:
c++:
class BigInteger {
   protected:
   int sz,start,maxsize, *arr;
   
    public:
    BigInteger(){
         start=0;
         maxsize=1;
         sz=1;
          arr=new int[1];
     }
   
    BigInteger(int val): BigInteger() {
          arr[0]=val;
     }
};

Author:  wtd [ Sat Mar 26, 2005 1:40 pm ]
Post subject: 

First thing's first. You should be using proper constructor syntax, and since you're dynamically allocating memory, you should have a destructor.

c++:
struct BigInteger
{
   int sz,start,maxsize, *arr;

   BigInteger()
   : start(0)
   , maxsize(1)
   , sz(1)
   , arr(new int[1])
   { }

   BigInteger(int val)
   : start(0)
   , maxsize(1)
   , sz(1)
   , arr(new int[1])
   {
      arr[0] = val;
   }

   ~BigInteger()
   {
      delete [] arr;
   }
};

Author:  rizzix [ Sat Mar 26, 2005 1:46 pm ]
Post subject: 

hmmm is that syntax C friendly?

Author:  bugzpodder [ Sat Mar 26, 2005 1:47 pm ]
Post subject: 

i do have a destructor, but didnt bother to post it. my full code is 200 lines long. Okay, so a class probably works, but what the heck is wrong with struct?

Author:  wtd [ Sat Mar 26, 2005 1:48 pm ]
Post subject: 

None of this is valid C. It is, however, perfectly valid C++ code.

Author:  bugzpodder [ Sat Mar 26, 2005 1:49 pm ]
Post subject: 

hmm interesting, never seen code like that before wtd.

and the second problem is... well here is the full code (first problem was fixed): funny things are happening in toString (outputs dont match), which calls div

no clue why it is happening

code:

#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;


#define pb push_back            //pushes an element in the back
#define pf push_front           //pushes an element in the front

#define fe first                //first element of a pair container
#define se second               //second element of a pair container
#define len length()            //length of a string

using namespace std;

typedef unsigned int uint;      //32-bit unsigned int
typedef long long ll;           //64-bit signed long long
typedef unsigned long long ull; //64-bit unsigned long long

struct BigInteger{
       
        int sz,start,maxsize;
        uint *arr;
        BigInteger(int val=0){start=0;maxsize=1;sz=1; arr=new uint[1];arr[0]=val;}
        ~BigInteger(){delete [] arr;}
       
        int operator[](int i) {return arr[(start+i)%maxsize];}
       
        void resize(int size){
                if (sz>=size) return;
                uint *oldarr=arr;
                arr=new uint[size];
                for (int i=0;i<sz;i++) arr[i]=oldarr[(start+i)%maxsize];
                delete [] oldarr;
                start=0; maxsize=size;
               
        }
        void pb(uint v){
                if (sz==maxsize) resize(maxsize*2);
                arr[(start+(sz++))%maxsize]=v;
        }
        void pop_back(){
                if (sz>0) sz--;
        }
        void pf(uint v){
                if (sz==maxsize) resize(maxsize*2);
                sz++; start=(start+maxsize-1)%maxsize;
                arr[start]=v;
        }

};


typedef pair<bool,BigInteger> bigint;   //signed BigInt
typedef pair<BigInteger,uint> divtype;  //type returned by division



BigInteger add(BigInteger v1, BigInteger v2){
  bool carry=false;
  int i; ull v;BigInteger ret;
  for (i=0;i<v1.sz || i<v2.sz;i++){
    v=(ull)(i<v1.sz?v1[i]:0)+(i<v2.sz?v2[i]:0)+carry;
    carry=v>=(1ULL<<32);
    ret.pb((uint)v);   
  }
  if (carry) ret.pb(1);
  return ret;
}

BigInteger sub(BigInteger v1, BigInteger v2){
  bool carry=false;
  int i; ull v;BigInteger ret;
  for (i=0;i<v1.sz || i<v2.sz;i++){
    v=(ull)(i<v1.sz?v1[i]:0)-(i<v2.sz?v2[i]:0)-carry;
    carry=v>=(1ULL<<32);
   
    ret.pb((uint)v);   
  }
  if (carry) ret.pb(1);
  return ret;
}



divtype div(BigInteger &v1, uint v2){
        int i; ull v=0;
        divtype ret; ret.fe.sz=0;
        for (i=v1.sz-1;i>=0;i--){
                v=v*(1ULL<<32)+v1[i];      
                ret.fe.pf(v/v2);
                v%=v2;
        }
        if (ret.fe.sz>1 && ret.fe[ret.fe.sz-1]==0) ret.fe.pop_back();
        ret.se=v;
        cout<<ret.fe.start<<' '<<ret.fe[0]<<' '<<ret.fe.sz<<' '<<ret.se<<endl;
        return ret;
}

BigInteger convert(uint val){
        BigInteger ret;ret.pb(val); return ret;
}

int compareTo(BigInteger &v1, BigInteger &v2){
        if (v1.sz!=v2.sz) return v1.sz<v2.sz?1:-1;
        for (int i=v1.sz-1;i>=0;i--)
        if (v1[i]!=v2[i]) return v1[i]<v2[i]?1:-1;
        return 0;
}

string toString(BigInteger v){
  if (v.sz==1 && v[0]==0) return "0";
  divtype p; string ret;
  BigInteger zero(0);
  int i;
 
  //while(compareTo(v,zero)!=0){
        p=div(v,1e9);
        v=p.fe;
        cout<<v.start<<' '<<v[0]<<' '<<v.sz<<' '<<p.se<<endl;
        for (i=0;i<9;i++){ret+=p.se%10+'0';p.se/=10;}
  //}
  reverse(ret.begin(),ret.end());
  for (i=0;i<ret.len-1 && ret[i]=='0';i++);
  return ret.substr(i);
}




BigInteger num[5001];
int main(){
        BigInteger u(50);
        cout<<u.sz<<endl;
        u.resize(20);
        cout<<toString(u)<<endl;
        cout<<u[0]<<endl;
return 0;
}

Author:  bugzpodder [ Sat Mar 26, 2005 1:56 pm ]
Post subject: 

and i still dont get what the heck is wrong with what I did (in my first post) the second constructor calls the first, and it IS getting called, so it seems perfectly fine

Author:  wtd [ Sat Mar 26, 2005 2:04 pm ]
Post subject: 

Do NOT do I/O in a function like that.

Author:  bugzpodder [ Sat Mar 26, 2005 2:04 pm ]
Post subject: 

??? err?? why not? its just debugging output? my code is getting SIGFPE (division/mod by 0) and SIGSEV's... these outputs pinpointed where the error is... I was wondering why the hell my code is getting SIGFPE until i found out that the variable sz mysteriously changed its value to 0 when the second constructor is called (so i made everything into one constructor... still not knowing why I cant keep two constructors like what I did before) and then I am getting an infinite loop in toString, which it turns out that the return value from div is different than the value I am getting in toString?!?! I am completely lost as to why this is happening...

anyhow i think the problem is with structs since the code has being tested if you remove the struct and use typedef deque<uint> BigInteger;

unfortunately deque is much slower... Sad and I dont get why structs are giving me these resuts.

Author:  wtd [ Sat Mar 26, 2005 2:27 pm ]
Post subject: 

Because I/O is not meat to go into functions designed purely to output a new value. It's just bad. First make your changes, then check to see if things are as you expected. If you feel the need to do this inside a function, it's a good sign that function is doing too much.

Anyway, a sane basis for such work:

c++:
#include <vector>

template <typename T>
class LimitedVector : public std::vector<T>
{
   protected:
      size_t max_size;
   public:
      LimitedVector() : std::vector<T>() { }
      LimitedVector(size_t s) : std::vector<T>(s) { }   
      LimitedVector(size_t s, const T& v) : std::vector<T>(s, v) { }
      ~LimitedVector() { delete this; }

      void resize(size_t new_size)
      {
         if (new_size <= max_size)
            std::vector<T>::resize(new_size);
      }
};

class BigInteger : public LimitedVector<unsigned int>
{
   public:
      BigInteger() : LimitedVector<unsigned int>(1, *new unsigned int) { }
      BigInteger(unsigned int init_val)
      : LimitedVector<unsigned int>(1, *new unsigned int)
      {
         at(0) = init_val;
      }
      ~BigInteger() { delete this; }
};

Author:  rizzix [ Sat Mar 26, 2005 2:37 pm ]
Post subject: 

bugzpodder wrote:
i do have a destructor, but didnt bother to post it. my full code is 200 lines long. Okay, so a class probably works, but what the heck is wrong with struct?


its because u have to pay close attention to the Consturctor() : initialization {} statements

although it appears to be two ways to intialize members of a class/struct in c++. there really is only one recognized official way. i suggest u create get/set accessor/mutators or simply define variables protected, for this to work out well.

also note Constructor(some_args) : Consturct() {} is the only working way to go about with calling previously defined constructs including the parent class' constuctor in c++. that is you cannot call the constuctor within the {} block of another constrcutor. although this should work, its does not always work well with all compilers.

although in D, Java, and a hell a lot of other languages, you dont have such annoying complications.

Author:  bugzpodder [ Sat Mar 26, 2005 2:39 pm ]
Post subject: 

wtd, One of my original plans is to push performance, since there is just too much overhead in vectors.

rizzix, ic, well it seemed to work :S heh

Author:  rizzix [ Sat Mar 26, 2005 2:46 pm ]
Post subject: 

the fist most common way in most languages:
code:
class BigInteger {
   protected:
   int sz,start,maxsize, *arr;
   
   public:
   BigInteger(){start=0;maxsize=1;sz=1; arr=new int[1];}
};


the second the more c++ specific way"
code:
class BigInteger {
   protected:
   int sz,start,maxsize, *arr;
   
   public:
   BigInteger() : start(0), maxsize(1), sz(1), arr(new int[1]) {}
};


Note that if you want to initialzise members of class using a previously defined consructor always use the second method:
code:
BigInteger(int val) : BigInteger() {arr[0]=val;}


you may if you wish, initialize member of the class directly using the second way, although the first way will work just as well.

Author:  wtd [ Sat Mar 26, 2005 2:48 pm ]
Post subject: 

bugzpodder wrote:
wtd, One of my original plans is to push performance, since there is just too much overhead in vectors.


I can guarantee std::vector will be faster than what you can cook up. That's not to insult your skills. but a lot of people have invested a lot of time in making the STL fast.

Also, your use of macros, and lack of spacing in your code will not make it any faster.

Author:  bugzpodder [ Sat Mar 26, 2005 3:01 pm ]
Post subject: 

well, i am not looking for minimal optimizations. I am inclined to believe STL vector is slower since it is not optimized for any specific type and plus of the overhead it carries. At least from my experience of the other STL wrappers they are slow as hell (deque, queue, list, stack, etc)
But seeing how struct is not working out, i probably have no other choice.

Author:  bugzpodder [ Sat Mar 26, 2005 3:11 pm ]
Post subject: 

i found some benchmarking results on the net. without compiler optimization flags, arrays are definitely >>>>> faster than std::vectors
with some optimzation flags, they are about the same

Author:  wtd [ Sat Mar 26, 2005 3:24 pm ]
Post subject: 

Arrays are also dangerous, and inconvenient. So much of what you've written the STL would give you for free.

Author:  bugzpodder [ Sat Mar 26, 2005 3:25 pm ]
Post subject: 

rizzix wrote:

Note that if you want to initialzise members of class using a previously defined consructor always use the second method:
code:
BigInteger(int val) : BigInteger() {arr[0]=val;}




the compiler (DJGPP) refuses to accept this code :S
'BigInteger' is not immediate base case of 'BigInteger'

Author:  bugzpodder [ Sat Mar 26, 2005 3:27 pm ]
Post subject: 

wtd wrote:
Arrays are also dangerous, and inconvenient. So much of what you've written the STL would give you for free.

correct, but if you see some of the hardcore programmers who construct complete C programs in asm by hand in order to gain performance, you'll see that what I am trying in nothing. meh I guess i'll stick to vectors.

Author:  wtd [ Sat Mar 26, 2005 4:10 pm ]
Post subject: 

bugzpodder wrote:
wtd wrote:
Arrays are also dangerous, and inconvenient. So much of what you've written the STL would give you for free.

correct, but if you see some of the hardcore programmers who construct complete C programs in asm by hand in order to gain performance, you'll see that what I am trying in nothing. meh I guess i'll stick to vectors.


Yes, they're using C. C doesn't provide them with these conveniences, so they're not losing anything by not using the STL. Smile

code:
if (C == CPP) pigs_fly();


As for your earlier comment... you can only use member variable names and immediate base class names.

Author:  rizzix [ Sat Mar 26, 2005 4:10 pm ]
Post subject: 

bugzpodder wrote:
the compiler (DJGPP) refuses to accept this code :S
'BigInteger' is not immediate base case of 'BigInteger'


oh, well then in that case, i take it back, only use it (when it comes to constructors) for intializing the base class' members through the base class's constructors.

(strange though, i wonder what is the ansi standard, i thought what i mentioned was pretty much ansi c++, but i could definitely be wrong)

Author:  bugzpodder [ Sat Mar 26, 2005 4:17 pm ]
Post subject: 

everything works as expected using vectors... must be array's fault :S

Author:  bugzpodder [ Sat Mar 26, 2005 4:49 pm ]
Post subject: 

seems vectors is still too slow




USACO Training Grader Results for [bugz_po1]
12 users online
BGR/2 BRA/2 CAN/2 ITA/1 LTU/1 POL/1 POR/1 RUS/1 USA/1



TASK: buylow
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1 OK [0.01 secs]
Test 2 OK [0.01 secs]
Test 3 OK [0.01 secs]
Test 4 OK [0 secs]
Test 5 OK [0.02 secs]
Test 6 OK [0.09 secs]
Test 7 OK [0.05 secs]
Test 8 OK [0.12 secs]
Test 9 OK [0.19 secs]
Execution error: Your program (`buylow') used more than the allotted
runtime of 1 seconds (it ended or was stopped at 1.04 seconds) when
presented with test case 10, shown below.

----- Test Case 10 ------
5000
4718 18 19887 17551 9375 3376 7966 5372 5230 15044
16023 5255 15160 8877 11961 15814 13865 2128 4785 9055
18223 19393 11291 1343 7697 6945 1423 6721 2520 7650
14203 7235 7666 14088 4785 17042 17466 12754 2417 2700
7803 18447 7963 2971 7334 19934 18797 1212 2076 3597
10282 316 3007 1591 1679 10724 8558 3124 17469 11102
10800 11698 18365 18494 5816 3180 15567 3314 15967 18019
6050 3807 16504 14052 6817 3878 14028 5657 5133 16148
9299 15462 16512 12354 17102 18241 3130 5713 1418 654
16871 12274 12410 15294 10828 18286 18535 6458 1664 14567
4543 7781 18441 1115 1902 5329 5065 16002 11059 10273
12226 434 5812 8817 12868 2995 7139 16081 8791 8642
16820 5748 1003 9319 1132 11922 7697 19759 18473 9455
14421 3112 17334 12961 4327 19337 18391 9494 15443 9554
13 7776 10096 5793 16702 3075 8900 3953 19269 17806
12710 16206 3672 13832 5644 4924 5875 13463 4807 4473
3044 19354 7712 506 12445 12169 141 10968 1797 15552
658 1806 3465 10892 7739 307 14108 16782 4404 13522
14733 17260 9875 18553 11242 15669 3629 17270 9285 8590
1898 12486 8102 9768 13151 707 2099 13288 11839 4060
9006 12663 6034 12639 3725 13943 13117 18005 10898 17695
11702 5808 15133 1756 4541 6556 17606 8352 4009 7076
17127 6093 19749 5418 16051 13091 6316 18342 6573 18349
2598 15775 11210 8830 8613 15135 2975 1933 13344 14078
74 5252 93 15176 7218 4844 1943 5036 13410 6166
12328 10754 12477 12296 16391 8748 5608 2930 7314 12406
1505 10138 8408 12943 19197 17252 8309 2405 19419 1887
16718 19490 7377 17049 14905 14835 2135 17090 115 15789
3502 12690 6790 16227 5235 3432 5227 11096 6615 12795
3757 8376 3190 12424 1578 2648 9937 10150 5317 9621
12303 2301 9378 252 19620 4553 15056 2028 1917 15445
18092 5696 8412 5161 2202 13928 8875 7712 5307 15774
792 9350 4438 4271 2063 6307 7211 12293 16750 12822
2210 9350 15420 11886 9598 15341 16741 4956 17672 18963
707 16071 4966 9428 1542 7479 3667 10729 15504 9288
6818 16613 18956 11574 1203 1340 18203 8737 13957 15277
1884 16493 4955 17633 8708 14883 13305 5782 172 11312
5080 1215 7720 10384 10982 9602 18205 14992 674 14053
4626 7839 11013 3930 147 12567 5622 18318 1657 322
13951 3897 16783 19264 1890 5852 14508 15557 11997 15045
... [and more] ...
----------------------------
Read this if your program works on your computer but not the grader. Do not write a letter to the coaches until you have tried these techniques!

Thanks for your submission!


Problem Statement for buylow | USACO Gateway | Comment or Question


--------------------------------------------------------------------------------

Submit a file:
Be sure to include "LANG: C++", "LANG: JAVA", or whatever is appropriate.
EXPERIMENTAL GRADER -- Report *any* problem or unexpected result to Rob Kolstad

Author:  bugzpodder [ Sat Mar 26, 2005 5:10 pm ]
Post subject: 

passed the last test by adding & to the first variable of my add function. btw wtd, I tried to delete the macro and it actually up-ed my runtime to 10ms more.

Author:  wtd [ Sat Mar 26, 2005 5:13 pm ]
Post subject: 

Perhaps the compiler you're using is simply bad. If you're using Windows, why not use a recent version of MinGW rather than DJGPP?

Author:  wtd [ Sat Mar 26, 2005 5:15 pm ]
Post subject: 

As for & making a difference, yes, it will. C++, by default, uses pass-by-value arguments. The entire value passed in will be copied. This consumes memory and CPU time. Adding & to the type specifies a reference, and no copy is made.

Additionally, specifying const references where possible may yield performance gains.

Author:  bugzpodder [ Sun Mar 27, 2005 12:16 pm ]
Post subject: 

meh, I am using the judge's compiler.

someone told me exactly whats happening regarding my very first post. Its probably what you guys wanted to say, but he made it clearer to me.
Quote:

in C++ it is imposible to call a constructor from another one. What actually happens here is that you construct a temprary BigInteger object, that is immidiatly destroyed afterwards.

For the second problem: Have you implemented a copy constructor, assignment operator and destructor? If you don't actually allocate a new array, the old array may be destroyed by the time you try to use it.


time to benchmark if structs are faster than vectors Very Happy


: