- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
#include <iostream>
#include <thread>
#include <list>
#include <functional>
#include <chrono>
using namespace std;
void outputToSomeContainer(int val, list<int>& result){
result.push_back(val);
}
class async{
list<thread> a;
public:
async(){}
async(async&& a): a(move(a.a))
{}
void addTask(function<void()>&&f){
a.emplace_back(move(f));
}
void wait(){
for(auto&& i: a)
i.join();
}
};
async async_O_n_Sort(const list<char>& unsorted, function<void(int)> outputToContainer){
async a;
for(int i: unsorted)//O(n)
a.addTask([i, outputToContainer](){this_thread::sleep_for(chrono::milliseconds(5+i*10));outputToContainer(i);});
return a;
}
int main() {
list<char> unsorted {1, 0, 6, 3, 4};
list<int> sorted;
auto a = async_O_n_Sort(unsorted, bind(outputToSomeContainer, placeholders::_1, ref(sorted)));
cout<<"А мы веселые пельменья, мы похоже на варенья"<<endl;
a.wait();
for(int i: sorted)
cout<<i<<endl;
return 0;
}
Follow us!
Кстати какая самая недорогая по памяти сортировка с приемлимой (до квадратичной) сложностью, в треде как я понял советуют:
том 3 Кнута упражение 18 раздел 5.2.4
ага. конечно. с какой константой? небось 2^64 для 64-битных систем? :)
давно когда-то читал бумажку чудака который O(1) структурами занимается. там все очень и очень нетривиально и константы в этом O(1) просто заоблачные. даже в случае если делать нативно в железе.
Пузырёк же.
O-нотация отражает только асимптотическую зависимость производительности от количества входных элементов, стремящегося к бесконечности. Поэтому константы как правило опускаются.
Но часто когда анализируются алгоритмы, народ так же записывает и константы (и другие асимптотически незначительные функции). Например: вместо O(n) пишут (например) O(5n + 10). что значит что у алгоритма, на каждый элемент есть избыточность 5, плюс 10 на инициализацию/деинициализацию.
В частности в области O(1) алгоритмов, т.к. асимптотика заранее известна, народ соосредотачивается на константе, которая отражает избыточность алгоритма.
Формального определения для юнита констант я не видел. Народ либо Кнутовским MIXом пользуется, либо количеством CPU циклов на каком-то настоящем проце.
> Пузырёк же.
где?
>где?
Пример сортировки с честной O(1) по памяти без страшных констант и скрытых рекурсивных комиссий.
while (!sorted(array)) shuffle(array);
Божественный one-liner.
http://rextester.com/DRGN82512
Интересно, а как с async \ await убрать потоки совсем? Внизу показывает 8. Слышал как-то можно кооперативную многозадачность через них организовать при использовании ExecutionContext и SynchronisationContext.
Ну понятно что по хорошему должны быть таймеры, но это наверное не наш путь. Хотя может наш.
И кстати с async лямбдой у меня что-то не получилось.
Смотрю что оно там показывает. Вероятно, Process.GetCurrentProcess().Threads.Coun t.
Минимум будет три потока. Плюс энное количество специальных: http://blogs.msdn.com/b/yunjin/archive/2005/07/05/435726.aspx
Убрать совсем, чтоб UI замёрз?
http://rextester.com/GODX99721
Ну а с другой стороны не факт, что это число потоков в пуле. Тогда сортировка совсем поломается.
http://rextester.com/SQIHB19182
Не знаю как тут C# творит чудеса
Однако, читал где-то год назад на кывте один тред , где схлестнулись гуру c++ и дотнета, как раз по поводу async/await, так дотнетчики позорно слились (имхо).
Крестовики показали, что можно с любой функцией работать асинхронно, а в шарпике она должна быть специально для этого написана.
В крестах дефолтный асинк либо порождает новый тред, либо выполняет функцию прямо в текущем потоке (зависит от опций и кол-ва живых тредов). При наличии нормального тредпула кресты в теории могут быть удобнее.
Да не может быть! Неужели макрософт это всеже смогла пропихнуть? Это в С++14? Или какое-то расширение в майкрософтском компиляторе?
А я попутал. Майкрософт свой чуда асинк пытался впихнуть в сишарповом смысле в стандарт 11. Слились. Линус послал всех лесом
и резьюмейбл йелд
Тред большой и там в разных подветках была битва.
Ищи ключевые слова, что я назвал:
http://meetingcpp.com/index.php/br/items/resumable-functions-async-and-await.html
async_code
await_async
И я что-то не понял где асинхронный кол и последующий авайт в произвольном месте кода? А то await_async не позволяет в произвольном месте кода произвести авейт
Других вариантов получить тот же функционал помоему нет
Ну так вызов обычной функции завернуть в асинк функцию и вот тебе проблема решена.
Это потому что большинство дотнетчиков — тупые и ограниченные этим самым C#, кмк.
Хоть С++ и говно, но на ГК большая часть толковых пользователей промышляет именно крестоблядством.
Разгадка парадкоса мне видится в том что написание и понимание разных ебанутых крестокодов, а также непрерывная борьба с граблями неплохо развивает мышление и смекалку.
Вот только проблема в том, что плюсовики добираются до буста, корутин, асинхронности и т. п. лишь через несколько лет обучения.
В то время как в современном дотнетике сходу предлагается использовать async/await. Поэтому даже кодомакаки его используют.
Благодаря чему они к этому морально готовы, а не бросаются пихать все это во все дыры.
Стойко перенося боль и унижения от boost::asio.
> ничего не умеешь
Нук, насоветуй чего-нибудь интересного на почитать (кроме бустовских либ, само собой).
TarasB от нас что-то скрывает....
> И последний работает тока в вин8
Это же развитие C++/CLI с фреймворком и сборкой мусора?
тбб - это интел тбб. я хз. может даже платить надо. не качал
с++\сх для вин восемь - это как Swift для макоси.
привязка целого языка. личный вин рантайм на ком объектах с рефлексией (вин рт) вместо фреймворка. счетчики ссылок вместо гц. притом местный счетчик ссылок boost::intrusive_ptr встроен в язык как ^ вместо *.
tbb - очень даже неплохая либа. Есть опен-сорсная версия либы, она присутствует в дебиановской репе с незапамятных времён.
Юзал из неё контейнеры, параллельные алгоритмы, pipeline.
http://rextester.com/SDYJI94409
Добавил элементов и отреверсил, чтобы наименьшие элементы были в конце листа. Получается или число потоков совпадает с числом элементов в листе или все происходит в одном или н потоках притом в каждом из них запланированно к событий одновременно (По сути потоки переиспользуются кооперативно).
Кстати сортировка очевидно работает на листах без random access
sort(left)
sort(right)
Потому никаких хвостовых рекурсий там не будет, будет дерево 2-4-8-16.
Поздравляю, еще чуть-чуть и вы изобретёте quantum bogosort.
И сюрприз!, положить/достать из этой очереди 1 элемент можно за O(log(N)), а отсортировать надо N. Опять N*log(N)
ps: А гейдев не только говнокод пытается захватить, он ещё и на хабр свои щупальца протянул.
Вроде в статье написано:
Сортировка слияниями на месте (in-place merge sort) укладывается в ограничения 1 и 2 (есть даже ее stable вариант, но там жесть), но совершенно непонятно, как ее эффективно реализовать без произвольного доступа к памяти.
А зачем он? Он и не нужен, когда список сортируешь.
я тоже не совсем понимаю как этот инплейс (то есть на том же списке) мердж сорт будет сливать последние блоки данных, сравнивая их начала. Для этого ему надо будет постоянно бегать в средину списка.
> Он и не нужен, когда список сортируешь.
Любой произвольный доступ по индексу можно заменить последовательной итерацией N элементов.
В первом случае мы получаем элемент за O(1), во втором за O(N).
поблочно копируешь из листа в вектор длиной к
юзаешь любую сортировку на блоке.
сливаешь обратно в лист
ну а вообще в типичном квик сорте стек тоже юзается, так что там О(log n) на память внезапно.
И тут мы подходим к вопросу - а так ли нужно это O(1) по памяти? Ведь их квиксорт с медианой гарантированно укладывается в O(log(N)) памяти, и для всех разумных применений это жалкие 32 слота, которые можно считать константой...
32 байта хватит всем
Блоки с размером по степеням двойки поди? Забыл как называется этот метод ;(
Почему? Там же вроде свободные половинки приклеивались друг к другу? Или ради O(1) этой поклейкой пришлось пожертвовать?
http://www.gamedev.ru/flame/forum/?id=196218
(не с 1 страницы)
тупо да?
единственное что я допилил чуток освобождение последних пустых блоков
same shit
А ещё я настолько ебанулся на алгоритмической сложности, что вместо вектора с его ужасными реаллокациями запилил треугольный буфер - это массив из указателей на блоки элементов, в первых двух блоках по 16 элементов, в каждом следующем вдвое больше, блоки заполняются последовательно. Все операции по сложности как у вектора, только константа в 10 раз больше XD, зато вставка нового элемента гарантированно (а не амортизированно) О(1).
у него O(1) гарантия на вставку в конец?
вы блин идеи знакомые услышали, ближайшее слово по смыслу нашли и типа опа оно
O(k) в худшем случае. k конфигурируемо при компиляции (размер сегмента). Так что да, O(1), меняется только размер константы.
Тю, я где-то похожее видел.
И тоже пилил свой, но у меня проще: буфер прирастает блоками константного размера. Адресация — сегмент+смещение.
Стандартный java arrayList — по мне говно. Плюс когда удаляем элементы (с концов) вектор составленный из страниц сдувается, а стандартный — хуй, вроде как-то руками можно шринкать, но это говнятина.
>зато вставка нового элемента гарантированно (а не амортизированно) О(1).
Тоже так получается.
Где-то у классиков (Кнут вроде цитату приводил) видел мысль: о экспоненциальной сложности надо думать, только когда имеешь экспоненциальные объемы данных.
У меня-то 28 блоков хватит на миллиард, и я 28 указателей на блоки храню статически.
А причём тут экспоненциальная сложность?
Я думал над иерархической структуров из блоков. Типа rope, но обломался писать.
>А причём тут экспоненциальная сложность?
При том что для практических целей задрачивать сложность не особо и следует, т.к. у нас немного данных.
Гораздо большее значение и вес имеет константа. В типичных случаях O(N/64) может оказаться быстрее чем O(>9000)
Тогда потеряем O(1) и довольно низкую константу на произвольном доступе...
Я тоже так подумал.
> Хотя, если мы возьмем достаточно большие блоки (4096 байт например) - трёх уровней хватит за глаза.
Ну я думал что число уровней будет расти по мере роста структуры.
То есть <64 - один уровень - линейная адресация.
<64*64=4096 два уровня - сегмент+смещение
>4096*64=256К
Три уровня
>4M
4 уровня
>256M
5 уровней.
Но это сложно. Мне больше нравится идея (опять-таки ничего нового я не предлагаю) динамического размера страницы, как в процессорах: можно выбрать 4К, можно 4М. И просто 2 уровня: сегмент+смещение.
А там и память кончится. Реально на практике очередей больше 1 миллиарда не встречал, а списки/векторы и того меньше (обычно их потолок - десятки тысяч).
Но ведь это ужасная переголова в момент переключения размера страниц. Или просто выбираем такой размер страницы, которого для нашей задачи будет достаточно?
Ну в процессоре так и делают. Что мешает сделать нам программно?
К сожалению софт так просто не может выбрать размер страницы, с которой он запущен (чтобы ускорить адресацию на уровне ЦПУ).
Но вот 7max может запускать приложения в отдельном адресном пространстве со страницами 4Mb, в то время как ОС работает со стандратными маленькими 4Kb.
То есть фактически в рамках одной оси могут сосуществовать приложения с разным размером страниц.
Более того в последних процах сделали монструозные 1Gb страницы.
Это и есть std::deque, упомянутая выше
>сливаешь обратно в лист
к - константа, верно понимаю?
Как тогда смерджить джва блока, которые больше чем к?
Ну хорошо у тебя есть джва отсортированных блока размером ка, что дальше? N» к
алгоритмическая сложность зависит от ка
очевидно, что если ка равно 1, то имеем сортировку вставками, тоисть квадрат по сложности
>да, по сути все идеи данной статьи не мои — я просто разместил объяву
Типичный хабр, в принципе я схватил идею сразу, я и раньше много думал/читал как оптимальнее найти медиану для квиксорта.
В целом статья неплохая, но есть сомнения что сложность O(log(N)*N) (с учётом связности списка обмен и перемещения джвух произвольных элементов - O(N))
для двусвязного и так сам понимаешь
> забанен
начало очень в стиле