Как стать автором
Обновить
2
0

Пользователь

Отправить сообщение

Динамический неоднородный плотно упакованный контейнер

Время на прочтение11 мин
Количество просмотров20K

Определение 1. Однородный контейнер – это такой контейнер, в котором хранятся объекты строго одного типа.


Определение 2. Неоднородный контейнер — это такой контейнер, в котором могут храниться объекты разного типа.


Определение 3. Статический контейнер — это контейнер, состав которого полностью определяется на этапе компиляции.


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

Определение 4. Динамический контейнер — это контейнер, состав которого частично или полностью определяется на этапе выполнения.


По такой классификации, очевидно, существуют четыре вида контейнеров:


  1. Статические однородные


    Сможете придумать пример?

    Обычный массив — int[n].


  2. Статические неоднородные


    Примеры?

    Наиболее яркий пример такого контейнера — это кортеж. В языке C++ он реализуется классом std::tuple<...>.


  3. Динамические однородные


    Догадались?

    Правильно, std::vector<int>.


  4. Динамические неоднородные


    Вот об этом виде контейнеров и пойдёт речь в данной статье.


Читать дальше →
Всего голосов 35: ↑32 и ↓3+29
Комментарии64

Поразрядная сортировка с человеческим лицом

Время на прочтение8 мин
Количество просмотров39K
Несмотря на известность алгоритма поразрядной сортировки, в интернете сложно найти приличную его реализацию на языке C++ (честно говоря, думаю, что и на других языках тоже). Почти всё, что находится поисковиками, чудовищно либо в плане кода, либо в плане эффективности. А чаще всего плохо и то, и другое.

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

Возможно, именно поэтому многие люди до сих пор считают поразрядку алгоритмом, представляющим исключительно академический интерес, и малоприменимым в реальности. Однако, это заблуждение.
Читать дальше →
Всего голосов 28: ↑26 и ↓2+24
Комментарии6

И ещё о сортировках

Время на прочтение26 мин
Количество просмотров24K

И ещё о сортировках


Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать дальше →
Всего голосов 25: ↑23 и ↓2+21
Комментарии53

Умные алгоритмы обработки строк в ClickHouse

Время на прочтение12 мин
Количество просмотров22K

В ClickHouse постоянно возникают задачи, связанные с обработкой строк. Например, поиск, вычисление свойств UTF-8 строк или что-то более экзотическое, будь то поиск типа учёта регистра или поиск по сжатым данным.


Всё началось с того, что руководитель разработки ClickHouse Лёша Миловидов o6CuFl2Q пришёл к нам на факультет компьютерных наук в НИУ ВШЭ и предложил огромное количество тем для курсовых и дипломов. Когда я увидел «Умные алгоритмы обработки строк в ClickHouse» (я, человек, который увлекается разными алгоритмами, в том числе экспериментальными), сразу же настроил планов, как сделаю самый крутой диплом. Мою радость и выражение лица можно описать следующей картинкой:



Читать дальше →
Всего голосов 59: ↑58 и ↓1+57
Комментарии7

Дерево ван Эмде Боаса

Время на прочтение6 мин
Количество просмотров19K
Всем доброго времени суток!

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

Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2k, проще говоря, числа, состоящие не более чем из k бит. Казалось бы, зачем нужно еще какое-то дерево, да еще позволяющее хранить только целые числа, когда существует множество различных сбалансриованных двоичных деревьев поиска, позволяющих выполнять операции вставки, удаления и прочие за O(log n), где n — количество элементов в дереве?

Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

Что же там еще есть такого вкусного?
Всего голосов 193: ↑191 и ↓2+189
Комментарии39

Узнаем паспортные данные физического лица по ФИО (если есть залоговое имущество)

Время на прочтение1 мин
Количество просмотров471K
А так же узнаем ФИО и паспортные данные по номеру автомобиля если он взят в кредит.
Без регистрации и СМС.
Читать дальше →
Всего голосов 102: ↑98 и ↓4+94
Комментарии87

