• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Programming |OT| C is better than C++! No, C++ is better than C

Big Chungus

Member
i really wan to apply for programming jobs but im afraid i wont be good enough...

i did pretty well at school, always finished my programming assignments early and got good marks but i got "stage fright" whenever i worked with a partner...

anyone else feel this way?
 

Water

Member
I guess I'm looking at this more from an engineering perspective than a CS one. It is reasonable to say that your chosen hashing algorithm will not place all elements into the same index of the backing array. The solution I proposed is concise and eliminates the fixed length hindrance.
Conflicts are not the issue. Even with perfect hashing, the hashmap cannot grow larger in O(1). The correct solution to the problem is fundamentally different. It has a very nice property that a hashmap does not. Major hint:
In addition to the properties I named as the goals of the puzzle, the structure that solves the problem is also O(1) to initialize, and O(1) to resize during reset! The structure automatically has those properties, when the implementation language offers access to raw memory; in a managed environment it's impossible to create or resize any data structure of size N in O(1) because the system always zeroes out the memory before it's handed to the application.
 
i really wan to apply for programming jobs but im afraid i wont be good enough...

i did pretty well at school, always finished my programming assignments early and got good marks but i got "stage fright" whenever i worked with a partner...

anyone else feel this way?

I think it's natural to get a little nervous when working with people. Like everything else, practice, practice, practice!

Chat with other coders, practice white board sessions on your own, try explaining a bit of your code to a buddy or even to yourself.
 

Water

Member
Didn't know that hash maps are O(n) to set. I could have sworn they were O(1).
They are O(1) to read and write if the hashmap has previously been initialized to some specific size large enough for all the data, and the hash function is perfect for the data, meaning no conflicts will occur.
But that initialization required for an arbitrary size hashmap is not O(1).
 

Water

Member
Wouldn't the writes be amortized constant time if you used geometric growth?
I think to say that you'd have assume that a sufficiently large portion of the structure gets manually set after each reset. Consider this type of usage pattern where we only manually set a value at the last indices of the structure after each reset:

fill structure with value x
structure[1000000] = value y
fill structure with value z
structure[1000000] = value w

I think it's obvious these writes are O(n).
 

upandaway

Member
One way or another, I ended up with an interview to a startup internship involving Javascript, tomorrow. I never saw javascript code in my life.

They know that, and I gave them my repo and everything so they know exactly what I know, but I still want to brush up on javascript a little before talking to them. Does anyone have a quick tutorial that can give me an idea?


This nerdsniped me hard, but I think I got it now:
http://pastebin.com/eTfWUFi1
Gonna have to look at this later, at a glance I have no clue what's going on.

I also gave it some more tries and couldn't do it.
 

poweld

Member
...the structure that solves the problem is also O(1) to initialize, and O(1) to resize during reset!

http://pastebin.com/eTfWUFi1

The initialization here has a time complexity of O(n), unless if your solution skirts that.

Water said:
They are O(1) to read and write if the hashmap has previously been initialized to some specific size large enough for all the data, and the hash function is perfect for the data, meaning no conflicts will occur.

This is misleading. Gets from a hashmap can in the worst case approach O(n) if the hashing algorithm places many or all of the entries into the same bucket, or if you use a very small number of buckets. Insertions will in the worst case be O(n) due to the need for a resizing event, which exponentially rare in any reasonable hashmap implementation.

A little more on hashmaps (and some insight for the last two assertions), a common way to implement a hash map is to create an array of some default length on initialization. Each entry in this array is called a "bucket", and contains a linked list of key value pairs. Each insertion into the hashmap runs the hashing function on your key and mods that number with the current length of the backing array. The returned value is the index of the bucket this value will go into.

This is why a bad hashing algorithm that puts every element into one bucket will perform gets at O(n) - because the elements all exist in a linked list which must be traversed to find the key you're looking for.

Insertion performance may be non-linear because at some point the hashmap implementation will (hopefully) decide that you have inserted too many elements, and the array is filling up or too many collisions are occurring, and will initiate a resize. A new, larger, array is initialized, and the old elements are re-hashed to find their new bucket location and inserted into the new array.

