LINUX.ORG.RU
Форум — Development  

Царям сишки

 


3

2

А могут ли многоуважаемые цари, короли и императоры сишки создать такую функцию для сортировки, которая бы работала для 3 элементов быстрее, чем стандартный qsort()? Я не могу и не думаю, что это возможно. Но я знаю, что истинный царь смог бы. Итак, конкурс объявляю открытым. Победителю достанется... силенд, может быть?



Последнее исправление: lisper-pipisper (всего исправлений: 2)
← BLAS и поэлементые действия и срезы
Работа над двумя патчами одновременно... →
 ← 1 2 3 4

Ты хоть погуглил бы снипеты для сортировки массивов из конечного числа элементов! Все уже придумано до нас!!!

Здесь как раз пузырек нужен. В данном случае — три операции: 

cmpmv(0,1); 
cmpmv(1,2);
cmpmv(0,1);
Макрос cmpmv сам напишешь?

Eddy_Em ☆☆☆☆☆
() 
int a01 = a[0] <= a[1];
int a02 = a[0] <= a[2];
int a12 = a[1] <= a[2];
if ((!a01) && (!a12))
   return;
if ((a01) && (a12))
{
   swap(a[0], a[2]);
   return;
}
if ((a01) && (!a12))
{
   swap(a[0], a[1]);
   swap(a[1], a[2]);
   return;
}
if ((!a01) && (a12))
{
   swap(a[1], a[2]);
   swap(a[0], a[1]);
   return;
}

Как-то так, возможно что-то упустил

sambist ★★
()

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

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

unt1tled ★★★★
()
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от sambist

Для трех элементов столько условий? Дабавьте еще штук 10.

andreyu ★★★★★
()

Я не могу и не думаю, что это возможно. Но я знаю, что истинный царь смог бы.

Это, конечно лютый вброс, но сказал ты очень хорошо, красиво.

Aswed ★★★★★
()

А могут ли многоуважаемые цари, короли и императоры сишки создать такую функцию для сортировки, которая бы работала для 3 элементов быстрее, чем стандартный qsort()?

AFAIK «стандартный qsort(3)» юзает для этого insert sort.

Я не могу и не думаю, что это возможно.

можно. Просто тупо рассмотри все варианты. Нужно ровно 2½ сравнений.

Итак, конкурс объявляю открытым.

шёл-бы ты Кнута осилил. У него там и другие задачки имеются.

emulek ★
()
Ответ на: комментарий от sambist

Как-то так, возможно что-то упустил

ты упустил тот факт, что если A<B && B<C, то третьего сравнения не нужно.

emulek ★
()
Ответ на: комментарий от anonymous

std::sort - это сиплюсплюс, в вопрос про реализацию на с. Ты сравниваешь бегуна и велосипедиста.

Aswed ★★★★★
()

А ты азартен, Парамоша! (с)

mos ★★☆☆☆
()

по приколу можно так: 

int x[3]
...
// упорядочим тройку:
if ((x[0]-x[1])*(x[1]-x[2])<0) swap(x,0,1);
// и если направление сортировки важно:
if (x[0]-x[2]<0) swap(x,0,2)

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

А теперь посмотри, что у тебя будет на выходе для массива {3,2,1}: первый шаг даст {3,2,1}, второй шаг опять даст {3,2,1}

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от lisper-pipisper

советуют какой-то кнут

А ты забавный =D

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от lisper-pipisper

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

i-rinat ★★★★★
()

Я не могу

Бенчмарк наверное корявый написал?

anonymous
()
Ответ на: комментарий от i-rinat

Использовать не in-place алгоритм? Тогда массива будет только 2. Ну и опять цикл. Фактически все алгоритмы будут в равных условиях

lisper-pipisper
() автор топика
Ответ на: комментарий от Eddy_Em

Тоже мне. Царь бы сам написал, а не стыбздил с stack overflow.

А вообще мне надо сначала подумать в целесобразности что-то сортировать

lisper-pipisper
() автор топика
Ответ на: комментарий от lisper-pipisper

Фактически все алгоритмы будут в равных условиях

