Царям сишки

Merge-sort по-моему подходит лучше.

Тут вот есть моя имплементация для linked-lists: http://www.dim13.org/cgi-bin/cvsweb/src/lsort/

Для N = кол-во элементов, надо ⌈√N шагов. Для 3-х элементов — 2 шага.

проверь на {1, 3, 2}

It seems that this manner of sorting would be less productive than sort3b

оптимизатор оптимизировал, оптимизировал, да не выоптимизировал

Почему лучше? И так же 3 сравнения:

3 2 1

3 2 1

3 2 1

3 12 - первое

1 3 2 - второе

1 2 3 - третье

цари, короли и императоры

С прописной буквы, пожалуйста.

Два:

in: [3 2 1]
[[2 3] [1]]
[[1] [2 3]]

Одна перестановка, одно сравнение, два или с двумя сдвигами и свитч.

A = _mm_set_epi32(a,b,c,0);
B = _mm_shuffle(A, (1,2,3) -> (2,3,1));
C = _mm_cmpgt_epi32(A, B);
switch( C[0] << 2 | C[1] << 1 | C[2] ) {
 case 1 : {c,b,a};break;
 case 2 : {b,a,c};break;
 case 3 : {b,c,a};break;
 case 4 : {a,c,b};break;
 case 5 : {c,a,b};break;
 case 6 : {a,b,c};break;
}

Ну так это повезло, что единица сразу в голову вставилась. А если 3 2 5?

Если массивов будет очень много, упрётся в память.

Ты же мне напишешь сортировку хотябы 3-х елементов, которая упрётся в память?

Если массивов будет не слишком много, может ворваться агрессивный оптимизатор.

Ахриненная история и как конкретно он ворвётся ты нам не скажешь и почему ты не осилишь написать бенч в котором он не ворвётся тоже?

Эксперты подтянулись. Масочка не написалась?

Одна перестановка, одно сравнение, два или с двумя сдвигами и свитч.

2 ора у пацана не посчиталось? Ещё штук 5мувов тоже.

И к чему ты что-то там считаешь? Давай, высирай бенч или пиши рабочую функцию.

ТСу подумать на досуге: какое минимальное количество сравнений надо, чтобы отсортировать 5 элементов?

Балаболки на досуге подумать: каким образом минимальное кол-во сравнений связано с быстротой даже для 5-ти елементов.

подсказка: ответ есть в одном из томов Кнута. Но лучше подумать самому, это не трудно.

Куллстори. Я жду твои ваяния от кнута.

К чему ты это высрал? Причем тут qsort()? Нахрен ты ТС"ишь херню?

А как надо?

Брать минимальное значение, оно ближе к правильным значениям. Медиана и среднее — это методики измерения из реального мира, где флуктуации стрелки вольтметра могут быть в обе стороны. Усреднением и выкидыванием выбросов помехи усредняют. Так как они считаются шумом с нулевым ожиданием, это имеет смысл.

В бенчмарках все помехи делают результаты только хуже, но никогда не делают его лучше, то есть ошибка всегда больше нуля.

Ты же мне напишешь сортировку хотябы 3-х елементов, которая упрётся в память?

О, а вот и царь пришёл.

Вообще-то qsort указатели двигает, структуры на месте останутся.

Да и пофиг. Погрешность ±тапок вполне меня устраивает.

Вообще-то нет

Кнут дональда это что-то вроде куртки бейна.

Если у тебя массив структур, то двигает структуры. Если массив указателей на структуры, то указатели.

Если ты ему на вход дашь массив указателей на структуры, то структуры на месте останутся, только указатели будут передвинуты, т.к. не умеет qsort memmove делать. Да и незачем это!

А передавать ему на вход не массив указателей, а именно массив структур — это ж ССЗБизм.

Если ты ему на вход дашь массив указателей на структуры, то структуры на месте останутся, только указатели будут передвинуты

Это уже не сортировка структур, а сортировка указателей. qsort всегда перемещает элементы переданного массива.

не умеет qsort memmove делать.

qsort сортирует указанный массив вне зависимости от размера элемента. чего он там не умеет?

Да и незачем это!

если структура маленькая быстрее будет перемещать саму структуру чем по указателям ходить

