structs :shock:

[bugzpodder]

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.

[bugzpodder]

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

[wtd]

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

[bugzpodder]

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'

[bugzpodder]

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.

[wtd]

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.

code:

if (C == CPP) pigs_fly();

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

[rizzix]

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)

[bugzpodder]

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

[bugzpodder]

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

[bugzpodder]

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.

[wtd]

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?

[wtd]

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.

[bugzpodder]

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