какую структуру данных вы бы использовали для передачи задач между двумя потоками
Обмен данными между потоками
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Обмен данными между компьютером и ПЛК по TCP
Добрый день! Подскажите пожалуйста, реально ли написать программу на C++ Builder для получения.
Обмен данными между RAD Studio Berlin и cmd
Всем привет. Как реализовать обмен данными между C++ и cmd. Отправляю команду в консоль, а из.
Обмен данными между программой и сервисом через NamedPipe
Всем доброго времени суток. Друзья, у меня такая проблема: Создаю сервис, на OnExecute создаю.
Обмен данными между C++ Builder и Java компонентами socket-ов
Всем доброго времени суток. Не знаю, следует-ли создавать эту тему именно в данном разделе, т.к.
Добавлено через 2 минуты
SatanaXIII, то есть будет достаточно сделать большой массив глобальной переменной, писать в него в 1м потоке, но запретить изменять её во 2 потоке (аналогично и для потоков 2 и 3) и добавить пару флагов, которые сообщал бы следующему потоку, что данные можно забирать?
Я как-то так и предполагал, но меня это смущает только тем, что глобальные переменные присущи С, в С++ рекомендуется их всячески избегать. В принципе, я понимаю, что если внимательно проследить, чтобы два класса не меняли данные одновременно, то ничего страшного нет, но думал, что есть какой-то более правильные метод обмена данными.
gumi250, в вашем варианте не может быть такого, что первый поток хочет писать данные, но второй ещё не закончил обработку и не дает ему это делать, из-за чего данные теряются?
Ещё один вопрос: мою задачу можно реализовать на таймерах TTimer, не связываясь с потоками. Насколько это решение хуже/лучше/правильней/неправильней потоков? Не смог найти никакой информации об этом.
Передача сообщений между потоками. Классические блокирующие алгоритмы
Когда-то я вылез из песочницы с совочком в руке и постом о неблокирующих очередях и передаче данных между потоками. Тот пост был не столько об алгоритмах и их реализации, сколько об измерении быстродействия. Тогда же мне в комментариях задали совершенно резонный вопрос об обычных, блокирующих алгоритмах передачи — насколько они медленнее и вообще как выбрать оптимальный алгоритм под конкретную задачу.
Я конечно обещал и с энтузиазмом принялся за дело, даже получил забавные результаты, однако… какой-то изюминки не хватало, выходило скучно и плоско. В результате мой внутренний перфекционист обьединился с моим нескрываемым прокрастинатором и вдвоем они меня одолели, пост надолго осел в черновиках и даже совесть уже не вздрагивала при виде забытого заголовка.
Однако все меняется, появляются новые технологии, старые исчезают в архивах, и я вдруг решил что пришло время отдавать долги и сдерживать обещания. В качестве наказания мне пришлось все переписать с нуля, если скупой платит дважды, то ленивый дважды переделывает, так мне и надо.
Да, за КДПВ извиняюсь — оно конечно совсем из другой предметной области, но для иллюстрации взаимодействия между потоками подходит тем не менее идеально.
Так что же разбудило Герцена?
— чрезвычайно концептуально красивым языком, унаследовавшим и мощно двинувшим вперед идиомы C++ и при этом сохранившим эффективные низкоуровневые инструменты, вплоть до указателей. Возможно из-за этого на мой взгляд в стандартной библиотеке D есть некоторая раздвоенность — большинство функционала можно вызвать или из коробки, простым и легким способом, или через приближенный к нативному интерфейс, зато полностью используя ресурсы и возможности системы. Если C++ перекрывает непрерывным спектром весь диапазон, то в D обычно хорошо заметно такое разделение. Посмотрите сами: нужно измерить интервал времени, есть замечательный модуль std.datetime, однако квант измерения — 100 нс, что мне совершенно недостаточно, пожалуйста — есть не менее замечательный модуль — core.time. Не устраивает облегченный до предела яваподобный std.concurrency.spawn — можете использовать весь букет из core.thread. И так практически везде, за исключением одного, но чрезвычайно важного места — разделения данных между потоками. Да, да, все локальные для данного потока переменные размещаются в thread local storage и никакими силами нельзя заставить другой поток увидеть их адрес. А для обмена данными предусмотрены встроенные очереди, надо признать очень удобные — полиморфные, с возможностью внеочередной посылки важных сообщений и чрезвычайно приятным интерфейсом. Посылать данные через них можно естественно или by value, или неизменяемые (immutable) ссылки. Я, когда об этом прочитал первый раз, просто подпрыгнул от возмущения — «Да как же рука ваша поганая поднялась. » — а потом задумался, припомнил свои проекты за последние годы и признал — да, весь обмен между потоками проходит по такой схеме, а то что не проходит — явная ошибка дизайна.
И тем не менее вопрос повис в воздухе — насколько эффективны очереди в D? Если нет, то это сводит на нет всю прочую эффективность языка, этакое встроенное бутылочное горлышко. Вот так я проснулся и снова взялся за измерения.
Что же конкретно мы будем мерить?
Вопрос на самом деле непростой, я об этом писал и в прошлый раз и пожалуй повторюсь. Обычный «наивный» подход, когда посылают N сообщений, замеряют общее время и делят на N не работает. Давайте разберемся, мы меряем производительность очереди, так? Следовательно можно считать что в процессе измерения скорость генератора сообщений и приемника сообщений стремится к бесконечности, при разумном предположении что внутри очереди данные не копируются, оказывается выгодным поместить как можно больше данных в очередь, потом выполнить однократную передачу некоторого внутреннего указателя и все, данные уже там. При этом среднее время на сообщение будет падать как 1/N (на самом деле ограничено снизу временем вставки/удаления, которое может составлять единицы наносекунд) тогда как время доставки каждого сообщения в теории остается постоянным, и даже растет как O(N) на практике.
Вместо этого я использую противоположный подход — каждое сообщение посылается, замеряется время и только потом посылается следующее (latency). Как следствие, результаты представляются в виде гистограмм, по оси X — время, по оси Y — число пакетов доставленных за это время. Наиболее интересны численно два параметра — медианное среднее время распределения и процент сообщений не уложившихся в некоторый (произвольный) верхний предел.
Строго говоря, такой подход тоже не вполне адекватен, тем не менее он гораздо точнее описывает требования к быстродействию. Я немножко позанимаюсь самокритикой в заключении, пока только скажу что полное описание включало бы генерацию всех возможных видов трафика и анализ его статистическими методами, получилась бы полноценная научная работа из области теории QA, или скорее меня бы настиг очередной приступ прокрастинации.
Еще один момент, упоминаю об этом потому что прошлый раз были долгие дебаты, генератор сообщений может вставлять их в очередь сколь угодно быстро, но при условии что получатель в среднем успевает их извлекать и обрабатывать, иначе все измерение просто лишено смысла. Если ваш принимающий поток не успевает обрабатывать поток данных, надо сделать код быстрее, распараллелить обработку, изменить протокол сообщений, но в любом случае сама очередь здесь не причем. Вроде бы мысль простая, однако прошлый раз пришлось повторять несколько раз в комментариях. Флуктуации скорости, когда вдруг в очереди оказывается много сообщений, вполне возможны и даже неизбежны, это как раз один из факторов который хорошо спроектированный алгоритм должен сглаживать, но это возможно только если максимальная скорость приема больше средней скорости посылки.
Начнем-с
Это что? А это собственно результат, все мои труды уложились в одну картинку, зато я сейчас буду долго обьяснять что и зачем здесь нарисовано.
Розовый. Стандартный механизм D
Синий. Лютый и неприкрытый C++.
Так что же можно сделать оставаясь в рамках разумного?
Красный. Разумный и взвешенный C++.
Выход один и он очевиден — использовать std::condition_variable, благо что мьютексы для синхронизации у нас уже используются и изменения в коде будут минимальными. В таком варианте получатель засыпает на переменной если очередь пуста, а генератор сообщений посылает сигнал если подозревает что партнер может спать. В этом случае ядро имеет все возможности для оптимизации и мы получаем результат, 3 микросекунды. Это уже можно сказать что ого, мы наступаем буквально на пятки всяким хитрым реализациям, при этом базовый код крайне прост и его можно адаптировать под все случаи жизни. Никакой полиморфизм здесь конечно и не ночевал как в D, зато и получилось почти в два раза быстрее. Без шуток, это вполне реальный конкурент неблокирующим алгоритмам.
Зеленый. Мастштабируемость, масштабируемость.
А это архитектурное решение которое я долго искал и вынашивал, хотя результат выглядит крайне просто. Часто спрашивают, сколько максимально сообщений в секунду можно передать через очередь и тому подобные вещи, забывая что противоположная ситуация случается не менее часто — пусть у нас имеется некоторое количество потоков, которые занимаются своим делом и время от времени должны посылать сообщения, не слишком часто, но важных. Мы не хотим на каждый такой поток вешать отдельного слушателя, который все равно будет по большей части спать, значит придется создать один общий центр обработки, который будет опрашивать все очереди и обслуживать сообщения по мере поступления. Но поскольку у нас сегодня не вечер длинного кода, а вечер коротких концептуальных фрагментов, я предлагаю использовать boost::asio, в качестве огромного бонуса этот же поток может обслуживать еще и сокеты и таймеры. Здесь, кстати, можно было бы легко обойтись вообще без очереди, захватывая данные прямо в передаваемой функции, очередь служит скорее как агрегатор и буфер для данных, ну и для смысловой связки с предыдущими примерами.
И что же мы получаем? 4.3 микросекунды на процессе из только одного генератора, совсем даже неплохо. Надо учитывать что результат неизбежно ухудшится в системе где много потоков одновременно пишут сообщения, однако масштабируемость практически ничем неограничена и это многого стоит.
Еще раз хочу подчеркнуть в чем философский смысл этого фрагмента — мы пересылаем в другой поток не просто данные, а данные плюс функтор, который сам знает как с ними работать, что-то вроде межпоточной виртуальности. Это настолько общая концепция, что могла бы наверное претендовать на звание отдельного design pattern.
На этом экспериментальная часть заканчивается, если нужен код всех тестов то вот он. Осторожно, это не готовая библиотека, так что бездумно копировать не советую, однако может служить вполне годным тьюториалом для разработки своего кода. Дополнения и улучшения приветствуются.
Разные рассуждения, по делу и не очень.
Однако самый возможно тяжелый режим — когда сообщения приходят очень редко, но требуют немедленной реакции. За такое время может произойти что угодно, включая выпадение в своп. Если при нормальном распределении интервалов такие события случаются редко и попадают в те доли процента которые мы отбросили в тестах, то в этом случае эффективность может упасть на порядки.
8 известных структур данных, о которых спросят на собеседовании
Кратко разбираем 8 основных структур данных, в которых должен разбираться каждый разработчик. Проверьте свои теоретические знания.
Никлаус Вирт, швейцарский информатик, написал в 1976 году книгу под названием «Алгоритмы + структуры данных = программы».
Больше сорока лет спустя это уравнение все еще верно. Почти все задачи программирования требуют от разработчика глубокого понимания структур данных. Вопросы на эту тему обязательно встречаются на любом IT-собеседовании.
Иногда в этих вопросах явно упоминается искомая структура, например, «дано двоичное дерево». В других случаях это не столь очевидно, например, «мы хотим отслеживать количество книг, связанных с каждым автором».
Изучение структур данных имеет важное значение, даже если вы не ищете новую работу, а просто хотите улучшить текущую. Давайте начнем с понимания основ.
Что такое структуры данных?
Простыми словами, структура данных – это контейнер, который хранит информацию в определенном виде. Из-за такой «компоновки» она может быть эффективной в одних операциях и неэффективной в других. Цель разработчика – выбрать из существующих структур оптимальный для конкретной задачи вариант.
Зачем нужны структуры данных?
Данные являются самой важной сущностью в информатике, а структуры позволяют хранить их в организованной форме.
Какую бы проблему вы не решали, вам приходится иметь дело с данными — будь то зарплата сотрудника, цены на акции, список покупок или даже простой телефонный справочник.
В зависимости от ситуации данные должны храниться в некотором определенном формате. Структуры данных предлагают несколько вариантов таких размещений.
8 часто используемых структур
Давайте сначала перечислим наиболее часто используемые структуры данных, а затем рассмотрим их одну за другой:
Массивы
Массив – это самая простая и наиболее широко используемая из структур. Стеки и очереди являются производными от массивов.
Вот изображение простого массива размером 4, содержащего элементы (1, 2, 3 и 4).
Каждому из них присваивается неотрицательное числовое значение – индекс, который соответствует позиции этого элемента в массиве. Большинство языков определяют начальный индекс массива как 0.
Существует два типа массивов:
Основные операции с массивами
Частые вопросы о массивах
Стеки
Мы все знакомы с опцией Отменить (Undo), которая присутствует практически в каждом приложении. Вы когда-нибудь задумывались, как это работает?
Для этого вы сохраняете предыдущие состояния приложения (определенное их количество) в памяти в таком порядке, что последнее сохраненное появляется первым. Это не может быть сделано только с помощью массивов. Здесь на помощь приходит стек.
Пример стека из реальной жизни – куча книг, лежащих друг на друге. Чтобы получить книгу, которая находится где-то в середине, вам нужно удалить все, что лежит сверху. Так работает метод LIFO (Last In First Out, последним пришел – первым ушел).
Вот изображение стека, содержащего три элемента (1, 2 и 3). Элемент 3 находится сверху и будет удален первым:
Основные операции со стеками
Часто задаваемые вопросы о стеках
Очереди
Как и стек, очередь – это линейная структура данных, которая хранит элементы последовательно. Единственное существенное различие заключается в том, что вместо использования метода LIFO, очередь реализует метод FIFO (First in First Out, первым пришел – первым ушел).
Идеальный пример этих структур в реальной жизни – очереди людей в билетную кассу. Если придет новый человек, он присоединится к линии с конца, а не с начала. А человек, стоящий впереди, первым получит билет и, следовательно, покинет очередь.
Вот изображение очереди, содержащей четыре элемента (1, 2, 3 и 4). Здесь 1 находится вверху и будет удален первым:
Основные операции с очередями
Часто задаваемые вопросы об очередях
Связный список
Еще одна важная линейная структура данных, которая на первый взгляд похожа на массив, но отличается распределением памяти, внутренней организацией и способом выполнения основных операций вставки и удаления.
Связный список – это сеть узлов, каждый из которых содержит данные и указатель на следующий узел в цепочке. Также есть указатель на первый элемент – head. Если список пуст, то он указывает на null.
Связные списки используются для реализации файловых систем, хэш-таблиц и списков смежности.
Вот визуальное представление внутренней структуры связного списка:
Основные операции со связными списками
Часто задаваемые вопросы о связных списках
Графы
Граф представляет собой набор узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x, y) называется ребром, которое указывает, что вершина x соединена с вершиной y. Ребро может содержать вес/стоимость, показывая, сколько затрат требуется, чтобы пройти от x до y.
В языке программирования графы могут быть представлены в двух формах:
Часто задаваемые вопросы о графах
Деревья
Дерево – это иерархическая структура данных, состоящая из вершин (узлов) и ребер, соединяющих их. Они похожи на графы, но есть одно важное отличие: в дереве не может быть цикла.
Деревья широко используются в искусственном интеллекте и сложных алгоритмах для обеспечения эффективного механизма хранения данных.
Вот изображение простого дерева, и основные термины:
Из всех типов чаще всего используются бинарное дерево и бинарное дерево поиска.
Часто задаваемые вопросы о деревьях
Префиксное дерево
Префиксные деревья (tries) – древовидные структуры данных, эффективные для решения задач со строками. Они обеспечивают быстрый поиск и используются преимущественно для поиска слов в словаре, автодополнения в поисковых системах и даже для IP-маршрутизации.
Вот иллюстрация того, как три слова top, thus и their хранятся в префиксном дереве:
Слова размещаются сверху вниз. Выделенные зеленым элементы показывают конец каждого слова.
Часто задаваемые вопросы о префиксных деревьях
Хеш-Таблица
Хеширование – это процесс, используемый для уникальной идентификации объектов и хранения каждого из них в некотором предварительно вычисленном уникальном индексе – ключе. Итак, объект хранится в виде пары ключ-значение, а коллекция таких элементов называется словарем. Каждый объект можно найти с помощью его ключа. Существует несколько структур, основанных на хешировании, но наиболее часто используется хеш-таблица, которая обычно реализуется с помощью массивов.
Производительность структуры зависит от трех факторов:
Вот иллюстрация того, как хэш отображается в массиве. Индекс вычисляется с помощью хеш-функции.
Часто задаваемые вопросы о хеш-таблицах
Теперь вы знаете 8 основных структур данных любого языка программирования. Можете смело отправляться на IT-собеседование.
Структура данных
Помогите, пожалуйста, с ответами на вопросы по структуре данных, а так же если можно, посоветуйте какую-нибудь литературу или ресурс по этой теме.
Задача №1. Какую структуру данных Вы бы использовали для передачи задач между двумя потоками, в случае если один поток генерирует задачи, другой их выполняет. Выполнение должно быть в порядке получения (считаем, что все
структуры данных предназначены для работы в многопоточной среде):
а) Ассоциативный хеш-массив
б) Блокирующая очередь
в) Сбалансированное дерево
г) Стек
Задача №2. На вход поступают задачи со связанным с ними моментом времени, в который необходимо эти задачи выполнить. Причем, если у двух задач одинаковое время исполнения, вторая задача не добавляется. Периодически,
в определенные моменты времени, необходимо выполнять все добавленные задачи с моментом времени, меньшем текущего, в порядке указанного в них момента времени. Какую структуру данных Вы бы выбрали для хранения этих
задач, для наиболее быстрого добавления и выборки нужных нам задач на исполнение (считаем, что все работает в одном потоке):
а) Ассоциативный хеш-массив (хеш-таблицу)
б) Очередь с приоритетами (реализованную как двоичная куча/пирамида)
в) Двусвязный список
г) Сбалансированное бинарное дерево
д) Стек
Задача №3. Нам необходимо проанализировать, сколько и каких слов встречается в тексте. Какая структура данных наиболее эффективно подойдет для решения данной задачи?
а) Двусвязный список
б) Сбалансированное дерево
в) Хеш-таблица
г) Очередь
д) Стек
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Структура базы данных
В общем проблема такова, нужно сделать примерно журнал посещаемости работников(колличество которых.
Массив как структура данных и размещение его в памяти
Добрый день! Как правильно ответить на вопрос почему в java можно написать Object x = new int.
Создание в базе данных таблиц, структура которых заранее неизвестна
Всем добрый вечер. Очень нужна помощь в решении следующей проблемы. Есть документ xml, который.
Основные структуры данных. Матчасть. Азы
Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.
Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.
40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.
В статье так же будут вопросы, которое вы можете услышать на интервью.
Что такое структура данных?
Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.
Какие бывают?
Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди.
Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.
Основные структуры данных.
Массивы
Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.
Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).
Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.
Бывают
Одномерные, как показано выше.
Многомерные, массивы внутри массивов.
Основные операции
Вопросы
Стеки
Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Это не массивы. Это очередь. Придумал Алан Тюринг.
Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.
Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.
Основные операции
Вопросы
Очереди
Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.
Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.
Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым
Основные операции
Вопросы
Связанный список
Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.
Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Бывают
Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.
Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.
Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.
Самое частое, линейный однонаправленный список. Пример – файловая система.
Основные операции
Вопросы
Графы
Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).
Бывают
Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные
Встречаются в таких формах как
Общие алгоритмы обхода графа
Вопросы
Деревья
Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.
Древовидные структуры везде и всюду. Дерево скилов в играх знают все.
«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs
Три способа обхода дерева
Вопросы
Trie ( префиксное деревое )
Разновидность дерева для строк, быстрый поиск. Словари. Т9.
Вот как такое дерево хранит слова «top», «thus» и «their».
Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.
Вопросы
Хэш таблицы
Хэширование — это процесс, используемый для уникальной идентификации объектов и хранения каждого объекта в заранее рассчитанном уникальном индексе (ключе).
Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа.
По сути это массив, в котором ключ представлен в виде хеш-функции.
Эффективность хеширования зависит от
Вопросы
Список ресурсов
Вместо заключения
Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.
Спасибо, что прочли. Надеюсь не зря потратили время =)
PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.