Ну вот представьте Бизнес тазики:
N тазиков потребно N часов!
Да-да, по правде говоря, я снова сделал невозможное возможным:
O(C*log(C)) операций.
derscountsort()! И всякий час O(N).
| perf\perf12\main.cpp |
|---|
const int N=1000000;
const int M=100;
template<class T>
void stdsort(int size, const T* arr, int* out)
{
for (int i=0; i<size; i++) out[i]=i;
sort(out, out+size, [=](int a, int b) { return arr[a]<arr[b]; });
}
int main(int argc, char** argv)
{
mem_pool mpo, *mp=&mpo;
fd_file out(mp, fd_out), err(mp, fd_err);
try {
// ...
vector<int> v(N);
for (int i=0; i<N; i++) v[i]=rand30()%card;
vector<int> s1(v.size()), s2(v.size());
derscountbuf dbuf;
vector<int> cnts(card);
vector<ushort> ids(v.size());
derscountids(v.size(), v.data(), card, cnts.data(), ids.data(), [](int a) { return a; });
auto t1=steady_clock::now();
for (int j=0; j<M; j++) {
stdsort(v.size(), v.data(), s1.data());
}
auto t2=steady_clock::now();
for (int j=0; j<M; j++) {
derscountsort(&dbuf, ids.size(), ids.data(), 0, card, cnts.data(), 0, s2.data(),
[](ushort a) { return a; });
}
auto t3=steady_clock::now();
for (int i=0; i<N; i++) perm_assert(v[s1[i]]==v[s2[i]]);
out.ex_write(tx_buf(mp)+"std\t"+card+'\t'+duration_cast<milliseconds>(t2-t1).count()+'\n');
out.ex_write(tx_buf(mp)+"ders\t"+card+'\t'+duration_cast<milliseconds>(t3-t2).count()+'\n');
return 0;
}
catch (...) {
err.ex_write(toTextAll(get(recatch(mp, FLLN, false)))->str());
return 2;
}
}
|
Миллион элементов с заданной кардинальностью:
| card | std | ders | std/ders |
|---|---|---|---|
| 2 | 2112 | 107 | 19.7 |
| 10 | 3214 | 99 | 32.5 |
| 100 | 5107 | 106 | 48.2 |
| 1000 | 6696 | 191 | 35.1 |
| 10000 | 8160 | 396 | 20.6 |
| 65535 | 9552 | 524 | 18.2 |
И в этом случае derscountsort() от 20 до 50 раз быстрее!!
Но так как случаи бывают разные, имеет смысл упомянуть нюанс:
stdsort() заставляет стандартный sort() генерировать последовательность, а не сортировать массив.
derscountids() сохраняет для нас идентификаторы в vector<ushort> ids. Для демонстрации такой возможности.
derscountsort() их сортирует, а не исходный vector<int> v. Так тоже можно.
seq) в функцию derscountsort(). И даже так!
[](ushort a) { return a; } в вызове функции derscountsort() имеет параметр ushort, т.к. мы сортируем vector<ushort> ids.
perm_assert(v[s1[i]]==v[s2[i]]). Хотя не можем просто написать s1==s2, понеже sort() стандартный не устойчив!
А гениальность в том, чтоб разложить на части неделимое.
Уж с давних пор так повелось, что сортирока -- это вызов функции. Нельзя наковырять одну начинку!
Мне удалось разделаться с DersCountsort и разложить на три самодостаточных этапа:
O(C*log(C)).
O(N).
O(N).
Да, однократная и уникального. Но оглядитесь и принюхайтесь! Ведь сплошь и рядом мы неоднократно сортируем почти такие же по сути данные в почти таком же, так сказать, порядке... Хлоп! Хлоп! Хлоп!
Спасибо за аплодисменты! Доселе мыслил не дождусь, ну а поди ж ты.
Все дело в том, что небольшие изменения массива можно быстро применить к результатам предыдущих этапов и расторопно отсортировать. Излишне все этапы переделывать!
O(N*log(N)).
O(N), но почти бесполезны.
derscountsort() полезен и в любом порядке сортирует за O(N)!
Невозможно? Давайте включим свет и разберемся.
Но перво-наперво заметим, что сортируемый массив обычно состоит из двух неодинаковых частей:
C (cardinality, т.е. кардинальность).
N-C.
O(C*log(C)) операций на создание сортирующей последовательности. А сортировка будет стоить токмо O(N)!
derscountsort() так и работает: всегда за O(N), т.к. использует уже готовую последовательность! А что кто-то когда-то потратил O(C*log(C)) уже не относится к делу, т.к. ее потом попользуют неоднократно.
Ну, хорошо. А если элементы уникальны?
Да, в этом случае не будет Чуда! Ибо O(C*log(C)) становится O(N*log(N)) и сотворение последовательности эквивалентно полной сортировке.
Но не забудьте про повторы! Ведь (пере)сортировка почти тех же данных в почти том же порядке уже стоит дешево. И в целом можно утверждать, что практическое использование DersCountsort имеет амортизированную сложность O(N)!
std::sort()! Вы хотите об этом поговорить?
Тогда приступим с кардинальности. И как казано свыше, любой массив длины N всегда содержит С уникальных элементов (1<=С<=N).
Тем самым, каждому из уникальных мы можем присвоить номер-идентификатор (число от 0 до C-1), зело устанавливая взаимно однозначное соответствие.
Короче, idnt() -- это функтор, концептуально, эдакой сигнатуры: ushort idnt(const T&). Т.е. поддерживается кардинальность до 65535, не более.
На первый взгляд хотелось бы и более, но в этом случае страдает здравый смысл! Бо при массивах миллиардной протяженности, пришел момент оборотиться к параллельности.
Итак. Мы вызываем функтор idnt() для каждого сплошного элемента, что намекает: его скорость все определяет! Пришло время воззриться на разные случаи:
{ return a.id; }.
{ return a.N-minN; }.
{ return tbl[a.key]; }. А в случае моих таблиц, используйте позицию: { return tbl.find(a.key); }.
Айда заметим, что в процессе сортировки:
cmp(a, b).
idnt(a) и сразу же использует позицию!
Да, Революция! Ну а теперь детали.
Чисто технически, сортирующая последовательность -- это массив всех чисел от 0 до C-1. В произвольном порядке.
Вот здесь подробнее описаны перестановки и последовательности. А так же функция to_sequence().
Ну а я же лишь просто отмечу, что последовательность:
{0, 1, 2, 3} сортирует в обычном порядке: по возрастанию. Ее можно не создавать.
{3, 2, 1, 0} сортирует в обратном порядке: по убыванию.
{2, 0, 1, 3} третий вырвался вперед!
O(C*log(C)) для любой кардинальности.
Так, что еще. Ну да, конечно же dersort_append()!
Ведь иногда (почти всегда?) у вас уже будет готовая сортирующая последовательность, в которую желательно добавить лишь пару-тройку новых элементов. И в этом случае всех вылечит dersort_append():
to_sequence() для превращения последовательности в перестановку.
dersort_append().
to_sequence() для возвращения к последовательности.
O(C)! Весьма недурно для больших массивов.
Э... Так и DersCountsort обязан что-то каунтить:
| derslib\inc\ders\derscountsort.hpp |
|---|
template<class T, class ID>
void derscountids(int size, const T* arr, ushort card, int* cnts, ushort* ids, ID idnt)
{
for (ushort i=0; i<card; i++) cnts[i]=0;
if (ids) {
for (int i=0; i<size; i++) {
ushort id=idnt(arr[i]);
assert(id<card);
cnts[id]++;
ids[i]=id;
}
}
else {
for (int i=0; i<size; i++) {
ushort id=idnt(arr[i]);
assert(id<card);
cnts[id]++;
}
}
}
|
Как грабли просто это чтиво, но есть и важная деталь:
derscountids() подсчитывает количества уникальных элементов массива arr длины size и возвращает их в cnts.
cnts должен указывать на массив int длины card.
ids, то он должен указывать на массив ushort длины size. В него будут записаны идентификаторы элементов.
idnt -- функтор-идентификатор.
id, чтобы потом не пересчитывать.
Не пересчитывать?!
Ну да, для наведения порядка derscountsort()-у хватит ids.
Еще забавная деталь? Так, иногда (почти всегда?) уже имеется готовый cnts, но массив вдруг расширился свежим хвостом... Ага, издоволь просто отработать по хвосту!
| derslib\inc\ders\derscountsort.hpp |
|---|
template<class T, class ID>
void derscountsort(derscountbuf* buf, int size, const T* arr, const int* prev,
ushort card, const int* cnts, const ushort* seq, int* out, ID idnt)
{
buf->reserve(card);
auto pos=buf->pos;
int sum=0;
if (seq) {
for (ushort i=0; i<card; i++) {
ushort si=seq[i];
assert(si<card);
pos[si]=sum;
sum+=cnts[si];
}
}
else {
for (ushort i=0; i<card; i++) {
pos[i]=sum;
sum+=cnts[i];
}
}
assert(sum==size);
if (prev) {
for (int i=0; i<size; i++) {
int pi=prev[i];
assert(pi<size);
ushort id=idnt(arr[pi]);
assert(id<card);
out[pos[id]++]=pi;
}
}
else {
for (int i=0; i<size; i++) {
ushort id=idnt(arr[i]);
assert(id<card);
out[pos[id]++]=i;
}
}
}
|
На удивление, derscountsort() и правда сортирует!
Не удивительно? Зато красиво: всего лишь out[pos[id]++]=i!
OK, все дружно челюсть поднимаем и вникаем:
derscountsort() никак не изменяет сам массив, а создает последовательность.
v[s[i]] и вы получите отсортированный массив.
derscountsort() сортирует массив arr длины size и записывает последовательность в out.
out должен указывать на массив int длины size.
buf -- просто буфер. Никакой магии: создайте где-нибудь derscountbuf и много раз его передавайте.
prev -- результат предыдущей сортировки: последовательность длины size. Передавайте, только если нужно досортировать массив по другому ключу.
card -- кардинальность массива.
cnts -- массив счетчиков длины card, результат derscountids().
seq -- cортирующая последовательность длины card. Не передавайте тривиальную последовательность.
idnt -- функтор-идентификатор.
Но как быть, если сразу два поля, и потребен нам ORDER BY A,B?
В стандартном сортинге мы просто изменяем компаратор:
sort(v.begin(), v.end(), [](const AB& e1, const AB& e2) {
if (e1.a!=e2.a) return e1.a<e2.a;
return e1.b<e2.b;
});
|
С DersCountsort-ом этот фокус не пройдет!
Излишни фокусы, когда устойчив алгоритм. Два раза прозаично сортируем: по B и A -- так победим!
| perf\perf12\main.cpp |
|---|
struct AB {
int a, b;
};
void test2()
{
// ...
vector<int> cntsa(CA), cntsb(CB);
derscountids(v.size(), v.data(), CA, cntsa.data(), 0, [](const AB& e) { return e.a; });
derscountids(v.size(), v.data(), CB, cntsb.data(), 0, [](const AB& e) { return e.b; });
derscountbuf dbuf;
vector<int> sa(v.size()), sb(v.size());
derscountsort(&dbuf, v.size(), v.data(), 0, CB, cntsb.data(), 0, sb.data(),
[](const AB& e) { return e.b; });
derscountsort(&dbuf, v.size(), v.data(), sb.data(), CA, cntsa.data(), 0, sa.data(),
[](const AB& e) { return e.a; });
vector<AB> v2(v);
sort(v2.begin(), v2.end(), [](const AB& e1, const AB& e2) {
if (e1.a!=e2.a) return e1.a<e2.a;
return e1.b<e2.b;
});
for (int i=0; i<N; i++) perm_assert(v[sa[i]].a==v2[i].a && v[sa[i]].b==v2[i].b);
}
|
Читатель пристальный немедленно заметит: во второй вызов мы передаем sb.data(). Тот самый редкий вариант, когда без prev ни в коем случае!
Ну вот и все: O(N) два раза все равно для всех O(N)!
Легко и просто ведь сортировать массивы идеальных идентификаторов. Но в жизни это не бывает!
А вы уверены? Может вспомним внезапно Star schema: Fact tables generally consist of numeric values, and foreign keys to dimensional data... Dimension tables usually have a relatively small number of records.
Все это значит, что таблицы Фактов имеют УЙМИЩЕ колонок с низкой кардинальностью: идеальная пища для DersCountsort!
Но мы опять вернемся к сложным случаям. Таким, как сортировка слов из книги.
В обычной книге среднего объема (около 300 страниц) содержится примерно 70000-100000 слов, но уникальных слов обычно 5000-15000.
Ага! Прекрасно для DersCountsort, вот только как присвоить идентификаторы?
Ответ известен: хеш-таблица! И таким образом:
ids и подобьете счетчики cnts.
derscountsort(). И это будет ОЧЕНЬ эффективно!
Кому глава, а кому просто хвост массива:
derscountsort(). И это честные O(N)!
ushort, и это значит больше 65535 уже не будет!
Но жизнь есть жизнь, и так бывает, надо больше:
65535 -- не беда! Просто скопируйте derscountsort.hpp и замените там ushort-ы на uint. И имена, конечно, исказите! Ну, например, bigcountsort(). Солидный BigSort для солидных господ!
Итак, лишь с появлением DersCountsort мы все узнали, что:
O(C*log(C)), а не O(N*log(N)).
O(N)!
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.