• 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

H

Harpuia

Member
I'm doing some simple algorithm analysis atm. Though I'm not sure if I'm getting all the right stuff down. Here's the code that my professor showed us of the selection sort:

Code: 
#include <iostream>

using namespace std;

int find_Max(int*, int);
void swapElements(int*, int, int);

int main()
{
    int n = 10;
    int *arr = new int[n];

    arr[0] = 8;
    arr[1] = 5;
    arr[2] = 2;
    arr[3] = 6;
    arr[4] = 9;
    arr[5] = 3;
    arr[6] = 1;
    arr[7] = 4;
    arr[8] = 0;
    arr[9] = 6;


    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;


    for(int i = n; i > 0; i--)
    {
        swapElements(arr, find_Max(arr, i), i-1);
    }

    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    delete[] arr;

   return 0;
}

int find_Max(int *arr, int last)
{
    int index = 0;
    for(int j = 1; j < last; j++)
    {
        if(arr[index] < arr[j]) index = j;
    }


    return index;

}

void swapElements(int *arr, int index, int last)
{
        int temp = arr[last];
        arr[last] = arr[index];
        arr[index] = temp;

}

Some minor questions
A) How do I assign all the elements at once of a dynamically created array?

B) Does every single array access count? The if statement inside the two for loops gets accessed at worst, every single time for n-1 times. In otherwords, working inside out, the if statement gets executed 2(n-1) times?

My professor ended up getting T(n) = 3/2(n^2) +3/2(n) - 3 as the actual run time of the problem. Now selection sort is very obviously O(n^2) due to the for loops. I'm having trouble determining what actually contributes to running time. AFAIK, every ; signifies 1, and for loops multiply 1 by however many times it must be run.
 
T

tokkun

Member
Harpuia said:
Some minor questions
A) How do I assign all the elements at once of a dynamically created array?

B) Does every single array access count? The if statement inside the two for loops gets accessed at worst, every single time for n-1 times. In otherwords, working inside out, the if statement gets executed 2(n-1) times?
Click to expand...

A) You can't. If you know the array contents at compile time, that's usually a sign you should be using a static array rather than a dynamic one.

B) There is no universal rule for what constant costs to assign to a single statement. The number of actual instructions it takes to evaluate that IF statement depends on the compiler and the processor's ISA. You will need to ask your professor what constant costs he is using.

If I had to take a guess, I would say that your professor is probably counting the conditional (if(arr[index] < arr[j])) as one instruction and the body (index = j) as one instruction, making its cost 1 or 2, depending on whether the conditional resolves to 'true'.
 
H

Harpuia

Member
tokkun said:
A) You can't. If you know the array contents at compile time, that's usually a sign you should be using a static array rather than a dynamic one.

B) There is no universal rule for what constant costs to assign to a single statement. The number of actual instructions it takes to evaluate that IF statement depends on the compiler and the processor's ISA. You will need to ask your professor what constant costs he is using.

If I had to take a guess, I would say that your professor is probably counting the conditional (if(arr[index] < arr[j])) as one instruction and the body (index = j) as one instruction, making its cost 1 or 2, depending on whether the conditional resolves to 'true'.
Click to expand...

That makes sense. I wanted to dynamically create the array in case of fiddling around with this code in the future.

I've been looking around, and some places I've come up with seem to count both array accesses in the if statement as 2, and worst case scenario the if actually is true, another statement, for 3 total statements.

This seems to be a lot closer to what he got on the board, so now I have 3(sum_j=0^(n-1) n-j)
 
T

tokkun

Member
Harpuia said:
That makes sense. I wanted to dynamically create the array in case of fiddling around with this code in the future.

I've been looking around, and some places I've come up with seem to count both array accesses in the if statement as 2, and worst case scenario the if actually is true, another statement, for 3 total statements.

This seems to be a lot closer to what he got on the board, so now I have 3(sum_j=0^(n-1) n-j)
Click to expand...

