Search
Write a publication
Pull to refresh
4
0.1
Send message

Классические алгоритмы генерации лабиринтов. Часть 1: вступление

Reading time8 min
Views65K


Предисловие


На написание статьи меня сподвигло практически полное отсутствие материалов на русском языке про алгоритмы генерации лабиринтов. На Хабре, из того, что вообще есть по теме, можно отметить две статьи: раз и два. Ценность и пользу из которых несет лишь вторая. В первой – просто перевод формального алгоритма и небольшое его пояснение. Что, конечно, неплохо, но очень скудно и не вызывает желания изучать тему дальше.

Если моя статья Вам понравится, я продолжу писать о различных алгоритмах. Мы рассмотрим два самых примитивных и простых случая – генерация двоичного дерева и Сайдвиндер, который, по своей сути, просто чуть измененная версия двоичного дерева с одним заметным плюсом. ОСТОРОЖНО ТРАФИК.
Читать дальше →

Домашнее задание от МТИ: пишем нейросеть для манёвров в дорожном трафике

Reading time4 min
Views23K


DeepTraffic — интересная интерактивная игра, поучаствовать в которой может любой желающий, а студенты Массачусетского технологического института (МТИ), которые изучают курс глубинного обучения в беспилотных автомобилях, обязаны показать хороший результат в этой игре, чтобы им засчитали выполненное задание.
Читать дальше →

Грааль и Трюфель (Graal & Truffle)

Reading time12 min
Views23K
Малоизвестный исследовательский проект, который может значительно ускорить инновации в проектировании языков программирования

От переводчика


Хочу сразу предупредить, что статья местами напоминает презентацию крупной компании из-за эпитетов в духе «изменит индустрию», «лучший на рынке», «прорывные технологии» и др. Если закрыть глаза на такой эмоциональный стиль повествования, то получится интересная вводная статья про новинки технологий компиляторов и виртуальных машин.


Введение


Со времён расцвета компьютерной индустрии многие были увлечены квестом в поисках идеального языка программирования. Квест очень сложный: создание нового языка — задача не из лёгких. И очень часто в процессе происходит дробление сложившейся экосистемы программирования и возникает необходимость заново строить базовые инструменты для нового языка: компилятор, отладчик, HTTP стек, IDE, библиотеки и бесконечное число базовых блоков пишутся с нуля для каждого нового языка. Совершенство в дизайне языков программирования недостижимо, и новые идеи возникают постоянно. Мы похожи на Сизифа: приговоренного богами на вечное толкание камня в гору, чтобы в итоге увидеть, как тот скатывается вниз снова и снова … целую вечность.


Как можно разорвать этот порочный цикл? Давайте помечтаем, чего бы нам хотелось.

Читать дальше →

Повышаем производительность кода: сначала думаем о данных

Reading time20 min
Views64K


Занимаясь программированием рендеринга графики, мы живём в мире, в котором обязательны низкоуровневые оптимизации, чтобы добиться GPU-фреймов длиной 30 мс. Для этого мы используем различные методики и разработанные с нуля новые проходы рендеринга с повышенной производительностью (атрибуты геометрии, текстурный кеш, экспорт и так далее), GPR-сжатие, скрывание задержки (latency hiding), ROP…

В сфере повышения производительности CPU в своё время применялись разные трюки, и примечательно то, что сегодня они используются для современных видеокарт ради ускорения вычислений ALU (Низкоуровневая оптимизация для AMD GCN, Быстрый обратный квадратный корень в Quake).


Быстрый обратный квадратный корень в Quake

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

Эта статья — не исчерпывающее хардкорное руководство по железу. Это всего лишь введение, напоминание, свод базовых принципов написания эффективного кода для CPU. Я хочу «показать, что низкоуровневое мышление сегодня всё ещё полезно», даже если речь пойдёт о процессорах, которые я мог бы добавить.

В статье мы рассмотрим кеширование, векторное программирование, чтение и понимание ассемблерного кода, а также написание кода, удобного для компилятора.
Читать дальше →

Теорема Гёделя о неполноте за 20 минут

Reading time8 min
Views216K


Теореме Гёделя о неполноте, одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой — в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума». И вот одни пытаются приспособить её в качестве аргумента против материализма, а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.

Математическая логика — наука действительно довольно сложная, а главное — не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

Читать дальше →

Фингерпринтинг конкретного ПК с точностью 99,24%: не спасает даже смена браузера

Reading time4 min
Views84K

Задачи рендеринга на клиентской стороне с целью фингерпринтинга

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

Группа американских исследователей опубликовала научную работу с описанием более продвинутых техник фингерпринтинга, которые не учитывают версию браузера, но всё равно распознают конкретный ПК с высокой точностью.
Читать дальше →

О строковом форматировании в современном C++

Reading time9 min
Views156K

Доброго времени суток! В этой статье я хотел бы рассказать о существующих возможностях строкового форматирования в современном C++, показать свои наработки, которые я уже несколько лет использую в реальных проектах, а также сравнить производительность различных подходов к строковому форматированию.