Разбираемся с латинскими сокращениями и фразами в английском языке

Время на прочтение6 мин
Количество просмотров65K


Полтора года назад, читая работы про уязвимости Meltdown и Spectre, я поймал себя на том, что не очень понимаю разницу между сокращениями i.e. и e.g. Т.е. по контексту вроде бы понятно, но потом вроде бы как-то и не совсем то. В результате я тогда сделал себе небольшую шпаргалку именно по этим сокращениям, чтобы не путаться. И тогда же появилась идея этой статьи.


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

Читать дальше →
Всего голосов 143: ↑142 и ↓1+141
Комментарии72

Современный CMake: 10 советов по улучшению скриптов сборки

Время на прочтение8 мин
Количество просмотров81K

CMake — это система сборки для C/C++, которая с каждым годом становится всё популярнее. Он практически стал решением по умолчанию для новых проектов. Однако, множество примеров выполнения какой-либо задачи на CMake содержат архаичные, ненадёжные, раздутые действия. Мы выясним, как писать скрипты сборки на CMake лаконичнее.

Читать дальше →
Всего голосов 40: ↑40 и ↓0+40
Комментарии28

CMake и C++ — братья навек

Время на прочтение11 мин
Количество просмотров82K

Дружба навек


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


Многие ругают CMake, и часто заслуженно, но если разобраться, то не всё так плохо, а в последнее время очень даже неплохо, и направление развития вполне позитивное.


В данной заметке я хочу рассказать, как достаточно просто организовать заголовочную библиотеку на языке C++ в системе CMake, чтобы получить следующую функциональность:


  1. Сборку;
  2. Автозапуск тестов;
  3. Замер покрытия кода;
  4. Установку;
  5. Автодокументирование;
  6. Генерацию онлайн-песочницы;
  7. Статический анализ.

Кто и так разбирается в плюсах и си-мейке может просто скачать шаблон проекта и начать им пользоваться.
Читать дальше →
Всего голосов 52: ↑49 и ↓3+46
Комментарии51

Модели дженериков и метапрограммирования: Go, Rust, Swift, D и другие

Время на прочтение16 мин
Количество просмотров29K

В некоторых сферах программирования нормально хотеть написать такую структуру данных или алгоритм, которые могут работать с элементами разных типов. Например, список дженериков или алгоритм сортировки, которому нужна только функция сравнения. В разных языках предложены всевозможные способы решения этой задачи: от простого указания программистам на подходящие общие функции (С, Go) до таких мощных систем дженериков, что они стали полными по Тьюрингу (Rust, C++). В этой статье я расскажу о системах дженериков из разных языков и их реализации. Начну с решения задачи в языках без подобной системы (вроде С), а затем покажу, как постепенное добавление расширений приводит к системам из других языков.
Читать дальше →
Всего голосов 112: ↑110 и ↓2+108
Комментарии14

Камеры глубины — тихая революция (когда роботы будут видеть) Часть 2

Время на прочтение15 мин
Количество просмотров34K


В первой части этого текста мы рассмотрели камеры глубины на основе структурного света и измерения round-trip задержки света, в которых в основном применяется инфракрасная подсветка. Они отлично работают в помещениях на расстояниях от 10 сантиметров до 10 метров, а главное — весьма дешевы. Отсюда массовая волна их текущего применения в смартфонах. Но… Как только мы выходим на улицу, солнце даже сквозь облака засвечивает инфракрасную подсветку и их работа резко ухудшается. 

Как говорит Стив Бланк (по другому поводу, впрочем): «Хотите успеха — выходите из здания». Ниже речь пойдет про камеры глубины, работающие вне помещений. Сегодня эту тему сильно двигают автономные автомобили, но, как мы увидим, не только.


Источник: Innoviz Envisions Mass Produced Self-Driving Cars With Solid State LiDAR

