Re[4]: Аллокация памяти и тредовый робот
От: B0FEE664  
Дата: 22.12.21 08:52
Оценка:
Здравствуйте, σ, Вы писали:

A>>>>
σ>>>void f13() {
σ>>>    struct S {
σ>>>        const char const* s;
σ>>>        S(char const* const s) : s(s) {}
σ>>>    };
σ>>>    char storage[2 * sizeof(S)];
σ>>>    S* s = reinterpret_cast<S*>(storage);
σ>>>    new(s) S("hello world");
σ>>>}
σ>>>

σ>>>Я бы поинтересовался почему не S* s = new(storage) S("hello world"); вместо последних двух строк и в чём разница с дальнейшим использованием s (слева) в s->s.

BFE>>А она (разница) есть? storage не выровнен => s — unspecified. Разве нет?

σ>Выравнивание… Ну да, может не быть недостаточным, но это не то, про что я думал. Можно считать что с ним всё ок.
σ, о чём вы подумали догадаться не сложно, вы лучше скажите, зачем объём storage равен удвоенному размеру S.
И каждый день — без права на ошибку...
Re[5]: Аллокация памяти и тредовый робот
От: σ  
Дата: 23.12.21 09:12
Оценка:
A>>>>>
σ>>>>void f13() {
σ>>>>    struct S {
σ>>>>        const char const* s;
σ>>>>        S(char const* const s) : s(s) {}
σ>>>>    };
σ>>>>    char storage[2 * sizeof(S)];
σ>>>>    S* s = reinterpret_cast<S*>(storage);
σ>>>>    new(s) S("hello world");
σ>>>>}
σ>>>>

σ>>>>Я бы поинтересовался почему не S* s = new(storage) S("hello world"); вместо последних двух строк и в чём разница с дальнейшим использованием s (слева) в s->s.

BFE>>>А она (разница) есть? storage не выровнен => s — unspecified. Разве нет?

σ>>Выравнивание… Ну да, может не быть недостаточным, но это не то, про что я думал. Можно считать что с ним всё ок.
BFE>σ, о чём вы подумали догадаться не сложно, вы лучше скажите, зачем объём storage равен удвоенному размеру S.
Это вопрос к составителям теста.
нелады у вас с ответами
От: жванецкий.головного.мозга Интернет https://youtube.com/shorts/eapWB7W8hEE
Дата: 05.01.22 22:29
Оценка:
Здравствуйте, avovana, Вы писали:

A>На решение был 1 час в домашней обстановке.

A>Image: scal1.pn
static_assert(std::is_same<const int*, int const* >::value, "is not equal");
Отредактировано 06.01.2022 1:49 ботаныч . Предыдущая версия .
Re[13]: таблица виртуальных функций
От: незнайка.незнаек Интернет https://youtube.com/shorts/eapWB7W8hEE
Дата: 10.01.22 04:21
Оценка:
Здравствуйте, reversecode, Вы писали:

R>и тогда на вопрос при собеседовании — что выведет тот код с не виртуальными деструкторами использующие виртуальные методы

R>вы вы как практикующий программист с пруфами на все существующие компилеры скажете ?

>>from A

>>the end
Я конечно могу быть неправым, но это происходит в силу логики переопределения указателя на таблицу виртуальных функций на т.текущего класса. любой имплементер бы сделал без вопросов если есть ненулевой указатель на т.в.ф (а где оно будет заменой указателя на this, или просто сменой указателя в рантайме в сях опять кто его знает, что это будет?), и безусловно сделал бы этот вызов до вызова деструктора. Потому оно и вероятно везде одинаковое. Но это — детали реализации и стандарт это не обсуждает. В силу чего в теории, ткскть стандарта может присутствовать только УБ. и вот это УБ меня лично вполне удовлетворяет. и знаете почему?

R>хотя вопрос будет наверняка провокационным и задающий будет ожидать ответа — уб

потому как любой может проверить, в силу общей костыльности и кустарности отрасли а идет ли вызов из виртуального деструктора или нет, просто потому, что до собственно указателя на твф добраться тяжело и нереально в заявленные сроки. и, соответственно, путь в графе к конечному вызову будет чем дальше, тем запутаннее. Потому, лучше глянуть, что в стандарте и ответить.


R>и я в +100500 раз бы повторил, лавер с++ != программист с++

R>этот точно так же как гражданин страны не обязан знать наизусть все законы той страны где он проживает,

R>иначе юристы бы померли от голода