Читать дальше →

Поиск утечки GDI объектов: Как загнать мастодонта

Reading time6 min
Views17K
Строго говоря именно это оригинальный текст статьи, а в блоге уже перевод. Здесь статья публикуется чуть позже и только потому получает бирку перевод.

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

Проблема


Утечка или использование слишком большого числа GDI объектов.

Симптомы:


  • В Task Manager на вкладке Details колонка GDI objects показывает угрожающие 10000(Если этой колонки нету, ее можно добавить, кликнув на заголовке таблицы правой кнопкой и выбрав пункт Select Columns)
  • При разработке на C# или другом языке выполняемом CLR полетит исключение, не блещущее конкретикой:
    Message: A generic error occurred in GDI+.
    Source: System.Drawing
    TargetSite: IntPtr GetHbitmap(System.Drawing.Color)
    Type: System.Runtime.InteropServices.ExternalException

    Также при определенных настройках или версии системы исключения может и не быть, но Ваше приложение не сможет нарисовать ни единого объекта.
  • При разработке на С/С++ все методы GDI вроде Create%SOME_GDI_OBJECT% стали возвращать NULL
Читать дальше →

NoSQL – коротко о главном

Reading time17 min
Views88K


Сергей Туленцев (TextMaster)


Меня зовут Сергей Туленцев, я уже несколько лет интересуюсь NoSQL базами данных и сегодня попытаюсь поделиться с вами знаниями и опытом.

Кому будет полезен этот доклад? Это обзорный доклад с претензией на структурированность. Если вы что-то где-то когда-то слышали про NoSQL, то через 40 минут вы будете знать гораздо больше, вы будете легче ориентироваться в терминах и более уверенно выбирать базы данных для своего проекта.

Поговорим также про типичные примеры применения и как не надо применять NoSQL базы данных.
Читать дальше →

Малоизвестные Git-команды

Reading time4 min
Views74K


У Git есть строгие обязательства по обратной совместимости: многие продвинутые возможности скрыты за разнообразными опциями, а не применяются как поведение по умолчанию. К счастью, Git также поддерживает и алиасы, так что вы можете создавать свои собственные команды, которые делают всю характерную для Git магию. Под катом — подборка полезных (или как минимум забавных) алиасов, определённых в моём .gitconfig.
Читать дальше →

Гайд по Pascal: разбираемся в видеокартах NVIDIA 2016 года

Reading time20 min
Views66K
2016 год уже на исходе, но его вклад в игроиндустрию останется с нами надолго. Во-первых, видеокарты из красного лагеря получили неожиданно удачное обновление в среднем ценовом диапазоне, ну а во-вторых NVIDIA в очередной раз доказала, что не зря занимает 70% рынка. Maxwell’ы были хороши, GTX 970 по праву считалась одной из лучших карточек за свои деньги, но Pascal — совсем другое дело.


Новое поколение железа в лице GTX 1080 и 1070 буквально похоронило результаты прошлогодних систем и рынок флагманского б/у железа, а «младшие» линейки в лице GTX 1060 и 1050 закрепили успех в более доступных сегментах. Владельцы GTX980Ti и прочих Titan’ов рыдают крокодильими слезами: их убер-пушки за много тысяч рублей разом потеряли 50% стоимости и 100% понтов. Сама NVIDIA заявляет, что 1080 быстрее, чем прошлогодний TitanX, 1070 легко «наваляет» 980Ti, а сравнительно бюджетная 1060 сделает больно владельцам всех остальных карточек.

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

Конец халяве: I Know What You Download

Reading time6 min
Views303K
Продолжение (часть 2).
Не понимаю, почему никто не кричит «полундра» (поискал здесь и на Хабре по слову «iknowwhatyoudownload», но ничего).

Итак, некий сайтик iknowwhatyoudownload.com по IP-адресу показывает список торрентов, скаченных и розданных с этого адреса.
Судя по всему, запустились недавно. Домен зарегистрирован 14 сентября 2016. Отображается статистика примерно за месяц. Но как долго она собиралась, неизвестно.
Читать дальше →

Карринг vs Частичное применение функции

Reading time7 min
Views22K

Перевод статьи Джона Скита, известного гуру языка C#, автора книги C# In Depth, сотрудника Google, человека #1 по репутации на stackoverflow.com и наконец героя Jon Skeet Facts. В этой статье Джон доступно объясняет, что представляют из себя карринг и частичное применение функции, концепции, пришедшие из мира функционального программирования. Кроме того, он подробно поясняет в чём их различие. Признаюсь, что я и сам их путал до прочтения этой статьи, поэтому мне показалось полезным сделать перевод.


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

  • Те, кто не интересуются функциональным программированием и находят функции высшего порядка запутанными: вы можете пропустить эту статью полностью.
  • Те, кто знают всё о функциональном программировании и хорошо понимают разницу между каррингом (currying) и частичным применением функции (partial function application): пожалуйста, внимательно прочтите этот пост и отпишитесь в комментариях, если найдете неточности.
  • Те, кто частично знаком с функциональным программированием, и заинтересован узнать больше: отнеситесь к этому посту скептически и внимательно прочтите комментарии. Прочитайте другие статьи более опытных разработчиков для получения дополнительной информации.

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