Итак, камеры глубины, т.е. устройства снимающие видео, в каждом пикселе которого расстояние до объекта сцены, работающие при солнечном свете!

Кому интересно — добро пожаловать под кат!
Читать дальше →
Всего голосов 87: ↑87 и ↓0+87
Комментарии59

Марвин Мински «The Emotion Machine» (хабраперевод, раунд второй)

Время на прочтение3 мин
Количество просмотров5.2K
image


Привет, Хабр!

Год назад мы проделали отличную работу. Корявенько, наполовину, но всё же отличную. Ноосфера послала мне сигнал, что пришла пора доделать её до конца. Я думал, что эта работа оказалось никому не нужна, но неделю назад известный писатель-фантаст-киберпанкер спросил меня, когда же продолжение переводов? Я ответил, что основного бойца забрали в армию год назад и пока перевод не предвидится. А через 10 часов после моего ответа — получаю письмо: «Я вернулся из армии, готов возобновить переводы.»

Тезисы:

  1. Мы рождаемся с множеством ментальных ресурсов.
  2. Мы учимся взаимодействовать с другими.
  3. Эмоции — это разные Образы Мышления.
  4. Мы учимся думать о недавних мыслях.
  5. Мы учимся думать на различных уровнях.
  6. Мы накапливаем колоссальный опыт.
  7. Мы переключаемся между различными Образами Мышления.
  8. Мы находим различные пути представления вещей.
  9. Мы строим различные модели себя.

Спасибо всем кто помогал: Станиславу Суханицкому, Savva Sumin, Victor Ivanov, urticazoku

Поэтому ждите новых глав, присоединяйтесь и помогайте с переводами (пишите в личку или на почту alexey.stacenko@gmail.com) Вот что есть готового на данный момент:
Читать дальше →
Всего голосов 20: ↑17 и ↓3+14
Комментарии0

ІТ термины на примере процесса выращивания картошки

Время на прочтение7 мин
Количество просмотров99K

image


Недавно меня спросили, чем разработка на C# отличается от разработки на C++. В результате родилась идея объяснить значение тех или иных ИТ терминов на примере процесса выращивания картошки.

Читать дальше →
Всего голосов 98: ↑84 и ↓14+70
Комментарии87

Принципы построения REST JSON API

Время на прочтение8 мин
Количество просмотров344K

Эта памятка писалась для внутренних нужд (открыть глаза менее опытным в вебе коллегам). Но, т.к. я насмотрелся велосипедов от довольно уважаемых, казалось бы, контор, — выкладываю на хабр. Мне кажется, многим будет полезно.


Зачем


Надеюсь, читающий уже понимает, зачем ему вообще нужен именно REST api, а не какой-нибудь монстр типа SOAP. Вопрос в том, зачем соблюдать какие-то стандарты и практики, если браузеры вроде бы позволяют делать что хочешь.


  • Стандарт HTTP это стандарт. Его несоблюдение вредно для кармы и ведёт к постоянным проблемам с безопасностью, кэшированием и прочими "закидонами" браузеров, которые совсем не закидоны, а просто следование стандарту.
  • Велосипеды со всякими {error: "message","result":...} невозможно нормально тестировать и отлаживать
  • Поддержка большим количеством готовых клиентских библиотек на все случаи жизни. Те, кто будет вашим api пользоваться, скажут большое человеческое спасибо.
  • Поддержка автоматизированного интеграционного тестирования. Когда сервер на любые запросы отдаёт 200 ОК — ну, это такое себе развлечение.
Читать дальше →
Всего голосов 71: ↑55 и ↓16+39
Комментарии207

Умножение матриц: эффективная реализация шаг за шагом

Время на прочтение14 мин
Количество просмотров104K


Введение


Умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверточных слоях неронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию. Почему так происходит? Ответ кроется в очень эффективной реализации этого алгоритма для процессоров, графических ускорителей (а в последнее время и специальных ускорителей матричного умножения). Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому не удивительно, что многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.

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