Тогда стоило обвязку сделать, чтобы все в равных условиях писали. Если кто-то вообще что-то будет делать.

i-rinat ★★★★★
()

Давай уже с плюсами сравнивать, чо уж там

template <typename T>
constexpr inline const T &_min(const T &a, const T &b) { return (a < b) ? a : b; }
template <typename T>
constexpr inline const T &_max(const T &a, const T &b) { return (a < b) ? b : a; }
template <typename T>
constexpr inline const T &_bound(const T &min, const T &val, const T &max)
{ return _max(min, _min(max, val)); }

fluorite ★★★★★
()
Ответ на: комментарий от Eddy_Em

Вот, набросал пример: 

#include <stdio.h>

static __inline__ unsigned long long rdtsc(void){
	unsigned hi, lo;
	__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
	return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
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}};


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
}

int main(){
	unsigned long long time1, time2;
	int i;
	time1 = rdtsc();
	for(i = 0; i < 5 ; i++){
		sort3a(arra[i]);
	}
	time1 = rdtsc() - time1;
	time2 = rdtsc();
	for(i = 0; i < 5 ; i++){
		sort3b(arrb[i]);
	}
	time2 = rdtsc() - time2;
	printf("Time is %llu (A) & %llu (B)\nData:\n\n", time1, time2);
	for(i = 0; i < 5; i++)
		printf("A[%d]: %d, %d, %d\n", i, arra[i][0], arra[i][1], arra[i][2]);
	printf("\n");
	for(i = 0; i < 5; i++)
		printf("B[%d]: %d, %d, %d\n", i, arrb[i][0], arrb[i][1], arrb[i][2]);
}

Запускаем с O0: 

gcc -O0 11.c -o sorting && ./sorting 
Time is 408 (A) & 384 (B)
Data:

A[0]: 1, 2, 3
A[1]: 3, 4, 6
A[2]: 5, 7, 8
A[3]: 1024, 5543, 9875
A[4]: -1001, 1001, 1002

B[0]: 1, 2, 3
B[1]: 3, 4, 6
B[2]: 5, 7, 8
B[3]: 1024, 5543, 9875
B[4]: -1001, 1001, 1002
вывод убираем, чтобы поднакопить статистику: 
printf("%llu\t%llu\n", time1, time2);
Все, таперча проверяем: 
gcc -O0 11.c -o sorting 
echo -n "median([" > tmpout; for i in $(seq 1 100); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   450   414

gcc -O1 11.c -o sorting
echo -n "median([" > tmpout; for i in $(seq 1 100); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   108.00   145.50

gcc -O2 11.c -o sorting
echo -n "median([" > tmpout; for i in $(seq 1 100); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   123   138

gcc -O3 11.c -o sorting
echo -n "median([" > tmpout; for i in $(seq 1 100); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   105   156
Забавно, да? Кто бы мог подумать что первый код, вроде как более жрущий ресурсы, в итоге соптимизируется значительно лучше, чем второй!

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Кстати, по 1000 интересней получается: результаты по времени уже более точны.

-O0 дает 453 405

-O1 дает 108 141

-O2 — 126 138

-O3 — 108 147

Вот такие пироги — ионогда и наоптимизировать можно себе же в убыток!

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Вот такие пироги — ионогда и наоптимизировать можно себе же в убыток!

Забавно, ага

lisper-pipisper
() автор топика
Ответ на: комментарий от Eddy_Em

Едрена сковородка! На -O1 или -O2 можно сделать еще быстрей: 

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
}

Результаты: 

/*
 * It seems that this manner of sorting would be less productive than sort3b
 * but even on -O1 it gives better results (median by 1000 seq);
 * sort3c works best until -O3:
 * -Ox  timing a    timing b   timing c
 *   0   444        396        243
 *   1   108        144        93
 *   2   126        141        93
 *   3   105        138        159
 */
Кинул себе в сниппеты, авось пригодится.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

В данном случае непонятно, что ж такого наделал gcc на -O3, что третий вариант стал так тормознуто работать.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

