Царям сишки

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

Да, это всё верно. Имеет смысл ещё измерять «ничего», гоняя пустые циклы, чтобы вычислить время, затрачиваемое именно на циклы. Но где ты это видишь в тестах в этом треде? Тут мизерная операция производится пять раз. Ни о какой предсказуемости тут речи быть не может. Выбирать минимум — единственный разумный вариант.

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

Я говорил о сравнительной оценке скоростей небольших участков кода. А о чём говоришь ты? О производительности программы целиком? Тогда да, усреднение имеет смысл.

Мне кажется, что задачи у этих алгоритмов более специфические. Не будешь же ты на том же C создавать лишние потоки, чтобы тем же bitonic сортом отсортировать хоть 100 эл-тов

ну я и не согласен, как эдди делает свои тесты

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

Скорость кода — штука бессмысленная. Скорость кода на моей тачке — более-менее понятно.

Да, это всё верно. Имеет смысл ещё измерять «ничего», гоняя пустые циклы, чтобы вычислить время, затрачиваемое именно на циклы. Но где ты это видишь в тестах в этом треде? Тут мизерная операция производится пять раз. Ни о какой предсказуемости тут речи быть не может. Выбирать минимум — единственный разумный вариант.

Да, тест в треде вообще ни о чем не говорит.

которая бы работала для 3 элементов быстрее, чем стандартный qsort()?

stacksort?))

Может так?

static inline void sort3_sorting_network_simple_swap(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(1, 2);
SWAP(0, 2);
SWAP(0, 1);
#undef SWAP
#undef min
#undef max
}

И что это за тест будет? Измерение длины питона в попугаях?

Как алгоритм не назови, всё равно на 3 эл-тах происходит одно и то же ) Я, например, делал, вспоминая selection sort

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

Тут только ассемблер ковырять разве что.

блжад, Эдди, тут всего ШЕСТЬ вариантов, проверь их ВСЕ.

И сделай это Over9000 раз.

Ну и время посчитай, за сколько оно Over9000×6 сортировок сделает.

В твоём коде какая-то дикая смесь SSE и обычных команд, и не факт, что обычные команды не зависят от SSE команд.

И да, сделай ещё и сортировку double, ну и каких-то структур с нетривиальной compare().

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

ВНЕЗАПНО: больше всего времени qsort проводит сортируя маленькие обрывки в 2, 3, и 4 длинной. Т.е. быстродействие qsort в основном и определяется быстродействием процедуры, сортирующей маленькие массивы. Ну с сортировкой array[2] ничего не сделать, там одно сравнение и ½ перестановка, а вот за array[3] можно и нужно бороться.

Вот поэтому я и предложил ТСу проверить, на каком количестве элементов qsort начинает рвать пузырек.

А насчет "бороться" — ты попробуй нетривиальный алгоритм нарисуй для сортировки девяти чисел. Нафиг-нафиг, проще готовье взять (то, что у меня обзывается sort3a).

Кстати, еще есть методики "неполной сортировки" для быстрого поиска медианы, тоже использую, т.к. часто изображения или одномерные данные нужно фильтровать скользящей медианой.

сортируя маленькие обрывки в 2, 3, и 4 длинной.

Узнаём количество элементов, если мало -> применяем сортировку через сеть.

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

По идее это должно быть быстрее на OoO процессорах.

Вот поэтому я и предложил ТСу проверить, на каком количестве элементов qsort начинает рвать пузырек.

AFAIK на семи-шести. IRL используют простые вставки, там пологий оптимум где-то на 10..13 (т.е. на 13 qsort чуть лучше простых вставок, на 10 обычно чуть хуже). Пузырёк AFAIK никто и никогда не применяет в чистом виде даже не из-за среднего (которое O(N²)), а из-за худшего случая(который O(N³)).

А насчет «бороться» — ты попробуй нетривиальный алгоритм нарисуй для сортировки девяти чисел.

insert sort. Зачем мне что-то пробовать? Я и так знаю, какой оптимальный алгоритм.

Нафиг-нафиг, проще готовье взять (то, что у меня обзывается sort3a).

у тебя самодельный велосипед с квадратными колёсами.

Кстати, еще есть методики «неполной сортировки» для быстрого поиска медианы

я в курсе. Кстати, они не влияют на скорость qsort.