Water said:
But that initialization required for an arbitrary size hashmap is not O(1).

Yes, it is. In fact, it is impossible for the initialization of an arbitrary size hashmap to be anything but O(1), since it has no association with the data.
 

Water

Member
Gonna have to look at this later, at a glance I have no clue what's going on.
If you want to still try to work out the most interesting part of the problem, here's the first half of the solution explained.

As I said in the hints before, the first step is a data structure that has O(1) reset, but takes more time for individual element access. The final step of the solution uses this structure as a starting point and improves it to boost the element access to O(1).

We maintain a value K that is the last value the entire structure has been initialized to, and an integer N keeping a count of how many items have been accessed after the last reset. To reset the data structure, just set K=newK and N = 0. We store the actual data in a simple array I'll call Data. Any item that is written to index i in our data structure is written to the same index in the internal Data array. Clearly we could get to the data in O(1), but we have the problem that we don't know if we've actually written a valid value in there after the last reset. To solve that problem we use a second array I'll call Valid. It's the same length, and contains indices of items that have been accessed, in the order they have been accessed after the last reset. To access an individual item in index i, you have to first perform a linear search into Valid[0..N-1] and see if you find i there. If yes, then you just access Data. If no, then the current value at index i in the data structure is K. If index i is written into, you have to record that by Valid[N] = i; N = N+1. Obviously, the data access in this stepping-stone data structure costs O(n) so further work is needed.
 

phoenixyz

Member
If you want to still try to work out the most interesting part of the problem, here's the first half of the solution explained.

As I said in the hints before, the first step is a data structure that has O(1) reset, but takes more time for individual element access. The final step of the solution uses this structure as a starting point and improves it to boost the element access to O(1).

We maintain a value K that is the last value the entire structure has been initialized to, and an integer N keeping a count of how many items have been accessed after the last reset. To reset the data structure, just set K=newK and N = 0. We store the actual data in a simple array I'll call Data. Any item that is written to index i in our data structure is written to the same index in the internal Data array. Clearly we could get to the data in O(1), but we have the problem that we don't know if we've actually written a valid value in there after the last reset. To solve that problem we use a second array I'll call Valid. It's the same length, and contains indices of items that have been accessed, in the order they have been accessed after the last reset. To access an individual item in index i, you have to first perform a linear search into Valid[0..N-1] and see if you find i there. If yes, then you just access Data. If no, then the current value at index i in the data structure is K. If index i is written into, you have to record that by Valid[N] = i; N = N+1. Obviously, the data access in this stepping-stone data structure costs O(n) so further work is needed.


Actually, I did it the other way round.
 

Water

Member
Actually, I did it the other way round.
Oh, I didn't notice your solution had that slight difference. Works just as good, obviously.

Doing the way I did allows splitting the problem into two parts that each contain one of the key ideas necessary, and where the output of the first part is already a functional data structure, so it's nice for presenting/explaining the problem to others. I can't immediately come up with a similar progression that makes sense and ends up in your implementation variant.
 

phoenixyz

Member
Oh, I didn't notice your solution had that slight difference. Works just as good, obviously.

Doing the way I did allows splitting the problem into two parts that each contain one of the key ideas necessary, and where the output of the first part is already a functional data structure, so it's nice for presenting/explaining the problem to others. I can't immediately come up with a similar progression that makes sense and ends up in your implementation variant.

My notion was filling up the original data array in an ordered manner, so I can reset it by clearing a single "fill" variable. So I need another array which holds associations but allows getting and settings in O(1) (the mapper). But then I would need to reset this one too. To solve this I added the third array which always keeps the associations fresh.
 

Water

Member
This is misleading. Gets from a hashmap can in the worst case approach O(n) if the hashing algorithm places many or all of the entries into the same bucket, or if you use a very small number of buckets. Insertions will in the worst case be O(n) due to the need for a resizing event, which exponentially rare in any reasonable hashmap implementation.
I'm sorry for having been unnecessarily confusing about the hashmap issue in my previous posts.

