Регистрация

Сайт о развлечениях


Чем заняться в свободное время
   
 
 
Измерение объема Помимо цен, столбчатые диаграммы нередко отражают объем торгов, т.е. количество акций, купленных или проданных за определенный период времени, представленный каждым столбиком. На дневной диаграмме объем торгов отражает совокупное количество акций, купленных или проданных в течение соответствующего торгового дня. По соглашению этот объем отображается в виде отдельной столбчатой диаграммы и обычно приводится непосредственно под диаграммой цены акций.
Сочетание накопления
  • Предприятие осуществляет права владения.
  • Предприятие не отвечает по обязательствам организации, которой оно подчинено.
Популярные новости

Потоки под капотом

  1. Потоковые трубопроводы
  2. Источники потока
  3. Строительство потокового трубопровода
  4. Таблица 1. Потоковые флаги
  5. Листинг 1. Потоковый конвейер, в котором операции могут быть автоматически исключены
  6. Выполнение потокового конвейера
  7. Рисунок 1. Потоковая машина (анимация предоставлена ​​Тагиром Валеевым)
  8. Заказ встречи
  9. Создание потоков
  10. Заключение к части 3

Первые две статьи в эта серия узнайте, как использовать библиотеку java.util.stream, добавленную в Java SE 8, которая упрощает декларативное выражение запроса к набору данных. Во многих случаях библиотека выясняет, как эффективно выполнять запросы без помощи пользователя. Но когда производительность критически важна, важно понять, как библиотека работает внутри, так что вы можете устранить возможные источники неэффективности. В третьей части рассматривается, как работает реализация Streams, и объясняются некоторые оптимизации, которые делает возможным декларативный подход.

Потоковые трубопроводы

Потоковый конвейер состоит из источника потока , нуля или более промежуточных операций и операции терминала . Источниками потока могут быть коллекции, массивы, функции генератора или любой другой источник данных, который может надлежащим образом обеспечить доступ к его элементам. Промежуточные операции преобразуют потоки в другие потоки - путем фильтрации элементов (filter ()), преобразования элементов (map ()), сортировки элементов (sorted ()), усечения потока до определенного размера (limit ()) и скоро. Терминальные операции включают агрегации (redu (), collect ()), поиск (findFirst ()) и итерацию (forEach ()).

Об этой серии
С пакетом java.util.stream вы можете кратко и декларативно выражать, возможно, параллельные массовые операции над коллекциями, массивами и другими источниками данных. В эта серия от архитектора языка Java Брайана Гетца, познакомьтесь с библиотекой Streams и узнайте, как ее использовать с максимальной выгодой.

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

Источники потока

Источник потока описывается абстракцией, называемой Spliterator. Как следует из его названия, Spliterator сочетает в себе два поведения: доступ к элементам источника (итерация) и, возможно, декомпозиция входного источника для параллельного выполнения (разбиение).

Хотя Spliterator включает в себя те же базовые функции, что и Iterator, он не расширяет Iterator, а использует другой подход к доступу к элементам. Итератор имеет два метода, hasNext () и next (); доступ к следующему элементу может включать (но не требует) вызов обоих этих методов. В результате для правильного кодирования Итератора требуется определенное количество защитного и дублирующего кодирования. (Что, если клиент не вызывает hasNext () перед next ()? Что если он дважды вызывает hasNext ()?) Кроме того, протокол с двумя методами обычно требует достаточного количества состояний, таких как просмотр одного элемента вперед (и отслеживание того, вы уже заглянули вперед). Вместе эти требования в совокупности увеличивают затраты на доступ к элементам.

Наличие лямбда-выражений в языке позволяет Spliterator использовать подход к доступу к элементам, который, как правило, более эффективен и легче кодируется правильно. У Spliterator есть два метода доступа к элементам:

логическое tryAdvance (действие Consumer <? super T>); void forEachRemaining (действие Consumer <? super T>); Показать больше Показать больше icon

Метод tryAdvance () пытается обработать один элемент. Если элементов не осталось, tryAdvance () просто возвращает false; в противном случае он перемещает курсор и передает текущий элемент предоставленному обработчику и возвращает true. Метод forEachRemaining () обрабатывает все оставшиеся элементы, передавая их по одному предоставленному обработчику.

Даже игнорируя возможность параллельной декомпозиции, абстракция Spliterator уже является «лучшим итератором» - проще в написании, проще в использовании и, как правило, с меньшими накладными расходами на доступ к элементу. Но абстракция Spliterator также распространяется на параллельную декомпозицию. Сплитератор описывает последовательность оставшихся элементов; вызов метода доступа к элементам tryAdvance () или forEachRemaining () продвигается через эту последовательность. Чтобы разделить источник так, чтобы два потока могли работать отдельно в разных разделах ввода, Spliterator предоставляет метод trySplit ():