у тебя самодельный велосипед с квадратными колёсами

А вот хрен: это как раз та самая сортировка вставками (sort3a).

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

По идее это должно быть быстрее на OoO процессорах.

вывод неправильный по двум причинам:

1. что тебе мешает обычными средствами сортировать сами обрывки? Т.е. если qsort разделила массив в 7 на две части по 3 и 3, то что тебе мешает форкнуться, и сортировать на одном ядре первую тройку, а на втором ядре вторую тройку? Это лучше, чем форкаться внутри сортировок троек для одновременного сравнения(к тому же, последовательность следующих сравнений зависит от результатов предыдущих).

2. сортировка проводится в RAM. У тебя уже есть две раздельные RAM? Или у тебя лишь несколько ядер, и одна RAM, как у меня? Пойми: два ядра могут сделать два сравнения сразу, но вот только одно RAM не сможет дать два набора данных для сравнения.

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

А вот хрен: это как раз та самая сортировка вставками (sort3a).

при сортировке вставками, последовательность

2,   3,  1
[0],[1],[2]

[2]→tmp
[1]→[2]
[0]→[1]
tmp→[0]

что тебе мешает форкнуться

Оверхед.

Это лучше, чем форкаться внутри сортировок троек для одновременного сравнения

Зачем форкаться?
Вопрос - сортировать мелкие массивы одним алгоритмом, а крупные - другим.

сортировка проводится в RAM.

Кэши и предзагрузка.

два ядра могут сделать два сравнения сразу

Повторюсь про пайплайн и OoO. При отсутствии зависимости по данным, и одно ядро сможет несколько сравнений сразу.

последовательность следующих сравнений зависит от результатов предыдущих

Не факт, перестановки могут и параллельно идти:

Different from algorithms like quick sort All operations are planned out in advance (aka data-independent or oblivious) Any given sorting network only works on a fixed size input

0) 2,3,1
1) 2,3,1
2) 2,1,3
3) 1,2,3

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
}

ВНЕЗАПНО: больше всего времени qsort проводит сортируя маленькие обрывки в 2, 3, и 4 длинной. Т.е. быстродействие qsort в основном и определяется быстродействием процедуры, сортирующей маленькие массивы

Первое предложение похоже на какое-то откровение, а дальше идут глубокие выводы. А как ещё должен работать алгоритм, в котором заложено деление пополам? Ведь у нас всего 2 половинки, а четвертинок уже 4, а восьмеринок так вообще 8! Вот и приходится бедному алгоритму возиться с восьмеринками и прочими мелочами. Более того, у алгоритмов, в сложности которых есть логарифм, так или иначе заложено деление пополам или ещё на какие-нибудь более-менее равные части. Только как мы видели, для массивов из маленького количества эл-тов (скажем, 3) все эти алгоритмы сводятся к одному в 3 сравнения. Так что не для того придумывали все эти алгоритмы, чтобы одним сортировать 3 эл-та, а другим 4, а из-за всяких разных «хороших» входных данных, где один алгоритм может работать быстрее другого.

Детский сад вас читать. За 3 эл-та боретесь, такты считаете.

Узнаём количество элементов, если мало -> применяем сортировку через сеть.

Лол, а какой смысл в этом, когда глубина будет почти такая же, сколько и элементов, ха-ха-ха

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

За 3 эл-та боретесь, такты считаете.

Предлагаю писать сортировки на Java.

Предлагаю писать сортировки на Java.

Ну-ка объясни мне, чем это плохо, а то я не в курсе

Давай на жабкоскрипте, с чтением данных для сортировки из бинарного файла ☺

Ознакомься:

Сортировка списка. Помогите отладить.

Пользуясь случаем, хочу спросить, какого типа в Си выражение *ptr. Например:

my_type x;
my_type *p = &x;

*p /* <-- какой тип? */

В C++ понятно какой - my_type &, ссылка то есть. Но в Си ссылок нет. Вот туплю сижу.

my_type

Не, тогда бы мы с копией данных работали, ведь в Си семантика значений.

my_type foo();

foo(); /* вот тут тип my_type, но мы при изменении изменять будем копию */

По сути, мы никак сами не можем в языке выразить саму операцию разыменования, т.к. мы не сможем описать тип возвращаемого значения.

Я ответил. Как знаешь

