В этой статье я бы хотел рассказать о том, как работают списки инициализации (braced initializer lists) в C++, какие проблемы они были призваны решать, какие проблемы, в свою очередь, вызвали и как не попасть в просак.
Пользователь
Насколько медленны iostreams?
Вопрос производительности iostreams не праздный. В частности, с проблемой производительности консольного ввода-вывода можно столкнуться в системах спортивного программирования, где даже применив хороший алгоритм, можно не пройти по времени только из-за ввода-вывода. Я также встречался с этой проблемой при обработке научных данных в текстовом формате.
Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
а aesamson даёт такую рекомендацию
Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.
Моноиды и их приложения: моноидальные вычисления в деревьях
Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.
Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.
Моноид как концепция
Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.
Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+":
"John"
◦ "Doe"
= "JohnDoe"
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так,
"foo"
, "bar"
) = "foo"
Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.
И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка
""
: с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
T Zero { get; }
T Append(T a, T b);
}
Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Суффиксный массив — удобная замена суффиксного дерева
Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.
Повышаем производительность кода: сначала думаем о данных
Занимаясь программированием рендеринга графики, мы живём в мире, в котором обязательны низкоуровневые оптимизации, чтобы добиться GPU-фреймов длиной 30 мс. Для этого мы используем различные методики и разработанные с нуля новые проходы рендеринга с повышенной производительностью (атрибуты геометрии, текстурный кеш, экспорт и так далее), GPR-сжатие, скрывание задержки (latency hiding), ROP…
В сфере повышения производительности CPU в своё время применялись разные трюки, и примечательно то, что сегодня они используются для современных видеокарт ради ускорения вычислений ALU (Низкоуровневая оптимизация для AMD GCN, Быстрый обратный квадратный корень в Quake).
Быстрый обратный квадратный корень в Quake
Но в последнее время, особенно в свете перехода на 64 бита, я заметил рост количества неоптимизированного кода, словно в индустрии стремительно теряются все накопленные ранее знания. Да, старые трюки вроде быстрого обратного квадратного корня на современных процессорах контрпродуктивны. Но программисты не должны забывать о низкоуровневых оптимизациях и надеяться, что компиляторы решат все их проблемы. Не решат.
Эта статья — не исчерпывающее хардкорное руководство по железу. Это всего лишь введение, напоминание, свод базовых принципов написания эффективного кода для CPU. Я хочу «показать, что низкоуровневое мышление сегодня всё ещё полезно», даже если речь пойдёт о процессорах, которые я мог бы добавить.
В статье мы рассмотрим кеширование, векторное программирование, чтение и понимание ассемблерного кода, а также написание кода, удобного для компилятора.
Идиома Ranges
Идиома ranges — крайне удачное развитие итераторов. Она позволяет писать высокопроизводительный код, не выделяющий память, где это не надо, находясь на предельно высоком уровне абстракции. Кроме того делает библиотеки гораздо более универсальными, а их интерфейсы гибкими. Под катом краткое описание и практические примеры использования идиомы, тесты производительности, а так же сравнение с популярными реализациями итераторов в C++ и C#.
Как написать свою «песочницу»? Разбор простейшей «песочницы»
Если вам случалось писать большие приложения, вы, вероятно, использовали такие виртуальные машины, как VMWare, Virtual PC или что-то иное. Но задавались ли вы вопросом: как они работают? Эти удивительные, можно сказать, магические технологии увлекали меня довольно долгое время. Чтобы развенчать «магию» и разобраться в деталях, я написал «с нуля» собственную систему виртуализации – «песочницу». Решение этой задачи было довольно сложным делом. Реализация подобного продукта ставит множество вопросов, ответы на которые вы не найдете в Google, поэтому я хочу поделиться своим опытом с сообществом.
Самая нужная программа на свете
Какими программами постоянно пользуются люди? Если подумать над этим вопросом, то окажется, что список этот не такой уж большой. К постоянно используемым программам можно отнести: саму операционную систему, файловый менеджер, текстовый редактор, браузер, мессенджер. Это именно тот базовый набор, которым пользуется на компьютере практически каждый человек. Требования к таким программам должны быть высокими: безотказная работа, быстрое выполнение всех функций, понятный и удобный интерфейс.
Можно сказать, что вышеперечисленный набор программ — это самые нужные программы, которыми пользуется человек в цифровую эпоху. Этот список покрывает все базовые потребности человека-пользователя. Или не все? Есть ли еще одна базовая потребность, которая не учтена в вышеприведенном списке самых необходимых программ? Является ли эта потребность самой важной из тех, что должен автоматизировать компьютер? Для меня такая потребность есть, но в списке самых используемых программ ей места не нашлось. Что же это за потребность?
Современная операционная система: что надо знать разработчику
Александр Крижановский (NatSys Lab.)
Нас сегодня будет интересовать операционная система – ее внутренности, что там происходит… Хочется поделиться идеями, над которыми мы сейчас работаем, и отсюда небольшое вступление – я расскажу о том, из чего состоит современный Linux, как его можно потюнить?
По моему мнению, современная ОС – это плохая штука.
Дело в том, что на картинке изображены графики сайта Netmap (это штуковина, которая позволяет вам очень быстро захватывать и отправлять пакеты сетевого адаптера), т.е. эта картинка показывает, что на одном ядре с разной тактовой частотой до 3 ГГц Netmap позволяет 10 Гбит – 14 млн. пакетов в сек. отрабатывать уже на 500 МГц. Синенькая линия – это pktgen – самое быстрое, что, вообще, есть в ядре Linux’а. Это такая штуковина – генератор трафика, который берет один пакет и отправляет его в адаптер много раз, т.е. никаких копирований, никакого создания новых пакетов, т.е., вообще, ничего – только отправка одного и того же пакета в адаптер. И вот оно настолько сильно проседает по сравнению с Netmap (то, что делается в user-space показано розовой линией), и оно вообще где-то там внизу находится. Соответственно, люди, которые работают с очень быстрыми сетевыми приложениями, переезжают на Netmap, Pdpdk, PF_RING – таких технологий море сейчас.
Оптимизация кода: память
В действительности система памяти образует иерархию устройств хранения с разными ёмкостями, стоимостью и временем доступа. Регистры процессора хранят наиболее часто используемые данные. Маленькие быстрые кэш-памяти, расположенные близко к процессору, служат буферными зонами, которые хранят маленькую часть данных, расположеных в относительно медленной оперативной памяти. Оперативная память служит буфером для медленных локальных дисков. А локальные диски служат буфером для данных с удалённых машин, связанных сетью.
Иерархия памяти работает, потому что хорошо написанные программы имеют тенденцию обращаться к хранилищу на каком-то конкретном уровне более часто, чем к хранилищу на более низком уровне. Так что хранилище на более низком уровне может быть медленнее, больше и дешевле. В итоге мы получаем большой объём памяти, который имеет стоимость хранилища в самом низу иерархии, но доставляет данные программе со скоростью быстрого хранилища в самом верху иерархии.
Оптимизация кода: процессор
В этой статье мы рассмотрим базовые техники оптимизации кода, которые могут увеличить производительность вашей программы во много раз. Мы также коснёмся устройства процессора. Понимание как работает процессор необходимо для написания эффективных программ.
Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python
Нахождение экстремума(минимума или максимума) целевой функции является важной задачей в математике и её приложениях(в частности, в машинном обучении есть задача curve-fitting). Наверняка каждый слышал о методе наискорейшего спуска (МНС) и методе Ньютона (МН). К сожалению, эти методы имеют ряд существенных недостатков, в частности — метод наискорейшего спуска может очень долго сходиться в конце оптимизации, а метод Ньютона требует вычисления вторых производных, для чего требуется очень много вычислений.
Для устранения недостатков, как это часто бывает, нужно глубже погрузиться в предметную область и добавить ограничения на входные данные. В частности: МНС и МН имеют дело с произвольными функциями. В статистике и машинном обучении часто приходится иметь дело с методом наименьших квадратов (МНК). Этот метод минимизирует сумму квадрата ошибок, т.е. целевая функция представляется в виде
Алгоритм Левенберга — Марквардта является нелинейным методом наименьших квадратов. Статья содержит:
- объяснение алгоритма
- объяснение методов: наискорейшего спуска, Ньтона, Гаусса-Ньютона
- приведена реализация на Python с исходниками на github
- сравнение методов
Исследуем вопрос наказаний 2.0
Итак. Если вы не садист или моральный урод, а ваши сотрудники — не мазохисты, то сомневаюсь, что кому-то из вас наказания доставляют удовольствие. Мне — нет.
Супермедленный и супербыстрый бенчмарк
В недавней статье про производительность Java разгорелась дискуссия на тему измерения производительности. Глядя на неё, с грустью приходится сознавать, что многие люди до сих пор не понимают, насколько сложно правильно измерить время выполнения того или иного кода. Кроме того, люди вообще не привыкли, что один и тот же код в разных условиях может выполняться существенно разное время. К примеру, вот одно из мнений:
Если мне надо узнать, "какой язык быстрее для меня на моей задаче", то я прогоню самый примитивный бенчмарк в мире. Если разница будет существенной (скажем, на порядок) — то скорее всего и на пользовательской машине все будет примерно также.
К сожалению, самый примитивный бенчмарк в мире — это как правило неправильно написанный бенчмарк. И не следует надеяться, что неправильный бенчмарк измерит результат хотя бы с точностью до порядка. Он может измерить что-нибудь абсолютно другое, что будет совершенно отличаться от реальной производительности программы с аналогичным кодом. Давайте рассмотрим пример.
Новая редакция популярного бесплатного учебника электроники, архитектуры компьютера и низкоуровневого программирования
Книжка содержит «введение во все», доступное способному школьнику или младшему студенту, который после ее прочтения может спроектировать, написать на SystemVerilog или VHDL и реализовать на ПЛИС несложный, но при этом совершенно настоящий конвейерный процессор. Книга написана живым языком и для введения концепций, например конечных автоматов, использует примеры типа:
Деанонимизируем пользователей Windows и получаем учетные данные Microsoft и VPN-аккаунтов
Если вы не видите эту картинку, то данные вашей учетной записи Windows уже скомпрометированы.
Введение
Давным-давно, когда компьютеры были одноядерными и прекрасно работали с 256 МБ RAM, а сети под управлением Windows уже использовались очень широко, ребята из Microsoft подумали, что было бы удобно аутентифицироваться только один раз, при загрузке компьютера, а доступ на внутренние ресурсы происходил бы автоматически, без ввода пароля, и сделали так называемую технологию единого входа (Single Sign-on). Единый вход работает очень просто: когда пользователь пытается получить доступ к какому-либо ресурсу с NTLM-аутентификацией (стандартный способ аутентификации в сетях Windows), ОС сразу передает название домена, имя учетной записи и хеш пароля текущего пользователя, и если под этими данными войти не удалось, показывает диалог ввода имени пользователя и пароля. Шли годы, проблемы с безопасностью реализации технологии единого входа давали о себе знать, одни из которых успешно исправляли, другие исправляли менее успешно, а о третьих почему-то совсем забыли. Так и забыли о проблеме передачи учетных данных для единого входа на SMB-ресурсы (сетевые ресурсы: файлы и папки, принтеры, и т.д.) через интернет, которую можно эксплуатировать во всех современных ОС, включая Windows 10 со всеми последними обновлениями. Об этой особенности работы стека аутентификации вспоминают каждые 1-2 года, последний раз о ней рассказывали на Blackhat US 2015, но Microsoft не спешит что-либо менять.Как продавать: как должен работать продавец
Привет! Не думал, что когда-нибудь буду публиковать тут настолько далёкое от ИТ, но давайте попробуем, благо новые тематики позволяют. Сейчас расскажу, как именно мы учим своих продавцов. Если вы физически что-то продаёте — это гайд, как не сильно накосячить. Механика обтачивалась примерно три года.
Итак, первое и главное в рознице — продавец должен быть уверен в своём товаре. Если товар — отстой, который надо впаривать, то продавец получит такое дикое искривление психики через месяц, что к живым людям его выпускать нельзя будет вообще. Товар должен быть такой, чтобы про него можно было спокойно искренне рассказывать — и чтобы люди после этого брали. Это основа маркетинга. Уверенность в товаре — базис для всех остальных принципов.
Теперь посмотрим на сам процесс продажи. Он делится на пять шагов — приветствие, засада, разработка, презентация, продажа. Самая частая ошибка приветствия в том, что продавец, скорее всего, не доктор. Поэтому «Вам чем-нибудь помочь?» — это где угодно, но только не в стенах нашего магазина. Правильно улыбнуться и поздороваться с человеком, когда он заходит на точку. Задать настроение и обозначить, что вы его увидели. И всё. Не лезть к нему и не подходить даже. Человек зашёл — не надо набрасываться.
Хотя нет, прежде чем переходить к пунктам, обсудим подготовку.
Главный наш принцип в отношении покупателя — относиться к нему как к другу. Это не красивые слова, а одна предельно конкретная вещь — не делай ничего такого, что не сделал бы с другом.
Эффективное использование Github
Github — важная часть жизни современного разработчика: он стал стандартом для размещения opensource-проектов. В «2ГИС» мы используем гитхаб для разработки проектов web-отдела и хостинга проектов с открытым кодом.
Хотя большинство из нас пользуются сервисом практически каждый день, не все знают, что у него есть много фишек, помогающих облегчить работу или рутинные операции. Например, получение публичного ключа из URL; отслеживание того, с каких сайтов пользователи приходят в репозиторий; правильный шаринг ссылок на файлы, которые живут в репозиториях гитхаба; горячие клавиши и тому подобное. Цель этой статьи — рассказать о неочевидных вещах и вообще о том, что сделает вашу работу с гитхабом продуктивнее и веселее (я не буду рассматривать здесь работу с API гитхаба, так как эта тема заслуживает отдельной статьи).
Содержание
- Трюки с URL
- Горячие клавиши
- Тикеты и пулл-реквесты
- Github markdown
- Аккаунт
- Работа с репозиториями
- Поиск кода
- Командная строка и Github
- User scripts
- Github-вандализм
- Дополнительные Github-ресурсы
- Полезные ссылки
300 потрясающих бесплатных сервисов
Автор оригинальной статьи Ali Mese добавил ещё 100 новых бесплатных сервисов. Все 400 потрясающих сервисов доступны здесь. И еще подборку +500 инструментов от 10 марта 2017 г. смотрите здесь.
A. Бесплатные Веб-Сайты + Логотипы + Хостинг + Выставление Счета
- HTML5 UP: Адаптивные шаблоны HTML5 и CSS3.
- Bootswatch: Бесплатные темы для Bootstrap.
- Templated: Коллекция 845 бесплатных шаблонов CSS и HTML5.
- Wordpress.org | Wordpress.com: Бесплатное создание веб-сайта.
- Strikingly.com Domain: Конструктор веб-сайтов.
- Logaster: Онлайн генератор логотипов и элементов фирменного стиля (new).
- Withoomph: Мгновенное создание логотипов (англ.).
- Hipster Logo Generator: Генератор хипстерских логотипов.
- Squarespace Free Logo: Можно скачать бесплатную версию в маленьком разрешении.
- Invoice to me: Бесплатный генератор счета.
- Free Invoice Generator: Альтернативный бесплатный генератор счета.
- Slimvoice: Невероятно простой счет.
Гарвардский курс по основам программирования CS50 теперь на русском
Предыстория: кто мы и как дошли до жизни такой
Мы — команда проекта JavaRush. А JavaRush, кто еще не в курсе, — это полностью автоматизированный обучающий онлайн-курс по Java. Когда-то давно, именно благодаря поддержке хаброюзеров и статьям на хабре, JavaRush и появился. В то время мы собирались переучить на программистов миллион человек.
Информация
- В рейтинге
- Не участвует
- Откуда
- Ижевск, Удмуртия, Россия
- Зарегистрирован
- Активность