The way you are wording this shows a bit of confusion on your part too, which I guess has compounded the communication problem. It is not misleading to say that growing a hashmap is O(n). There is no such thing as "can in the worst case approach O(n)" or "will in the worst case be O(n)". O notation is an upper bound on a function's growth rate, so it describes exactly the worst case and nothing else. The distinction between it and average behavior is not merely a point of academic interest if you are working on a realtime system (games for one), need absolute reliability, etc.

Yes, it is. In fact, it is impossible for the initialization of an arbitrary size hashmap to be anything but O(1), since it has no association with the data.
Initializing a hashmap to empty is O(1), but as I've tried to point out, using a hashmap in this fashion cannot lead to a valid solution since then set operations will grow the hashmap and be O(n).

What I meant by "arbitrary size" was initializing a hashmap to its final size immediately, so that set operations could be made O(1), but then the initialization would not be O(1) and neither would be the reset operation of our data structure.
 

Apt101

Member
I need to brush up on SQL and want to take a class. I know the basics, built and run clusters from an infrastructure standpoint for years, can write simple queries (a lot of PowerShell scripts that work with MS SQL databases for in-house apps we develop) so I need something advanced. Any good on-line courses anyone can recommend?
 

injurai

Banned
Man all this talk about data structure implementation and expected runtimes... when I took my algorithms class it was before systems. So we never actually manually implemented the structures that we theoretically talked about. I really should go back through all that material.
 

poweld

Member
I'm sorry for having been unnecessarily confusing about the hashmap issue in my previous posts.

The way you are wording this shows a bit of confusion on your part too, which I guess has compounded the communication problem. It is not misleading to say that growing a hashmap is O(n). There is no such thing as "can in the worst case approach O(n)" or "will in the worst case be O(n)". O notation is an upper bound on a function's growth rate, so it describes exactly the worst case and nothing else. The distinction between it and average behavior is not merely a point of academic interest if you are working on a realtime system (games for one), need absolute reliability, etc.


Initializing a hashmap to empty is O(1), but as I've tried to point out, using a hashmap in this fashion cannot lead to a valid solution since then set operations will grow the hashmap and be O(n).

What I meant by "arbitrary size" was initializing a hashmap to its final size immediately, so that set operations could be made O(1), but then the initialization would not be O(1) and neither would be the reset operation of our data structure.

I think we're in agreement :)

I was considering the average instead of the worst-case. As Slavik81 mentioned, the growth of a hashmap occurs infrequently. We're talking on the order of tens of resizes for millions of entries. Only those insertions which trigger a resize are guaranteed to have O(n) performance. Well, that and if you have an awful hashing algorithm. I'm sure you're aware of this, just want to explain my point and inform anyone else that's reading this.
 

Cindres

Vied for a tag related to cocks, so here it is.
Alright folks, cross posting this from WebDev cause I haven't had a response there yet:

This is probably the best thread for this. I need help with some sort of hosting solution.

Basically I need to run:
Maven projects (Locally these run on Tomcat, can be JBoss or whatever the service has available).
MySQL DB

What're my best chances at hosting options for these?

Any help would be great, I've tried one but the name escapes me now and the DB support wasn't great.
 
May be a bit off topic, but i'm trying to learn html and javascript so that I can find some kind of job since my useless degree isn't helping.

I'm using codecademy right now learning HTML, and so far, it isn't bad. Is there an order to learning these programs? Am I better off learning HTML first and then Javascript?

Also, is there another OT for HTML and web development, or will this thread be ok for me to ask for tips and help?

Thanks
 

Siphorus

Member
Are we able to ask questions on this thread? I'm stuck on a weird code problem and I'm not sure what's happening. (Most likely some local vs heap thing).

Actually nevermind! I just fixed it!

The problem was I was copying a local variable of char* to a char** array of pointers that were allocated using new and I just had to declare the char* packet struct as an array instead so it got moved to heap! :)

Now onto congestion control and ACKs! :D
 

MiszMasz

Member
May be a bit off topic, but i'm trying to learn html and javascript so that I can find some kind of job since my useless degree isn't helping.

I'm using codecademy right now learning HTML, and so far, it isn't bad. Is there an order to learning these programs? Am I better off learning HTML first and then Javascript?

Also, is there another OT for HTML and web development, or will this thread be ok for me to ask for tips and help?

Thanks

