Programming Forums > Application Development > C

The Dark · Jan 9th, 2008, 6:07 PM

I don't think your wasting your time writing your own hashing, its a great learning experience and, as you said, more tailored algorithms can be a lot faster than a generic stl one. That may be critical if the running time is tight.

However, during the contest you are likely to be under time pressure for yourself as well as the code, so maybe using the stl would help you concentrate on the parts of the problem than can't be so easily solved.

Sane · Jan 9th, 2008, 6:22 PM

Yes, and I'm considering my research time valuable too. Where is it better spent? Learning C++'s STL (when I don't know C++...)? Or researching and learning about different data structures?

It's a tough call, because the time is very limited for the competition. But so is my knowledge of obscure data structures...

My thought right now is that the STL is not powerful enough to cut down implementation time enough, and still be worth the resulting execution time. Will someone challenge that statement? I'd like to hear arguments for both sides here.

rhish.franks · Feb 11th, 2008, 11:45 PM

Just want to ask, whether dynamic hashing is needed and linear probing has to be used?

Game_Ender · Feb 21st, 2008, 3:06 AM

This uses the fastest possible associative data structure: an array. That is all you need in this case because you are only dealing with numbers. It could use more memory than the map depending on the ratio of n to the max value of x. It runs in 40% the time of the STL map based version. (Both compiled with -O3)

 c Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_VAL 10000000
 
int main() {
    unsigned int n, x, size, mode=0;
    unsigned int* counts = calloc(MAX_VAL, sizeof(unsigned int));
 
    freopen("mode.in", "rt", stdin);
    scanf("%d\n", &n);
 
    while (n--) {
        scanf("%d\n", &x);
        if (( size = ++counts[x]) > mode) mode = size;
    }
    printf("%d\n", mode);
 
    return 0;
}
#include <stdio.h>
#include <stdlib.h>

#define MAX_VAL 10000000

int main() {
    unsigned int n, x, size, mode=0;
    unsigned int* counts = calloc(MAX_VAL, sizeof(unsigned int));
    
    freopen("mode.in", "rt", stdin);
    scanf("%d\n", &n);
    
    while (n--) {
        scanf("%d\n", &x);
        if (( size = ++counts[x]) > mode) mode = size;
    }
    printf("%d\n", mode);

    return 0;
}

Just up and learn the STL it will save you a *ton* of time. It will give you tested, debugged, and optimized data structures and algorithms. That is what you want when you are working under pressure. You don't want to lose because you made a stupid error in your linked list or binary tree, you want to be solving the problem. You can find plenty of STL tutorials on google.

Sane · Feb 21st, 2008, 4:47 AM

Well I've found that these years, the problems focus more on Dynamic Programming and Graph Theory than on Data Structures. In which case, the STL will do very little for me. I managed to do last year's Stage 1 competition, in Pure C, with about 40 lines of code for each question. So it's not as needy for standard libraries and pre-written code as I first thought. If I mess up a linked list, I shouldn't be writing the competition at all.

Game_Ender · Feb 21st, 2008, 10:00 PM

Well nobody is perfect and a line of code you don't have to write is a line of code you don't have to debug.

Kentski · Feb 22nd, 2008, 3:49 AM

hmmm im just new around the forums and still studying on programming.
so pls dont be bugged if il be asking some terms your using.

i hope everyone will be patient with me here. i just want to learn programming that much to give my grades a boost.

so what is STL by the way?

Ooble · Feb 22nd, 2008, 6:04 AM

The STL is C++'s Standard Template Library - a collection of lightweight but useful classes, templates, objects and functions you can use in your own programs. The beauty of it is that you can assume any C++ compiler will automatically have access to it.

Jan 9th, 2008, 6:07 PM	#11
The Dark Expert Programmer Join Date: Jun 2005 Posts: 824 Rep Power: 4	Re: Hashing In C I don't think your wasting your time writing your own hashing, its a great learning experience and, as you said, more tailored algorithms can be a lot faster than a generic stl one. That may be critical if the running time is tight. However, during the contest you are likely to be under time pressure for yourself as well as the code, so maybe using the stl would help you concentrate on the parts of the problem than can't be so easily solved.

Jan 9th, 2008, 6:22 PM	#12
Sane Programming Guru Join Date: Apr 2005 Posts: 1,827 Rep Power: 5	Re: Hashing In C Yes, and I'm considering my research time valuable too. Where is it better spent? Learning C++'s STL (when I don't know C++...)? Or researching and learning about different data structures? It's a tough call, because the time is very limited for the competition. But so is my knowledge of obscure data structures... My thought right now is that the STL is not powerful enough to cut down implementation time enough, and still be worth the resulting execution time. Will someone challenge that statement? I'd like to hear arguments for both sides here.

Feb 11th, 2008, 11:45 PM	#13
rhish.franks Programmer Join Date: Feb 2008 Location: India Posts: 58 Rep Power: 1	Re: Hashing In C Just want to ask, whether dynamic hashing is needed and linear probing has to be used?

Feb 21st, 2008, 3:06 AM	#14
Game_Ender Professional Programmer Join Date: May 2006 Location: Maryland, USA Posts: 306 Rep Power: 3	Re: Hashing In C This uses the fastest possible associative data structure: an array. That is all you need in this case because you are only dealing with numbers. It could use more memory than the map depending on the ratio of n to the max value of x. It runs in 40% the time of the STL map based version. (Both compiled with -O3) c Syntax (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> #define MAX_VAL 10000000 int main() { unsigned int n, x, size, mode=0; unsigned int* counts = calloc(MAX_VAL, sizeof(unsigned int)); freopen("mode.in", "rt", stdin); scanf("%d\n", &n); while (n--) { scanf("%d\n", &x); if (( size = ++counts[x]) > mode) mode = size; } printf("%d\n", mode); return 0; } #include <stdio.h> #include <stdlib.h> #define MAX_VAL 10000000 int main() { unsigned int n, x, size, mode=0; unsigned int* counts = calloc(MAX_VAL, sizeof(unsigned int)); freopen("mode.in", "rt", stdin); scanf("%d\n", &n); while (n--) { scanf("%d\n", &x); if (( size = ++counts[x]) > mode) mode = size; } printf("%d\n", mode); return 0; } Just up and learn the STL it will save you a ton of time. It will give you tested, debugged, and optimized data structures and algorithms. That is what you want when you are working under pressure. You don't want to lose because you made a stupid error in your linked list or binary tree, you want to be solving the problem. You can find plenty of STL tutorials on google. __________________ Robotics @ Maryland AUV Team - Software Lead Last edited by Game_Ender; Feb 21st, 2008 at 3:18 AM.

Feb 21st, 2008, 4:47 AM	#15
Sane Programming Guru Join Date: Apr 2005 Posts: 1,827 Rep Power: 5	Re: Hashing In C Well I've found that these years, the problems focus more on Dynamic Programming and Graph Theory than on Data Structures. In which case, the STL will do very little for me. I managed to do last year's Stage 1 competition, in Pure C, with about 40 lines of code for each question. So it's not as needy for standard libraries and pre-written code as I first thought. If I mess up a linked list, I shouldn't be writing the competition at all. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Feb 21st, 2008, 10:00 PM	#16
Game_Ender Professional Programmer Join Date: May 2006 Location: Maryland, USA Posts: 306 Rep Power: 3	Re: Hashing In C Well nobody is perfect and a line of code you don't have to write is a line of code you don't have to debug. __________________ Robotics @ Maryland AUV Team - Software Lead

Feb 22nd, 2008, 3:49 AM	#17
Kentski IM A N00B but WILL RISE! Join Date: Feb 2008 Location: Philippines Posts: 1 Rep Power: 0	Re: Hashing In C hmmm im just new around the forums and still studying on programming. so pls dont be bugged if il be asking some terms your using. i hope everyone will be patient with me here. i just want to learn programming that much to give my grades a boost. so what is STL by the way? __________________ IM JUST AN ORDINARY GUY WHO WANTS TO LEARN PROGRAMMING BUT NEEDS HELP FROM OTHER PROGRAMMERS TO MAKE ME ONE OF THE BEST!

Feb 22nd, 2008, 6:04 AM	#18
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Re: Hashing In C The STL is C++'s Standard Template Library - a collection of lightweight but useful classes, templates, objects and functions you can use in your own programs. The beauty of it is that you can assume any C++ compiler will automatically have access to it. __________________ Me :: You :: Them

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Custom Hashing Algorithms	Sane	C	21	Oct 16th, 2006 9:05 PM
MD5 hashing...	Un4given	C++	3	May 31st, 2005 6:51 PM
Hashing Collashing	mtanti	Coder's Corner Lounge	0	Apr 10th, 2005 11:29 AM

Programming Forums > Application Development > C

Hashing In C