Я вижу лажу в аксиоматике "А". Мы вводим полугруппу по сложению (без нейтрали), а потом вдруг вводим операцию "меньше-или-равно", определённую через сложение. Вы это, или крестик или трусы.
Или хотя бы вставьте костыль:
То есть, "меньше-или-равно" - это "или строго меньше, или равно"
Нет, ДДП можно разместить в массиве. Но это будет массив не только со значениями, но и со всей служебной информацией. В отличие от кучи, чья структура прибита гвоздями, и индексы дочерних и родительского элемента вычисляются.
Поскольку размер дерева фиксированный, то и память под узлы можно выделить один раз. И вместо указателей пользоваться индексами. И вообще, вместо строчного представления взять столбцовое: отдельно массив значений, отдельно массивы индексов, отдельно массив флажков балансировки.
Да, разменяли время на память. Но - разменяли ли? С одной стороны - куча и мусорная корзина (хеш-таблица, которая тоже хранит значения плюс свою служебную информацию), а с другой - просто дерево, которое сразу хранит служебную информацию, зато не дублирует значения.
Кстати, не set, а multiset... Или же map счётчиков.
Ну кстати да. Раз уж у нас добавление в кучу логарифмическое, то возьмём вместо двух куч два ДДП.
Единственная выгода двоичной кучи - в том, что она эффективно размещается на массиве, тогда как set требует динамическую память.
Ну ок, возьмём std::set с пользовательским аллокатором, разместим на массиве (правда, впятеро большего размера: в каждом узле, помимо значения, ещё три указателя и флажок балансировки).
От логарифма на каждом шаге мы никак не избавимся, потому что heappush. Мы хотели бы избавиться от n или даже nlogn при удалении произвольного элемента из кучи.
Но давайте-ка сделаем совсем по-другому.
Пусть у нас есть упорядоченный контейнер с логарифмическим поиском-удалением-вставкой. То есть, любое ДДП (хоть АВЛ, хоть КЧД, неважно). И пусть у этого контейнера есть двунаправленные итераторы! Да-да, std::map.
И вот пусть мы знаем не только значение медианного элемента (или пары смежных), но и итератор на медианный элемент.
Теперь, добавляем новое значение в мап. Пусть мап сам занимается своей балансировкой, нам пофигу. Но мы ведь и понимаем, добавили в левое или правое крыло относительно значения медианы. Поэтому сдвигаем итератор медианы в нужную сторону, и это амортизированная O(1).
А потом удаляем старое значение из мапа. И мы также понимаем, из левого или правого крыла. И опять сдвигаем итератор.
Если последовательность монотонно растёт, то мы постоянно добавляем в левую кучу новые элементы (на вершину), а старые помечаем как выбывшие. Но они никогда не окажутся наверху кучи, и поэтому никогда не будут удалены. В результате у нас разрастается и куча, и мусорная корзина. И мы получаем и утечку, и логарифм от маляра Шлемюэля.
Я по-прежнему не понимаю, почему вы включаете режим ССЫКЛА.
Как можно себя подставить, если назвать прямым текстом, что у компании Яндекс есть фейковое приложение-двойник, маскирующееся под оригинальное яндексовское, что это приложение выглядит опасным, а первая линия поддержки проявила себя как-то беспомощно?
Ну вот что случится? Яндекс вычислит по айпи и забанит вас как курьера, в назидание? Или что? Или другие курьеры-конкуренты забьют самокатами? Или хозяева фишингового приложения приедут из своего кол-центра в днепропетровске и тризубом затыкают?
Вовсе нет. Вы для них не настолько важная персона, что первая линия поддержки известила их отдел соцсетей службы пиара, чтобы они вообще смогли увязать публикацию этой статьи с какой-то там перепиской.
По очень простой причине. Первая линия настолько загружена обращениями пользователей, что они намеренно это всё автоматизируют и в лучшем случае записывают самые интересные случаи куда-нибудь в беклог. Авось раз в квартал набежит менеджер и сделает обзор. В противном случае менеджеры поддержки не могли бы заснуть от распухшей головы в заботах о юзерах.
Думаете, от хорошей жизни там роботы с футболом?
А вот научить первую линию отличать рутинное от критического - это важная задача. И сделать это можно, к сожалению, исключительно через голову службы поддержки.
Поэтому хватит жеманничать. ИМЯ КОМПАНИИ - В СТУДИЮ. Иначе Яндекс будет думать, что вы ломились в Сбер, Сбер - что во Вкусно-И-Точку, а Вкусно-и-Точка - в шавермачечную на вокзале.
Конечно, если желание узнать состояние асинхронной задачи (запускаем - запустили - отменили - закончили с отменой - закончили без отмены) входит в ТЗ, то реализация несколько усложнится.
Но тут мы встанем на очень скользкую дорожку конкурентного выполнения. Когда информация о статусе будет зависеть от моментов, когда мы этот статус спрашиваем и параллельно изменяем.
Поэтому - а насколько часто нам это в коде нужно? Может быть, "выстрелил и забыл" тоже подойдёт?
Меня не покидает чувство, что вы только что переизобрели std::promise/future/async. Да ещё и с довольно странным дизайном, в котором у вас есть явные владельцы и всё такое.
Имхо, надо было отталкиваться от описания задачи, а не от допиливания фич к существующему первичному коду. Причём замечу, что если с самого начала взять фьючерсы, то оперировать тредами вообще не придётся. (Они там будут под капотом).
Итак, хочется
асинхронную функцию, которая как-то сама может проверять флажок остановки
частный случай - функцию, которая делает это в цикле, собранном из условия и тела
Ну окей. Договоримся, что в первом случае это void(atomic_bool& /*stop*/)
Второй делается из первого нехитрым образом:
auto make_async_while_loop(auto precondition, auto body) {
return [=](atomic_bool& stop) {
while(!stop && precondition()) { body(); }
};
}
auto make_async_do_while_loop(auto body, auto postcondition) {
return [=](atomic_bool& stop) {
while(!stop && postcondition(body())) {}
}
}
Если body само по себе длинная операция - ну окей, переделать на body(stop)
Всё. Теперь нам нужна сущность, у которой есть две ручки: cancel и wait. Первая посылает команду остановки (мгновенно), вторая - ждёт завершения, какое бы оно ни было.
Я бы посоветовал сперва скомпилировать код, прежде чем вставлять его в статью... Потому что он с ошибками.
bool StopFunc() // метод для её остановки
{
if (!FuncThread && !FuncStatus)
return false;
FuncStatus = false;
if (FuncThread.joinable()) FuncThread.join(); // не . а ->
if (FuncThread) delete FuncThread; // delete не нуждается в проверке на nullptr
FuncThread = nullptr;
return true;
}
bool FuncStatus() { return FuncStatus; } // два члена с одним именем
private:
thread* FuncThread; // (лишняя косвенность)
Я думаю, что надо открытым текстом назвать компанию, чья служба поддержки так беспомощно и НАОТШИБИСЬ прореагировала на сообщение о критической проблеме. Потому что это входит в систему. И пока менеджерам самого верхнего уровня не настучат по шапке за антипиар, которого они добились и заслужили, - на первой и второй линиях поддержки (а то и на нулевой, с этими чёртовыми роботами) ничего не изменится.
Описуемые числа - это числа, которые можно (не обязательно уникально) задать некоторой конечной нотацией, - например, математической формулой или программой на любом языке программирования.
Например, конечные десятичные числа включают в себя множество целых и подмножество рациональных (среди рациональных есть бесконечные десятичные).
Десятичные числа со специальной нотацией ЦЕЛАЯ_ЧАСТЬ , КОНЕЧНАЯ_ДРОБЬ ( ПЕРИОД ) неуникально охватывают все рациональные числа. Неуникально - потому что периоды из девяток равны единице в предыдущий разряд и вырожденному периоду из нулей. То есть, 1,23(9) = 1,23(99) = 1,24.
Алгебраические числа - корни многочленов. Это не только рациональные, но и иррациональные числа. И как мы знаем, для многочленов 5 и более высоких степеней мы даже не всегда можем записать это в виде арифметических формул, дополненных знаком корня целой степени... Но тем не менее, эти числа (неуникально) определяются в виде "вот коэффициенты многочлена, а вот порядковый номер его корня". Если коэффициенты рациональные, номер натуральный, то кортежи таких чисел образуют счётное множество. Поэтому, хоть множество алгебраических чисел и шире, чем рациональных (включает их), но оно по-прежнему счётно.
Трансцедентные числа - то есть, не алгебраические. Вот тут дело обстоит интереснее. Да, очевидно, что вещественные числа - это континуум, а трансцедентные = вещественные \ алгебраические, континуум минус счётность = континуум. Пусть и всюду дырявый.
Однако, если мы попробуем описать любое трансцедентное число... ну, какие у нас есть средства? Именованные константы наподобие пи, е, гаммы там всякой. Именованные функции наподобие синуса, куда подставляем константы и числовые литералы. Безымянные ряды с формулой для члена. Интегралы-неберучки с формулой для подынтегрального выражения. И тому подобное.
А все ли трансцедентные числа можно так описать? А давайте посчитаем!
Пусть у нас есть некоторый язык формул. (И неважно, насколько он формальный - то есть, насколько мы где-то отдельно записали его синтаксис и семантику). Формулы конечной длины из символов конечного алфавита. Образуют множество строк... мощностью... ПРАВИЛЬНО! Счётное!!!
И вот что получилось. Описуемые числа - это счётное множество, которое включает в себя
целые (конечные цепочки цифр и знака)
рациональные (конечные цепочки цифр, знака, разделителей целой части и периода)
алгебраические (инструкции "реши-ка мне вот такое уровнение с многочленом")
некоторые трансцедентные (формулы произвольной громоздкости)
Но мы-то знаем, что всего вещественных чисел - континуум...
СЛЕДОВАТЕЛЬНО: существует континуум (везде дырявый) неописуемых чисел, - подмножество трансцедентных.
И - нет, не пытайтесь найти неописуемое число. Каждая такая попытка, если будет успешной, просто добавит ещё одно число в жалкую счётность описуемых, а континуум без этой штуки останется континуумом.
Ненене, мы ещё до нулевой длины не дошли.
Я вижу лажу в аксиоматике "А". Мы вводим полугруппу по сложению (без нейтрали), а потом вдруг вводим операцию "меньше-или-равно", определённую через сложение. Вы это, или крестик или трусы.
Или хотя бы вставьте костыль:
То есть, "меньше-или-равно" - это "или строго меньше, или равно"
Эээ, погодите-ка
A7: ∀x∀y(x ≤ y ↔ ∃z(x + z = y)) [определение порядка]x <= x, правда же? Ну и что за "существует z", такой, что x+z = x?
Мы ведь убрали нейтральный элемент из абелевой полугруппы по сложению...
Нет, ДДП можно разместить в массиве. Но это будет массив не только со значениями, но и со всей служебной информацией. В отличие от кучи, чья структура прибита гвоздями, и индексы дочерних и родительского элемента вычисляются.
Поскольку размер дерева фиксированный, то и память под узлы можно выделить один раз. И вместо указателей пользоваться индексами. И вообще, вместо строчного представления взять столбцовое: отдельно массив значений, отдельно массивы индексов, отдельно массив флажков балансировки.
Да, разменяли время на память. Но - разменяли ли? С одной стороны - куча и мусорная корзина (хеш-таблица, которая тоже хранит значения плюс свою служебную информацию), а с другой - просто дерево, которое сразу хранит служебную информацию, зато не дублирует значения.
Кстати, не set, а multiset... Или же map счётчиков.
Ну кстати да. Раз уж у нас добавление в кучу логарифмическое, то возьмём вместо двух куч два ДДП.
Единственная выгода двоичной кучи - в том, что она эффективно размещается на массиве, тогда как set требует динамическую память.
Ну ок, возьмём std::set с пользовательским аллокатором, разместим на массиве (правда, впятеро большего размера: в каждом узле, помимо значения, ещё три указателя и флажок балансировки).
Ну мы же знаем, сколько в каждой куче живых элементов, а сколько дохлых. И балансируем по количеству живых, а не по суммарному размеру контейнера.
От логарифма на каждом шаге мы никак не избавимся, потому что heappush. Мы хотели бы избавиться от n или даже nlogn при удалении произвольного элемента из кучи.
Но давайте-ка сделаем совсем по-другому.
Пусть у нас есть упорядоченный контейнер с логарифмическим поиском-удалением-вставкой. То есть, любое ДДП (хоть АВЛ, хоть КЧД, неважно). И пусть у этого контейнера есть двунаправленные итераторы! Да-да, std::map.
И вот пусть мы знаем не только значение медианного элемента (или пары смежных), но и итератор на медианный элемент.
Теперь, добавляем новое значение в мап. Пусть мап сам занимается своей балансировкой, нам пофигу. Но мы ведь и понимаем, добавили в левое или правое крыло относительно значения медианы. Поэтому сдвигаем итератор медианы в нужную сторону, и это амортизированная O(1).
А потом удаляем старое значение из мапа. И мы также понимаем, из левого или правого крыла. И опять сдвигаем итератор.
Если последовательность монотонно растёт, то мы постоянно добавляем в левую кучу новые элементы (на вершину), а старые помечаем как выбывшие. Но они никогда не окажутся наверху кучи, и поэтому никогда не будут удалены. В результате у нас разрастается и куча, и мусорная корзина. И мы получаем и утечку, и логарифм от маляра Шлемюэля.
Или нет?
Петрик сам активно подставлял свою шёрстку для поглаживания. И искал антибестолочей. И ведь находил, гад! (возможно, к обоюдной пользе)
Он ведь не только с активированным углём бегал, но и с красной ртутью, и со вполне реальными твердотельными лазерами.
Скажите прямо и честно: у вас есть средства на внедрение ваших изобретений? (Средства - это деньги, люди, компании и т.д.)
Если да, то почему ищете денег на патентование не там, а здесь? Ведь ваши партнёры первые заинтересованы в охране ваших и их реализаций.
Если нет, то какой у вас бизнес-план?
Вы ведь понимаете, что выглядите очень странно: патентный тролль, да ещё и шаромыжник.
Может быть, вы и не тролль. Но доказывать вашу благонамеренность - это ваша задача.
Я по-прежнему не понимаю, почему вы включаете режим ССЫКЛА.
Как можно себя подставить, если назвать прямым текстом, что у компании Яндекс есть фейковое приложение-двойник, маскирующееся под оригинальное яндексовское, что это приложение выглядит опасным, а первая линия поддержки проявила себя как-то беспомощно?
Ну вот что случится? Яндекс вычислит по айпи и забанит вас как курьера, в назидание? Или что? Или другие курьеры-конкуренты забьют самокатами? Или хозяева фишингового приложения приедут из своего кол-центра в днепропетровске и тризубом затыкают?
тогда очень похоже - 1230, 1800, 1810 этих саженей = 2274, 3341, 3346 метров "приблизительно"
Вовсе нет. Вы для них не настолько важная персона, что первая линия поддержки известила их отдел соцсетей службы пиара, чтобы они вообще смогли увязать публикацию этой статьи с какой-то там перепиской.
По очень простой причине. Первая линия настолько загружена обращениями пользователей, что они намеренно это всё автоматизируют и в лучшем случае записывают самые интересные случаи куда-нибудь в беклог. Авось раз в квартал набежит менеджер и сделает обзор. В противном случае менеджеры поддержки не могли бы заснуть от распухшей головы в заботах о юзерах.
Думаете, от хорошей жизни там роботы с футболом?
А вот научить первую линию отличать рутинное от критического - это важная задача. И сделать это можно, к сожалению, исключительно через голову службы поддержки.
Поэтому хватит жеманничать. ИМЯ КОМПАНИИ - В СТУДИЮ. Иначе Яндекс будет думать, что вы ломились в Сбер, Сбер - что во Вкусно-И-Точку, а Вкусно-и-Точка - в шавермачечную на вокзале.
что происходит при краже браслета?
Конечно, если желание узнать состояние асинхронной задачи (запускаем - запустили - отменили - закончили с отменой - закончили без отмены) входит в ТЗ, то реализация несколько усложнится.
Но тут мы встанем на очень скользкую дорожку конкурентного выполнения. Когда информация о статусе будет зависеть от моментов, когда мы этот статус спрашиваем и параллельно изменяем.
Поэтому - а насколько часто нам это в коде нужно? Может быть, "выстрелил и забыл" тоже подойдёт?
Меня не покидает чувство, что вы только что переизобрели std::promise/future/async. Да ещё и с довольно странным дизайном, в котором у вас есть явные владельцы и всё такое.
Имхо, надо было отталкиваться от описания задачи, а не от допиливания фич к существующему первичному коду. Причём замечу, что если с самого начала взять фьючерсы, то оперировать тредами вообще не придётся. (Они там будут под капотом).
Итак, хочется
асинхронную функцию, которая как-то сама может проверять флажок остановки
частный случай - функцию, которая делает это в цикле, собранном из условия и тела
Ну окей. Договоримся, что в первом случае это
void(atomic_bool& /*stop*/)Второй делается из первого нехитрым образом:
Если body само по себе длинная операция - ну окей, переделать на
body(stop)Всё. Теперь нам нужна сущность, у которой есть две ручки: cancel и wait. Первая посылает команду остановки (мгновенно), вторая - ждёт завершения, какое бы оно ни было.
Конечно же, нам хотелось бы семантики перемещения хотя бы. Но для этого есть пимпл.
Я бы посоветовал сперва скомпилировать код, прежде чем вставлять его в статью... Потому что он с ошибками.
предлагаете бизнесу размещать свои офисы у вас в датацентрах?
Я думаю, что надо открытым текстом назвать компанию, чья служба поддержки так беспомощно и НАОТШИБИСЬ прореагировала на сообщение о критической проблеме. Потому что это входит в систему. И пока менеджерам самого верхнего уровня не настучат по шапке за антипиар, которого они добились и заслужили, - на первой и второй линиях поддержки (а то и на нулевой, с этими чёртовыми роботами) ничего не изменится.
Это не говнокод, а ху_ня какая-то.
Подкину смежный пример.
Описуемые числа - это числа, которые можно (не обязательно уникально) задать некоторой конечной нотацией, - например, математической формулой или программой на любом языке программирования.
Например, конечные десятичные числа включают в себя множество целых и подмножество рациональных (среди рациональных есть бесконечные десятичные).
Десятичные числа со специальной нотацией ЦЕЛАЯ_ЧАСТЬ , КОНЕЧНАЯ_ДРОБЬ ( ПЕРИОД ) неуникально охватывают все рациональные числа. Неуникально - потому что периоды из девяток равны единице в предыдущий разряд и вырожденному периоду из нулей. То есть, 1,23(9) = 1,23(99) = 1,24.
Алгебраические числа - корни многочленов. Это не только рациональные, но и иррациональные числа. И как мы знаем, для многочленов 5 и более высоких степеней мы даже не всегда можем записать это в виде арифметических формул, дополненных знаком корня целой степени... Но тем не менее, эти числа (неуникально) определяются в виде "вот коэффициенты многочлена, а вот порядковый номер его корня". Если коэффициенты рациональные, номер натуральный, то кортежи таких чисел образуют счётное множество. Поэтому, хоть множество алгебраических чисел и шире, чем рациональных (включает их), но оно по-прежнему счётно.
Трансцедентные числа - то есть, не алгебраические. Вот тут дело обстоит интереснее. Да, очевидно, что вещественные числа - это континуум, а трансцедентные = вещественные \ алгебраические, континуум минус счётность = континуум. Пусть и всюду дырявый.
Однако, если мы попробуем описать любое трансцедентное число... ну, какие у нас есть средства? Именованные константы наподобие пи, е, гаммы там всякой. Именованные функции наподобие синуса, куда подставляем константы и числовые литералы. Безымянные ряды с формулой для члена. Интегралы-неберучки с формулой для подынтегрального выражения. И тому подобное.
А все ли трансцедентные числа можно так описать? А давайте посчитаем!
Пусть у нас есть некоторый язык формул. (И неважно, насколько он формальный - то есть, насколько мы где-то отдельно записали его синтаксис и семантику). Формулы конечной длины из символов конечного алфавита. Образуют множество строк... мощностью... ПРАВИЛЬНО! Счётное!!!
И вот что получилось. Описуемые числа - это счётное множество, которое включает в себя
целые (конечные цепочки цифр и знака)
рациональные (конечные цепочки цифр, знака, разделителей целой части и периода)
алгебраические (инструкции "реши-ка мне вот такое уровнение с многочленом")
некоторые трансцедентные (формулы произвольной громоздкости)
Но мы-то знаем, что всего вещественных чисел - континуум...
СЛЕДОВАТЕЛЬНО: существует континуум (везде дырявый) неописуемых чисел, - подмножество трансцедентных.
И - нет, не пытайтесь найти неописуемое число. Каждая такая попытка, если будет успешной, просто добавит ещё одно число в жалкую счётность описуемых, а континуум без этой штуки останется континуумом.
Тональ и Нагваль. Живите с этим, как хотите.