Here you go:
Web Design and Development |OT| Pixel perfect is dead, long live responsive design

I don't do much with webdev, but i do know both are worth knowing. The folk in that thread will be able to sort you out though.
 

Mr.Mike

Member
Can anyone speak to breadth vs depth of programming knowledge? Mostly I suppose, as a student or new grad looking for internships/work, but also just in general as far as programming careers go.

It seems like you can either 1) learn as MANY things as possible and apply for every position you can hoping to get on, or 2) learn something as MUCH as possible and hope to do well in getting the jobs you can apply for.

I'm currently leaning towards that second option, having just finished a web development course. I did well and all, but I came away from it not entirely too excited about the topic, and have sort of decided not to pursue that "direction" anymore. So now I've started learning C++, in earnest this time (I swear, but there sure is a hell of a lot of C++ to learn). I suppose the best thing really might be to sample a lot of different things and then focus in on and specialize in what you like.
 

Slavik81

Member
Alright folks, cross posting this from WebDev cause I haven't had a response there yet:



Any help would be great, I've tried one but the name escapes me now and the DB support wasn't great.
I like Digital Ocean because there's no magic. It's like having my own machine. I can install and run anything I want.

That said, you become responsible for keeping it secure and up to date. Also, if you need terabytes of storage, you may need to do some work to offload it to some other service.
 

tokkun

Member
Can anyone speak to breadth vs depth of programming knowledge? Mostly I suppose, as a student or new grad looking for internships/work, but also just in general as far as programming careers go.

It seems like you can either 1) learn as MANY things as possible and apply for every position you can hoping to get on, or 2) learn something as MUCH as possible and hope to do well in getting the jobs you can apply for.

I'm currently leaning towards that second option, having just finished a web development course. I did well and all, but I came away from it not entirely too excited about the topic, and have sort of decided not to pursue that "direction" anymore. So now I've started learning C++, in earnest this time (I swear, but there sure is a hell of a lot of C++ to learn). I suppose the best thing really might be to sample a lot of different things and then focus in on and specialize in what you like.

C/C++ is primarily used in software where you are very concerned about performance, memory use, and/or energy consumption. Today those are fields like high-throughput computing, cloud / service backends, embedded devices / Internet of Things, high-end games, and system software (OS, hypervisor, drivers, compilers / libraries, etc). One thing that may not instantly be apparent from this list is that these are all areas where you will benefit a lot from having systems knowledge; that is, also having a good understanding of hardware architecture, operating systems, and networking principles. So my specific advice about C++ is to think about whether you are interested in becoming a systems person. If you are, focus your breadth on understanding systems concepts like memory architecture, threading, and kernel networking. If you become a systems programmer, those core skills carry over even if C++ starts getting replaced in those areas by something like D, Rust, or Go. The same is true of general software engineering knowledge like data structures, algorithms, and design patterns.
 

Cindres

Vied for a tag related to cocks, so here it is.
You mentioned JBoss and MySQL and the only thing I can think of is https://www.openshift.com/

I like Digital Ocean because there's no magic. It's like having my own machine. I can install and run anything I want.

That said, you become responsible for keeping it secure and up to date. Also, if you need terabytes of storage, you may need to do some work to offload it to some other service.

Both look like solid suggestions, cheers guy. I guess I'll try OpenShift first 'cause it's free but only $5 to give Digital Ocean a try is fine anyyway
 

Slavik81

Member
Both look like solid suggestions, cheers guy. I guess I'll try OpenShift first 'cause it's free but only $5 to give Digital Ocean a try is fine anyyway
If you use a referral link, you can get $10 credit for DO. Plus $100 from the Github education pack, if you qualify.
 
Im working my way through Harvard's CS50 and i got to say, C seems like such a retarded language coming from Python and C#. So many quality of life functions are missing, from capitalizing a string to getting the length of a number. Its helpful from a educational perspective and Im sure C is a great language once you know how to deal with it but damn. :lol
 

Massa

Member
Im working my way through Harvard's CS50 and i got to say, C seems like such a retarded language coming from Python and C#. So many quality of life functions are missing, from capitalizing a string to getting the length of a number. Its helpful from a educational perspective and Im sure C is a great language once you know how to deal with it but damn. :lol