От зря вы эту тему подняли. Юристы вообще не оперируют формальными языками, они условно говоря "чешут от балды" вроде бы некоторые мысли, которые еще проверять и проверять на однозначность, хотя вероятность нелогичного противоречивого бреда коррелирует с "положением дел", хотя кто и как это посчитает эту противоречивость, особенно, если она преднамеренная, да? Но вот опыта общения с юристами в своей области у меня был. так, что и непреднамеренной неоднозначности от них хватает).
Отредактировано 10.01.2022 4:40 ботаныч . Предыдущая версия .
Многопоточно распарсить файл с fix сообщениями
От: avovana Россия  
Дата: 14.01.22 14:27
Оценка:
Добрый день, дорогие форумчане!

Задача на многопоточность на парсинг файла.
На вход приходит файл под 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 итоговый
Отредактировано 15.01.2022 9:04 avovana . Предыдущая версия .
Re: Многопоточно распарсить файл с fix сообщениями
От: Максим Россия  
Дата: 15.01.22 21:28
Оценка: +1
A>Придумал такое решение:
A>а) Разделить исходный файл на куски == количеству ядер == количеству потоков
A>б) Каждому потоку отдать свой кусок и условие для фильтрации

Когда в дело вступает "диск", сложно обходиться теоретическими рассуждениями, все надо мерить на конкретной системе. Возможно быстрее будет работать подход, когда только один поток читает данные с диска и "накидывает" их пулу обработчиков.

П.С.
Владимир, как собеседования продвигаются? Понравились какие-нибудь конторы?

Смотрю сейчас канал парня, который активно, в данный момент, ходит по собеседованиям, может будет полезно и Вам https://www.youtube.com/channel/UC99om0N3qZc5t8iSy2QrHZA/videos
Вот, например, интересные, на мой взгляд, задачки https://www.youtube.com/watch?v=UdY_YMFx7SY

Дан отсортированный массив целых чисел, нужно вернуть отсортированный массив квадратов этих чисел.

(с 40 минуты)
Errare humanum est
Отредактировано 15.01.2022 21:35 Максим . Предыдущая версия .
Re: Многопоточно распарсить файл с fix сообщениями
От: AndrewJD США  
Дата: 18.01.22 17:14
Оценка:
Здравствуйте, 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 сообщениями
От: PM  
Дата: 18.01.22 20:23
Оценка: 3 (1)
Здравствуйте, Максим, Вы писали:

М>Смотрю сейчас канал парня, который активно, в данный момент, ходит по собеседованиям, может будет полезно и Вам https://www.youtube.com/channel/UC99om0N3qZc5t8iSy2QrHZA/videos

М>Вот, например, интересные, на мой взгляд, задачки https://www.youtube.com/watch?v=UdY_YMFx7SY
М>

М>Дан отсортированный массив целых чисел, нужно вернуть отсортированный массив квадратов этих чисел.

М>(с 40 минуты)

Видео лень смотреть, но в конце код выглядит сложновато. Решение из серии "переверни строку", что-то типа
vector<int> sortedSquares(vector<int>& A)
{
    vector<int> ret(A.size());
    int r=A.size()-1,l=0;
    for(int i=r;i>=0;i--)
    {
        if(abs(A[r])>abs(A[l]))
            ret[i]=A[r]*A[r--];
        else
            ret[i]=A[l]*A[l++];
    }
    return ret;
}


https://marcoarena.wordpress.com/2019/11/28/tale-of-an-insight/
Re: Многопоточно распарсить файл с fix сообщениями
От: avovana Россия  
Дата: 13.02.22 17:45
Оценка:
Моя реализация:
https://github.com/avovana/temp/tree/master/filter_FIX_message_with_thread_pool

П.С. Подсчитывал время, сколько на него потратил. Попробуйте угадать
Re[2]: Многопоточно распарсить файл с fix сообщениями
От: reversecode google
Дата: 13.02.22 17:47
Оценка:
A>П.С. Подсчитывал время, сколько на него потратил. Попробуйте угадать

>CMakeLists.txt

>Added FIX messages filtering
>25 days ago
Re[2]: Многопоточно распарсить файл с fix сообщениями
От: avovana Россия  
Дата: 13.02.22 17:49
Оценка:
Здравствуйте, AndrewJD, Вы писали:

AJD>Пара замечаний:

AJD>1. если файл всего 1 Мб, то быстрее его распарсить в один поток.
AJD>2. Как разделить файл на части, ведь одно сообщение может попасть в разные куски?

Ответил на своё же сообщение ссылкой на гитхаб.
1. Как оказалось, надо было уточнять. Похоже, входящий поток может быть и больше.
2. Верно подмечено. В реализации в моменте как-раз и добегал до окончания сообщения прежде чем кинуть весь кусок в поток. Чтобы очередному потоку пошёл кусок, который начинается с начала очередного сообщения.
Re[2]: Многопоточно распарсить файл с fix сообщениями
От: avovana Россия  
Дата: 13.02.22 17:51
Оценка:
Здравствуйте, Максим, Вы писали:

М>Когда в дело вступает "диск", сложно обходиться теоретическими рассуждениями, все надо мерить на конкретной системе. Возможно быстрее будет работать подход, когда только один поток читает данные с диска и "накидывает" их пулу обработчиков.

Это интересно! Измерения не делал. Как бы Вы их сделали?

М>Владимир, как собеседования продвигаются? Понравились какие-нибудь конторы?

Спасибо, что поинтересовались. Устраиваюсь на новую работу.
Даже хотел статью написать. Точнее, цикл. Первая статья готова. Осталось картинку вставить и нажать "Отправить" из черновика хабра. Что-то не нажму всё никак)

Спасибо за ссылку!
Re: replace
От: sergii.p  
Дата: 14.02.22 09:01
Оценка:
Здравствуйте, avovana, Вы писали:

A>// написать функцию replace c 3-мя входными аргументами, возвращающую новую строку


input копируете и никак потом не используете. Тогда уж лучше по string_view передавать. substr и replace_to — тоже самое. Результирующая строка res гарантированно расширяется и неизбежны переаллокации памяти. Надо reserve добавить, как минимум.
Ну и куча мутабельных состояний, из-за чего алгоритм нечитабелен.

Мой вариант:

std::string replace_impl(std::string source, std::string_view from, std::string_view to, const std::string::size_type start_idx)
{
    const auto pos = source.find(from, start_idx);
    if(pos == std::string::npos) {
        return source;
    }
    else {
        source.replace(pos, from.size(), to);
        return replace_impl(std::move(source), from, to, pos + to.size());
    }
}

std::string replace_all(std::string source, std::string_view from, std::string_view to)
{
    return replace_impl(std::move(source), from, to, 0);
}
Re: Вопросы с собеседований
От: _NN_ www.nemerleweb.com
Дата: 18.02.22 17:44
Оценка:
В нескольких компаниях спрашивали как написать планировщик.
Ещё из вопросов как наиболее быстро фильтровать поступающие данные.
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re[2]: Вопросы с собеседований
От: reversecode google
Дата: 18.02.22 17:47
Оценка: +1 :)
это наверное на джуниорские позиции ?
обычно синьорам дают написать имплементацию strlen или strcpy
Re[3]: Вопросы с собеседований
От: _NN_ www.nemerleweb.com
Дата: 18.02.22 18:15
Оценка:
Здравствуйте, reversecode, Вы писали:

R>это наверное на джуниорские позиции ?

Синьор, принципал.
R>обычно синьорам дают написать имплементацию strlen или strcpy

Такое никто не просил
Одну-две задачки в стиле leetcode, разного уровня сложности это да.
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re: Реализация тредпула с отложенным выполнением
От: avovana Россия  
Дата: 08.10.22 08:07
Оценка:
Вот приходите на интервью и вам говорят сделать:
"Реализацию тредпула с отложенным выполнением".

О чём в первую очередь подумаете когда услышите такую формулировку?
Какие есть мысли по реализации?
Какие есть хорошие примеры?

Я накопал в интернете несколько примеров:

======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]: Реализация тредпула с отложенным выполнением
От: reversecode google
Дата: 08.10.22 13:08
Оценка:
если вы хотите дальше ходить по собеседованием и делать тупые никому не нужные задания
то вы все делаете правильно продолжайте

если хотите найти работу, то сразу переходите в нападение
и сразу заявляйте что никаких тестовых заданий вы делать не будете, вам это не интересно
Re[4]: Вопросы с собеседований
От: GarryIV  
Дата: 08.10.22 19:37
Оценка:
Здравствуйте, Максим, Вы писали:

М> 100000 100000 ... 1000000

М>-100000 -100000 ... -1000000
М> 100000 100000 ... 1000000
М>-100000 -100000 ... -1000000
М> 100000 100000 ... 1000000
М>-100000 -100000 ... -1000000
М>....

М>При одном способе обхода будет 0, а при другом все, что угодно.


А можно пример кода когда на одной и той же платформе, ключах компилятора и тд будут действительно разные результаты?
Это реально вообще?
WBR, Igor Evgrafov
Re: Красивые числа
От: s_aa Россия  
Дата: 11.10.22 06:31
Оценка:
Заинтересовался что-то, тем более правильный ответ есть.
Вот вариант на JS

// число цифр слева и справа от центральной
const m = 6;
// общее количество цифр - оно же система счисления
const n = m * 2 + 1;
// последняя цифра в системе счисления по основанию n
const 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;
}
Жизнь не обязана доставлять удовольствие. Достаточно отсутствия страданий.
Отредактировано 11.10.2022 8:17 s_aa . Предыдущая версия .
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.