梅子的Programming Pearls Problems Solutions(Column 1),然后我在filipegoncalves的基础上改成了多线程的版本。
10000000个数排序在200ms内。
//
// main.cpp
// bitmap_sort
//
// Created by Ryza 15/11/9.
// Copyright © 2015年 [data deleted]. All rights reserved.
//
#include <stdio.h>
#include <limits.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <unistd.h>
#include <pthread.h>
#define MAXINT 10000000
#define CHAR_BIT_LOG 3 /* assumes that CHAR_BIT == 8, so log_2(8) = 3 */
#define MASK (~(~0 << CHAR_BIT_LOG))
#define setbit(a, x) ((a)[(x) >> CHAR_BIT_LOG] |= 1 << ((x) & MASK))
#define isset(a, x) ((a)[(x) >> CHAR_BIT_LOG] & (1 << ((x) & MASK)))
char array[MAXINT + 1];
char * mbuf = NULL;
off_t len;
#define number_of_threads 8
pthread_t sort_tids[number_of_threads];
off_t parts[number_of_threads + 1] = { 0 };
void printnumbers();
void analyse(char *, off_t, off_t);
void * thread(void * arg) {
analyse(mbuf, parts[(long)(off_t *)arg], parts[(long)(off_t *)arg + 1]);
return nullptr;
}
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "[%s] Usage: %s input-file\n", argv[0], argv[0]);
return 1;
}
int fd = open(argv[1], O_RDONLY);
if (fd == 0) {
fprintf(stderr, "[%s] Could not open file %s\n", argv[0], argv[1]);
return 1;
}
len = lseek(fd, 0, SEEK_END);
mbuf = (char *)mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
parts[number_of_threads] = len;
for (int i = 1; i < number_of_threads; i++) {
parts[i] = len / number_of_threads * i;
while (mbuf[parts[i]] != ' ') {
parts[i]++;
}
}
for (int i = 0; i < number_of_threads; i++) {
pthread_create(&(sort_tids[i]), NULL, thread, reinterpret_cast<void *>(i));
pthread_join(sort_tids[i], NULL);
}
printnumbers();
return 0;
}
void analyse(char *buf, off_t from, off_t to) {
long long number = 0;
for (char *p=(char*)((long)(char*)buf + from);*p && p - buf < to; p++) {
if (*p == ' ') {
setbit(array, number);
number = 0;
} else {
number = number * 10 + *p - '0';
}
}
}
void printnumbers() {
int i;
for (i = 0; i <= MAXINT; i++)
if (isset(array, i))
printf("%d ", i);
}
Hi 通过V2EX了解到的 我也是小岛这所学校毕业的 能否给个联系方式 有空的话多多向你请教下