Need Help with a program in C

[fabianhjr]

Well,I am someone who is just getting started. As a matter of fact I also showed some code and got the response: terrible formatting. Now I got a great formatting and never forgot to comment when necessary. It is always important to learn from mistakes.

In Python you could do it with one less loop tough, it would still be less efficient.

Code: Select all

for i in range(num): print char * num

Other thing you could do(Pseudocode) is create a string and append the first char in each outer loop cycle.

Code: Select all

string me,int num
input me[0], num
for i  in range(num)
  output me
  me .= me[0]

[Arameus]

Well,I am someone who is just getting started. As a matter of fact I also showed some code and got the response: terrible formatting. Now I got a great formatting and never forgot to comment when necessary. It is always important to learn from mistakes.

In Python you could do it with one less loop tough, it would still be less efficient.

Code: Select all

for i in range(num): print char * num

Other thing you could do(Pseudocode) is create a string and append the first char in each outer loop cycle.

Code: Select all

string me,int num
input me[0], num
for i  in range(num)
  output me
  me .= me[0]

Actually, that Python code wouldn't work. It would output char to the screen num times. If char is "a", and num is 5, your code would do the following:

aaaaa
aaaaa
aaaaa
aaaaa
aaaaa

since num is always 5, you are printing char * 5, for num iterations. Here is how it should be done:

Code: Select all

num = input("Input your integer: ")
character = raw_input("Input your character: ")

for i in range(1, num + 1):
    print character * i


My Python is not as good as it used to be, since I've started learning C I almost never use it anymore. I think I will start programming Python modules in C, so I can stay sharp in both.

As far as efficiency, Python's interpreter is programmed in C, and I am willing to bet you they use a while or for loop (maybe even recursion, but I doubt it) to multiply the number of times to print out a string like that.

In your psuedocode, you use the assignment operator .= that I have never seen. What does that do? Would you mind translating that psuedocode into a real language so I can see how exactly it works? I see what you are doing, using a string and adding the extra char to it each time. Since a string is just an array of characters, I think that's more or less the same as just printing out the individual letters, since to print a string that is what it has to do beneath the hood.

are you trying to do this?

Code: Select all

num = input("Input your integer: ")
character = raw_input("Input your character: ")
string = character

for i in range(num):
    print string
    string += character


If so, that's a terrible way to do it, but I can see how as a Python programmer you would think that way. Honestly, Python people will do stuff like make string a list, use the append() function to add each character to it, and print them with print ''.join(string). One thing is for sure, the Python code you wrote is very elegant and simple, and I probably would not have thought to do it that way, though I'm not sure if that's because I am not used to using Python, or because you are just clever.

[thetan]

are you trying to do this?

Code: Select all

num = input("Input your integer: ")
character = raw_input("Input your character: ")
string = character

for i in range(num):
    print string
    string += character


If so, that's a terrible way to do it, but I can see how as a Python programmer you would think that way.

I'm interested in hearing your reasoning into why this would be a terrible solution. Off the top of my head i can think of at least 2 situations where it would be pretty efficient in comparison to other solutions posted thus far. I'm currently on the road coming back from a family weekend so i don't have the time to post anything too exciting at the moment.

However, expect me to either post again by the end of the night or to do an after post edit with more specifics on the situation. Either way i still look forward to hearing a more specific opinion on the mentioned code.

[Arameus]

are you trying to do this?

Code: Select all

num = input("Input your integer: ")
character = raw_input("Input your character: ")
string = character

for i in range(num):
    print string
    string += character


If so, that's a terrible way to do it, but I can see how as a Python programmer you would think that way.

I'm interested in hearing your reasoning into why this would be a terrible solution. Off the top of my head i can think of at least 2 situations where it would be pretty efficient in comparison to other solutions posted thus far. I'm currently on the road coming back from a family weekend so i don't have the time to post anything too exciting at the moment.

However, expect me to either post again by the end of the night or to do an after post edit with more specifics on the situation. Either way i still look forward to hearing a more specific opinion on the mentioned code.

It's a terrible way to do it because you still go through each character, just instead of printing them, you add them to a string and them print them, which is arbitrary anyway, since a string is just an array of characters. Also, you have to use one more variable. Now, instead of just having all the characters, you the an array of all the characters plus the actual variable that the character is in. Finally, you concatenate two strings EACH iteration, which is a lot more resource expensive than just printing them each iteration (which you still do in either version).

[fashizzlepop]