Процесс изложения будет вестись ввиде шагов с примерами по последовательному ускорению алгоритма. Я старался писать максимально упрощая задачу, но не более того. Надеюсь у меня получилось…
Читать дальше →
Всего голосов 90: ↑90 и ↓0+90
Комментарии49

Управление ресурсами с помощью явных специализаций шаблонов

Время на прочтение14 мин
Количество просмотров24K


RAII – одна из наиболее важных и полезных идиом в C++. RAII освобождает программиста от ручного управления ресурсами, без неё крайне затруднено написание безопасного с точки зрения исключений кода. Возможно, самое популярное использование RAII – это управление динамически выделяемой памятью с помощью умных указателей, но она также может с успехом применяться и к другим ресурсам, особенно в мире низкоуровневых библиотек. Примеры включают в себя дескрипторы Windows API, файловые дескрипторы POSIX, примитивы OpenGL и тому подобное.
Читать дальше →
Всего голосов 30: ↑29 и ↓1+28
Комментарии17

Open source: кодоюмор, кодотрюки, НЕ кодобред

Время на прочтение9 мин
Количество просмотров11K

Старый GLib vs новый Clang


Ковыряясь в разнообразном СПО, я периодически нахожу всякие интересные штуки: иногда это просто смешной комментарий, иногда — нечто остроумное в более широком смысле. Подобные подборки периодически появляются и в «глобальном Интернете», и на Хабре — есть, скажем, широко известный вопрос на StackOverflow про комментарии в коде, а здесь недавно публиковалась подборка забавных названий юрлиц и топонимов. Попробую и я структурировать и выложить то, что постепенно у меня копилось. Под катом вас ждут цитаты из QEMU, ядра Linux, и не только.

Читать дальше →
Всего голосов 38: ↑38 и ↓0+38
Комментарии12

Зоопарк AFL фазеров

Время на прочтение12 мин
Количество просмотров17K
image

На Хабре уже пару раз появлялись статьи, поднимающие тему American Fuzzy Lop (AFL) (1,2). Но в данной статье речь пойдет не о классическом AFL, а о вспомогательных утилитах для него и его модификациях, которые, на наш взгляд, могут значительно улучшить качество фаззинга. Если вам интересно узнать, как можно прокачать AFL и искать быстрее и больше уязвимостей, то добро пожаловать под кат!
Читать дальше →
Всего голосов 32: ↑31 и ↓1+30
Комментарии7

Ctrl-Alt-Del: учимся любить легаси-код

Время на прочтение22 мин
Количество просмотров21K


Какое отношение к легаси-коду имеют «Звёздные войны», группа «Тату» и сочетание «Ctrl-Alt-Del»? Как быть, когда приходишь в большой проект и сталкиваешься с пропастью непонятного старого кода? И как эффективнее донести до начальства, что трудозатраты на ликвидацию технического долга оправдывают себя?

Доклады Дилана Битти не обходятся без шуток, но эти шутки сопровождают вполне серьёзные рассуждения о главных вопросах разработки. Такое хорошо подходит для завершения конференции: когда зрители уже услышали много хардкора и больше не могут воспринимать слайды с кодом, самое время для более общих вопросов и яркой подачи. И когда нашу .NET-конференцию DotNext 2018 Moscow завершало выступление Дилана про легаси-код, зрителям оно понравилось сильнее всего.

Поэтому теперь для Хабра мы сделали переведённую текстовую версию этого выступления: и для дотнетчиков, и для всех остальных. Помимо текста, под катом есть и оригинальная англоязычная видеозапись.

Всего голосов 74: ↑72 и ↓2+70
Комментарии16

Нейросеть для разработчиков C++

Время на прочтение7 мин
Количество просмотров50K
Всем привет.

Написал библиотеку для обучения нейронной сети. Кому интересно, прошу.
Читать дальше →
Всего голосов 54: ↑51 и ↓3+48
Комментарии30

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность