Trip Report: Front End Web Guy On C

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Trip Report: Front End Web Guy On C

Hegel: Dec 17, 2009

Code bootcamp grad here with around 3 months of experience hacking css/javascript with an occasional couple of hours on python when I need to do something and no one else has gotten to it yet.

I have imposter syndrome really bad so on the weekends I try to write algorithms in C. This week was randomized array search with what should be an average running time of O(n) (taken from a coursera algos course).

Here's how it's going:

code:

void testPart() {
    int data[] = {5, 2, 4, 1, 7};
    int piv = 2;
    int pivot = partition(data, 0, 5, 2);
    int i = 0;
    while (i < 5) {
        if (data[i] == 4) {
            break;
        }
        i++;
    }
    int j = 0;
    while (j < 5) {
        if (data[j] == 7) {
            break;
        }
        j++;
    }
    int z = 0;
    while (z < 5) {
        if (data[z] == 5) {
            break;
        }
        z++;
    }

    assert (z > i);
    assert(j > i);
    assert(pivot == 2);

    printf("done\n");
}

int partition(int arr[], int start, int end, int pivot) {
    assert(*arr >= 0);
    assert(*(arr + pivot) >= 0);
    swap(arr + start, arr + pivot);

    int i = start;
    int k = start + 1;

    while (k <= end)  {
       if (arr[k] < arr[i]) {
           swap(arr + k, arr + i + 1);
           swap(arr + i + 1, arr + i);
           i++;
       }
       k++;
    }

    return i;
}

you can view the whole thing here: https://github.com/Axylos/randSel
The Makefile is a little hectic, but i guess that's what happens when you're trying to figure out make? I tend to use make and other basic unix stuff quite a bit at work, so it pays to get more familiar with these basic utilities.

Given that background, am I doing things that are obviously insane? The code could definitely be cleaner, but at least from a first approximation, how does it rank against a first or second yr CS guy?

# ? Nov 24, 2014 05:13

Adbot: ADBOT LOVES YOU

# ? Apr 26, 2024 23:00

sensual donkey punching: Mar 13, 2004; =); Nap Ghost

replace dem while loops with a find the element function

(replace dat test with randomized property test)

# ? Nov 24, 2014 05:31

sudonim: Oct 6, 2005

Algorithm aside, why C instead of C++? It has a lot of convenient features C doesn't, like objects, iterators, and even the ability to define variables whenever the hell you want, not just at the top of the function like C. If you're scared of all the fancy C++ features like polymorphism and template meta-programming, you don't have to use those (in my experience, most people use them badly).

Unless your job relies on running algorithms, I wouldn't worry about them unless you enjoy puzzling them out. A lot of CS guys use them as dick-waving contests but then turn around and don't know much about actual computer functions like threading or I/O.

Also, if you want to share code, there are sites where you can paste code in your browser and share a link with someone, where they can examine and even run the code. Try http://cpp.sh/

# ? Jan 8, 2015 23:39

ExcessBLarg!: Sep 1, 2001

Here's a few comments:

Avoid hardcoding the length of the array ("while (i < 5)") as it breaks if you add or remove numbers from the array. You can use the idiom ("sizeof(data)/sizeof(data[0])") to determine the number of elements in the array, which in this case is 5. I personally like to define a macro to simplify that:

code:

#define numof(a) (sizeof(a)/sizeof(a[0]))
...
while (i < numof(data))

The caveat is that sizeof (and numof) is only useful in the function where the array is first defined. As soon as you pass the array into another function, it actually degrades into a pointer and the size of the array is lost. This is why most functions require you to explicitly pass in the size of the array, or alternatively, the array contains a sentinel element at the end that the function can use internally to determine when the array stops.

You may also want to familiarize yourself with the "for (initializer; condition; increment)" method of writing loops as they're very idiomatic and would simplify some of your while loops. For example, in C99 the first loop could be written:

code:

for (int i = 0; i < numof(data); i++) {
    if (data[i] == 4) {
        break;
    }
}

Third, while pointer arithmetic and array indexing are equivalent operations, it's generally preferred to use array indexing notation when accessing items from a previously defined array. Thus, the partition function would probably more commonly be written as:

code:

int partition(int arr[], int start, int end, int pivot) {
    assert(arr[0] >= 0);
    assert(arr[pivot] >= 0);
    swap(&arr[start], &arr[pivot]);
    ...
}

ExcessBLarg! fucked around with this message at 01:06 on Jan 9, 2015

# ? Jan 9, 2015 01:03

ExcessBLarg!: Sep 1, 2001

sudonim posted:

Algorithm aside, why C instead of C++?

Because he wants to learn C? I mean, C++ is cool and all, but C itself is a worthwhile language to learn both because it's relatively simple (in terms of the scope of the language) and extremely easy to get oneself into trouble. It's also very relevant for anyone interested in systems programming.

Also, the above examples could just as well be C++. With what he's doing, the two languages are nearly equivalent anyways.

sudonim posted:

Unless your job relies on running algorithms, I wouldn't worry about them unless you enjoy puzzling them out. A lot of CS guys use them as dick-waving contests but then turn around and don't know much about actual computer functions like threading or I/O.

I have to disagree. It's important to have knowledge of common algorithms, big-O notation, and generally be aware of when/why code is performant and when it's not.

A common weakness of code bootcamp folks is they don't have the same background knowledge of algorithms and data structures that are commonly taught in sophomore CS courses. The result is that when faced with a problem of moderate complexity they may end up implementing an unnecessarily complicated or inefficient due to not knowing better. So these kinds of thought exercises are entirely appropriate to fill in for what background knowledge may be missing.

# ? Jan 9, 2015 01:14

Pollyanna: Mar 5, 2005; Milk's on them.

ExcessBLarg! posted:

A common weakness of code bootcamp folks is they don't have the same background knowledge of algorithms and data structures that are commonly taught in sophomore CS courses. The result is that when faced with a problem of moderate complexity they may end up implementing an unnecessarily complicated or inefficient due to not knowing better. So these kinds of thought exercises are entirely appropriate to fill in for what background knowledge may be missing.

My bootcamp recognized this flaw and attempts to fix it by fitting in a section on algorithms and data structures. I still feel like I need a bit more teaching on the subject though, because I'm really picky about doing things the "best" way (which I realize doesn't usually exist). Anyway my point is we're not all CS-retarded :v:

# ? Jan 10, 2015 18:44

BlackMK4: Aug 23, 2006; wat.; Megamarm

Is there a recommended book on Amazon about data structures and algorithms?

# ? Jan 10, 2015 21:43

evensevenone: May 12, 2001; Glass is a solid.

Don't gently caress around, get Cormen: http://www.amazon.com/gp/product/02...2BGKD5BGR3QQPD6

The only issue I have is that it's a bit too comprehensive (so it can be tough to tell what the most important sections are). Most college classes cover only a few chapters. Luckily the MIT Intro to Algorithms class uses this book, so their syllabus is a good place to start.

# ? Jan 11, 2015 00:00

Adbot: ADBOT LOVES YOU

# ? Apr 26, 2024 23:00

BlackMK4: Aug 23, 2006; wat.; Megamarm

evensevenone posted:

Don't gently caress around, get Cormen: http://www.amazon.com/gp/product/02...2BGKD5BGR3QQPD6

The only issue I have is that it's a bit too comprehensive (so it can be tough to tell what the most important sections are). Most college classes cover only a few chapters. Luckily the MIT Intro to Algorithms class uses this book, so their syllabus is a good place to start.

Done. Thank you much

# ? Jan 11, 2015 09:58

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Trip Report: Front End Web Guy On C