Ну так ответ неверный. Если бы в си была семантика ссылок, как почти везде, то да. В общем проблема в том, что в языке си есть операции, которые нельзя описать псевдофункцией. В C++ - можно, а в си - нет. Меня это беспокоит.

my_type foo()
my_type & bar()

А ведь я всегда считал, что си более целостен, чем кресты. Вот ведь отстой-то.

6.5.3.2 Address and indirection operators
...
The unary* operator denotes indirection. If the operand points to a function, the result is a function designator; if it points to an object, the result is an lvalue designating the object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’
...

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

C++

struct my_ptr { int * p; };
...

int & deref(my_ptr p) { return *p; }

...

deref(x) = 10; // ok

C

struct my_ptr { int * p; };
...

/* Что мне тут написать??? */ deref(my_ptr p) { return *p; }

Если я напишу int, то потом не смогу модифицировать исходный объект - я буду модифицировать его копию.

Да это-то понятно... Но смотри пример выше.

Блин, там, конечно retrun *x.p

Слишком много опечаток

struct my_ptr { int * p; };
...

int & deref(my_ptr ptr) { return *ptr.p; }

...

deref(x) = 10; // ok

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

Да, си отстой в плане концептуальном, но как тебя это беспокоит на практике?

что тебе мешает форкнуться

Оверхед.

т.е. форкаться для сравнения троек тебе мешает оверхед, в внутри сравнения троек форкаться уже можно, да? Ты не забыл о том, что внутри сравнения троек, нужность сравнения зависит от результата предыдущего сравнения? К примеру, если A<B && B<C, то дальнейших сравнений не нужно, а вот если A<B && B>C, то нужно ещё одно сравнение. Т.е. _внутри_ троек применять параллельное сравнение невыгодно. Зато можно снаружи. Вот тебе пример: {321}4{765}. Мы можем одновременно отсортировать {321} и {765}.

Не факт, перестановки могут и параллельно идти:

думай головой, а не цитатами. И да, читай Кнута, у него про это есть.

0) 2,3,1 1) 2,3,1 2) 2,1,3 3) 1,2,3

Эдди, задолбал ты. Где ещё два варианта? Неужели так сложно рассмотреть все варианты, когда их всего ШЕСТЬ(sic!)???

И да, ты упоролся, вариант №0 идентичен варианту №1. Нахера такой «тест» нужен? Что ты доказываешь? Что ты идиот?

Для идиотов:

	int aa[][3] = {
		{1,2,3},
		{1,3,2},
		{2,1,3},
		{2,3,1},
		{3,1,2},
		{3,2,1}
	};

все эти алгоритмы сводятся к одному в 3 сравнения.

мало кому надо сортировать целые числа. Если ты сортируешь строки из N байт, тебе потребуется примерно O(N) сравнений. Строки достаточно большие, и имеют размер как минимум 50 байт, а сейчас, с UTF-8, даже и 100 байт. Потому цена их сравнения имеет значение. Переставлять их местами мы можем почти мгновенно с помощью указателей, но вот сравнивать — увы.

Детский сад вас читать. За 3 эл-та боретесь, такты считаете.

ой, да не борись. Есть http://en.cppreference.com/w/cpp/algorithm/sort чё ты паришься?

Узнаём количество элементов, если мало -> применяем сортировку через сеть.

детка, пиши реализацию. А мы её забенчим.

Предлагаю писать сортировки на Java.

тоже. Не предлагай, а возьми и напиши. Тоже проверим. Я жеж свой вариант уже написал.

Ознакомься: Сортировка списка. Помогите отладить. lisper-pipisper (18.03.2015 20:00:41) sort =: ({.($:@:(<#]),[,$:@:(>:#]))}.) ` [ @. (#=0:)

ознакомился. Ну по-русски это просто называется: «мудак».

Но в Си ссылок нет. Вот туплю сижу.

*p /* <-- какой тип? */

в данном случае тип my_type

Hint:

typedef int my_type;
my_type x;
my_type* p = &x;

*p; /* int */

Меня это беспокоит.

убейся.

Покажи, какой тип должен возвращать deref в примере выше.

Царям сишки (комментарий)

Бетти, ты придурок что ли? Я тебе показал, что будет из себя массив {2,3,1} на каждом шаге твоей хрени представлять!