DesertEater
Member
Thanks a lot! I will look into these.
-
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
- Thread starter Kikarian
- Start date
oxrock
Gravity is a myth, the Earth SUCKS!
Working on a program to calculate the the nth prime number for practice. I have it running alright but getting it to run efficiently is a bit of a problem. Was thinking you guys would have some valuable insight. (written in python 2.7.8)
As it stands, this code will find the millionth prime number in 183.2 seconds (on my pc, results may vary obviously) with the "is_prime()" function and 190.1 seconds with the "prime_checker()" function. The strange thing is, when I run the functions independently of the main program, the prime_checker() function very clearly outperforms is_prime() so I have no idea why that doesn't hold true when integrated into the while loop.
The way the program interacts currently is that you first input the number of times you want to run the program. Then you input another number to find that prime number ( so inputting 50 will give you the 50th prime number). This is a program I wrote for a website (hackerrank) challenge and that's how it interfaces with their website, so don't mind it if it's odd. The actual challenge is here. The problem i'm having is that some unknown inputs they're feeding into my program are causing it to exceed the permitted time limit (10 seconds), so I'm just trying to streamline as much as I can. Also, I receive no prizes or anything for participating in this "contest" I'm just doing what I can to get better, so no reason to hold back!
Code:
import math
def prime_checker(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
for i in range(5, int(n ** 0.5) + 1, 6):
if n % i ==0 or n % (i + 2)==0:
return False
return True
def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
f = 5
while f <= r:
if n%f == 0: return False
if n%(f+2) == 0: return False
f +=6
return True
testCount = int(input())
for _ in range(testCount):
maximum = int(input())
if maximum == 1:
print 2
elif maximum == 2:
print 3
else:
count = 5
prime = 3
while prime < maximum:
count+=2
if is_prime(count): # <------- switch functions here for testing
prime+=1
print countAs it stands, this code will find the millionth prime number in 183.2 seconds (on my pc, results may vary obviously) with the "is_prime()" function and 190.1 seconds with the "prime_checker()" function. The strange thing is, when I run the functions independently of the main program, the prime_checker() function very clearly outperforms is_prime() so I have no idea why that doesn't hold true when integrated into the while loop.
The way the program interacts currently is that you first input the number of times you want to run the program. Then you input another number to find that prime number ( so inputting 50 will give you the 50th prime number). This is a program I wrote for a website (hackerrank) challenge and that's how it interfaces with their website, so don't mind it if it's odd. The actual challenge is here. The problem i'm having is that some unknown inputs they're feeding into my program are causing it to exceed the permitted time limit (10 seconds), so I'm just trying to streamline as much as I can. Also, I receive no prizes or anything for participating in this "contest" I'm just doing what I can to get better, so no reason to hold back!
Code:
def prime_checker(n):
if n == 2 or n == 3:
return True
elif n < 2 or not (n % 2):
return False
elif n < 9:
return True
elif not (n % 3):
return False
for i in range(5, int(n ** 0.5) + 1, 6):
if not (n % i) or not (n % (i + 2)):
return False
return Truethis is a little bit faster but if you want substantially faster maybe just use the Sieve of Eratosthenes.
oxrock
Gravity is a myth, the Earth SUCKS!
xrange helped a bit, still a long way off sadly.
I was looking into Sieve of Eratosthenes earlier but I need to know the end number for it to work. When counting the the nth prime, I don't find that out until I'm done. I've been awake for 35 hours and coding for far too long so it's quite possible that I'm just too burnt out to implement it properly.
It's probably not too hard, but I'm having a tough time using SQL to figure out how to compare two dates for the following question:
Using this database. Most of it is easy, but the trick seems to be figuring out when the SECOND review is higher instead of either.
Ah yes, xrange, I use Python 3 so I didn't think of that.
I kinda didn't realise you want to find huge primes. Then you should use e.g. the Miller–Rabin primality test. Although you would need to implement a fast modulo exponentiation yourself as e**x mod n is terribly slow in python.
http://sqlfiddle.com/#!2/16364/21
This works. No idea if it's the BEST way to accomplish what you are after though.
oxrock
Gravity is a myth, the Earth SUCKS!
After some sleep, I figured out how to implement Sieve of Eratosthenes.
Sadly, this is the best way I could think to implement it. Due to relying on iterating through lists, the scaling on this program is HORRIBLE! It takes 26 seconds to find the 100000th prime number as opposed to my earlier program doing it in 5.5 seconds and the larger it gets, the scarier the processing time.
Code:
import math
tests = int(input())
for _ in xrange(tests):
n = int(input())
limit = int((n * math.log(n)) + (n* (math.log(math.log(n - 0.9385)))))+1
primeCount = 1
numbers = range(3,limit,2) # <--- EVIL!
divisor = 3
while primeCount < n:
removeList = []
divisor = numbers.pop(0)
primeCount+=1
for x in numbers:
if x%divisor == 0: #<---- not that wonderful either
removeList.append(x)
for y in removeList:
numbers.remove(y)
print divisorSadly, this is the best way I could think to implement it. Due to relying on iterating through lists, the scaling on this program is HORRIBLE! It takes 26 seconds to find the 100000th prime number as opposed to my earlier program doing it in 5.5 seconds and the larger it gets, the scarier the processing time.
I swear I did pretty much the exact same thing and it still returned cases where either date was greater, not just the second (which I guess would be all of them that had multiple reviews by the same person). That did the trick though, thanks a bunch! So just having R2.ratingDate > R1.ratingDate and R2.stars > R1.stars is enough for it to find it - was thinking it would be more complicated! Maybe I messed up one of the other joins, because that was my first idea on how to do it but it wasn't working.
So the programI'm writing is at the point where it takes around 4 minutes to create all the data structures from the data I'm reading from. But this makes debugging a pain in the butt because I have to wait 4 minutes every time I want to see what's wrong with the newer code and to see what some test print statements are saying.
Is this a common thing in the programming world, waiting for programs to run and then having it crash instantly, change something, wait for it to run, crash...etc.
Any advice for this situation? Thanks guys.
Is this a common thing in the programming world, waiting for programs to run and then having it crash instantly, change something, wait for it to run, crash...etc.
Any advice for this situation? Thanks guys.
come up with smaller data?
TurtleTracks
Neo Member
Hey, I've been working on building a search engine in java this summer along with two other students as a sort of for fun project at my university. We've kind of gotten to the point where we can search links from our collection and return semi-relevant results most of the time.
Right now we're wondering if there's anyway to connect the java engine to a webpage. I have a domain hosted by Dream Host if that matters. I would also be fine with a local webpage/site that only exists on my laptop, if only to have some sort of web interface between a user search and the Java program.
We are also running into an issue where we are limited by the number of pages we can run the search on at a time. After about 5,000 pages we hit an Out of Memory Error with Java, even when we max out the virtual memory. We have been running the search engine on my laptop which has 8GB of physical memory, with the stored page files occupying about 124MB on disk. Is there anything we can do to get around the memory issue? I've heard about using databases but I don't really know how that works, as I've never dealt with one before.
Right now we're wondering if there's anyway to connect the java engine to a webpage. I have a domain hosted by Dream Host if that matters. I would also be fine with a local webpage/site that only exists on my laptop, if only to have some sort of web interface between a user search and the Java program.
We are also running into an issue where we are limited by the number of pages we can run the search on at a time. After about 5,000 pages we hit an Out of Memory Error with Java, even when we max out the virtual memory. We have been running the search engine on my laptop which has 8GB of physical memory, with the stored page files occupying about 124MB on disk. Is there anything we can do to get around the memory issue? I've heard about using databases but I don't really know how that works, as I've never dealt with one before.
I'm dealing with over 2 million documents, that's not really a possibility. But there's probably a way to save my data structure somewhere and load it up instead of re-creating it every time.
Look into unit testing. You can thoroughly test each data structure and class by itself using tests that run in mere seconds.
Are you running 64 bit Java?
I think he means to not load all the data on every test run.
fierrotlepou
Member
Has anyone actually - legitimately - been able to follow an online programming course and have something to show for it?
There are so many sources online that it's so hard to pick one thing and keep at it.
Is there a course that starts from 0 and ends at programming something worthwhile? I'm willing to put the work in for sure, but if the course just kinds of "ends", that sucks. Most tutorials I find show you a lot of things, but there are never great examples. I'm very good at learning something if I see it first. I want to learn a programming language that has a future. I want to be able to write simple programs. I want to be able to make small iOS apps.
Most of all, I want to be fluent at a - relevant - programming language.
I'm starting to think that it's only possible by going to school for this if I want to have some kind of structure.
There are so many sources online that it's so hard to pick one thing and keep at it.
Is there a course that starts from 0 and ends at programming something worthwhile? I'm willing to put the work in for sure, but if the course just kinds of "ends", that sucks. Most tutorials I find show you a lot of things, but there are never great examples. I'm very good at learning something if I see it first. I want to learn a programming language that has a future. I want to be able to write simple programs. I want to be able to make small iOS apps.
Most of all, I want to be fluent at a - relevant - programming language.
I'm starting to think that it's only possible by going to school for this if I want to have some kind of structure.
Yeah, that's what I meant, but then he runs the risk of not running into that specific bug if there's a problem with the input.
Purple Cheeto
Member
Test with a smaller data set until it works properly then scale up the data set.
Or improve your loading code?
I could think of a couple of other things, but it kind of depends on the nature of your application.
Maybe a "tutorial" isn't the right thing for you? Personally, I got a lot more out of introductions into certain topics and than program something for myself from that. An (although too advanced for beginners) example would be the C# Threading sample from the great "C# in a nutshell" book. You get some things to play around, but learning and using is ultimately up to yourself.
If you want to do iOS apps there basically is just Objective-C and the new Swift. However I honestly would recommend something less niche than these for starting, and rather begin with something more prevalent (Java, C#, Python). Once you "get" the mindset of programming, switching to a language is just a matter of learning syntax (which is usually pretty quick) and using the mechanics of the language to do what you want. The part where you learn "programming" is omitted by then.
Yes. Maybe not crashing, but gradually incrementing features by modifying small things is very common. Especially in larger applications where you just can't make large changes without the risk of breaking something else.
I'm from the old school that learned my fundamentals from book learnin' over a decade (maybe two? god I'm old) ago. I do use a lot of online resources, but it tends to be quick general primers, or short tutorials on how to resolve specific problems. As such, I would actually recommend you look at grabbing a book or two, as that would be more likely to give you that end-to-end resource you crave. Nowadays, they all come with ebook/PDF options, so you can just use your PDF viewer instead of a browser for the same sort of experience.
On a related note, "relevant" programming language is really a broad term nowadays. It used to be that it was C#, Java, C++, maybe JavaScript for the web side, and then everything else. Now there's a plethora of opportunities available in a wide variety of languages. It's funny that you mention iOS, as if you want to do iOS you pretty much need to learn Objective-C or Swift at this point, which are languages that aren't particularly useful outside of the Apple ecosystem.
The important thing, as I and others have said to a lot of new programmers, is to learn your fundamentals in any language, and you will find it isn't that difficult to pick up new languages if you feel the need to transition in the future. While there still are a ton of developers in the field that specialize in one corner of the field, and are C++ coders for life, there are more and more developers that are essentially polyglots. Being comfortable with picking up a new language/platform when necessary is increasingly becoming an essential skill.
As for my recommendation of where to start? Python or Ruby. Online resource? Learn Python the Hard Way or Learn Ruby the Hard Way. Get through either one, including the exercises at the end of each chapter, and you'll have a good understanding of the basics of programming in any language, and more importantly, the way you need to think to be a decent developer. Once you have that down pat, then look for more in-depth, specific use-case resources.
TurtleTracks
Neo Member
Yeah, I think so.
I can almost guarantee you're failing on input like this:Working on a program to calculate the the nth prime number for practice. I have it running alright but getting it to run efficiently is a bit of a problem. Was thinking you guys would have some valuable insight. (written in python 2.7.8)
Code:import math def prime_checker(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False for i in range(5, int(n ** 0.5) + 1, 6): if n % i ==0 or n % (i + 2)==0: return False return True def is_prime(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False r = int(n**0.5) f = 5 while f <= r: if n%f == 0: return False if n%(f+2) == 0: return False f +=6 return True testCount = int(input()) for _ in range(testCount): maximum = int(input()) if maximum == 1: print 2 elif maximum == 2: print 3 else: count = 5 prime = 3 while prime < maximum: count+=2 if is_prime(count): # <------- switch functions here for testing prime+=1 print count
As it stands, this code will find the millionth prime number in 183.2 seconds (on my pc, results may vary obviously) with the "is_prime()" function and 190.1 seconds with the "prime_checker()" function. The strange thing is, when I run the functions independently of the main program, the prime_checker() function very clearly outperforms is_prime() so I have no idea why that doesn't hold true when integrated into the while loop.
The way the program interacts currently is that you first input the number of times you want to run the program. Then you input another number to find that prime number ( so inputting 50 will give you the 50th prime number). This is a program I wrote for a website (hackerrank) challenge and that's how it interfaces with their website, so don't mind it if it's odd. The actual challenge is here. The problem i'm having is that some unknown inputs they're feeding into my program are causing it to exceed the permitted time limit (10 seconds), so I'm just trying to streamline as much as I can. Also, I receive no prizes or anything for participating in this "contest" I'm just doing what I can to get better, so no reason to hold back!
Code:
5
100001
100002
100003
100004
100005That first input should take roughly as long as this one:
Code:
1
100005Look into servlets and java web applications. You will need a java web server like Tomcat to host the web site, receive requests and return responses. I'm a bit at a loss to give you a starting point because there are tons of ways to go about this. This looks like a good summary: http://docs.oracle.com/javaee/7/tutorial/doc/webapp001.htm . You can follow the tutorial or use the terminology to find other tutorials or classes.
Have you looked at Lucence, Solr, and Elasticsearch? Solr is a web application built around the Lucene search engine. It will give an example of one way to go about this.
This is a bit more tricky. You can increase the RAM allocated to the JVM with the -Xms and -Xmx options when you launch your program. A 64-bit JVM will allow you to allocate more ram than a 32-bit one. There is a description here of those options here:http://docs.oracle.com/javase/7/docs/technotes/tools/windows/java.html . This is a bit old but a good intro to memory management with the JVM: http://www.oracle.com/technetwork/java/javase/memorymanagement-whitepaper-150215.pdf Try to look for the most recent version of that whitepaper as this is an area that is always evolving.
Keep in mind that if you have memory leaks, allocating more RAM will only delay the inevitable
TurtleTracks
Neo Member
Thanks so much! I'm reading through the links now. Though I was wondering, will I run into issues with running a server on a University network? I once tried to set up an ftp/ssh connection between my laptop on campus and my brother's laptop at home, I'm sure I went about it all wrong but I feel like there was an issue with not being able to port-forward those requests.
Ha, that's a good point. I don't know, check with your department. I'm sure they have some sort of policies and guidelines. You could also limit connections to the web server, to localhost.
One note about the whitepaper on memory management, it explains the concepts, but before tweaking the JVM, you should really measure your program first. There are tons of tools to do that like JConsole, VisualVM, and so forth. This is a guide for the standard tools that come with the JVM: http://docs.oracle.com/javase/8/docs/technotes/guides/tsgvm/ . It's terse but it'll give you an idea of what to look for. There are tons of easy/quick tutorials to follow.
close to the edge
Member
That's good advice, but the low hanging fruit is really just using a database, I think. You can look into Hibernate for a start. Hibernate is a framework that helps you map Java objects to database tables and relations. (an object relational mapper or ORM) As for which database, in the Java world, H2 is very popular for development (since it can run from memory if you want it to) and for production use I'd recommend PostgreSQL.
mugurumakensei
Member
Ah, these days I would recommend things like Spring Boot or Dropwizard especially if it's for a hobby project.
oxrock
Gravity is a myth, the Earth SUCKS!
With this advice in mind I modified my code to not keep recomputing the same data and it passed the site's tests with flying colors, thanks.
Code:
def prime_checker(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
for i in xrange(5, int(n ** 0.5) + 1, 6):
if n % i ==0 or n % (i + 2)==0:
return False
return True
if __name__ == "__main__":
primeslist = [2,3] # <-------- stores all primes here so I don't have to find primes more than once.
testCount = int(input())
for _ in xrange(testCount):
maximum = int(input())
if maximum == 1:
print 2
elif maximum == 2:
print 3
else:
if maximum < len(primeslist):
print int(primeslist[(maximum-1)])
else:
count = primeslist[-1]
prime = len(primeslist)
while prime < maximum:
count+=2
if prime_checker(count):
prime+=1
primeslist.append(count)
print countI was worried about throwing a memory error if it ended up storing too much information so I hadn't bothered trying before. This simple addition sped up the processing of batches considerably though, thanks.
fierrotlepou
Member
Thanks a lot for the help guys.
I'll get started with learnpythonthehardway. Sounds great! I'll come back when I'm done.
AbortedWalrusFetus
Member
Have any of you guys ever interviewed with Amazon? I got an email from a recruiter with Amazon to come for an interview for the Amazon Kindle team. It seems like a super awesome opportunity even if I'd have to relocate.
I've gotten a couple of those, too. I was tempted, but I already had plans.
That said, of all the big software companies, Amazon sounds the most like a meatgrinder. It's probably still a fantastic place to learn and a good company to work for overall, but you do hear the occasional horror story.
I hate linking to quara, but... If Amazon has a bad work environment with high attrition rates, why does it continue to be so successful?
Purple Cheeto
Member
I interviewed with their games team in Irvine. All the upper management types were your typical corporate types, they'll try to sell you on the fact that Amazon is a company "run by engineers" so all decisions are "made with engineering considerations in mind", but at the end of the day its a giant corporation.
All the more recent guys who came over from Double Helix seemed happy to work for a place that had money and wasn't run by game publishers (re:marketers), but depressed at the corporate bureaucracy and glacial pace of progress.
So it kind of comes down to how well you can handle working for a mega corp.
AbortedWalrusFetus
Member
I don't want to work for a mega corp, I want to move up and run the mega corp! But seriously, it depends on the product and the compensation. If I did it it would probably only be for three years anyway. It really depends on the compensation and what sort of job I could land. If I get like a team lead job it would be entirely worth it, and I hear the pay for that position is pretty great too. I emailed the guy asking to talk it over more so I guess we'll see what happens.
Directly an interview, without any pre-tests and screenings and stuff? I would do it just for the experience, even if you're not seriously interested.
I once got contacted by a recruiter from eBay/Paypal for their C#/.NET backend team. I had to do an online test with obscure Java Beans/JSP/JSF questions beforehand. Needless to say, they didn't invite me after that.
When I interviewed with Google, they linked me to this as suggested prep:
https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions
Written by a former Amazon employee when he was still there.
oxrock
Gravity is a myth, the Earth SUCKS!
More noob problems since you all love them so much! (python 2.7.8)
Doing another challenge on this website and yet again my program is running over the time limit. This time I'm given a variable and I have to sum up all the prime numbers from 0 --> variable.
Sadly, I don't get to find out what input they feed into my program to make it run for more than 10 seconds (which is the limit), but it passes most of the others tests in about half a second. I'm thinking my prime_counter() function could be the weak link, I know I can tackle it other ways but none have been any faster. Ideas on where a bit more efficiency can be gained are most certainly welcomed.
Doing another challenge on this website and yet again my program is running over the time limit. This time I'm given a variable and I have to sum up all the prime numbers from 0 --> variable.
Code:
def prime_counter(n,primes):
result = 0
for e in primes:
if e <= n:
result+= e
else:
break
return result
def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
for i in xrange(5, int(n ** 0.5) + 1, 6):
if n % i ==0 or n % (i + 2)==0:
return False
return True
primes = [2,3]
tests = int(input())
for _ in xrange(tests):
maximum = int(input())
count = int((primes[-1])+2)
if maximum <= primes[-1]:
print prime_counter(maximum,primes)
else:
while count <= maximum:
if is_prime(count):
primes.append(count)
count+=2
print prime_counter(maximum,primes)Sadly, I don't get to find out what input they feed into my program to make it run for more than 10 seconds (which is the limit), but it passes most of the others tests in about half a second. I'm thinking my prime_counter() function could be the weak link, I know I can tackle it other ways but none have been any faster. Ideas on where a bit more efficiency can be gained are most certainly welcomed.
Mysterious
Banned
What's the best compiler for Mac for C++?
I typically use Eclipse for Java and Dev-C++/Visual Studio on Windows for C++.
I typically use Eclipse for Java and Dev-C++/Visual Studio on Windows for C++.
Purple Cheeto
Member
Clang which is included with XCode.
I think you meant IDE.
The other part I forgot was they asked a lot of questions about helping customers or working with customers. Stuff that makes more sense for a sales person than someone working on their mobile games or AR software.
And stuff about resolution of technical conflicts. Software engineering skills were pretty low on their totem pole of questions.
Mysterious
Banned
This might (probably is) be a stupid question, but I could never figure it out: how do you compile C++ in Xcode?
This is sort of my yearly python re-learning exercise, so I gave it a shot as well:
Code:
#!/usr/bin/env python
from itertools import islice
prime_count = int(raw_input())
if prime_count < 0:
raise ValueError('Cannot find a negative number of primes.')
n_values = []
for i in xrange(prime_count):
n = int(raw_input())
if n < 1:
raise ValueError('When finding the nth prime, '
'n cannot be less than one.')
n_values.append(n)
largest_n = max(n_values) if n_values else -1
def is_prime(value, smaller_primes):
for prime in smaller_primes:
if value % prime == 0:
return False
return True
value = 3
prime_list = [2]
max_index = 0
while len(prime_list) < largest_n:
if (max_index < len(prime_list) - 1 and
prime_list[max_index] ** 2 <= value):
max_index += 1
if is_prime(value, islice(prime_list, max_index)):
prime_list.append(value)
value += 2
for n in n_values:
print prime_list[n-1]I figure this is the best place to ask. What's the best way to create a website that allows users to submit text and then have an admin approve it to show up on the page? Would creating something like this from scratch be too much for someone with very little programming experience (in C++)?
Are there any scripts already made that I could install and customize? I'm trying to think of the name for this type of thing, but comments and review doesn't really encompass it although it could be modified for that.
Are there any scripts already made that I could install and customize? I'm trying to think of the name for this type of thing, but comments and review doesn't really encompass it although it could be modified for that.
^ Depends on the web host. If you're going to get a generic one, most feature PHP, so you'll have to use it.
On a server with PHP you can install WordPress, which is a blog-type system, which allows you to create posts/pages and then have people comment on them. You can then make the posts only show up if they're approved.
On a server with PHP you can install WordPress, which is a blog-type system, which allows you to create posts/pages and then have people comment on them. You can then make the posts only show up if they're approved.
You just have to create a new command line project or a full featured one. Then you just run it. I've only done some basic command line ones, so I can't help you beyond that.