Всем привет! Недавно открыл для себя язык Rust. О своих первых впечатлениях поделился в предыдущей статье. Теперь решил копнуть немного глубже, для этого необходимо что-то посерьёзнее списка. Выбор мой пал на дерево Меркла. В этой статье я хочу:
Сегодня никого не удивить скоростью интернета 100 Мбитс., но существует проблема, как её использовать. Все основные операции загружают сеть не полностью. Одновременно с этим более высокую популярность получают тяжёлые форматы аудио и видео 4k-8k, которые хочется смотреть онлайн. И глядя на высокие скорости интернета, возникает логичный вопрос — а почему этого нет? Как освоить всю скорость предоставляемую провайдером? Как со стороны клиента, так и со стороны сервиса. Рассмотрим все эти вопросы в статье.
Читать полностью »
В подавляющем большинстве моих постов о генерации случайных чисел рассматривались в основном свойства различных схем генерации. Это может оказаться неожиданным, но производительность алгоритма рандомизации может зависеть не от выбранной схемы генерации, а от других факторов. В этом посте (на который меня вдохновила превосходная статья Дэниела Лемира) мы исследует основные причины снижения производительности генерации случайных чисел, которые часто перевешивают производительность движка ГПСЧ.
Представьте такую ситуацию:
В качестве домашнего задания Хуан и Саша реализуют одинаковый рандомизированный алгоритм на C++, который будет выполняться на одном университетском компьютере и с одним набором данных. Их код почти идентичен и отличается только в генерации случайных чисел. Хуан торопится на свои занятия по музыке, поэтому просто выбрал вихрь Мерсенна. Саша, с другой стороны, потратил несколько лишних часов на исследования. Саша провёл бенчмарки нескольких самых быстрых ГПСЧ, о которых недавно узнал из соцсетей, и выбрал наиболее быстрый. При встрече Саше не терпелось похвастаться, и он спросил Хуана: «Какой ГПСЧ ты использовал?»
«Лично я просто взял вихрь Мерсенна — он встроен в язык и вроде неплохо работает».
«Ха!», — ответил Саша. «Я использовал jsf32. Он намного быстрее, чем старый и медленный вихрь Мерсенна! Моя программа выполняется за 3 минуты 15 секунд!».
«Хм, неплохо, а моя справляется меньше, чем за минуту», — говорит Хуан и пожимает плечами. «Ну ладно, мне пора на концерт. Пойдёшь со мной?»
«Нет», — отвечает Саша. «Мне… эээ… нужно снова взглянуть на свой код».
Эта неловкая вымышленная ситуация не особо и вымышлена; она основана на реальных результатах. Если ваш рандомизированный алгоритм выполняется не так быстро, как хотелось бы, и узким местом похоже является генерация случайных чисел, то, как это ни странно, проблема может быть и не в генераторе случайных чисел!
Читать полностью »
Привет!
В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.
В статье предложена авторская система создания лабиринтных ландшафтов, с помощью которой пользователь может автоматически генерировать различные сложные узоры в простой и интуитивно понятной системе. С помощью информации о лабиринте, рассчитанной в программе, быстро и эффективно генерируется трехмерный ландшафт лабиринта.
Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:
С помощью предложенной системы, состоящей из этих трех функций, можно эффективно создавать различные лабиринты, от однородных до нерегулярных. Эта разработка позволит генерировать лабиринтные ландшафты различных концепций напрямую из расчетов, сделанных через эту же систему. Кроме того, в этой работе проведен анализ улучшения эффекта присутствия и погружения в виртуальную реальность, т.е. визуального реализма. Также, в этой работе был проведен анализ пригодности предложенной авторской системы с помощью опроса.
Лесли Лэмпорт — автор основополагающих работ в распределённых вычислениях, а ещё вы его можете знать по буквам La в слове LaTeX — «Lamport TeX». Это он впервые, ещё в 1979 году, ввёл понятие последовательной согласованности, а его статья «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs» получила премию Дейкстры (точней, в 2000 году премия называлась по-старому: «PODC Influential Paper Award»). Про него есть статья в Википедии, где можно добыть ещё несколько интересных ссылок. Если вы в восторге от решения задач на happens-before или проблемы византийских генералов (BFT), то должны понимать, что за всем этим стоит Лэмпорт.
Эта хабрастатья — перевод доклада Лесли на Heidelberg Laureate Forum в 2018 году. В докладе пойдёт речь о формальных методах, применяемых в разработке сложных и критичных систем вроде космического зонда Rosetta или движков Amazon Web Services. Просмотр этого доклада является обязательным для посещения сессии вопросов и ответов, которую проведет Лесли на конференции Hydra — эта хабрастатья может сэкономить вам час времени на просмотр видео. На этом вступление закончено, мы передаём слово автору.
Когда-то давно Тони Хоар написал: «В каждой большой программе живет маленькая программа, которая пытается выбраться наружу». Я бы это перефразировал так: «В каждой большой программе живет алгоритм, который пытается выбраться наружу». Не знаю, правда, согласится ли с такой интерпретацией Тони.
Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.
Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.
Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать полностью »
Софи Хебден
FQXi Awardees: Маркус Мюллер 1
18 января 2019 г.
Творение космоса.
Credit: Юрий Акурс, iStock
Читать полностью »
Расшифровка видеозаписи лекции.
Теория игр — дисциплина, которая прочно зависла между математикой и социальными науками. Одним канатом к математике, другим канатом — к социальным наукам, прочно прикреплена.
В ней есть теоремы, достаточно серьёзные (теорема существования равновесия), про неё снят фильм «Игры разума», теория игр проявляется в множестве художественных произведений. Если смотреть вокруг, то и дело встречаешь игровую ситуацию. Я собрал несколько сюжетов.
Все мои презентации делает жена. Все презентации могут свободно распространяться, я буду крайне рад, если вы по ней будете читать лекции. Это полностью свободный материал.
Некоторые сюжеты спорные. Модели могут быть разные, можете не соглашаться с моей моделью.
(В конце поста — опрос про бомбу.)
Читать полностью »
Попалась мне неплохая статья, про метод спектрального оценивания, который отлично подходит для короткого сигнала из суммы слабозашумленных гармоник. (-копия) Возможно, мои комментарии помогут читателю вникнуть в суть метода. Что немного огорчило, так это не до конца реализованные возможности метода. Метод применен для радиолокации — для быстрого определения направления на приходящие сигналы (угла θ) с последующей целью автоматической, надо понимать, адаптации системы. Но — численного определения этого угла автор не производит (причем по контексту это странно), хотя это определение вполне возможно. Имеем только красивые графики, по которым, получается, системе надо еще «ползать» и «ползать», определяя количество и расположение максимумов, что не совсем хорошо.
Иллюстрация автора упомянутой статьи
Читать полностью »
Примечание переводчика: оригинальная статья опубликована в серии твитов
Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования. Я же в первую очередь хочу объяснить, откуда он вообще взялся. Всем пристегнуться, погружаемся в теорию игр ИСТОРИЮ!
Хотя индустрия программного обеспечения процветала в 80-е годы, но действительно взлетела в 90-е. В это десятилетие число работников отрасли в США утроилось и превысило миллион человек. Со взрывным ростом пришла необходимость нанимать массу сотрудников и оценивать их.
Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.
C работал близко к железу без лишних абстракций. Пустой словарь Python расходует аж 288 байт, то есть 5% всего объёма памяти первого поколения Apple II. Абстракции слишком дороги, слишком много накладных расходов. Если вам нужна сложная структура данных, вы должны построить её самостоятельно с помощью массивов, структур и указателей.
Читать полностью »
