σ>>>Я бы поинтересовался почему не S* s = new(storage) S("hello world"); вместо последних двух строк и в чём разница с дальнейшим использованием s (слева) в s->s.
BFE>>А она (разница) есть? storage не выровнен => s — unspecified. Разве нет? σ>Выравнивание… Ну да, может не быть недостаточным, но это не то, про что я думал. Можно считать что с ним всё ок.
σ, о чём вы подумали догадаться не сложно, вы лучше скажите, зачем объём storage равен удвоенному размеру S.
σ>>>>Я бы поинтересовался почему не S* s = new(storage) S("hello world"); вместо последних двух строк и в чём разница с дальнейшим использованием s (слева) в s->s.
BFE>>>А она (разница) есть? storage не выровнен => s — unspecified. Разве нет? σ>>Выравнивание… Ну да, может не быть недостаточным, но это не то, про что я думал. Можно считать что с ним всё ок. BFE>σ, о чём вы подумали догадаться не сложно, вы лучше скажите, зачем объём storage равен удвоенному размеру S.
Это вопрос к составителям теста.
Здравствуйте, reversecode, Вы писали:
R>и тогда на вопрос при собеседовании — что выведет тот код с не виртуальными деструкторами использующие виртуальные методы R>вы вы как практикующий программист с пруфами на все существующие компилеры скажете ?
>>from A >>the end
Я конечно могу быть неправым, но это происходит в силу логики переопределения указателя на таблицу виртуальных функций на т.текущего класса. любой имплементер бы сделал без вопросов если есть ненулевой указатель на т.в.ф (а где оно будет заменой указателя на this, или просто сменой указателя в рантайме в сях опять кто его знает, что это будет?), и безусловно сделал бы этот вызов до вызова деструктора. Потому оно и вероятно везде одинаковое. Но это — детали реализации и стандарт это не обсуждает. В силу чего в теории, ткскть стандарта может присутствовать только УБ. и вот это УБ меня лично вполне удовлетворяет. и знаете почему?
R>хотя вопрос будет наверняка провокационным и задающий будет ожидать ответа — уб
потому как любой может проверить, в силу общей костыльности и кустарности отрасли а идет ли вызов из виртуального деструктора или нет, просто потому, что до собственно указателя на твф добраться тяжело и нереально в заявленные сроки. и, соответственно, путь в графе к конечному вызову будет чем дальше, тем запутаннее. Потому, лучше глянуть, что в стандарте и ответить.
R>и я в +100500 раз бы повторил, лавер с++ != программист с++ R>этот точно так же как гражданин страны не обязан знать наизусть все законы той страны где он проживает,
R>иначе юристы бы померли от голода
От зря вы эту тему подняли. Юристы вообще не оперируют формальными языками, они условно говоря "чешут от балды" вроде бы некоторые мысли, которые еще проверять и проверять на однозначность, хотя вероятность нелогичного противоречивого бреда коррелирует с "положением дел", хотя кто и как это посчитает эту противоречивость, особенно, если она преднамеренная, да? Но вот опыта общения с юристами в своей области у меня был. так, что и непреднамеренной неоднозначности от них хватает).
Задача на многопоточность на парсинг файла.
На вход приходит файл под 1 Мб c сообщениями FIX формата
Прикрепляю фотку как это выглядит на облачном диске и как в реале, если открыть Notepad++.
В основном, сообщение это тег=значениеSOHтег=значениеSOH
SOH — это такой символ-разделитель.
В начале каждого сообщения 8=FIX.4.4.
Т.е. отдельное сообщение будет выглядеть:
8=FIX.4.4SOH9=75SOH35=0SOH49=MFIXTradeIDSOH56=MU0319300002SOH34=4949SOH52=20211215-20:10:16.250076549SOH10=244SOH
Нужно выдать на выходе подмножество сообщений:
1) Используя самописный пул поток распарсить файл
2) Давая возможность юзеру задать временной интервал. В сообщение есть метка времени в теге 52. Собственно, проверить, входит ли значение в интервал
3) Еще юзер может задать доп фильтрацию. Типа хочет сообщения еще у которых тег1=значение1 && тег2=значение1 ...
4) Пользоваться только С++ и std. Не пользоваться регулярками.
Пример вывода:
8=FIX.4.4|9=11|35=0|49=some1|12=mp2|52=20221016-10:12:15|10=2|
8=FIX.4.4|9=22|35=0|49=some2|12=mp2|52=20221016-10:13:16|10=2|
8=FIX.4.4|9=33|35=0|49=some3|12=mp2|52=20221016-10:14:46|10=2|
====================
Придумал такое решение:
а) Разделить исходный файл на куски == количеству ядер == количеству потоков
б) Каждому потоку отдать свой кусок и условие для фильтрации
в) Каждый поток:
-парсит свой кусок выделяя сообщения. Сохраняет очередное сообщение в map<сообщение, hash_map<тег, значение>>
-перебирает map проверяя условия — временная метка входит ли в интервал, теги имеют ли нужные значения
-добавляет отфильтрованные сообщения в результирующий вектор
-возвращает результирующий вектор
г) Основной поток main:
-дожидается результата=результирующих векторов от всех потоков.
-складывает все вектора в итоговый
-возвращает в stdout итоговый
A>Придумал такое решение: A>а) Разделить исходный файл на куски == количеству ядер == количеству потоков A>б) Каждому потоку отдать свой кусок и условие для фильтрации
Когда в дело вступает "диск", сложно обходиться теоретическими рассуждениями, все надо мерить на конкретной системе. Возможно быстрее будет работать подход, когда только один поток читает данные с диска и "накидывает" их пулу обработчиков.
П.С.
Владимир, как собеседования продвигаются? Понравились какие-нибудь конторы?
Здравствуйте, avovana, Вы писали:
A>Задача на многопоточность на парсинг файла. A>На вход приходит файл под 1 Мб c сообщениями FIX формата
A>Придумал такое решение: A>а) Разделить исходный файл на куски == количеству ядер == количеству потоков A>б) Каждому потоку отдать свой кусок и условие для фильтрации
Пара замечаний:
1. если файл всего 1 Мб, то быстрее его распарсить в один поток.
2. Как разделить файл на части, ведь одно сообщение может попасть в разные куски?
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Re[2]: Многопоточно распарсить файл с fix сообщениями
Здравствуйте, AndrewJD, Вы писали:
AJD>Пара замечаний: AJD>1. если файл всего 1 Мб, то быстрее его распарсить в один поток. AJD>2. Как разделить файл на части, ведь одно сообщение может попасть в разные куски?
Ответил на своё же сообщение ссылкой на гитхаб.
1. Как оказалось, надо было уточнять. Похоже, входящий поток может быть и больше.
2. Верно подмечено. В реализации в моменте как-раз и добегал до окончания сообщения прежде чем кинуть весь кусок в поток. Чтобы очередному потоку пошёл кусок, который начинается с начала очередного сообщения.
Re[2]: Многопоточно распарсить файл с fix сообщениями
Здравствуйте, Максим, Вы писали:
М>Когда в дело вступает "диск", сложно обходиться теоретическими рассуждениями, все надо мерить на конкретной системе. Возможно быстрее будет работать подход, когда только один поток читает данные с диска и "накидывает" их пулу обработчиков.
Это интересно! Измерения не делал. Как бы Вы их сделали?
М>Владимир, как собеседования продвигаются? Понравились какие-нибудь конторы?
Спасибо, что поинтересовались. Устраиваюсь на новую работу.
Даже хотел статью написать. Точнее, цикл. Первая статья готова. Осталось картинку вставить и нажать "Отправить" из черновика хабра. Что-то не нажму всё никак)
Здравствуйте, avovana, Вы писали:
A>// написать функцию replace c 3-мя входными аргументами, возвращающую новую строку
input копируете и никак потом не используете. Тогда уж лучше по string_view передавать. substr и replace_to — тоже самое. Результирующая строка res гарантированно расширяется и неизбежны переаллокации памяти. Надо reserve добавить, как минимум.
Ну и куча мутабельных состояний, из-за чего алгоритм нечитабелен.
Здравствуйте, reversecode, Вы писали:
R>это наверное на джуниорские позиции ?
Синьор, принципал. R>обычно синьорам дают написать имплементацию strlen или strcpy
Такое никто не просил
Одну-две задачки в стиле leetcode, разного уровня сложности это да.
Вот приходите на интервью и вам говорят сделать:
"Реализацию тредпула с отложенным выполнением".
О чём в первую очередь подумаете когда услышите такую формулировку?
Какие есть мысли по реализации?
Какие есть хорошие примеры?
Я накопал в интернете несколько примеров:
======1========
Комбинация:
queue<function<void()>> jobs — в неё пишут функции для исполнения, из неё выгребают потоки пула чтобы исполнить.
vector<thread> — набор потоков для исполнения задач. В инициализации определяем сколько будет потоков.
mutex — один мьютекс на доступ записи в очередь очередной задачи, выбирания потоками на исполнение.
condition variable — сигнал от писателя, что есть данные в очереди. Потоки засыпают и ждут на ней пока не появятся данные.
// Использование:
thread_pool->QueueJob([] { /* ... */ });
class ThreadPool {
public:
void Start();
void QueueJob(const std::function<void()>& job);
void Stop();
void busy();
private:
void ThreadLoop();
bool should_terminate = false; // Tells threads to stop looking for jobs
std::mutex queue_mutex; // Prevents data races to the job queue
std::condition_variable mutex_condition; // Allows threads to wait on new jobs or termination
std::vector<std::thread> threads;
std::queue<std::function<void()>> jobs;
};
void ThreadPool::Start() {
const uint32_t num_threads = std::thread::hardware_concurrency(); // Max # of threads the system supports
threads.resize(num_threads);
for (uint32_t i = 0; i < num_threads; i++) {
threads.at(i) = std::thread(ThreadLoop);
}
}
void ThreadPool::ThreadLoop() {
while (true) {
std::function<void()> job;
{
std::unique_lock<std::mutex> lock(queue_mutex);
mutex_condition.wait(lock, [this] {
return !jobs.empty() || should_terminate;
});
if (should_terminate) {
return;
}
job = jobs.front();
jobs.pop();
}
job();
}
}
void ThreadPool::QueueJob(const std::function<void()>& job) {
{
std::unique_lock<std::mutex> lock(queue_mutex);
jobs.push(job);
}
mutex_condition.notify_one();
}
void ThreadPool::busy() {
bool poolbusy;
{
std::unique_lock<std::mutex> lock(queue_mutex);
poolbusy = jobs.empty();
}
return poolbusy;
}
void ThreadPool::Stop() {
{
std::unique_lock<std::mutex> lock(queue_mutex);
should_terminate = true;
}
mutex_condition.notify_all();
for (std::thread& active_thread : threads) {
active_thread.join();
}
threads.clear();
}
thread_pool->QueueJob([] { /* ... */ });
======2========
Реализация с помощью:
1) future + deferred. Как-то странно. Т.е. в пул как обычно кинули задачу. Внутри пул её обернули в future+deferred, положил в очередь. Поток проснулся, взял её. Выполнил get. Зачем эта связка — future + deferred? В этом же потоке происходит исполнение
2) Прокидывание аргументов — хорошая фича. Нет ограничений в сравнение с прошлым примером
Самый понятный и простой на данный момент пул.
#pragma once
#include <future>
#include <thread>
#include <condition_variable>
#include <atomic>
#include <queue>
#include <vector>
#include <tuple>
#include <functional>
#include <utility>
class ThreadPool {
using Task = std::future<void>;
public:
explicit ThreadPool(std::size_t threads_num);
~ThreadPool();
template <typename F, typename ... Args>
void addTask(F f, Args&& ... args) {
{
std::lock_guard<std::mutex> l(cv_m_);
if (quit_) {
throw std::runtime_error("adding task to stopped threadpool");
}
tasks_.emplace(std::async(std::launch::deferred, std::forward<F>(f), std::forward<Args>(args)...));
}
condition_.notify_one();
}
private:
std::mutex cv_m_;
std::condition_variable condition_;
std::atomic_bool quit_ = false;
std::queue<Task> tasks_;
std::vector<std::thread> workers_;
};
ThreadPool::ThreadPool(std::size_t threads_num)
{
for (std::size_t i = 0; i < threads_num; ++i) {
workers_.emplace_back(
[this](){
while (true) {
std::unique_lock<std::mutex> lk(this->cv_m_);
condition_.wait(lk, [this](){
return !this->tasks_.empty() || this->quit_;
});
if (this->quit_ && this->tasks_.empty()) {
return;
}
if (!this->tasks_.empty()) {
auto f = std::move(this->tasks_.front());
this->tasks_.pop();
lk.unlock();
f.get();
}
}
}
);
}
}
ThreadPool::~ThreadPool() {
quit_ = true;
condition_.notify_all();
for (auto& worker : workers_) {
worker.join();
}
}
Re[2]: Реализация тредпула с отложенным выполнением
Заинтересовался что-то, тем более правильный ответ есть.
Вот вариант на JS
// число цифр слева и справа от центральнойconst m = 6;
// общее количество цифр - оно же система счисленияconst n = m * 2 + 1;
// последняя цифра в системе счисления по основанию nconst lastNumber = n - 1;
// максимальная сумма m цифрconst maxSum = lastNumber * m;
// массив для подсчета количества вариантов разных значений суммы m цифрconst aSum = new Array(maxSum + 1).fill(0);
// максимальное число, которое можно представить m разрядами в системе счисления по основанию n
let maxNumber = 0;
for (let i = 0; i < m; ++i) {
maxNumber += n ** i * lastNumber;
}
// перебираем все варианты расположения цифр в m разрядах
// и подсчитываем в массиве aSum количество значений суммыfor (let i = 0; i <= maxNumber; ++i) {
const s = changeBaseNumber(i, n).reduce((partialSum, a) => partialSum + a, 0);
aSum[s]++;
}
// вычисляем общее количество "красивых" чиселconst result = aSum.reduce((partialSum, a) => partialSum + a * a * n, 0);
// сверяем с правильным результатом
console.log(result === 9203637295151);
/**
* Возвращает массив цифр для системы счисления по основанию osn для числе i
* @param {number} i
* @param {number} osn
* @returns
*/function changeBaseNumber(i, osn) {
const aOsn = [];
let i0 = i;
let j = 1;
while (true) {
const ost = i0 % osn;
i0 = (i0 - ost) / osn;
aOsn.push(ost);
if (i0 === 0) break;
j++;
}
return aOsn;
}
Жизнь не обязана доставлять удовольствие. Достаточно отсутствия страданий.