Lock-free структуры данных. Iterable list

Reading time7 min
Views15K
Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).

Можно ли такой подход распространить на lock-free list?.. Посмотрим…
Читать дальше →

Можно ли вычислять биткоины быстрее, проще или легче?

Reading time12 min
Views50K

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

Самый простой способ разобраться во всех деталях — изучить открытые исходники. Я взялся изучать Verilog исходники FPGA-майнера. Это не единственный такой проект, есть еще несколько примеров на github, и все они, хоть и разных авторов, похоже работают приблизительно по одной схеме. Вполне возможно, что автор то у них всех изначально был один, просто разные разработчики адаптируют один и тот же код под разные чипы и разные платы… По крайней мере мне так показалось…

Вот и я, поизучав исходники Verilog, адаптировал проект с github к плате Марсоход3 на основе ПЛИС Altera MAX10, 50 тыс. логических элементов. Я смог запустить свой майнер и даже смог запустить процесс вычисления биткоинов, но бросил это дело через пол часа из-за бесперспективности. Слишком медленно по нынешним временам работает мой FPGA майнер. Ну и пусть.

Честно говоря, меня во всем этом проекте заинтересовали не сами биткоины (ну их, эти денежные суррогаты), но скорее математическая сторона алгоритма SHA256. Вот об этом я и хотел бы поговорить. Я провел несколько экспериментов с алгоритмом SHA256, может быть результаты этих экспериментов покажутся вам интересными.
Читать дальше →

Исследование руткита Cremes

Reading time7 min
Views5.3K
В августе этого года мы публиковали информацию о новом state-sponsored вредоносном ПО под названием Cremes (aka Remsec). Антивирусные продукты ESET обнаруживают его компоненты как Win32/Cremes и Win64/Cremes. Cremes является сложным трояном со множеством компонентов, которые используются для кибершпионажа. Информация о Cremes также была опубликована специалистами Федеральной Службы Безопасности (ФСБ), поскольку Cremes использовался для кибершпионажа за сотрудниками государственных учреждений.


Cremes включает в себя и Ring 0 компонент (руткит), который используется злоумышленниками как LPE-шлюз (kernel gate) для исполнения своего кода в режиме ядра. В отличие от уже таких хорошо известных руткитов и буткитов как ZeroAccess, TDL4, Mebroot, Gapz и др., Cremes не обременяет себя сложными процедурами компрометации MBR и ранних стадий загрузки ядра NT для исполнения своего Ring 0 кода в системе в обход DSE, вместо этого он использует для этого легитимные драйверы.
Читать дальше →

Электронный микроскоп в гараже: Про вакуум

Reading time10 min
Views38K
Для тех, кто ещё не в курсе о проекте — почитать можно вот здесь.


Обратная связь


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

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

Вакуум


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

Вообще в вакууме всё пропускает и испаряется: даже металлы, вопрос глубины вакуума и температуры. Только представьте, что обычное резиновое уплотнение пропускает значительный объём газа для того, чтобы помешать вакуумированию. Не где-то через щель, а через саму резину. Или, например, гибкий шланг помимо того, что пропускает сквозь себя воздух, ещё и слегка испаряется сам. А внутренняя поверхность вакуумной камеры накапливает газ в своих шероховатостях, и поэтому её обычно полируют. Всё это очень непривычно для понимания.

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

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

Expressions в C# — impress yourself!

Reading time9 min
Views110K
.NET 4.0 уже не за горами и принесет кучу всего нового, нужного и не очень, крутого и суперкрутого. Однако и в старом добром .NET 3.5 есть много разных интересных фич, которые не используются в повседенвной работе, но иногда здорово облегчают жизнь разработчикам. Одна из таких замечательных штук — это Expressions.
Много текста и кода

О языке С и производительности

Reading time31 min
Views65K


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

Но как можно считать себя профессионалом в каком-либо (высокоуровневом) языке, если даже не знаешь, как именно работает процессор, как он выполняет вычисления, эффективным ли способом? Сегодня автоматическое управление памятью становится главной проблемой в большинстве высокоуровневых языков, и многие программисты подходят к её решению без достаточной теоретической базы. Я уверен, что знание низкоуровневых процессов сильно помогает в разработке эффективных высокоуровневых программ.
Читать дальше →

Погружаемся в глубины C# dynamic

Reading time5 min
Views77K
Одним из наиболее заметных дополнений в C# 4 является dynamic. Об этом рассказано много и не раз. Но всегда выпускается из виду DLR (Dynamic Language Runtime). В данной статье мы рассмотрим внутреннее устройство DLR, работу самого компилятора, а также дадим определение понятиям статически-, динамически- типизированный язык со слабой и сильной типизациями. И, конечно же, не останется без внимания техника PIC (Polymorphic Inline Cache), используемая, например, в Google V8 engine.
Читать дальше →

Information

Rating
7,469-th
Registered
Activity