qsort сортирует указанный массив вне зависимости от размера элемента.

Т.е. таки делает memmove? Жесть!

Наверняка для size == sizeof(void*) в glibc сделана оптимизация. Это же glibc, там даже strstr сделан не наивно, а через кнута-морриса-пратта с фоллбеком на ещё один какой-то адовый алгоритм для маленьких строк.

Вот — более правильная методика тестирования, разброс меньше 5% получается.

Итак, несмотря на то, что в тактах дольше выполнялась sort3c, в секундах таки шустрей получается. Невероятно, но факт.

qsort практически не зависит от уровня оптимизации, как и в тактах было.

Наилучшим временем для sort3a получилось ~110нс, для sort3c — ~73нс, а qsort в наносекундах совсем плох: 2200нс == 2.2мкс.

#include <stdio.h>
#include <time.h>

/*
 * Timings:
 * -Ox    sort3a       sort3c       qsort
 * 0    2.0978e-07   1.3690e-07   2.2661e-06
 * 1    1.1083e-07   8.7079e-08   2.2120e-06
 * 2    1.1385e-07   8.4983e-08   2.2280e-06
 * 3    1.0896e-07   7.2876e-08   2.2179e-06
 */


int arra[5][3] = {{3,2,1}, {3,6,4}, {7,5,8}, {1024,5543,9875}, {1001,-1001,1002}};
int arrb[5][3] = {{3,2,1}, {3,6,4}, {7,5,8}, {1024,5543,9875}, {1001,-1001,1002}};
int arrc[5][3] = {{3,2,1}, {3,6,4}, {7,5,8}, {1024,5543,9875}, {1001,-1001,1002}};

static inline void sort3a(int *d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); const int b = max(d[x], d[y]); d[x] = a; d[y] = b;}
	SWAP(0, 1);
	SWAP(1, 2);
	SWAP(0, 1);
#undef SWAP
#undef min
#undef max
}

static inline void sort3b(int *d){
#define CMPSWAP(x,y) {if(d[x] > d[y]){const int a = d[x]; d[x] = d[y]; d[y] = a;}}
	CMPSWAP(0, 1);
	CMPSWAP(1, 2);
	CMPSWAP(0, 1);
#undef CMPSWAP
}

static inline void sort3c(int *d){
	register int a, b;
#define CMPSWAP(x,y) {a = d[x]; b = d[y]; if(a > b){d[x] = b; d[y] = a;}}
	CMPSWAP(0, 1);
	CMPSWAP(1, 2);
	CMPSWAP(0, 1);
#undef CMPSWAP
}

static int cmpints(const void *p1, const void *p2){
	return (*((int*)p1) - *((int*)p2));
}

double timediff(struct timespec *tstart, struct timespec *tend){
	return ((double)tend->tv_sec + 1.0e-9*tend->tv_nsec) -
		   ((double)tstart->tv_sec + 1.0e-9*tstart->tv_nsec);
}

int main(){
	double t1, t2, t3;
	struct timespec tstart, tend;
	int i;
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < 5 ; i++){
		sort3a(arra[i]);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t1 = timediff(&tstart, &tend);
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < 5 ; i++){
		sort3c(arrb[i]);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t2 = timediff(&tstart, &tend);
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < 5 ; i++){
		qsort(arrc[i], 3, sizeof(int), cmpints);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t3 = timediff(&tstart, &tend);
	printf("%g, %g, %g; ", t1, t2, t3);
}

Эдди, ты совсем заболел? Там всего шесть вариантов:

123// два сравнения 1 < 2 < 3, ноль перестановок
132// три сравнения 1 < 3 > 2, затем 1 < 2, потому что первых двух сравнений недостаточно, одна перестановка.
213// дальше сам
231
312
321

Вообще не понимаю, какой смысл мерить наносекунды? Всё таки лучше тебе не делать бенчмарки никогда

Давай, сделай свой. Чего ты трындишь только, как тот царь?

Ну так давай — пиши аналогичный тест.

Вот только все равно у тебя будут сравнения → время будет тратиться. И скорость от этого значительно не подымешь.

А вообще, ясен пень, что кошерней было бы сгенерировать бешеный массив из массивов по 3 числа, скопировать его трижды, да измерить каждым способом. Но ломает.