Nope, C is still a pain in the ass even after you learn to deal with it. The only consolation is that it's not C++, now that's something else.
 

injurai

Banned
Im working my way through Harvard's CS50 and i got to say, C seems like such a retarded language coming from Python and C#. So many quality of life functions are missing, from capitalizing a string to getting the length of a number. Its helpful from a educational perspective and Im sure C is a great language once you know how to deal with it but damn. :lol

I think C is a far more beautiful language. The idea of C is that it mostly exists as syntactic sugar for assembly language (not quite, but in some sense.) It abstracts some elements that differ on varying architectures, but other than that it reveals a lot of truths about programming.

C# and Python are obviously modern. They try to abstract away many solved problems. But where they really shine is in their libraries, and the time it takes to go from concept to proof of concept. But ultimately I have a hard time seeing them as beautiful languages. I will say C# is probably my favorite OO language to work in. Python I'd happily use in place of a scripting language, though I'd prefer Lua. Unfortunate that it's not as mainstream as Python.

If we are calling C ugly, I feel in 2015 I can't help but call C# and Python are ugly as well. The programming language trends of the 90's just kind of baffle and upset me to some extent. We go from beautiful simplicity and purity. The C's, Lisps, Smalltalk, Ada. Then to language that are all about bloat, cruft, and esoteric OO design. I'm really glad things like Go and Rust cropped up. Both of which were sort of pet projects that could have ended up not existing at all. I'd really feel like the industry stopped moving forward if that was the case.
 

Water

Member
Nope, C is still a pain in the ass even after you learn to deal with it. The only consolation is that it's not C++, now that's something else.

Both suck, but for real-world use, I don't personally see any reason to use C if C++ is an option. At worst, you can write the code the same as you would in C, but most things can be written at least a bit better when C++ features are available. The worst thing about C++ is all the bad things it has inherited from C in order to remain (almost, but not quite) compatible.
 
I think C is a far more beautiful language. The idea of C is that it mostly exists as syntactic sugar for assembly language (not quite, but in some sense.) It abstracts some elements that differ on varying architectures, but other than that it reveals a lot of truths about programming.

C# and Python are obviously modern. They try to abstract away many solved problems. But where they really shine is in their libraries, and the time it takes to go from concept to proof of concept. But ultimately I have a hard time seeing them as beautiful languages. I will say C# is probably my favorite OO language to work in. Python I'd happily use in place of a scripting language, though I'd prefer Lua. Unfortunate that it's not as mainstream as Python.

If we are calling C ugly, I feel in 2015 I can't help but call C# and Python are ugly as well. The programming language trends of the 90's just kind of baffle and upset me to some extent. We go from beautiful simplicity and purity. The C's, Lisps, Smalltalk, Ada. Then to language that are all about bloat, cruft, and esoteric OO design. I'm really glad things like Go and Rust cropped up. Both of which were sort of pet projects that could have ended up not existing at all. I'd really feel like the industry stopped moving forward if that was the case.
I wasnt calling C ugly, just a bit clunky to use.

My very first introduction to programming was in Racket and it was all great. It just felt so natural to me. After that i took a Java class and OO just sucked the fun out of it for me.
 

Cindres

Vied for a tag related to cocks, so here it is.
You mentioned JBoss and MySQL and the only thing I can think of is https://www.openshift.com/

I spent half my afternoon battling with OpenShift but I ultimately was able to deploy my project to a Wildfly cartridge and get it working with the SQL DB also setup on there so I'm all up and running. Thanks for the suggestion, especially the ability to locally compile my WARs and EARs and throw them right up there was super convenient for me.
 

Massa

Member
Both suck, but for real-world use, I don't personally see any reason to use C if C++ is an option. At worst, you can write the code the same as you would in C, but most things can be written at least a bit better when C++ features are available. The worst thing about C++ is all the bad things it has inherited from C in order to remain (almost, but not quite) compatible.

I pretty much agree but I see it from a different perspective. The problem isn't that C++ inherits bad things from C, it's that it tries to be everything and most of the time those things don't go well with C.

Pure C is missing basic functionality but that is easily remedied with a couple of libraries.
 

