| Forum Index > General Forum |
Thread Rules 1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution. 2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20) 3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible. 4. Use [code] tags to format code blocks. | ||
|
meatpudding
Australia520 Posts
You could create a dict to count the elements like this:
Then you can do some quick lookups to determine which values to keep. Eg:
HTH | ||
|
Blisse
Canada3710 Posts
On August 28 2012 14:23 meatpudding wrote: + Show Spoiler + Blisse You could create a dict to count the elements like this:
Then you can do some quick lookups to determine which values to keep. Eg:
HTH ooo, looking it over now, it looks very promising. I must review it tomorrow. Thanks for your help!  | ||
|
phar
United States1080 Posts
On August 28 2012 10:28 Blisse wrote:The two lists can possibly have over 20,000 items each. Are you guaranteed to have the lists be small enough to be in memory? The dictionary approach becomes rapidly less appealing if you have to go out to disk. (20k strings is pretty small though, assuming each string is <1k or so) Assuming this is for an undergrad class and you're not in China or CMU or something, it may be safe to assume it's small enough to hold in memory. | ||
|
MisterD
Germany1338 Posts
that runs in linear time and doesn't touch the initial lists/arrays at all except for reading them. I assume you *could* implement this with about 50% less requirements in both time and memory if you really want to, but that just makes the algorithm harder to read, and half of linear is still linear, so it doesn't really matter all that much unless you happen to have real time constraints. | ||
|
Leafty
France84 Posts
On August 28 2012 10:28 Blisse wrote: A common example of the list would be, given a = [1,1,3,2,3,3,2,2] I need the following by the end a = [2,3,3] Why do you expect a = [2,3,3] instead of a = [3,3,2] if you say you expect the order to be preserved? | ||
|
KaiserJohan
Sweden1808 Posts
http://bitsquid.blogspot.se/2012/08/cleaning-bad-code.html so awesome written, the part about cleaning bad code is hilarious. Here's an excerpt: Megafunctions. You have heard about them. These mythic creatures that dwell in the deepest recesses of the darkest codebases. Broken programmers talk about them in dusky bars, their sanity shattered by their encounters: "I just kept scrolling and scrolling. I couldn't believe my eyes. It was 12 000 lines long." | ||
|
Deleted User 101379
4849 Posts
On August 28 2012 19:56 KaiserJohan wrote: Even if you aren't a game developer, you should read this blog: http://bitsquid.blogspot.se/2012/08/cleaning-bad-code.html so awesome written, the part about cleaning bad code is hilarious. Here's an excerpt: It's only hilarious if you don't face them every single day at work. Megafunctions? I would have been happy if my predecessor even had used a function. One project had 10k lines... without a single function. I found the same SQL query 13 times in a single file. Mutable state? What about this other project from a programmer that is now my superior that luckily got replaced by something slightly less bad when i joined the company.
Or SQL queries like this that were originally in a single line and where i broke up hundreds of similar queries into a slightly more readable format (SQL Formatter vim plugin is a life saver): + Show Spoiler +
Note that table aliases like 'a' for 'actor', 'm' for 'movie', 'mp' for 'movieproduct' where introduced by me. Before that it was all t1, t2, t3, ... t1000. I once was an avid reader of thedailywtf.com, then i found out: Such code is actually real and it's the norm, not the exception. | ||
|
Blisse
Canada3710 Posts
On August 28 2012 19:04 Leafty wrote: Why do you expect a = [2,3,3] instead of a = [3,3,2] if you say you expect the order to be preserved? Sorry, I started adding on elements in the list after I was finished once but I forgot to preserve the order. x.x really stupid mistake on my part. + Show Spoiler + On August 28 2012 17:35 MisterD wrote: if your language doesn't have established data structures don't use it or write your own :p the dict approach mentioned above basically implements a bag, and you can just as easily get a set by simply associating each key with a fixed value. If you have a bag and set, the implementation becomes pretty straight forward (dirty java snippet using apache commons collections classes):
that runs in linear time and doesn't touch the initial lists/arrays at all except for reading them. I assume you *could* implement this with about 50% less requirements in both time and memory if you really want to, but that just makes the algorithm harder to read, and half of linear is still linear, so it doesn't really matter all that much unless you happen to have real time constraints. Hmm, this looks like it gets the differences properly, but I want them removed from both sides, not just one. Right now I'm debating whether parsing both arrays separately for differences would be faster than only one. + Show Spoiler + a = [1,2,2,3,4,5,6,6] That's what my program currently gives, assuming the numbers are actually strings. This isn't a school project sadly. Going to try a bunch of your suggestions now. Really appreciate the help guys ^^ | ||
|
Craton
United States17281 Posts
Same old story: vague and changing requirements at the beginning and a lack of time/will by management to scrap code and start over. Trying to just constantly patchwork quilt the damn thing to work for every variation instead of rebuilding on a strong core. It's certainly an educational experience being thrown into an sprawling, convoluted system straight out of college. Everyone should probably do it once. + Show Spoiler + And then promptly say "fuck this shit" and refactor it from scratch. Oh, I forgot the best part: I receive fixed length ASCII files that have over 5000 distinct columns worth of data and not one bit of it is normalized when I receive it. You know you're having a fun day when your queries involve inner joining 7 900+ column tables  | ||
|
Leafty
France84 Posts
h = {} | ||
|
frogmelter
United States971 Posts
This is incredibly simple, except my professor put in 9223372036854775805 9223372036854775806 9223372036854775807 as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly. I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? | ||
|
Blisse
Canada3710 Posts
On August 29 2012 14:49 frogmelter wrote: For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime. This is incredibly simple, except my professor put in 9223372036854775805 9223372036854775806 9223372036854775807 as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly. I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. | ||
|
frogmelter
United States971 Posts
On August 29 2012 14:53 Blisse wrote: That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. | ||
|
Blisse
Canada3710 Posts
On August 29 2012 15:21 frogmelter wrote: Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler + Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you. From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2. So all the factors are, 2^0 * 3^0 = 1 2^1 * 3^0 = 2 2^2 * 3^0 = 4 2^3 * 3^0 = 8 2^4 * 3^0 = 16 2^0 * 3^1 = 3 2^1 * 3^1 = 6 2^2 * 3^1 = 12 2^3 * 3^1 = 24 2^4 * 3^1 = 48 2^0 * 3^2 = 9 2^1 * 3^2 = 18 2^2 * 3^2 = 36 2^3 * 3^2 = 72 2^4 * 3^2 = 144 Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. | ||
tofucake
Hyrule19203 Posts
On August 29 2012 14:49 frogmelter wrote: For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime. This is incredibly simple, except my professor put in 9223372036854775805 9223372036854775806 9223372036854775807 as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly. I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? You only need to check primes up to the square root of the number (so 3037000499 for 9223372036854775805) | ||
|
frogmelter
United States971 Posts
On August 29 2012 15:43 Blisse wrote: Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler + Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you. From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2. So all the factors are, 2^0 * 3^0 = 1 2^1 * 3^0 = 2 2^2 * 3^0 = 4 2^3 * 3^0 = 8 2^4 * 3^0 = 16 2^0 * 3^1 = 3 2^1 * 3^1 = 6 2^2 * 3^1 = 12 2^3 * 3^1 = 24 2^4 * 3^1 = 48 2^0 * 3^2 = 9 2^1 * 3^2 = 18 2^2 * 3^2 = 36 2^3 * 3^2 = 72 2^4 * 3^2 = 144 Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Ah yeah, this makes a lot more sense. My method was trying to brute force it, which clearly wasn't the intended path. Thanks a bunch. | ||
|
zzdd
United States484 Posts
On August 29 2012 14:49 frogmelter wrote: For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime. This is incredibly simple, except my professor put in 9223372036854775805 9223372036854775806 9223372036854775807 as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly. I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? Look up miller-rabin | ||
|
nakam
Sweden245 Posts
Is it possible to insert all values using only one execution or is this the best I can do? | ||
|
tofucake
Hyrule19203 Posts
$sql = "INSERT INTO test VALUES(?, ?, ?)"; | ||
|
nakam
Sweden245 Posts
On August 30 2012 03:58 tofucake wrote: $sql = "INSERT INTO test VALUES(?, ?, ?)"; Well that's if I wanted to insert the values in different columns. I want to insert multiple rows. | ||
| ||
RSL Revival
Season 5 Korea Qualifier
Solar vs SHINLIVE!
Classic vs Percival
[ Submit Event ] |
|
StarCraft 2 StarCraft: Brood War Britney Dota 2  22467Calm  6175Sea  2827Jaedong 1342Horang2 958Hyuk 778Leta 313BeSt 294Mini 236Soma 230[ Show more ] Counter-Strike Super Smash Bros Other Games singsing1583 B2W.Neo425 XaKoH  224Pyrionflax177 Trikslyr128 DeMusliM82 KnowMe71 RotterdaM56 QueenE11 ZerO(Twitch)7 |
|
Replay Cast
The PondCast
KCM Race Survival
WardiTV Map Contest Tou…
Gerald vs herO
Clem vs Cure
ByuN vs Solar
Rogue vs MaxPax
ShoWTimE vs TBD
OSC
CranKy Ducklings
Escore
RSL Revival
Replay Cast
WardiTV Map Contest Tou…
[ Show More ] |
|
|
EPT