А вообще, ясен пень, что кошерней было бы сгенерировать бешеный массив из массивов по 3 числа, скопировать его трижды, да измерить каждым способом. Но ломает.

А данные в кеш не влезут? Тут, если выйдет, надо бы какой-нибудь не in-place аналог использовать.

А я уже всё сделал в своей проге, лол. Правда ничего особенного не добился

При чем здесь кэш? В общем, вот, сделал тестилку: три идентичных массива на 10млн троек целых. Считается время сортировки каждым способом. Код + результат (в комментарии вначале):

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

#define NMEMB 10000000

/*
 * Timings (in seconds):
 * -Ox    sort3a    sort3c     qsort
 * 0     0.22787    0.24655    0.54751
 * 1     0.034301   0.120855   0.543839
 * 2     0.032332   0.102875   0.515567
 * 3     0.032472   0.102684   0.514301
 */

static inline void sort3a(int *d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); const int b = max(d[x], d[y]); d[x] = a; d[y] = b;}
	SWAP(0, 1);
	SWAP(1, 2);
	SWAP(0, 1);
#undef SWAP
#undef min
#undef max
}

static inline void sort3c(int *d){
	register int a, b;
#define CMPSWAP(x,y) {a = d[x]; b = d[y]; if(a > b){d[x] = b; d[y] = a;}}
	CMPSWAP(0, 1);
	CMPSWAP(1, 2);
	CMPSWAP(0, 1);
#undef CMPSWAP
}

static int cmpints(const void *p1, const void *p2){
	return (*((int*)p1) - *((int*)p2));
}

double timediff(struct timespec *tstart, struct timespec *tend){
	return (((double)tend->tv_sec + 1.0e-9*tend->tv_nsec) -
		   ((double)tstart->tv_sec + 1.0e-9*tstart->tv_nsec));
}

int main(){
	double t1, t2, t3;
	int *arra, *arrb, *arrc;
	struct timespec tstart, tend;
	int i, nmemb = 3*NMEMB;
	// generate
	i = nmemb * sizeof(int);
	arra = malloc(i);
	arrb = malloc(i);
	arrc = malloc(i);
	srand(time(NULL));
	for(i = 0; i < nmemb; i++){
		arra[i] = arrb[i] = arrc[i] = rand();
	}
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < nmemb ; i+=3){
		sort3a(&arra[i]);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t1 = timediff(&tstart, &tend);
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < nmemb ; i+=3){
		sort3c(&arrb[i]);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t2 = timediff(&tstart, &tend);
	clock_gettime(CLOCK_MONOTONIC, &tstart);
	for(i = 0; i < nmemb ; i+=3){
		qsort(&arrc[i], 3, sizeof(int), cmpints);
	}
	clock_gettime(CLOCK_MONOTONIC, &tend);
	t3 = timediff(&tstart, &tend);
	printf("%g, %g, %g; ", t1, t2, t3);
}

Итак, опять у qsort практически константное время, а вот sort3a выполз вперед. Вывод: у меня до этого слишком все шустро считалось, поэтому и был глюк.

Итак, qsort по крайней мере в 16 раз медленнее тупого пузырька для случая из трех элементов. Можно и для большего количества элементов взять из сниппетов готовые последовательности SWAP(x,y) и посмотреть, на каком же количестве элементов пузырек перестанет выигрывать у qsort, но это уж сам делай. Мне неохота, да и надо работой таки заняться.

Ну так давай — пиши аналогичный тест.

дык там писать много. У меня где-то был подобный код, найти не могу что-то.

ладно, написал, лови:

#include <stdio.h>

