• Вычисление центра масс за O(1) с помощью интегральных изображений



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

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

    В этой статье я расскажу:

    • Что за задача такая, о которой идет речь;
    • Подробнее об интегральных изображениях;
    • Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
    • Какой недостаток имеет это решение и как его исправить;
    • И, наконец, как за константное время вычислить центр масс для произвольного региона.
    Читать дальше →
  • Как масштабироваться с 1 до 100 000 пользователей

    • Translation
    • Tutorial
    Через такое прошли многие стартапы: каждый день регистрируются толпы новых пользователей, а команда разработчиков изо всех сил пытается поддержать работу сервиса.

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

    Попытаемся отфильтровать информацию и записать основную формулу. Мы собираемся пошагово масштабировать наш новый сайт для обмена фотографиями Graminsta с 1 до 100 000 пользователей.

    Запишем, какие конкретные действия необходимо сделать при увеличении аудитории до 10, 100, 1000, 10 000 и 100 000 человек.
    Читать дальше →
  • Как я заработал 1 000 000 $ без опыта и связей, а потом потратил их, чтобы сделать свой переводчик

    Как все начиналось


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

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

    В статье приводится метод построения проекции галактической орбиты Солнечной системы через анализ пространственного перепада космологического красного смещения. Кроме известных движений вращения вокруг центра Галактики и смещения вверх-вниз относительно её диска, на результатах ясно просматривается «покачивание» оси.

    image

    Рис.0. Визуальное представление минимумов (зелёный) перепада красного смещения на воображаемой гелиоцентрической сфере – результат вращения Солнечной системы вокруг центра Млечного Пути. Чёрная ось – X (положительные направо), красная полупрозрачная – Y (положительные вглубь), синяя – Z (положительные наверх). Жёлтый шар – направление движения согласно жёлтой тенденции (RA 10, DEC -30) – движение Солнечной системы под диск Млечного Пути. Чёрный шар – актуальное направление на Стрельца-А (RA 266, DEC -29), центр Млечного Пути.
    Читать дальше →
    • +20
    • 5.5k
    • 3
  • Хрестоматийный случай одного гика

    Киберздоровье через призму Мармока


    image

    Марин Мокану, более известный как «Marmok» — один из самых популярных игровых видеоблогеров в СНГ.

    Его пример весьма показателен и, что самое главное, вполне характерен для любого человека, жизнь которого проходит за компьютером — вне зависимости от конкретного рода деятельности.
    Читать дальше →
  • В поисках LD_PRELOAD

      Эта заметка была написана в 2014-м году, но я как раз попал под репрессии на хабре и она не увидела свет. За время бана я про неё забыл, а сейчас нашёл в черновиках. Думал было удалить, но авось кому пригодится.



      В общем, небольшое пятничное админское чтиво на тему поиска «включенного» LD_PRELOAD.
      Читать дальше →
      • +67
      • 10.4k
      • 9
    • Как работают квантовые компьютеры. Собираем паззл


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


      А недавно ко мне подошли коллеги и спросили “Ты понимаешь как работает квантовый компьютер? Можешь нам рассказать?” И тут я понял, что проблема со складыванием в голове целостной картинки есть не только у меня.


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

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

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

        • 28 июля: вес — 80,5 кг, из них жировой ткани 14,9% и мышц 44,8%. Режим сна как таковой отсутствует.
        • 7 августа, 10 дней спустя: вес — 75,3 кг, из них жировой ткани 13% и мышц 45,8%. Каждый день ложусь спать в течение часа после заката.


        Читать дальше →
      • Автоматическое разблокирование корневого LUKS-контейнера после горячей перезагрузки

        • Tutorial

        Зачем вообще люди шифруют диски своих персональных компьютеров, а иногда — и серверов? Понятное дело, чтобы никто не украл с диска фотографии их любимых домашних котиков! Вот только незадача: зашифрованный диск требует при каждой загрузке ввести с клавиатуры ключевую фразу, а она длинная и скучная. Убрать бы ее, чтобы хотя бы иногда не приходилось ее набирать. Да так, чтобы смысл от шифрования не потерялся.


        Котейка для привлечения внимания

        Котейка


        Ну, совсем убрать ее не получится. Можно вместо нее сделать ключевой файл на флешке, и он тоже будет работать. А без флешки (и без второго компьютера в сети) можно? Если повезло с BIOS, почти можно! Под катом будет руководство, как настроить шифрование диска через LUKS вот с такими свойствами:


        1. Ключевая фраза или ключевой файл нигде не хранится в открытом виде (или в виде, эквивалентном открытому) при выключенном компьютере.
        2. При первом включении компьютера требуется ввести ключевую фразу.
        3. При последующих перезагрузках (до выключения) ключевую фразу вводить не требуется.

        Инструкции проверены на CentOS 7.6, Ubuntu 19.04 и openSUSE Leap 15.1 в виртуальных машинах и на реальном железе (десктоп, ноутбук и два сервера). Они должны работать и на других дистрибутивах, в которых есть работоспособная версия Dracut.


        И да, по-хорошему, это должно было бы попасть в хаб "ненормальное системное администрирование", но такого хаба нет.

        Читать дальше →
        • +23
        • 3.9k
        • 5
      • Аппаратное ускорение глубоких нейросетей: GPU, FPGA, ASIC, TPU, VPU, IPU, DPU, NPU, RPU, NNP и другие буквы



          14 мая, когда Трамп готовился спустить всех собак на Huawei, я мирно сидел в Шеньжене на Huawei STW 2019 — большой конференции на 1000 участников — в программе которой были доклады Филипа Вонга, вице-президента по исследованиям TSMC по перспективам не-фон-неймановских вычислительных архитектур, и Хенга Ляо, Huawei Fellow, Chief Scientist Huawei 2012 Lab, на тему разработки новой архитектуры тензорных процессоров и нейропроцессоров. TSMC, если знаете, делает нейроускорители для Apple и Huawei по технологии 7 nm (которой мало кто владеет), а Huawei по нейропроцессорам готова составить серьезную конкуренцию Google и NVIDIA.

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

          Только в прошлом году в тему было вложено больше 3 миллиардов долларов. Google уже давно объявил нейросети стратегическим направлением, активно строит их аппаратную и программную поддержку. NVIDIA, почувствовав, что трон зашатался, вкладывает фантастические усилия в библиотеки ускорения нейросетей и новое железо. Intel в 2016 году потратил 0,8 миллиарда на покупку двух компаний, занимающихся аппаратным ускорением нейросетей. И это при том, что основные покупки еще не начались, а количество игроков перевалило за полсотни и быстро растет.


          TPU, VPU, IPU, DPU, NPU, RPU, NNP — что все это означает и кто победит? Попробуем разобраться. Кому интересно — велкам под кат!
          Читать дальше →
        • Рендеринг текста вас ненавидит

          • Translation

          Рендеринг текста: насколько сложным он может быть? Оказывается, невероятно сложным! Насколько мне известно, буквально ни одна система не выводит текст «идеально». Где-то лучше, где-то хуже.

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

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

          Мы обсудим темы, которые не объединяются в рамках какой-то единой концепции, это просто вопросы, с которыми мне пришлось столкнуться за несколько лет работы над рендерингом текста в Firefox. Например, не будем слишком подробно обсуждать проблемы сегментации текста или управления различными текстовыми библиотеками для конкретной платформы, поскольку этим я не слишком интересуюсь.
          Читать дальше →
        • Дифференцируемое программирование


            С четырьмя параметрами я могу задать слона, а с пятью я могу заставить его шевелить хоботом.
            – John Von Neumann

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


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


            Далее мы пролистаем полотно неинтересного текста, захотим узнать, что такое автодифференцирование и даже популяем из катапульты!

            Читать дальше →
            • +23
            • 9.8k
            • 8
          • Предложения относительно уязвимостей и защиты моделей машинного обучения

            • Translation


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

            В этой статье приведем несколько вероятных векторов атак на типичную систему машинного обучения в типичной организации, предложим ориентировочные решения для защиты и рассмотрим некоторые общие проблемы и наиболее перспективные практики.
            Читать дальше →
            • +24
            • 4.4k
            • 3
          • Взлом и защита шифрования дисков LUKS


              Шифрование дисков предназначено для защиты данных в компьютере от несанкционированного физического доступа. Бытует распространённое заблуждение, что дисковое шифрование с этой задачей действительно справляется, а сценарии, в которых это не так, представляются уж слишком экзотическими и нереалистичными. В этой статье показано, что извлечение мастер-ключа шифрованного тома LUKS легко осуществимо на практике, и предложен (давно не новый) метод защиты.
              Читать дальше →
            • Расшифровка LUKS контейнера в момент загрузки системы

              Всем доброго дня, ночи! Этот пост будет полезен тем, кто использует шифрование данных LUKS и хочет производить decryptдешифровку дисков под Linux (Debian, Ubuntu) на стадии расшифровки root раздела. И такой информации в интернете я найти не смог.

              Совсем недавно с увеличением количества дисков в полках, столкнулся с проблемой расшифровки дисков с использованием более чем известного метода через /etc/crypttab. Лично я выделяю несколько проблем использования этого метода, а именно то, что файл читается только после загрузки (mount) root-раздела, что негативно сказывается на импорте ZFS, в частности если они были собраны из разделов на *_crypt устройстве, или же mdadm рейды, собранные так же из разделов. Мы же все знаем, что можно использовать parted на LUKS контейнерах? И также проблема раннего старта других служб, когда массивов еще нет, а использовать уже что-то надо (я работаю с кластеризованным Proxmox VE 5.x и ZFS over iSCSI).

              Немного о ZFSoverISCSI
              iSCSI работает у меня через LIO, и собственно когда стартует iscsi-таргет и не видит ZVOL устройств, он их просто-напросто удаляет из конфигурации, что не дает возможности загружаться гостевым системам. Отсюда либо восстановление бэкапа json файла, либо ручное добавление устройств с идентификаторами каждой VM, что просто ужас, когда таких машин десятки и в конфигурации каждой более 1 диска.

              И второй вопрос, который я рассмотрю, это чем производить расшифровку (это ключевой момент статьи). И об этом мы поговорим ниже, заходите под кат!
              Читать дальше →
            • Авиационные газотурбинные двигатели

                Всем привет! В этой статье я хочу рассказать о том, как работают авиационные газотурбинные двигатели (ГТД). Я постараюсь сделать это наиболее простым и понятным языком.

                Авиационные ГТД можно можно разделить на:

                • турбореактивные двигатели (ТРД)
                • двухконтурные турбореактивные двигатели (ТРДД)
                • Турбовинтовые двигатели (ТВД)
                • Турбовальные двигатели (ТВаД)

                Притом, ТРД и ТРДД могут содержать в себе форсажную камеру, в таком случае они будут ТРДФ и ТРДДФ соответственно. В этой статье мы их рассматривать не будем.

                Начнём с турбореактивных двигателей.

                Турбореактивные двигатели


                Такой тип двигателей был создан в первой половине 20-го века и начал находить себе массовое применение к концу Второй мировой войны. Первым в мире серийным турбореактивным самолетом был немецкий Me.262. ТРД были популярны вплоть до 60-ых годов, после чего их стали вытеснять ТРДД.

                image
                Современная фотография Me-262, сделанная в 2016 году

                Самый простой турбореактивный двигатель включает в себя следующие элементы:

                • Входное устройство
                • Компрессор
                • Камеру сгорания
                • Турбину
                • Реактивное сопло (далее просто сопло)

                Можно сказать, что это минимальный набор для нормальной работы двигателя.

                А теперь рассмотрим что для чего нужно и зачем.
                Читать дальше →
              • Самые полезные приёмы работы в командной строке Linux

                • Translation
                Каждый, кто пользуется командной строкой Linux, встречался со списками полезных советов. Каждый знает, что повседневные дела вполне можно выполнять эффективнее, да только вот одно лишь это знание, не подкреплённое практикой, никому не приносит пользы.

                Как выглядят типичные трудовые будни системного администратора, который сидит на Linux? Если абстрагироваться от всего, кроме набираемых на клавиатуре команд, то окажется, что команды эти постоянно повторяются. Всё выходит на уровень автоматизма. И, если даже в работе есть что улучшать, привычка противится новому. Как результат, немало времени уходит на то, чтобы делать так, как привычнее, а не так, как быстрее, и, после небольшого периода привыкания – удобнее. Помнить об этом, сознательно вводить в собственную практику новые полезные мелочи – значит профессионально расти и развиваться, значит – экономить время, которое можно много на что потратить.

                image

                Перед вами – небольшой список полезных приёмов работы с командной строкой Linux. С некоторыми из них вы, возможно, уже знакомы, но успели их позабыть. А кое-что вполне может оказаться приятной находкой даже для знатоков. Хочется надеяться, что некоторые из них будут вам полезны и превратятся из «списка» в живые команды, которыми вы будете пользоваться каждый день.
                Читать дальше →
              • А если найду? Перелет еще дешевле чем вы уже нашли

                  Если вы планируете поездку и уже нашли недорогой перелет, не спешите покупать билеты, потому что сейчас вы найдете билеты еще дешевле. И это не реклама очередного говноагрегатора.

                  Всем известно, что авиакомпании берут свои цены с потолка. Маркетологи придумывают хитроумные непрозрачные схемы отъёма денег у пассажиров пропорционально финансовым возможностям последних. Так, чтобы богатые платили за билеты побольше, а бедные — сколько смогут.

                  Читать дальше →
                • [ В закладки ] Алгоритмы и структуры данных в ядре Linux, Chromium и не только

                  • Translation
                  Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.



                  Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.
                  Читать дальше →
                  • +140
                  • 81.6k
                  • 15
                • Как компьютер играет в шахматы?


                  Хикару Накамура, недавно бросивший вызов компьютеру

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

                  Если вам интересно, как же устроены шахматные движки — добро пожаловать под кат.
                  Читать дальше →