Any ideas on how I could make this program run faster?
It's supposed to run under 0.5 seconds.
In some cases it does, in others it fails. [b]The task : [/b]
INPUT:
From the first line of the standard input read one integer (5 <= n <= 100000). Each of the following n lines will have one of the following two formats:
- 1 a - meaning that Mirko said aloud the number a, (0 <= a <= 65535).
- 2 k - meaning that Mirko asks what is the kth smallest number he has said so far. k will always be less or equal to the number of numbers Mirko has said aloud so far.
The total number of different number will not be bigger than 400, but some of the numbers can repeat!
OUTPUT:
To the standard output write one line for each of the 2 k inputs. Representing the kth smallest number at that moment.
Input:
7
1 0
1 1
1 5
2 1
2 3
1 2
2 3
Output:
0
5
2
My solution :
#include <stdio.h>
int main(){
unsigned short int * a;
unsigned int n,j,x,y;
int m=-1;
scanf("%u",&n);
a=new unsigned short int[n];
while (n>0){
n=n-1;
scanf("%u %u",&x,&y);
if (x==1){
m=m+1;
j=m;
a[j]=y;
while((j>0)&&(a[j]<a[j-1])){
y=a[j-1];
a[j-1]=a[j];
a[j]=y;
j=j-1;
}
Not really telling what you're doing, but I'd iteratively see which is the biggest as I pass each line, i.e, if number two is bigger than three, and two was bigger than one, then I don't need to compare one to three. This makes the scaling O(n), and the space (1)
int c(const void *a, const void *b) {
return *(const unsigned short *)a - *(const unsigned short *)b;
}
inline unsigned long read() {
unsigned long l = 0;
int c;
while (isspace(c = getchar()));
do l = l * 10 + (c - '0');
while ((c = getchar()) >= '0' && c <= '9');
ungetc(c, stdin);
return l;
}
int main(void) {
unsigned long n = read(), i = 0;
bool s;
unsigned short *a = malloc(n*sizeof(unsigned short));
if (!a) return EXIT_FAILURE;
while (n--) {
switch (read()) {
case 1:
a[i++] = read();
s = 0;
break;
case 2:
if (!s) {
qsort(a, i, sizeof(unsigned short), c);
s = 1;
};
printf("%u\n", a[read()-1]);
}
};
free(a);
}
Excuse me but these implementations does not provide enough error checking, I am quite frankly embarrassed at the lack of ROBUST ENTERPRISE solutions to this problem. There is also a sore lack of comments that explain to the reader what is going on. I also see some of you use optimizing flag with your compilers while you really should be using debugging flags, such harmful behavior does not make J. Darcy proud.
I provide an implementation that provides at least some rudimentary error checking.
/*
* TODO:
* - Change all mentions of io_buffer and IO_BUFFER_SIZE
* to input_buffer and INPUT_BUFFER_SIZE. The identifier
* is misleading as there is no output performed through
* the buffer.
*
* - Check the return values of fprintf and printf,
* something might go wrong in the output as well
* as the input, just checking the input is not
* enough.
*
* - Find a more scalable solution, the current solution
* is inefficient, but at least it is robust.
*
* - Add constants for the legal values of first input
* parameter n, currently they are hardcoded in the middle
* of file see lines 171-177.
*
* Maybe:
* - Migrate to stdbool.h, which provides a boolean type
* for details see ``stdbool.h''.
*/
#ifdef __bool_true_false_are_defined
/* this means that stdbool has been included
at a higher level */
/* we use the higher level bool type in
case the compiler optimizes some of
its use */
# define boolean bool
#else /* not __bool_true_false_are_defined */
/* we make our own boolean type */
/**
* @enum boolean
*
* @brief assumes one of two possible values true and false
*
* @true branches on an if-test represents truth, integrity and honesty
* @false does not branch on an if-test represents lies, falsehood and trickery
*/
typedef enum {
false = 0,
true = 1
} _boolean;
# define boolean _boolean
#endif /* __bool_true_false_are_defined */
/*
* CONSTANTS
*/
/**
* @constant LOWEST_VALUE
* @value 0
*
* @brief lowest possible value for input number
*/
#define LOWEST_VALUE 0
/**
* @constant HIGHEST_VALUE
* @value 65535
*
* @brief highest possible value for an input number
*/
#define HIGHEST_VALUE 65535
/**
* @constant NUMBER_RANGE
* @value (HIGHEST_VALUE - LOWEST_VALUE)
*
* @brief represents the range of possible input values
*
* Note that there might be a small bug in this implementation,
* we assume that every number between LOWEST_VALUE and HIGHEST_VALUE
* are valid input numbers, if this is not the case we might store
* an array of valid_numbers and things would look very different.
*/
#define NUMBER_RANGE (HIGHEST_VALUE-LOWEST_VALUE)
/**
* @constant IO_BUFFER_SIZE
* @value 256
*
* @brief size of input buffer in bytes
*/
#define IO_BUFFER_SIZE (256)
/* sanity checking is important. */
#if (HIGHEST_VALUE < LOWEST_VALUE)
# error "inane parameters for input number range"
#endif
/*
* GLOBALS
*/
/**
* @variable numbers
* @type boolean array
* @size NUMBER_RANGE + 1
*
* @brief holds true at the index of an input number and false otherwise
*
* The idea here is to store the input numbers based on their values.
* Will have all elements initialized to zero which is the same as
* @false.
*/
boolean numbers[NUMBER_RANGE + 1];
/*
* PROGRAM
*/
/**
* @function main
* @return (int) EXIT_SUCCESS on success or EXIT_FAILURE otherwise
*/
int main (void) {
/**
* @variable i
* @type int
* @default undefined
*
* @brief outer input for loop counter
*/
int i;
/**
* @variable n
* @type int
* @default 0
*
* @brief will hold the first input number
*
* Legal limits for this number is 5 <= n <= 100000.
*/
int n = 0;
/**
* @variable stored
* @type int
* @default 0
*
* @brief holds the number of inputted numbers
*/
int stored = 0;
if (fgets(io_buffer, IO_BUFFER_SIZE, stdin) == NULL) {
fprintf(stderr, "Error: no first parameter\n");
exit(EXIT_FAILURE);
} /* no input */
/* Read first parameter */
n = atoi(io_buffer);
if (n < 4 || n > 100000) {
fprintf(stderr,
"Error: invalid parameter %d\n"
"Must be in range 5 <= n <= 100000.\n",
n);
exit(EXIT_FAILURE);
} /* invalid input */
/* input loop */
for (i = 0; i < n; i++) {
/**
* @variable j
* @type int
* @default undefined
*
* @brief inner for-loop counter
*/
int j;
/**
* @variable endptr
* @type char *
* @default NULL
*
* @brief holds pointer to first invalid character in a string to integer conversion, see strtol (3) for details.
*/
char * endptr = NULL;
/**
* @variable first
* @type int
* @default undefined
*
* @brief holds the first input number from the stdin line ``number number''
*
* Legal limits for this number is 1 <= first <= 2.
*/
int first;
/**
* @variable second
* @type int
* @default undefined
*
* @brief holds the second input number from the stdin line ``number number''
*
* Legal limits for this number is based on @first.
* If @first is 1 then the limits are
* LOWEST_NUMBER <= second <= HIGHEST_NUMBER
* else if @first is 2 then the limits are
* 1 <= second <= stored
*/
int second;
/* we clear the input buffer
before reading a new line */
memset(io_buffer, '\0', IO_BUFFER_SIZE);
if (fgets(io_buffer, IO_BUFFER_SIZE, stdin) == NULL) {
fprintf(stderr,
"Error: expected input at line %d out of %d lines\n",
i, n);
exit(EXIT_FAILURE);
} /* no input */
/* a nonzero errno after
a strtol call means that
there was some error in
the string to integer
conversion phase */
/* for details on errno see
the POSIX entry on ``errno.h'' */
errno = 0;
first = strtol(io_buffer, &endptr, 0); /* read first number */
/* this is where the magic happens */
switch (first) {
case 1: /* first == 1 */
if (second < LOWEST_VALUE ||
second > HIGHEST_VALUE) {
fprintf(stderr,
"Error: invalid input size %d\n"
"Must be in range %d <= a <= %d.\n",
second,
LOWEST_VALUE, HIGHEST_VALUE);
exit(EXIT_FAILURE);
} /* invalid value */
/*
* We want to avoid artificially
* inflating stored in case we
* don't actually store a new number.
*
* The specifications stated clearly
* ``The total number of different number
* will not be bigger than 400, but some
* of the numbers can repeat!''.
*/
if (!numbers[second - LOWEST_VALUE])
stored += 1;
numbers[second - LOWEST_VALUE] = true;
break;
case 2: /* first == 2 */
if (second > stored) {
fprintf(stderr,
"Error: invalid input %d for second number\n"
"Tried to fetch the %d smallest input while only having stored %d numbers.\n",
second,
second, stored);
exit(EXIT_FAILURE);
} /* invalid value */
/* this is the inner loop where
we search for the smallest
number. */
for (j = 0; j < NUMBER_RANGE; j++)
if (numbers[j]) { /* found a number */
if (second == 1) { /* is it the one we're looking for? */
printf("%d\n", j + LOWEST_VALUE);
break;
} else { /* look again */
second -= 1;
}
} /* number found */
break;
default: /* illegal value for first */
fprintf(stderr,
"Error: invalid input %d for first number\n"
"Must be in {1, 2}.\n",
first);
exit(EXIT_FAILURE);
break;
}
}
>>19 /**
* @enum boolean
*
* @brief assumes one of two possible values true and false
*
* @true branches on an if-test represents truth, integrity and honesty
* @false does not branch on an if-test represents lies, falsehood and trickery
*/ truth, integrity and honesty lies, falsehood and trickery
What?
>>23 >>19
FORCED DOCUMENTION OF CODE line by line is considered harmful. That code is unreadable since you spend all the time looking at comments and have to look for the sparse code lines which are hidden away and spread out far and vast.
Name:
Joseph D. Darcy2011-12-26 4:06
>>27
It's not over-commented, most of that code actually isn't commented. It's not line by line and none of those comments are redundant.
You are clearly not an [b]ENTERPRISE[(b] individual.
i could post more stupid comments but you'd be anal pained over it I'm sure of that especially since you can't even do proper bbcode
Name:
Joseph D. Darcy2011-12-26 5:21
>>29
The only reason that BB-code failed was because the implementation of BB-code on this site lacks proper facilities for comments, I was attempting to comment how I closed the BB-code tags in a FIFO manner, something you apparently are unable to appreciate since you don't understand the value of documentation.
None of those comments are redundant, you don't seem to understand the concepts of code scalability, it's a different, more enterprise kind of scalability. It means that as your program grows, the maintainability does not degrade, if a programmer is new to the program and wants to know what a certain variable is for, he can just look up the generated HTML documentation and search for the identifier. Clearly if you only do toy programs in languages nobody else uses, documentation doesn't matter because you have it all in your head, but I'm so good at programming that I not only keep the code in my own head, but also in the head of others.
That being said, you are not an ENTERPRISE individual. You are probably angry because your horrible uncommented implementation fails in the cases where mine produces a clear error message and exits signaling failure. Well guess what, I am J. Darcy, my programs run faster, scale better, and are overall more well documented than yours, I have two masters degrees but I don't even need them, I get hired and payed just based on the comments in the LaTeX file used to compile my CV. That's right son, I am a lean mean coding machine, I can code around your anti-patterns any day of the week. If you ever want to get a real job someday, try to find the companies I work with, I might just tell them J. Darcy sent you.
>>33
With such a huge backlog it's easy to find effective trolls and then bump them or imitate their technique.
Name:
Anonymous2012-02-25 19:49
>>34
All you need is a neural network that is capable of imitating, and another one to find butthurt posters so that you can actually identify the posts that are written by effective trolls.