inline void swap(int a[], int i, int j)
{
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

inline void sort3(int a[])
{
	if(a[0]<a[1])
	{
		if(a[1]<a[2])
			return;
		// 0<1>2
		if(a[0]<a[2])
		{// 0<2<1
			swap(a, 1, 2);
			printf("① ");
			return;
		}
		// 2<0<1
		printf("② ");
		int tmp = a[2];
		a[2] = a[1];
		a[1] = a[0];
		a[0] = tmp;
		return;
	}
	// 1<0
	if(a[1]<a[2])
	{// 0>1<2
		if(a[0]<a[2])
		{// 1<0<2
			printf("③ ");
			swap(a, 0, 1);
			return;
		}
		// 1<2<0
		printf("④ ");
		int tmp = a[2];
		a[2] = a[0];
		a[0] = a[1];
		a[1] = tmp;
		return;
	}
	// 2<1<0
	printf("⑤ ");
	swap(a, 0, 2);
}

void print3(const int a[])
{
	int j;
	for(j=0; j<3; j++)
		printf("%d%c", a[j], j<2? ',': ' ');
}

int main()
{
	int aa[][3] = {
		{1,2,3},
		{1,3,2},
		{2,1,3},
		{2,3,1},
		{3,1,2},
		{3,2,1}
	};
	int j;
	for(j=0; j<6; j++)
	{
		print3(aa[j]);
		sort3(aa[j]);
		print3(aa[j]);
		printf("\n");
	}
	return 0;
}

это минимальное количество действий. А по времени — не знаю. Теоретически должно быть самым быстрым.

а вот и нет: тупой sort3a все равно быстрей оказался:

/*
 * Timings (in seconds):
 * -Ox    sort3a    sort3c     qsort       sort3batty
 * 0     0.22787    0.24655    0.54751     0.25193
 * 1     0.034301   0.120855   0.543839    0.095754
 * 2     0.032332   0.102875   0.515567    0.087575
 * 3     0.032472   0.102684   0.514301    0.087387
 */

а вот и нет: тупой sort3a все равно быстрей оказался:

то-ли у тебя оптимизатор глючит, то-ли inline не сработало.

давай, показывай, что в машинном коде. objdump -M intel -S a.out

В бенчмарках все помехи делают результаты только хуже, но никогда не делают его лучше, то есть ошибка всегда больше нуля.

Очень и очень спорно.

Очень и очень спорно.

Спорь, я с интересом послушаю аргументы.

Что такое медиана измерений, я как-то себе представляю.

Минимум — абсолютно неинформативная вещь. Да, есть какое-то минимальное время, меньше которого программа работать не может. Но что с того? Что ты с этим минимальным временем будешь дальше делать? Какой его физический смысл? А никакого.

При чем здесь кэш?

Ну если у тебя массив на over 9000 массивов по 3, они целиком в кеш не влезут, и придется принимать во внимание разные флуктуации в работе твоей проги, лол.

Я, собственно, уже сказал, как я бы сделал

вроде заинлайнилось

Что ты с этим минимальным временем будешь дальше делать? Какой его физический смысл? А никакого.

«Быстрее на этом железе быть не может». А какой физический смысл у медианы? Её значение зависит не только от самого эксперимента, но и от неучтённого числа неучтённых помех. В этом значении смысла намешано так много, что его как будто и вовсе нет.

Медиана ближе к реальности. А твой минимум — это как расстояние в тапках мерить...

Медиана — я могу ожидать, что если запущу эту программу, то на её выполнение потребуется приблизительно столько времени.

А какой физический смысл у медианы? Её значение зависит не только от самого эксперимента, но и от неучтённого числа неучтённых помех.

Когда я буду реально использовать эту программу, все эти помехи будут присутствовать. Мне не интересно знать сферическую производительность в вакууме, которая _никогда_ не достигается в реальных условиях.

убери нафиг timediff из теста. Как и вообще время. Сделай тест просто циклом в котором тестируется ШЕСТЬ принципиально разных комбинаций, других не бывает.

ты предлагаешь замерять не скорость кода, а среднюю загруженность твоей тачки

«Быстрее на этом железе быть не может»

Кстати, а почему параллельные реализации сортировки не используют?

Моё имхо, что когда ты делаешь много итераций одного алгоритма в более-менее одних условиях, то эти помехи будут вносить довольно предсказуемый вклад в результат. Просто достаточно сделать, скажем, 100000 итераций на одних и тех же входных данных и замерить время в начале теста и в конце.

Скажем, от одной итерации ты можешь получить совершенно разные результаты от разных P-state'ов или бог ещё знает от чего. А когда прога уже поработает какое-то время, результаты должны стабилизироваться.

Кстати, а почему параллельные реализации сортировки не используют?

Аааа.... Для 3-х элементов? )

Я не про 3 элемента, я вообще во всяких libc.