N個の数から最大の上位10個を選択[C言語版]

タイトル:
N個の数から最大の上位10個を選択する、順次出力する.
Nは最大1000億に達する可能性がある
各範囲は0-2147483647です.
C言語版のテスト結果:
100万入力
合計[10000000]個入力合計比較[20001654]回合計書き込みメモリ[552]回合計消費時間[0.014687 s]
C言語バージョンソリューション

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>

/* 
 * author: goosman.lei
 * mail: [email protected]
 * blog: http://blog.csdn.net/lgg201
 */

#define BUFF_LEN	(4096)

/* #define DEBUG */
#define INFO

typedef struct queue_s	queue_t;
struct queue_s {
	int		data;
	queue_t	*next;
};

static void generate_test_data(long n) {
	long	i;
	int		r;
	int		l;

	l	= sizeof(int);
	srand(time(NULL));
	for ( i = 0; i < n; i ++ ) {
		r	= rand();
		fprintf(stdout, "%d
", r);
		write(STDERR_FILENO, &r, l);
	}
}
static int read_input(int fd, void *buff, int buff_len) {
	int		i, ret;

	for ( i = 0; i < buff_len; ) {
		ret = read(fd, buff, BUFF_LEN);
		if ( -1 == ret ) {
			perror("read error
");
			exit(0);
		} else if ( 0 == ret ) {
			break;
		} else {
			buff	+= ret;
			i		+= ret;
		}
	}
	return i;
}

static void dump_link(queue_t *q, int n) {
	for ( ; q != NULL; q = q->next )
		fprintf(n ? stderr : stdout, "%d
", q->data);
	if ( n ) printf("
");
}

int main(int argc, char *argv[]) {
	int		*sbuff;
	int		i, j, n;
	queue_t	*rbuff, **tmp, *t;
#ifdef INFO
	int		s_0, s_1, s_2;
	struct timeval	begin, end;
#endif

	if ( argc < 2 ) {
		printf("usage: 
\t1.       : %s <number> /*                 ,                       */
\t2.   Top 10  : %s <exec> /*        10     (  ),   INFO            ,   DEBUG            
", 
			argv[0], argv[0]);
		return (0);
	}
	if ( strcmp(argv[1], "exec") != 0 ) {
		/*             */
		generate_test_data(atoi(argv[1]));
		return 0;
	}

	sbuff	= malloc(1024 * 1024 * 4);
	rbuff	= malloc(sizeof(queue_t) * 10);

	/*        */
	bzero(rbuff, sizeof(queue_t) * 10);
	for ( i = 0; i < 9; i ++ ) {
		(rbuff + i)->next	= (rbuff + i + 1);
		(rbuff + i)->data	= -1;
	}
	(rbuff + 9)->data	= -1;
	(rbuff + 9)->next	= NULL;

#ifdef DEBUG
	dump_link(rbuff, 1);
#endif
#ifdef INFO
	s_0	= 0;
	s_1	= 0;
	s_2	= 0;
	gettimeofday(&begin, NULL);
#endif
	while ( 0 != (n = read_input(STDIN_FILENO, sbuff, 1024 * 1024 * 4)) ) {
#ifdef INFO
		s_0 ++;
#endif
		j	= n / 4;
#ifdef INFO
		s_2	+= j;
#endif
		for ( i = 0; i < j; i ++ ) {
#ifdef INFO
			s_0 ++;
#endif
#ifdef DEBUG
			fprintf(stderr, "processing %d
", *(sbuff + i));
#endif
			for ( tmp = &rbuff; *tmp != NULL && *(sbuff + i) >= (*tmp)->data; ) {
				tmp = &((*tmp)->next);
#ifdef INFO
				s_0 += 2;
#endif
			}
#ifdef INFO
			s_0	++;
#endif
			if ( *tmp == rbuff ) {
				continue;
			}
#ifdef DEBUG
			fprintf(stderr, "tmp %d %p, rbuff %d %p
", (*tmp) == NULL ? -1 : (*tmp)->data, *tmp, rbuff->data, rbuff);
#endif
			rbuff->data	= *(sbuff + i);
#ifdef INFO
			s_1	++;
			s_0 ++;
#endif
			if ( *tmp != rbuff->next ) {
				t				= rbuff;
				rbuff			= rbuff->next;
				t->next			= NULL == *tmp ? NULL : *tmp;
				*tmp			= t;
#ifdef INFO
				s_1 += 4;
				s_0 ++;
#endif
			}
#ifdef DEBUG
			dump_link(rbuff, 1);
#endif
		}
	}
#ifdef INFO
	gettimeofday(&end, NULL);
#endif

	dump_link(rbuff, 0);

#ifdef INFO
	fprintf(stderr, "  [%d]   
    [%d] 
     [%d] 
    [%0.6fs]
", 
		s_2, s_0, s_1, (end.tv_sec * 1000000 + end.tv_usec - begin.tv_sec * 1000000 - begin.tv_usec) / 1000000.0);
#endif

	return 0;
}