66 лет целенаправленного поиска блистательных умов... А найдется ль сегодня хоть что-нибудь новое? Да, полировка особых случаев.
А если Фундаментально?
Против всякого чаяния, как ни странно, нашлось!
С уважением, Сергей Деревяго.
Хорошо, продолжаю.
Допустим, у нас есть некий вектор v={14, 11, 10, 13} и перестановка p={3, 1, 0, 2}, упорядочивающая его элементы:
i | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
v[i] | 14 | 11 | 10 | 13 |
p[i] | 3 | 1 | 0 | 2 |
v[i] -> v2[p[i]] | 10 | 11 | 13 | 14 |
Т.е. используя перестановку p, мы можем перенести каждый элемент v[i] в позицию p[i] и получить упорядоченный вектор v2.
А теперь в конец вектора v мы добавим 12 -- что нужно сделать с перестановкой? Позицией 12-ти обязана стать 2, но она уже занята:
i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
v[i] | 14 | 11 | 10 | 13 | 12 |
p[i] | 3 | 1 | 0 | 2 | |
v[i] -> v2[p[i]] | 10 | 11 | 13 | 14 |
Не беда:
1 все элементы, чье значение >=2.
2 в ее конец.
i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
v[i] | 14 | 11 | 10 | 13 | 12 |
p[i] | 4 | 1 | 0 | 3 | 2 |
v[i] -> v2[p[i]] | 10 | 11 | 12 | 13 | 14 |
Гениальное просто. Как и функция добавления:
void append_pos(vector<short>& perm, short pos)
{
for (int i=0; i<perm.size(); i++) {
if (perm[i]>=pos) perm[i]++;
}
perm.push_back(pos);
}
|
Упражнение для читателя: А декрементом? А не с нуля??
| derslib\inc\ders\dersort.hpp |
|---|
template<class T, class C>
short* dersort(const T* first, const T* last, short* firstOut, C cmp)
{
auto lastOut=firstOut;
if (last<=first || last-first>SHRT_MAX) return lastOut;
*lastOut++=0;
short base=0;
for (int i=1; i<last-first; i++) {
int psz=lastOut-firstOut, beg=0, end=psz;
for (int j=i-1; j>=0; j--) {
auto pj=firstOut[j]-base;
if (pj<beg || pj>=end) continue;
if (cmp(first[i], first[j])) {
if (pj==0) {
*lastOut++=--base;
break;
}
end=pj;
}
else {
if (pj==psz-1) {
*lastOut++=psz+base;
break;
}
beg=pj+1;
}
if (beg==end) {
append_pos(base, firstOut, lastOut, beg);
break;
}
}
}
if (base) for (auto it=firstOut; it<lastOut; it++) *it-=base;
return lastOut;
}
void append_pos(short& base, short* first, short*& last, short pos)
{
auto pb=pos+base;
int sz=last-first;
if (pos>=sz/2) {
int cnt=sz-pos;
for (auto it=last-1; cnt>0; it--) {
if (*it>=pb) {
(*it)++;
cnt--;
}
}
}
else {
int cnt=pos;
for (auto it=last-1; cnt>0; it--) {
if (*it<pb) {
(*it)--;
cnt--;
}
}
base--;
}
*last++=pos+base;
}
|
А вот ключевые моменты:
dersort() никак не изменяет сам массив! Он создает перестановку.
v2[p[i]]=v[i] и вы получите отсортированный массив v2.
dersort() реализован в стиле STL: пара [first, last[ задает массив для сортировки, а перестановка будет записана в firstOut.
firstOut должен указывать на массив short той же длины: last-first.
dersort() возвращает lastOut -- конец записанной перестановки.
Обратите внимание, что сравнение элементов массива с помощью cmp(first[i], first[j]) вызывается ТОЛЬКО если pj лежит в диапазоне [beg, end]! А сам диапазон стремительно сужается: в среднем в два раза за шаг.
Таким образом, количество сравнений элементов стремится к минимально возможному, а массив сортируется "сам о себя". Т.е. диапазон [beg, end] сам собой формирует чарующее дерево сравнений.
std::sort() (вариант Quicksort) и ins_sort() (классический Insertion sort).
Увы, но это не привычный тест на скорость, т.к.
to_sequence().
Тем не менее, есть два ключевых параметра, которые можно сравнить:
| perf\perf08\main.cpp |
|---|
for (int j=0; j<M; j++) {
vector<int> v;
for (int i=0; i<N; i++) {
if (what=="asc") v.push_back(i);
else if (what=="desc") v.push_back(N-i);
else v.push_back(rand());
}
vector<short> p(v.size());
auto plast=dersort(v.data(), v.data()+v.size(), p.data(),
[](int a, int b) { dersCnt++; return a<b; });
perm_assert(plast-p.data()==int(p.size()));
vector<int> v2(v);
sort(v2.begin(), v2.end(), [](int a, int b) { stdCnt++; return a<b; });
for (int i=0; i<N; i++) perm_assert(v[i]==v2[p[i]]);
vector<int> v3(v);
ins_sort(v3.data(), v3.data()+v3.size(),
[](int a, int b) { insCnt++; return a<b; });
perm_assert(v2==v3);
}
|
Итак, случайные данные. Запускаем main с аргументом rand и любуемся:
| N | Quicksort | Insertion sort |
|---|---|---|
| 10 | 1.29 | 1.21 |
| 100 | 1.22 | 3.98 |
| 1000 | 1.09 | 22.89 |
Мы видим, что:
Уже отсортированные данные. Запускаем с аргументом asc:
| N | Quicksort | Insertion sort |
|---|---|---|
| 10 | 2.00 | 1.00 |
| 100 | 6.35 | 1.00 |
| 1000 | 10.63 | 1.00 |
Мы видим, что:
Отсортированные в обратном порядке. Запускаем с аргументом desc:
| N | Quicksort | Insertion sort |
|---|---|---|
| 10 | 1.00 | 5.00 |
| 100 | 5.31 | 50.00 |
| 1000 | 8.15 | 500.00 |
Мы видим, что:
| derslib\inc\ders\dersort.hpp |
|---|
template<class T>
inline void to_sequence(const T* first, const T* last, T* firstOut)
{
for (int i=0, end=last-first; i<end; i++) firstOut[first[i]]=i;
}
|
Спасибо, я вижу. А если серьезно?
А если серьезно, то ща будет show():
| perf\perf08\main.cpp |
|---|
void show(fd_file* out)
{
// ...
vector<short> p(v.size());
dersort(v.data(), v.data()+v.size(), p.data(), [](int a, int b) { return a<b; });
print(out, "p[i]", &p);
vector<short> s(p.size());
to_sequence(p.data(), p.data()+p.size(), s.data());
print(out, "s[i]", &s);
// ...
}
|
Она выводит на экран перестановку p:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
v[i] | 14 | 16 | 19 | 15 | 15 | 12 | 17 |
p[i] | 1 | 4 | 6 | 2 | 3 | 0 | 5 |
Но можем ли мы с ее помощью отсортировать вектор v? Да не вопрос!
Гы, это лихо! Но у матросов есть еще вопросы: как напечатать друг за другом элементы?
Гмм... Первый элемент перестановки -- савсэм адын, а нам нужно начать с нулевого. И потом уже будут 1, 2 и прочие... Всех придется искать перебором??
Вот поэтому есть и to_sequence()! Мы применим ее к результату dersort() и получим "последовательность" s:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
v[i] | 14 | 16 | 19 | 15 | 15 | 12 | 17 |
p[i] | 1 | 4 | 6 | 2 | 3 | 0 | 5 |
s[i] | 5 | 0 | 3 | 4 | 1 | 6 | 2 |
v[s[i]] | 12 | 14 | 15 | 15 | 16 | 17 | 19 |
Все реально прекрасно, как кажется: v[s[i]] нам выводит один за одним элементы.
Красотища, ага! Ну а как, например, из последовательности s нам получить исходную перестановку?
Как ни смешно, но это тоже сделает to_sequence(): примените ее к последовательности и получите перестановку!
Ну, например, вы чуточку расширили массив и нужно эффективно обновить перестановку.
И чтобы снова не сортировать все полностью, была добавлена удобная dersort_append():
| derslib\inc\ders\dersort.hpp |
|---|
template<class TA, class TP, class C>
void dersort_append(int size, const TA* arr, TP* perm, C cmp)
{
if (size==1) {
*perm=0;
return;
}
int sz1=size-1;
TP beg=0, end=sz1;
for (int j=sz1-1, cnt=0; j>=0; j--) {
TP pj=perm[j];
if (pj<beg) continue;
if (pj>=end) {
perm[j]=pj+1;
cnt++;
continue;
}
if (cmp(arr[sz1], arr[j])) {
end=pj;
perm[j]=pj+1;
cnt++;
}
else {
if (pj==sz1-1) {
perm[sz1]=sz1;
return;
}
beg=pj+1;
}
if (beg==end) {
cnt=sz1-beg-cnt;
for (auto it=perm+j-1; cnt>0; it--) {
cnt -= *it>=beg;
*it += *it>=beg;
}
perm[sz1]=beg;
return;
}
}
}
|
И вы, естественно, получите DerSort, вызывая ее раз за разом:
| perf\perf08\main.cpp |
|---|
void test_append()
{
// ...
vector<short> p1;
while (p1.size()<v.size()) {
p1.push_back(0); // место для позиции
dersort_append(p1.size(), v.data(), p1.data(), [](int a, int b) { return a<b; });
}
vector<short> p2(v.size());
dersort(v.data(), v.data()+v.size(), p2.data(), [](int a, int b) { return a<b; });
perm_assert(p1==p2);
}
|
DersOversort -- реализация DerSort поверх стандартного Quicksort:
| derslib\inc\ders\dersoversort.hpp |
|---|
template<class T1, class T2, class C>
void dersoversort(const T1* first, const T1* last, T2* firstOut, C cmp)
{
int sz=last-first;
for (int i=0; i<sz; i++) firstOut[i]=i;
std::sort(firstOut, firstOut+sz, [=](T2 a, T2 b) { return cmp(first[a], first[b]); });
}
|
Как бы все то же самое, но:
to_sequence().
| perf\perf08\main.cpp |
|---|
void test_over()
{
// ...
vector<short> s1(v.size());
dersoversort(v.data(), v.data()+v.size(), s1.data(), [](int a, int b) { return a<b; });
vector<short> p(v.size()), s2(v.size());
dersort(v.data(), v.data()+v.size(), p.data(), [](int a, int b) { return a<b; });
to_sequence(p.data(), p.data()+p.size(), s2.data());
for (int i=0; i<N; i++) perm_assert(v[s1[i]]==v[s2[i]]);
}
|
Само собой, не можно тупо написать perm_assert(s1==s2), т.к. позиции одинаковых могут не совпадать.
short. И это его Главная Проблема!
А дело в том, что массив short средних размеров гарантированно помещается в кэш первого уровня. И это ОГРОМНОЕ преимущество!
Вот почему Quicksort не задавил все квадратичные, а примитивный Insertion sort все еще рулит в районе тщедушных массивов. Непромедлительно сравним:
T.
short. Используйте DersOversort!
Невозможно.
Но я не знал и все-таки ускорил:
for (auto it=lastOut-1; cnt>0; it--) {
if (*it>=pb) {
(*it)++;
cnt--;
}
}
// ...
for (auto it=lastOut-1; cnt>0; it--) {
if (*it<pb) {
(*it)--;
cnt--;
}
}
|
for (auto it=lastOut-1; cnt>0; it--) {
cnt -= *it>=pb;
*it += *it>=pb;
}
// ...
for (auto it=lastOut-1; cnt>0; it--) {
cnt -= *it<pb;
*it -= *it<pb;
}
|
Старый добрый Branchless Programming, где вместо блока if (condition) {} мы напрямую подставляем результат condition в выражение.
На практике обычно бесполезно, но в этом случае мы удивленно чешем разницу:
| perf\perf11\main.cpp |
|---|
auto t1=steady_clock::now();
for (int j=0; j<M; j++) {
auto plast=dersort_v1(v.data(), v.data()+v.size(), p.data(), [](int a, int b) { return a<b; });
perm_assert(plast-p.data()==int(p.size()));
}
auto t2=steady_clock::now();
for (int j=0; j<M; j++) {
auto plast=dersort(v.data(), v.data()+v.size(), p.data(), [](int a, int b) { return a<b; });
perm_assert(plast-p.data()==int(p.size()));
}
auto t3=steady_clock::now();
|
Халява, сэр!
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.