Graal Forums Programming Exercise #1
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#31
11-29-2007, 09:07 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by Tolnaftate2004 The maximum size of the intersect should be the size of the small array as it cannot possibly have more elements in common than there are in the set.
I was half asleep, good point xD
I actually read my post before yours and was about to correct that (does so)
 __________________
#32
11-29-2007, 10:37 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
 Also, the method you proposed for determining the intersection gives duplicates.
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#33
11-29-2007, 10:54 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by Tolnaftate2004 Also, the method you proposed for determining the intersection gives duplicates.

PHP Code:
```   temp.intersect = new[smallerarray.size()];  for(e: temp.largerarray)   temp.b.("v"@e) = true;  for(e: smallerarray)   if(temp.b.("v"@e)) {     temp.intersect[temp.j] = e;     temp.b.("v"@e) = false;     temp.j++;   }  ```
I should also point out that its O(n+m)
 __________________

Last edited by Kristi; 11-29-2007 at 11:06 PM..
#34
11-29-2007, 11:08 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Kristi PHP Code: ```   temp.intersect = new[smallerarray.size()];   for(e: temp.largerarray)    temp.b.("v"@e) = true;   for(e: smallerarray)    if(temp.b.("v"@e)&&!(temp.c.("v"@e))) {      temp.intersect[temp.j] = e;      temp.c.("v"@e) = true;      temp.j++;    }  ```
Okay, so why the temp.intersect array now? We can just do:

PHP Code:
```   for(e: smallerarray)    if(temp.b.("v"@e))       temp.c.("v"@e) = true;   temp.intersect = temp.c.getdynamicvarnames();  ```
I think O(getdynamicvarnames) ~ O(temp.intersect[temp.j++] =), at worst. I suppose the only issue here would be getting the size to optimize the set-making and the eventual substrings. Just some thoughts...
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#35
11-29-2007, 11:11 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by Tolnaftate2004 Okay, so why the temp.intersect array now?
I changed it to falsify b instead, i guess while you were typing this up.
However, im not sure which would work faster. when i get home and have access to my rc ill find out by averaging the run times :P

creating temp.c set means creating and moving a lot of pointers. it might be faster to assign the intersects directly to the array instead of getting dynamic variable names because of it. Ill report back tonight
 __________________
#36
11-30-2007, 12:00 AM
 xAndrewx Registered User Join Date: Sep 2004 Posts: 5,260
 whats the use in this? I wouldn't use this in a script... lol Make a exercise that'll come in handy !!!!
 __________________ email: [email protected]
#37
11-30-2007, 12:04 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by xAndrewx I wouldn't use this in a script... lol
That's not really the point of the thread. We're trying to solve problems as efficiently as possible, which is a skill that will come in handy.
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#38
11-30-2007, 12:06 AM
 xAndrewx Registered User Join Date: Sep 2004 Posts: 5,260
 why if you're not intending to use it? i'm asking for you to base your exercises on something that'll come in handy
 __________________ email: [email protected]
#39
11-30-2007, 12:13 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by xAndrewx why if you're not intending to use it?
It's good practice.
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#40
11-30-2007, 12:53 AM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by xAndrewx why if you're not intending to use it? i'm asking for you to base your exercises on something that'll come in handy
Mathematical and computational efficiency is the basis of programming
 __________________
#41
11-30-2007, 01:45 AM
 Bell Registered User Join Date: Feb 2007 Posts: 1,824
 What Hell isn't telling you is he's using Graal to get his teaching degree and using you guys to do his homework for him.
 __________________ For support contact http://support.toonslab.com/
#42
11-30-2007, 04:57 AM
 Tigairius The Cat Join Date: Jan 2007 Location: Missouri, USA Posts: 4,240
Quote:
 Originally Posted by Bell What Hell isn't telling you is he's using Graal to get his teaching degree and using you guys to do his homework for him.
Hell Raven? A teacher scary...
 __________________ “Shoot for the moon. Even if you miss, you'll land among the stars.”
#43
11-30-2007, 05:01 AM
 Kyranki Freelance Coder Join Date: Aug 2007 Location: At the end of the rainbow, in the pot of gold. Posts: 202
Quote:
 Originally Posted by Tigairius Hell Raven? A teacher scary...
Hey! I'm a testament to his teaching abilities :<
 __________________ Stan.
#44
11-30-2007, 05:12 AM
 Tigairius The Cat Join Date: Jan 2007 Location: Missouri, USA Posts: 4,240
Quote:
 Originally Posted by Kyranki Hey! I'm a testament to his teaching abilities :<
Even scarier
 __________________ “Shoot for the moon. Even if you miss, you'll land among the stars.”
#45
11-30-2007, 06:39 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Kyranki Hey! I'm a testament to his teaching abilities :<
Where were you in this thread then?! :P
No offense, Hell Raven...
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

 Tags programming-exercise