Interesting. How would you go about making it more efficient then?

[fabianhjr]

Yeah, I also want to hear that. .= is append.

If you move trough my pseudocode you will noticed that the string is appended it's first member to the end and printing the whole string in each cycle.(2 operations) + jump and increase i(4). That makes a total complexity of O(num*4).(@thetan am I right?)

Code: Select all

num = 5
char = 3
string = ''.join(char)
for i in range(num):
   print string
   string = string[:] + string[0]

[Arameus]

Interesting. How would you go about making it more efficient then?

fabianhjr's first way of doing it is more efficient. This way:

Code: Select all

num = input("Input your integer: ")
character = raw_input("Input your character: ")

for i in range(1, num + 1):
    print character * i


That is the best way I can think of doing it :/

[thetan]

It's a terrible way to do it because you still go through each character, just instead of printing them, you add them to a string and them print them, which is arbitrary anyway, since a string is just an array of characters. Also, you have to use one more variable. Now, instead of just having all the characters, you the an array of all the characters plus the actual variable that the character is in.

A string is indeed just an array of characters.

The usage of one more variable is arbitrary because a variable is just an identifier to a segment of memory.

Finally, you concatenate two strings EACH iteration, which is a lot more resource expensive than just printing them each iteration (which you still do in either version).

Any form of IO will always be an order of magnitude or 2 slower then memory access (in the case of small data as were handling it 3-4 orders of magnitude slower then CPU cache and register access). In which case memory manipulations become inconsequential in comparison to the actual IO. Meaning the appending of one byte is the more efficient of the two.

Also,
Function call overhead is typically more expensive then appending a single byte of information to a segment of memory. As with a function call much more data must be pushed to the stack (all the arguments, register states etc) which is significant compared to one lonely byte of data.

That in mind, sending the entire string to stdout all at once should allow your kernel to perform IO buffering much more efficiently and that alone should improve performance by an order of magnitude.

If you move trough my pseudocode you will noticed that the string is appended it's first member to the end and printing the whole string in each cycle.(2 operations) + jump and increase i(4). That makes a total complexity of O(num*4).(@thetan am I right?)

Code: Select all

num = 5
char = 3
string = ''.join(char)
for i in range(num):
   print string
   string = string[:] + string[0]

Well, it depends on how you would go about abstracting big-o. Iteratively (given that strings in python track head + tail) i don't see why it wouldn't be an O(n) operation iteratively. Which is the way big-o is normally used to display the complexity of the solution. If you want to dissect on a per iteration basis though then yeah, you big-o would hold true for a per-iteration representation.

Anyways, i'm pulling an all nighter at the office and i have nothing better to do tonight so i'll compile some different solutions, and post them with time benchmarks, memory utilization benchmarks and cache hit benchmarks. In other words, i'll be having lots of fun with Valgrind tonight <3

EDIT1:
Ok, here are some basic simple implementations in C. Ran it through a quick benchmark and the difference is largely negligible.I'm willing to place good money that the bottleneck is the actual IO. Anways, heres what i got so far.

loopdeloop

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void loopdeloop(char c, int m)
{
    int i, j;
   
    for (i = 0; i < m; i++)
    {
        for (j = -1; j < i; j++) printf("%c", c);
        printf("\n");
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 1000; i++) loopdeloop('a', 75);
   
    return 0;
}


stack

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void stack(char c, int m)
{
    char s[512];
    int i, j;
   
    // impose arbitrary stack limit
    if (m >= 512) return;
   
    for (i = 0; i < m;)
    {
        s[i] = c;
        s[++i] = '\0';
        printf("%s\n", s);
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 1000; i++) stack('a', 75);
   
    return 0;
}



and the results are as follows:

Code: Select all

$time ./loopdeloop
...
...
...
real    0m17.679s
user    0m0.204s
sys     0m0.196s

$time ./stack
...
...
...
real    0m16.941s
user    0m0.064s
sys     0m0.224s


Whatever, this is largely unfair though so should be taken with a grain of salt, i'll remove the IO and then well get some usable benchmarks. just give me a minute ..............

[Arameus]

When you do print char * i, it doesn't call print 6 times. It means print (char * i), so it evaluates char * i and prints that. Thus, there aren't any more function calls than if you had printed it as a string. Concatenating the characters into a string just adds an extra (necessary) step.

I'm gonna be honest here, Thetan, you are throwing some pretty big words my way and I don't know what a good portion of them refer to.

[fashizzlepop]

Thetan's a babe.