If they are counting the conditional as 2 instructions, it probably isn't because of the array accesses. It's probably the comparison and the branch being considered separate instructions.

i.e.

Code: 
bool a = b > c;  // ONE
if (a) {  // TWO
  ...      // THREE (optional)
}

Though again, this is not a rule, and ultimately comes down to what your processor supports in its ISA.
 
H

Harpuia

Member
tokkun said:
If they are counting the conditional as 2 instructions, it probably isn't because of the array accesses. It's probably the comparison and the branch being considered separate instructions.

i.e.

Code: 
bool a = b > c;  // ONE
if (a) {  // TWO
  ...      // THREE (optional)
}

Though again, this is not a rule, and ultimately comes down to what your processor supports in its ISA.
Click to expand...

Thanks man! I've decided to conclude that going by the rules in the texbook for the class, I should come up with a correct answer. Just ran a worst case scenario for the sort, and the equation I came up with produced the same result as a tracker that counted whenever anything was executed. The equation being T(n) = n^2 -2n - 5 = O(n^2)
 
N

nOoblet16

Member
Guys, I want to create a particle rendering system that simulates collision, preferably in OpenGL. My coding experience is that of a beginner/intermediate but I am wondering where to start and what to read. Some help would be appreciated.
 
C

close to the edge

Member
SailorCosmos said:
Hi guys,

I am writing this on behalf of a friend who needs some help.

My friend has to write a UDP chat program. Here is the code he has so far.

...

He has to add a checksum like behavior to the program(something like writing the length of the message before the message and having the client verify it upon arrival) and an encryption/decryption algorithm as well. I have suggested that he use something like the Caesar cipher for the encryption/decryption. My friend would appreciate any advice or help you guys could give him on how to implement the checksum and encryption/decryption. I would help him but I myself am not that good at programming.
Click to expand...
Should the encryption actually do anything or is it just pro forma? Caesar's cipher is ridiculously easy to crack. If you want to actually secure your chat program, you should use one of the classes in javax.crypto. A checksum that only checks the length of the message is also not really enough at all since it ignores all errors that leave the message at its intended length but flip one or more bits in the message. For a simple (but cryptographically insecure) hash function he could look Adler-32.
 
oxrock

oxrock

Gravity is a myth, the Earth SUCKS!
I've ran into quite an annoying problem and I was hoping someone among us might have knowledge about it that could possibly help.

The problem is that a sprite that's created to represent a player is stuck at it's spawn location. A spawn location which btw is not where I tell it to spawn and won't accept coordinates to spawn elsewhere, it will only spawn there which happens to be the top left corner of the screen. I had my program print out it's location continuously while running as well as the commands to change it's coordinates and it's receiving updated information as it should, the sprite just won't move. It acts the same way as if I have it bumping against an impenetrable wall.

relavent python/pygame code:

Code: 
class Player(pygame.sprite.Sprite):
     #This class represents the Player. 
     
    def __init__(self):
        #Set up the player on creation. 
        # Call the parent class (Sprite) constructor
        pygame.sprite.Sprite.__init__(self) 
        #draws on the sprite
        self.image = pygame.image.load("spaceship.png").convert_alpha() 
        # scales sprite based on resolution
        self.image = pygame.transform.scale(self.image,(width // 8,height // 7))

        self.rect = self.image.get_rect()
        self.rect.y = y                                      #sets initial spawn point  to x and y which are variables
        self.rect.x = x                                      # set to the middle of the screen earlier in the program
        
         
    def update(self):
        # Update the player's position. #
       
        
     
        # Set the player's x,y coordinates to that of movex, movey
        self.rect.x = movex    #movex and movey are a means for changing x and y via player input
        self.rect.y = movey

.... calling the player class.....

player = Player()  #creates the player sprite that gets manipulated via the player class
player_list.add(player) #adds the new player to both lists to aid in tracking and updating
all_sprites_list.add(player)

......mean while inside the game function....
all_sprites_list.update()  #forces all sprites within the list to refer to their class's update function
all_sprites_list.draw(screen) #auto magically draws all the new sprites

pygame.display.flip()   #actually renders the updated imagery for entire program.

That should be anything relevant to the sprite in question. I of course can provide further information if it's requested, I just didn't want to post massive blocks of code in here as it would probably scare people away. :p
 
G

Granadier

Is currently on Stage 1: Denial regarding the service game future
First thing that comes to mind is that your paint method isn't receiving location data. Top left corner is the default (0, 0) location.

Check this area of your code for errors. (The constructor code and whatever code your sprite is calling)
Code: 
# Call the parent class (Sprite) constructor
pygame.sprite.Sprite.__init__(self) 
#draws on the sprite
self.image = pygame.image.load("spaceship.png").convert_alpha()
 
oxrock

oxrock

Gravity is a myth, the Earth SUCKS!
Gattsby said:
First thing that comes to mind is that your paint method isn't receiving location data. Top left corner is the default (0, 0) location.

Check this area of your code for errors. (The constructor code and whatever code your sprite is calling)
Code: 
# Call the parent class (Sprite) constructor
pygame.sprite.Sprite.__init__(self) 
#draws on the sprite
self.image = pygame.image.load("spaceship.png").convert_alpha()
Click to expand...

the sprite location isn't actually 0,0 though. In this case it's (100, 85) @ 800x600 res. When I change the resolution the relative position stays the same however the actual x and y values change. @ 1920,1080 resolution for example, the x and y values are (240, 154). I'm assuming if it's as you suggested, the sprite location would just be 0,0 regardless.
 
oxrock

oxrock

Gravity is a myth, the Earth SUCKS!
the topleft of the sprite is at 0,0 so it looks like your suggestion is right on the money. I have no idea why it won't update properly though.

edit: 5 hours staring at this stupid thing just to realize
Code: 
self.rect.x = movex    #movex and movey are a means for changing x and y via player input
self.rect.y = movey

simply needed to be
Code: 
self.rect.x += movex    #movex and movey are a means for changing x and y via player input
self.rect.y += movey

stupid plus sign before the equal sign made all the difference. I just kept assigning the value to movey,movex values instead of increasing it by that amount.
 
SailorCosmos

SailorCosmos

Member
close to the edge said:
Should the encryption actually do anything or is it just pro forma? Caesar's cipher is ridiculously easy to crack. If you want to actually secure your chat program, you should use one of the classes in javax.crypto. A checksum that only checks the length of the message is also not really enough at all since it ignores all errors that leave the message at its intended length but flip one or more bits in the message. For a simple (but cryptographically insecure) hash function he could look Adler-32.
Click to expand...

The encryption is just pro forma. What my friend has to do is for an assignment so it doesn't have to be anything very advanced so that is why I recommended he do some simple encryption and checksum.
 
G

Granadier

Is currently on Stage 1: Denial regarding the service game future
oxrock said:
the topleft of the sprite is at 0,0 so it looks like your suggestion is right on the money. I have no idea why it won't update properly though.

edit: 5 hours staring at this stupid thing just to realize
Code: 
self.rect.x = movex    #movex and movey are a means for changing x and y via player input
self.rect.y = movey

simply needed to be
Code: 
self.rect.x += movex    #movex and movey are a means for changing x and y via player input
self.rect.y += movey

stupid plus sign before the equal sign made all the difference. I just kept assigning the value to movey,movex values instead of increasing it by that amount.
Click to expand...

Glad to see you got it figured out. I didn't notice that either.
You may want to try an if/else statement for that player movement. I could be wrong, but I think that just using the '+=' to change the position will continue to increase the position to the right/down. You won't be able to decrease the value for left/up movement.
 
oxrock

oxrock

Gravity is a myth, the Earth SUCKS!
Gattsby said:
Glad to see you got it figured out. I didn't notice that either.
You may want to try an if/else statement for that player movement. I could be wrong, but I think that just using the '+=' to change the position will continue to increase the position to the right/down. You won't be able to decrease the value for left/up movement.
Click to expand...

adding a negative is the same as a subtraction so it works out :)

Anyhow, the game is far from perfect but I've done enough to be happy with it and call it quits. I sincerely hope you all take a look, it's gone through some mega changes!

Click for supreme awesomeness!
 
H

harSon

Banned
Need some help. I'm making a number guessing game that A) Asks the user for a number 1 - 8 B) Randomizes a number and C) Compares the input and randomized number to see if they're equal, and if not, the user is given two more attempts to guess correctly. I was trying to implement counters that kept track of the attempts, wins and losses, but my wins seems to start out at 1969623394 and my losses starts at -2:

Any ideas?
 
G

Granadier

Is currently on Stage 1: Denial regarding the service game future
Code: 
int wins, losses, attempts = 0;

I'm not very familiar with C, but is this line setting all three variables to 0 or is it setting 'attempts' to 0 and leaving the other two uninitialized?
 
H

harSon

Banned
Gattsby said:
Code: 
int wins, losses, attempts = 0;

I'm not very familiar with C, but is this line setting all three variables to 0 or is it setting 'attempts' to 0 and leaving the other two uninitialized?
Click to expand...

I'm an idiot :)

That was leftovers from when I was writing pseudo code... No clue how I missed that while looking for the error I was looking for LOL.
 
S

smokeandmirrors

Banned
parsing this xml data was fine but for some reason I cannot for the life of me find this error out where part of the data gives me an error when importing it into sqlite3.

There's like 20 files and atleast 30,000 items and the first 4 files work fine, after that there's an issue with it and it's pissing me off. The one table giving me the error has 6 elements but some of the data from the later files is being read as 2?

Any ideas on how I can stomp this bug out? because I am completely lost.
 
C

close to the edge

Member
I have a C++ question. I have this small project and I want to be able to compile it on Linux as well as on Windows. It compiles fine on Windows with Visual Studio 2013 but on Linux, clang++ freaks the fuck out. The errors are in the BitSet32 class, I'll just post the first few ones here:
Code: 
clang++ -Wall -std=c++11 -g -c BitSet32.cpp
In file included from BitSet32.cpp:2:
./BitSet32.h:13:24: error: expected ')'
        BitSet32 and(BitSet32 other) const;
                              ^
./BitSet32.h:13:14: note: to match this '('
        BitSet32 and(BitSet32 other) const;
                    ^
./BitSet32.h:13:30: error: expected ';' at end of declaration list
        BitSet32 and(BitSet32 other) const;
                                    ^
                                    ;
./BitSet32.h:14:2: error: must use 'class' tag to refer to type 'BitSet32' in this scope
        BitSet32 or(BitSet32 other) const;
        ^
        class 
./BitSet32.h:13:15: note: class 'BitSet32' is hidden by a non-type declaration of 'BitSet32' here
        BitSet32 and(BitSet32 other) const;
                     ^
./BitSet32.h:14:11: error: expected member name or ';' after declaration specifiers
        BitSet32 or(BitSet32 other) const;
        ~~~~~~~~ ^
./BitSet32.h:15:2: error: must use 'class' tag to refer to type 'BitSet32' in this scope
        BitSet32 xor(BitSet32 other) const;
        ^
        class 
./BitSet32.h:13:15: note: class 'BitSet32' is hidden by a non-type declaration of 'BitSet32' here
        BitSet32 and(BitSet32 other) const;
                     ^
I've put up a repository of the whole project including the Makefile here: http://wambo.at:85/GyrosOfWar/micro16/tree/master
I can't make much sense out of the errors, it's been a while since I've done C++
 
W

Water

Member
close to the edge said:
I've put up a repository of the whole project including the Makefile here: http://wambo.at:85/GyrosOfWar/micro16/tree/master
I can't make much sense out of the errors, it's been a while since I've done C++
Click to expand...
Site gives some login page instead of the project.

My theory: you are naming methods as "and", "or" and "xor". All of those are C++ keywords that you are supposed to be able to use instead of &&, || and ^. As a result, your code (interpreted correctly) is gibberish, and that's what clang sees; if you were to replace the words with the normal operator notation, you'd get the same errors. The code only compiles in VS because VS is non-conforming and doesn't support the standard keywords.
 
C

close to the edge

Member
Water said:
Site gives some login page instead of the project.

My theory: you are naming methods as "and", "or" and "xor". All of those are C++ keywords that you are supposed to be able to use instead of &&, || and ^. As a result, your code (interpreted correctly) is gibberish, and that's what clang sees; if you were to replace the words with the normal operator notation, you'd get the same errors. The code only compiles in VS because VS is non-conforming and doesn't support the standard keywords.
Click to expand...

Oh, I didn't know that. That sucks. Also, I didn't realize the repository was private. It should work now. I'll try renaming the methods.

Yeah, that helped. Had to make some other small changes as well (including <string> in some files).
 
S

smokeandmirrors

Banned
Water said:
Been an option for >15 years now according to the standard. But hey, I'm sure Microsoft will get their conformance in order soon.
Click to expand...

Huh. Well I guess you do learn something new every day.

And now i'm having an issue. Using an updated sqlite and now I suddenly can't use a multi-character separator? what gives.

I forgot to save the string when calling string.replace( ) and that was the source of my error. Guh.
 
Big Chungus

Big Chungus

Member
Anyone know if you can setup a small Microsoft SQL database using Visual Studio 2010?

I need to get some practice making Windows Forms using LINQ to SQL.
 
Zoe

Zoe

Member
fna84 said:
Anyone know if you can setup a small Microsoft SQL database using Visual Studio 2010?

I need to get some practice making Windows Forms using LINQ to SQL.
Click to expand...

No access to SQL server? If you're going to do MS development, you should really go for it.
 
Big Chungus

Big Chungus

Member
Zoe said:
No access to SQL server? If you're going to do MS development, you should really go for it.
Click to expand...

Nope, I don't have access to a SQL server.

I was thinking of renting one just to get some experience with it and to help study for future school exams.

Not sure where to rent one and how much they cost.
 
G

Granadier

Is currently on Stage 1: Denial regarding the service game future
fna84 said:
Nope, I don't have access to a SQL server.

I was thinking of renting one just to get some experience with it and to help study for future school exams.

Not sure where to rent one and how much they cost.
Click to expand...

If you are a student you should have access to DreamSpark.
I'm pretty sure you can get the server software from there.
 
C

Chris R

Member
I'm pretty sure you can setup a local DB from Visual Studio, and if not isn't SQL Server Express free???

edit: And ya, Linq To SQL is so damn nice, wish more people would use it... I make sure my DB design is exactly what it needs to be and the Linq To SQL takes care of the rest.
 
K

Kalnos

Banned
LINQ is a strange thing. I have seen some really nice LINQ queries and some hideous ones... not much in-between. Learn how to use the => operator ASAP.
 
U

usea

Member
I don't use linq to sql, but I do use linq. A lot. Like, I'd write my whole program in just linq if I could. Also the query syntax is shit; method syntax forever.

It's the best thing to happen to C#. By a mile.
 
Zoe

Zoe

Member
usea said:
I don't use linq to sql, but I do use linq. A lot. Like, I'd write my whole program in just linq if I could. Also the query syntax is shit; method syntax forever.

It's the best thing to happen to C#. By a mile.
Click to expand...

I use stored procedures for my DB calls, but I do use Linq for my collections from time to time.
 
L

Laurentius

Member
Internship interview this afternoon. Wish me luck. It's for a company that produces some pretty cool open source software that I bet a few of you have used. Hopefully it goes well.
 
O

Onemic

Member
How often are C-Style null terminated strings actually used in programming? By how much my C++ course has focused on them, it seems that they are extremely important
 
W

Water

Member
Onemic said:
How often are C-Style null terminated strings actually used in programming? By how much my C++ course has focused on them, it seems that they are extremely important
Click to expand...

In C++ you pretty much shouldn't use them at all. They are both unsafe, inefficient and hard to use compared to a proper string class. Old APIs give you C strings sometimes, but you can convert directly into std::string or another decent string.

That said, it may be your course is just using them as an excuse to get you to do stuff with pointers.
 
Y

Ya no

Member
Hey GAF,

I have a java program I've been looking at that I'm trying to understand all the different parts. I was hoping someone could look at the two lines below and tell me what exactly they're doing...

Code: 
LinkedQueue<Customer> customerQueue = new LinkedQueue<Customer>();
      
int[] cashierTime = new int[MAX_CASHIERS];

For the first line, is it just creating a new LinkedQueue named customerQueue from the Customer class?

For the second line, I know it's creating an array. If MAX_CASHIERS = 10, does that mean the array holds the integers 0-10? or does it hold just the number 10? or does it just create an array with 10 spaces with no values?

Thanks
 
G

Granadier

Is currently on Stage 1: Denial regarding the service game future
leroidys said:
Best of luck. When in doubt, hashtables!
Click to expand...

Why do you say that? Genuine curiosity.

Ya no said:
Hey GAF,

I have a java program I've been looking at that I'm trying to understand all the different parts. I was hoping someone could look at the two lines below and tell me what exactly they're doing...

Code: 
LinkedQueue<Customer> customerQueue = new LinkedQueue<Customer>();
      
int[] cashierTime = new int[MAX_CASHIERS];

For the first line, is it just creating a new LinkedQueue named customerQueue from the Customer class?

For the second line, I know it's creating an array. If MAX_CASHIERS = 10, does that mean the array holds the integers 0-10? or does it hold just the number 10? or does it just create an array with 10 spaces with no values?

Thanks
Click to expand...

Not sure about the first line because I haven't dealt with LinkedQueue, but

The second line is creating an int array with the amount of spaces stored in the MAX_CASHIERS constant. In this case, 10 spaces. (index 0 - 9)

Edit: beaten, read rhfb's instead.
 
C

Chris R

Member
Ya no said:
Hey GAF,

I have a java program I've been looking at that I'm trying to understand all the different parts. I was hoping someone could look at the two lines below and tell me what exactly they're doing...

Code: 
LinkedQueue<Customer> customerQueue = new LinkedQueue<Customer>();
      
int[] cashierTime = new int[MAX_CASHIERS];

For the first line, is it just creating a new LinkedQueue named customerQueue from the Customer class?

For the second line, I know it's creating an array. If MAX_CASHIERS = 10, does that mean the array holds the integers 0-10? or does it hold just the number 10? or does it just create an array with 10 spaces with no values?

Thanks
Click to expand...

The first line is creating a LinkedQueue that will ONLY deal with the Customer class. This is good, because you won't be able to insert a string for example, and will know that everything you get from it will be a Customer.

The second line is creating an array of default integer values with a size of MAX_CASHIERS. So if MAX_CASHIERS is 10, you now have an array that can hold 10 different integer values, each initialized to zero.
 
You must log in or register to reply here.

Similar threads

Ken Kutaragi is the Greatest 'emperor' Of All Time and remains SIE's only true visionary
Opinion 2 3 4
156
14K
GAF machine replied
Nvidia reports record earnings, profits on growth in AI and gaming
Business Analysis Hardware 2
68
5K
FStubbs replied
Dave the Diver |OT| Life is better, down where's it wetter
|OT| Indie 2 3
133
11K
Aenima replied
WWE and Endeavor (UFC) announce 21 billion dollar deal.
40
3K
thefool replied
A Windows user's experiences with Linux (should you switch?)
Opinion Analysis 2 3 4
190
16K
twilo99 replied
Top Bottom