А теперь посмотри, что у тебя будет на выходе для массива {3,2,1}: первый шаг даст {3,2,1}, второй шаг опять даст {3,2,1}

И что ??? первый шаг делает упорядоченную тройку, второй при необходимости приводит её к «неубывающему» виду.

зы. зря ты в треде упираешь на линейку из 3-х swapv - академически для «сортировки на месте» 3-х чисел нужно не более двух сравнений и стольких-же обменов, а аппаратные (на стеке,регистрах и особенностях архитектуры) варианты выиграет виртуальный камень с инструкцией srt3

MKuznetsov ★★★★★
()

(записал царей в отдельный списочек)

anonymous
()
Ответ на: комментарий от Eddy_Em

Эдди, а почему твоя методика тестирования настолько убога? Ты делаешь какие-то выводы всего лишь по 5 проходам, к тому же 4 из них работают уже на отсортированных данных (как минимум из того, что я вижу прямо щас CMPSWAP может при этом не делать 2 присваивания). При разных запусках твоей софтины, у меня результаты только так прыгают. Ты же ученый, Эдди!

lisper-pipisper
() автор топика
Ответ на: комментарий от Eddy_Em

К тому же, какой смысл мерить такты? Явно ты меришь что-то совсем не то.

lisper-pipisper
() автор топика
Ответ на: комментарий от lisper-pipisper

Shit! Я забыл третий массив забульбенить.

Теперь вот как: 

/*
 * It seems that this manner of sorting would be less productive than sort3b  or sort3c
 * but even on -O1 it gives better results (median by 1000 seq):
 *
 * -Ox  timing a    timing b   timing c
 *   0   453        402        366
 *   1   111        174        147
 *   2   126        165        144
 *   3   117        171        141
 */
Т.е. таки первый вариант какого-то фига оптимизируется круче!

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от lisper-pipisper

Ты внимательно читал? Я 1000 раз запускаю и считаю медиану!

Результаты меняются не очень-то и сильно. Вот: 

gcc -O3 11.c -o sorting 

echo -n "median([" > tmpout; for i in $(seq 1 1000); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   114   168   141

echo -n "median([" > tmpout; for i in $(seq 1 1000); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   105   171   141

echo -n "median([" > tmpout; for i in $(seq 1 1000); do ./sorting >> tmpout; done; echo "])" >> tmpout; cat tmpout | octave -q
ans =

   117   168   141
Можно и время считать. Только это нужна функция, которая наносекунды возвращает. Либо генерировать гигантский тестовый массив.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Код: 

#include <stdio.h>

static __inline__ unsigned long long rdtsc(void){
	unsigned hi, lo;
	__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
	return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
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));
}

int main(){
	unsigned long long time1, time2, time3;
	int i;
	time1 = rdtsc();
	for(i = 0; i < 5 ; i++){
		sort3a(arra[i]);
	}
	time1 = rdtsc() - time1;
	time2 = rdtsc();
	for(i = 0; i < 5 ; i++){
		sort3c(arrb[i]);
	}
	time2 = rdtsc() - time2;
	time3 = rdtsc();
	for(i = 0; i < 5 ; i++){
		qsort(arrc[i], 3, sizeof(int), cmpints);
	}
	time3 = rdtsc() - time3;
	printf("%llu, %llu, %llu; ", time1, time2, time3);
}

Eddy_Em ☆☆☆☆☆
()

Что-то я не понял, а куда, собственно, царь подевался? Скоро уже вторая страница темы пойдет, а он так и не рассказал, какие мы тут все "лалки анскильные" ☺

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

А, ну ладно, уговорил )

Надо мне что-то такое запилить. Только у меня не числа, а структуры. qsort тут плох тем ещё, что он их перемещает. А может быть вообще можно как-то отказаться от сортировки

lisper-pipisper
() автор топика
Ответ на: комментарий от Eddy_Em

Я 1000 раз запускаю и считаю медиану!

Медиану. В бенчмарке. На системах с многозадачностью. На процах со скачущей частотой. Ага.

i-rinat ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2 3 4
← BLAS и поэлементые действия и срезы
Development
Работа над двумя патчами одновременно... →