Kyuur

Member
Anyone here familiar with powershell? I've had a strange instance where this line:

$users = (Get-ChildItem C:\Users).FullName

Worked on several PCs but not one. I've since replaced it with:

$users = (Get-ChildItem C:\Users) | ForEach-Object { $_.FullName }

Which seems to work, but I am flabbergasted why the initial code would work sometimes instead of all the time or not at all..
 

Pegasus Actual

Gold Member
Have you guys seen Livecoding.tv already? It's something like Twitch, but for programmers. It works flawlessly and without a delay.
Wait... why? The last thing I'd ever want is a peanut gallery watching me write code.

Clicked a random stream, and it was a guy scrolling through a Stack Overflow thread with a perplexed look on his face, so at least it's capturing the real coding experience.
teZGSGT.png
 
Have you guys seen Livecoding.tv already? It's something like Twitch, but for programmers. It works flawlessly and without a delay.

I've considered streaming programming in Rust, but I've not gotten around to setting that up yet. I'm not exactly a Rust expert, but I feel like that's the language that might have the best ratio of "interesting to people" to "not everyone knows it".
 

injurai

Banned
I've considered streaming programming in Rust, but I've not gotten around to setting that up yet. I'm not exactly a Rust expert, but I feel like that's the language that might have the best ratio of "interesting to people" to "not everyone knows it".

Let me know if you do. It's been on my backburner for a while but I'm starting to dig into it more and more. I don't have any projects yet, probably was just going to start off implementing red black trees, hashmaps, and some sieves.
 

wolfmat

Confirmed Asshole
Have you guys seen Livecoding.tv already? It's something like Twitch, but for programmers. It works flawlessly and without a delay.

It doesn't seem interesting. Skimming the archived videos, I see stuff like "here's this library" stuff or "look at me building Django things". And then a video starts and there's dubstep. I dunno.
It's not really performing well on my end, also.

A noble endeavor though.
 
Dang, I really should've started browsing Off-Topic Community sooner; I was wondering where all the programmers were posting on GAF.

Anyone have any experience with datacenter network programming and can point me to some resources to learn about it? I'm going into a job soon where I'll have to work with some pretty heavy stuff, and I get the feeling that my at-home iptables experiences won't be enough...

Anyone here familiar with powershell? I've had a strange instance where this line:

$users = (Get-ChildItem C:\Users).FullName

Worked on several PCs but not one. I've since replaced it with:

$users = (Get-ChildItem C:\Users) | ForEach-Object { $_.FullName }

Which seems to work, but I am flabbergasted why the initial code would work sometimes instead of all the time or not at all..

I'm a UNIX guy, but it sounds like Get-ChildItem may return a set of objects, and ForEach-Object can handle both enumerable and non-enumerable objects?

Wait... why? The last thing I'd ever want is a peanut gallery watching me write code.

Streaming software development isn't exactly a new thing, but I'm right there with you; the last thing I'd want is someone watching me go to Google to look up something simple that I forgot/haven't used in a while. Having an entire site dedicated to it is certainly interesting though. Considering the popularity of streaming today, it has the potential to get more people interested in programming, but I feel like you'd already have to be pretty interested to want to watch it in the first place...
 

JesseZao

Member
Twitch has a game dev section, but most of them are people using map editors...

If I were to start a hobby game project, I might think about streaming it. Just not sure I want to make games as my side projects is all.
 

survivor

Banned
My problem with most programming streams is that a lot of them just waste their time on random shit or just staring at the screen or going to other websites. And the ones that are a bit more famous, just interact with the chat way too much.

Casey Muratori is about one of the few examples of what I want. He is so focused on his tasks and doesn't get distracted during his streams. And then he has an extensive Q&A session at the end so there is an interactivity segment with the viewers as well.
 

mltplkxr

Member
I spent half my afternoon battling with OpenShift but I ultimately was able to deploy my project to a Wildfly cartridge and get it working with the SQL DB also setup on there so I'm all up and running. Thanks for the suggestion, especially the ability to locally compile my WARs and EARs and throw them right up there was super convenient for me.

Nice! Really glad to know my post was helpful. I need to look into it myself.
 
Top Bottom