Spliterator <T> trySplit (); Показать больше Показать больше icon

Поведение trySplit () заключается в попытке разделить оставшиеся элементы на две секции, в идеале одинакового размера. Если Spliterator может быть разделен, trySplit () нарезает начальную часть описанных элементов на новый Spliterator, который возвращается, и корректирует его состояние для описания элементов, следующих за вырезанной частью. Если источник не может быть разделен, trySplit () возвращает null, указывая, что разделение невозможно, и вызывающая сторона должна продолжать последовательно. Для источников, чьи порядок встречи имеет значение (например, массивы, список или SortedSet), trySplit () должен сохранить этот порядок; он должен разделить начальную часть оставшихся элементов на новый разделитель, а текущий разделитель должен описать остальные элементы в порядке, согласующемся с исходным.

Все реализации Collection в JDK оснащены высококачественными реализациями Spliterator. Некоторые источники допускают лучшую реализацию, чем другие: ArrayList с более чем одним элементом всегда можно разделить чисто и равномерно; LinkedList всегда плохо разбивается; и основанные на хэше и основанные на дереве наборы обычно могут быть достаточно хорошо разделены.

Строительство потокового трубопровода

Потоковый конвейер создается путем построения представления связанного списка источника потока и его промежуточных операций. Во внутреннем представлении каждый этап конвейера описывается битовой картой потоковых флагов, которые описывают то, что известно об элементах на этом этапе потокового конвейера. Streams использует эти флаги для оптимизации как построения, так и исполнения потока. Таблица 1 показывает флаги потока и их интерпретации.

Таблица 1. Потоковые флаги

РАЗМЕР Размер потока известен. DISTINCT Элементы потока различны в соответствии с Object.equals () для потоков объектов или в соответствии с == для потоков примитивов. SORTED Элементы потока сортируются в естественном порядке. ЗАКАЗАН Поток имеет значимый порядок встреч (см. Заказ встречи " раздел).

Флаги потока для исходного этапа выводятся из битовой карты характеристик сплитератора (сплитераторы поддерживают больший набор флагов, чем потоки). Высококачественная реализация сплитератора не только обеспечивает эффективный доступ к элементам и их разделение, но также описывает характеристики элементов. (Например, разделитель для HashSet сообщает о характеристике DISTINCT, поскольку известно, что элементы набора различны.)

Каждая промежуточная операция оказывает известное влияние на флаги потока; операция может установить, очистить или сохранить настройки для каждого флага. Например, операция filter () сохраняет флаги SORTED и DISTINCT, но очищает флаг SIZED; операция map () очищает флаги SORTED и DISTINCT, но сохраняет флаг SIZED; и операция sorted () сохраняет флаги SIZED и DISTINCT и вставляет флаг SORTED. По мере того, как создается представление этапов в связанном списке, флаги для предыдущего этапа объединяются с поведением текущего этапа для получения нового набора флагов для текущего этапа.

В некоторых случаях флаги позволяют полностью исключить операцию, как в потоковом конвейере в листинге 1.

Листинг 1. Потоковый конвейер, в котором операции могут быть автоматически исключены

TreeSet <String> ts = ... String [] sortedAWords = ts.stream () .filter (s -> s.startsWith ("a")) .sorted () .toArray (); Показать больше Показать больше icon

Флаги потока для этапа источника включают в себя SORTED, поскольку источником является TreeSet. Метод filter () сохраняет флаг SORTED, поэтому флаги потока для этапа фильтрации также включают флаг SORTED. Обычно результатом метода sorted () будет создание нового этапа конвейера, добавление его в конец конвейера и возврат нового этапа. Однако, поскольку известно, что элементы уже отсортированы в естественном порядке, метод sorted () не используется - он просто возвращает предыдущий этап (этап фильтрации), поскольку сортировка будет избыточной. (Точно так же, если известно, что элементы DISTINCT, операция Different () может быть полностью исключена.)

Выполнение потокового конвейера

Когда операция терминала инициируется, реализация потока выбирает план выполнения. Промежуточные операции подразделяются на операции без сохранения состояния (filter (), map (), flatMap ()) и операции с состоянием (sorted (), limit (), Different ()). Операция без сохранения состояния - это операция, которая может выполняться над элементом без знания других элементов. Например, операция фильтрации должна только исследовать текущий элемент, чтобы определить, следует ли включить его или исключить, но операция сортировки должна увидеть все элементы, прежде чем она узнает, какой элемент должен выдать первым.

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

Терминальные операции являются либо короткими замыканиями (allMatch (), findFirst ()), либо короткими замыканиями (redu (), collect (), forEach ()). Если операция терминала не имеет короткого замыкания, данные могут быть обработаны в массе (используя метод forEachRemaining () исходного сплитератора, что дополнительно снижает накладные расходы на доступ к каждому элементу); если оно короткое замыкание, оно должно обрабатываться по одному элементу за раз (используя tryAdvance ()).

Для последовательного выполнения Streams создает «машину» - цепочку объектов-потребителей, структура которых совпадает со структурой конвейера. Каждый из этих объектов-потребителей знает о следующей стадии; когда он получает элемент (или получает уведомление о том, что элементов больше нет), он отправляет ноль или более элементов на следующий этап в цепочке. Например, потребитель, связанный со стадией filter (), применяет предикат фильтра к элементу ввода и либо отправляет, либо не отправляет его на следующую стадию; потребитель, связанный со стадией map (), применяет функцию отображения к элементу ввода и отправляет результат на следующую стадию. Потребитель, связанный с операцией с состоянием, такой как sorted (), буферизует элементы до тех пор, пока не увидит конец ввода, а затем отправит отсортированные данные на следующий этап. Завершающий этап в машине реализует работу терминала. Если эта операция выдает результат, такой как redu () или toArray (), этот этап действует как аккумулятор для результата.

На рисунке 1 показана анимация (или, в некоторых браузерах, снимок) «потокового компьютера» для следующего потокового конвейера. (На рисунке 1 желтый, зеленый и синий блоки последовательно входят в первую ступень машины сверху. На первом этапе каждый блок сжимается в меньший блок, а затем попадает во вторую ступень. Подобно тому, как персонаж глотает каждый желтый блок, позволяя только третьему этапу попасть в зеленый и синий блоки. Сжатый синий и зеленый блоки попеременно отображаются на экране компьютера.)

blocks.stream () .map (block -> block.squash ()) .filter (block -> block.getColor ()! = YELLOW) .forEach (block -> block.display ()); Показать больше Показать больше icon

Рисунок 1. Потоковая машина (анимация предоставлена ​​Тагиром Валеевым)
Первые две статьи в   эта серия   узнайте, как использовать библиотеку java

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

Выполнение потоковых конвейеров также может быть оптимизировано с помощью потоковых флагов. Например, флаг SIZED указывает, что размер конечного результата известен. Операция терминала toArray () может использовать этот флаг для предварительного выделения массива правильного размера; если флаг SIZED отсутствует, он должен будет угадать размер массива и, возможно, скопировать данные, если угадать неверно.

Оптимизирующая печать еще более эффективна при параллельном выполнении потоков. В дополнение к флагу SIZED еще одна характеристика разделителя, SUBSIZED, означает, что известен не только размер, но и то, что если разделитель разделен, размеры разделения также будут известны. (Это верно для массивов и ArrayList, но не обязательно верно для других разделяемых источников, таких как деревья.) Если присутствует характеристика SUBSIZED, при параллельном выполнении операция toArray () может выделить один массив правильного размера для всего результата и отдельные потоки (каждый из которых работает в отдельном разделе ввода) могут записывать свои результаты непосредственно в правильный раздел массива - без необходимости синхронизации или копирования. (При отсутствии флага SUBSIZED каждый раздел собирается в промежуточный массив и затем копируется в конечное местоположение.)

Заказ встречи

Другое тонкое соображение, которое влияет на способность библиотеки оптимизировать, - это порядок встреч . Порядок встречи относится к тому, является ли порядок, в котором источник распределяет элементы, значимым для вычисления. Некоторые источники (такие как основанные на хэше наборы и карты) не имеют значимого порядка встреч. Флаг потока ORDERED описывает, имеет ли поток значимый порядок встреч или нет. Сплитераторы для коллекций JDK устанавливают этот флаг на основе спецификации коллекции; некоторые промежуточные операции могут вводить ORDERED (sorted ()) или очищать его (unordered ()).

Если поток имеет порядок встречи, большинство операций с потоками должны соблюдать этот порядок. Для последовательных выполнений сохранение порядка столкновения является по существу бесплатным, поскольку элементы естественным образом обрабатываются в том порядке, в котором они встречаются. Даже параллельно, для многих операций (промежуточные операции без сохранения состояния и некоторые терминальные операции, такие как redu ()), соблюдение порядка встречи не налагает никаких реальных затрат. Но для других (промежуточные операции с состоянием и терминальные операции, семантика которых связана с порядком встреч, например, findFirst () или forEachOrdered ()), обязательство соблюдать порядок встреч при параллельном выполнении может быть значительным. Если поток имеет определенный порядок встречи, но этот порядок не имеет значения для результата, возможно, можно ускорить параллельное выполнение конвейеров, содержащих чувствительные к порядку операции, удалив флаг ORDERED с помощью операции unordered ().

В качестве примера операции, чувствительной к порядку встречи, рассмотрим limit (), который усекает поток до указанного размера. Реализация limit () в последовательном выполнении тривиальна: ведите счетчик количества увиденных элементов и отбрасывайте все элементы после этого. Но в параллельном исполнении реализация limit () намного сложнее; Вы должны сохранить первые N элементов. Это требование сильно ограничивает способность использовать параллелизм; если вход разделен на разделы, вы не знаете, будет ли результат раздела включен в окончательный результат, пока все разделы, предшествующие этому разделу, не будут завершены. В результате у реализации обычно плохой выбор: не использовать все доступные ядра или буферизовать весь предварительный результат до тех пор, пока вы не достигнете целевой длины.

Если поток не имеет порядка встречи, операция limit () может свободно выбирать любые N элементов, что допускает гораздо более эффективное выполнение. Элементы могут быть отправлены в нисходящем направлении, как только они станут известны, без какой-либо буферизации, и единственная координация, необходимая между потоками, - это семафор, чтобы гарантировать, что длина целевого потока не превышена.

Другой, более тонкий пример затрат на порядок встреч - сортировка. Если порядок встречи значительный, операция sorted () реализует стабильную сортировку (равные элементы появляются в том же порядке в выходных данных, что и во входных данных), тогда как для неупорядоченного потока стабильность - которая имеет стоимость - не требуется. Аналогичная история существует для Different (): если поток имеет порядок встречи, то для нескольких равных входных элементов отдельный () должен испускать первый из них, тогда как для неупорядоченного потока он может испускать любой из них - что снова допускает гораздо более эффективная параллельная реализация.

Аналогичная ситуация возникает, когда вы агрегируете с collect (). Если вы выполняете операцию collect (groupingBy ()) в упорядоченном потоке, элементы, соответствующие любому ключу, должны быть представлены нижестоящему коллектору в том порядке, в котором они появляются во входных данных. Часто этот порядок не имеет значения для приложения, и любой заказ подойдет. В этих случаях может быть предпочтительнее выбрать параллельный сборщик (такой как groupingByConcurrent ()), который может игнорировать порядок встречи и разрешать всем потокам собираться непосредственно в общую параллельную структуру данных (такую ​​как ConcurrentHashMap), а не иметь каждый поток собирать в свою промежуточную карту, а затем объединять промежуточные карты (что может быть дорого).

Создание потоков

Хотя многие классы в JDK были модифицированы для использования в качестве источников потоков, также легко адаптировать существующие структуры данных для распределения потоков. Чтобы создать поток из произвольного источника данных, необходимо создать Spliterator для элементов потока и передать его в StreamSupport.stream () вместе с логическим флагом, указывающим, должен ли результирующий поток быть последовательным или параллельным.

Реализации Spliterator могут значительно различаться по качеству, что делает компромисс между усилиями по реализации и производительностью потоковых конвейеров, которые используют сплитераторы в качестве источника. Интерфейс Spliterator имеет несколько необязательных методов, таких как trySplit (). Если вы не хотите реализовывать разбиение, вы всегда можете вернуть null из trySplit () - но это означает, что потоки, использующие этот Spliterator в качестве источника, не смогут использовать параллелизм для ускорения вычислений.

Соображения, которые влияют на качество сплитератора, включают в себя:

  • Указывает ли сплитератор точный размер?
  • Может ли сплитератор разделить вход вообще?
  • Может ли он разделить входные данные на примерно равные части?
  • Являются ли размеры расщеплений предсказуемыми (отраженными через СУБСИЗИРОВАННЫЕ характеристики)?
  • Сообщает ли сплитератор обо всех соответствующих характеристиках?

Самый простой способ сделать сплитератор, но который приводит к худшему качеству, это передать итератор в Spliterators.spliteratorUnknownSize (). Вы можете получить немного лучший сплитератор, передав Итератор и размер в Spliterators.spliterator. Но если важна производительность потока, особенно параллельная, реализуйте полный интерфейс Spliterator, включая все применимые характеристики. Источники JDK для классов коллекций, такие как ArrayList, TreeSet и HashMap, предоставляют примеры высококачественных сплиттераторов, которые вы можете эмулировать для своих собственных структур данных.

Заключение к части 3

В то время как производительность Streams из коробки в целом хорошая (иногда даже лучше, чем соответствующий императивный код), твердое понимание того, как Streams работает под капотом, позволяет вам использовать библиотеку с максимальной эффективностью и создавать собственные адаптеры для получение потока из любого источника данных. Следующие два серии рассрочка подробно изучает параллелизм.

Что, если клиент не вызывает hasNext () перед next ()?
Что если он дважды вызывает hasNext ()?
Действие Consumer <?
Действие Consumer <?
Может ли сплитератор разделить вход вообще?
Может ли он разделить входные данные на примерно равные части?
Являются ли размеры расщеплений предсказуемыми (отраженными через СУБСИЗИРОВАННЫЕ характеристики)?
Сообщает ли сплитератор обо всех соответствующих характеристиках?