• Коты в коробочках, или Компактные структуры данных

      image


      Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?


      В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.


      А тем временем на Хабре найдется ли герой, способный пересковоговорить три раза подряд
      [səkˈsɪŋkt]?

      Читать дальше →
    • Веская причина для проверки ваших зависимостей: AGPL-edition

      • Translation
      Вот вы берёте код под лицензиями BSD, MIT и Apache2 и в ус не дуете, а потом – бац! – вторая смена, и в транзитивной зависимости рисуется код под AGPL. Мы стараемся следить за этим и предпочитаем скорее перебдеть, чем недобдеть.


      Читать дальше →
    • Название имплементации и название результата

      • Translation


      Я хотел написать этот пост ещё в июле, но никак не мог, о ирония, решить, как его назвать. Удачные термины пришли мне в голову только после доклада Кейт Грегори на CppCon, и теперь я наконец могу рассказать вам, как не надо называть функции.


      Бывают, конечно, названия, которые вообще не несут информации, типа int f(int x). Ими пользоваться тоже не надо, но речь не о них. Порой бывает, что вроде бы и информации в названии полно, но пользы от неё абсолютно никакой.

      Читать дальше →
    • Илья Якямсев: Эффективность не работает

        С точки зрения проект-менеджера и с точки зрения управления людьми, люди в депрессии — идеальные работники.

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

        Недавно посмотрела выступление одного scrum-мастера и stand up комика по совместительству. Выступление оказалось эмоциональное, с большим количеством непечатных слов и долей здравого смысла.

        В каждой шутке только доля шутки, но все же прошу не относиться к этому материалу слишком серьезно. Предлагаю для ознакомления свое изложение в «очищенном» формате. Увидеть полное выступление Ильи Якямсева «Эффективность не работает» на конференция FrontDays 2018 можно по ссылке.


        Эффективность не работает


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

        Я работаю менеджером проекта. Начинал я в Тольятти, в 96 году, на должности «эй, пацан, принеси пиво». С 99 года я начал программировать front, тогда это называлось «верстак». Потом я открыл контору, закрыл ее, многое произошло, и сейчас я менеджер проектов.

        Мой доклад называется «Эффективность не работает». И я объясню почему.

        Жизнь после 30


        Дело в том, что мне сорокет в этом году. Я работаю в основном с людьми помоложе себя, и они у меня часто спрашивают: «Илья, как она жизнь в IT после 30? Ну, то есть, что с ней происходит?». Я отшучиваюсь: как говорится, баб поменьше, детей побольше



        Но я всерьез задался этим вопросом, подумал, что случилось со всеми людьми, с которыми я начинал, с которыми продолжаю. Всем моим друзьям около 40, все по-разному живут. Какое у нас общее свойство? О чем стоит рассказать людям? На что им ориентироваться в процессе работы? Каким образом это будет у них? И я вывел то общее, о котором хочу сегодня рассказать.
        Читать дальше →
      • Восход разработчикономики

          От переводчика
          Почитывая несколько лет назад журнал "Форбс", я наткнулся на статью, которую нашёл крайне интересной. Ну, знаете как бывает — читаешь, читаешь, и на каждом абзаце воскликаешь: «О! Це ж про меня!». Не мог поверить, что я один такой, и никто не сподобится уж если не перевести, то хотя бы сослаться на неё в русскоязычной прессе. Однако за четыре года этого так и не произошло. Ну что ж, «хочешь сделать что-то правильно — сделай это сам», посему предоставляю вниманию почтенной публики первую половину статьи. (Стараюсь переводить художественно, поэтому работа двигается небыстро; размер оригинала — больше 30 килобайт, и, «земную жизнь пройдя до половины», я понял, что держаться нету больше сил.)

          P.S. Так и не смог разобраться, как поставить в заголовке тег «перевод».

          Восход разработчикономики


          Статья Венкатеша Рао опубликована в декабре 2011 года в журнале «Форбс».

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

          В последнее время я размышлял над этой идейкой в контексте человеческого богатства. Если только вы не являетесь профессиональным инвестором (а даже если и являетесь), в настоящее время находить места для хранения избытка капитала, где он бы был в безопасности и не амортизировался слишком быстро (не говоря уже о принесении дохода) становится всё сложнее и сложнее. Фондовый рынок всё чаще навевает мысли о кровавом пиршестве “медведей”. Волатильность и неожиданные кратковременные ралли делают игру с короткими позициями небезопасной. Даже хранение активов в долларах, похоже, таит свои опасности — благодаря угрозе девальвации и всяким новомодным словечкам вроде «количественного смягчения», которые мы, среднестатистические инвесторы, слышим впервые. Евро сейчас тоже не смотрится как радужная альтернатива. Решение инвестировать в золото — и вообще в любое сырьё — кажется, требует несколько апокалиптического взгляда на мир, и размышлений о том, как вы планируете получить доступ к собственно предмету владения в случае, если всё и правда полетит в тартарары (хочется отметить, что в настоящий момент не могу назвать такой взгляд на мир так уж неоправданным).

          Но есть одна тихая гавань — если вы знаете, как в неё вложиться: разработчики ПО.

          Читать дальше →
        • Применение принципов функционального программирования при проектировании ERP

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

            В этой статье мы попробуем взглянуть на архитектуру учетных систем (ERP, CRM, WMS, MES, B2B, ...) с позиций функционального программирования. Существующие системы сложны. Они базируются на реляционной схеме данных, и имеют огромный мутабельный стейт в виде сотен связаных таблиц. При этом единственным «источником правды» в таких системах является хронологически-упорядоченный журнал первичных документов (отпечатков событий реального мира), которые, очевидно, должны быть иммутабельными (и это правило соблюдается в аудируемых системах, где корректировки «задним числом» запрещены). Журнал документов составляет от силы 20% объема БД, а все остальное — промежуточные абстракции и агрегаты, с которыми удобно работать на языке SQL, но которые требуют постоянной синхронизации с документами, и между собой.

            Если вернуться к истокам (устранить избыточность данных и отказаться от хранения агрегатов), а все бизнес-алгоритмы реализовать в виде функций, применяемых непосредственно к потоку первичных документов — мы получим функциональную СУБД, и построенную на ней функциональную ERP. Проблема производительности решается благодаря мемоизации, а объем функционального кода будет вполне соизмерим с объемом декларативного SQL, и не сложнее для понимания. В данной статье мы продемонстрируем подход, разработав простейшую файловую СУБД на языке TypeScript и рантайме Deno (аналог Node.js), а также протестируем производительность сверток на примере типичных бизнес-задач.

            Почему это актуально


            1) Мутабельный стейт + избыточность данных — это плохо, особенно когда необходимо обеспечивать его постоянную синхронизацию с потоком документов. Это источник потенциальных расхождений учетных данных (баланс не сходится) и трудно обнаруживаемых побочных эффектов.
            Читать дальше →
          • Учёный Хэ Цзянькуй – герой, а не преступник

            • Translation


            Когда я увидел новость о том, что Хэ Цзянькуй и его коллеги были приговорены к трём годам тюремного заключения за первые эксперименты по изменению генов и имплантации человеческого эмбриона, всё, что я мог подумать, было: «Как мы оглянемся на его поступок через 100 лет?»
            Китайский учёный описал свою работу и заявил о рождении девочек-близнецов на International Summit on Human Genome Editing в Гонконге в конце ноября 2018 года, и я не мог уснуть, пока не наступило раннее утро в Окленде, штат Калифорния, смотря в новостях о нём. После этого я не спал несколько суток и не мог перестать размышлять о его прорыве.

            Это был первый раз, когда жизнеспособный человеческий эмбрион был изменён и ему было разрешено жить более 14 суток, тем более, когда первый эмбрион был имплантирован и привёл к беременности женщины.
            Читать дальше →
          • Итоги: 9 главных технологических прорывов 2019 года

              На связи Александр Чистяков, я евангелист vdsina.ru и расскажу про 9 лучших технологических событий 2019 года.

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

              Я не сортировал события в списке по значимости или вау-эффекту, потому что их значимость будет понятна лет через десять, а вау-эффект слишком краткосрочен, просто постарался сделать эту историю связной.
              Читать дальше →
            • Функциональное программирование — это не то, что нам рассказывают

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



                Хотя люди обычно признают удобства ФП фич, ведь намного приятнее писать:


                int Factorial(int n)
                {
                    Log.Info($"Computing factorial of {n}");
                    return Enumerable.Range(1, n).Aggregate((x, y) => x * y);
                }

                чем ужасные императивные программы вроде


                int Factorial(int n)
                {
                    int result = 1;
                    for (int i = 2; i <= n; i++)
                    {
                        result *= i;
                    }
                    return result;
                }

                Так ведь? С одной стороны да. А с другой именно вторая программа в отличие от первой является функциональной.


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

                Читать дальше →
              • Нечёткое сравнение строк: пойми меня, если сможешь

                  image
                  Привет!

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

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

                  Результатом работы, описанием процесса, кодом на git'е готов поделиться с вами.

                  Итак, кратко задачу можно озвучить так: «С определенной периодичностью из различных источников приходят актуальные новости. Необходимо фильтровать их таким образом, чтобы на выходе не было двух новостей об одном и том же факте.»
                  Предупреждение: в статье присутствуют заголовки реальных новостей. Я отношусь к ним исключительно как к рабочему материалу, не представляю какую-либо точку зрения на политическую или экономическую ситуацию в какой бы то ни было стране.
                  Читать дальше →
                  • +22
                  • 28.9k
                  • 8
                • Категории, большие и малые

                  • Translation
                  Это четвертая статья в цикле «Теория категорий для программистов».

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

                  Без объектов


                  Самая простая категория — без объектов и, как следствие, без морфизмов.
                  Читать дальше
                • Learn OpenGL. Урок 6.1. PBR или Физически-корректный рендеринг. Теория

                  • Translation
                  • Tutorial
                  OGL3

                  Физически-корректный рендеринг


                  PBR, или физически-корректный рендеринг (physically-based rendering) это набор техник визуализации, в основе которых лежит теория, довольно хорошо согласующаяся с реальной теорией распространения света. Поскольку целью PBR является физически достоверная имитация света, он выглядит гораздо более реалистичным по сравнению с использованными нами ранее моделями освещения Фонга и Блинна-Фонга. Он не только лучше выглядит, но и дает неплохое приближение к реальной физике, что позволяет нам (и в частности художникам) создавать материалы, основанные на физических свойствах поверхностей, не прибегая к дешевым трюкам дабы заставить освещение выглядеть реалистично. Главным преимуществом такого подхода является то, что создаваемые нами материалы будут выглядеть как задумано независимо от условий освещения, чего нельзя сказать о других, не PBR подходах.

                  Читать дальше →
                • Почему Google нуждалась в графе знаний

                  • Translation
                  Когда я представляюсь и говорю, чем занимается наш стартап, у собеседника сразу возникает вопрос: вы раньше работали в Facebook, или ваша разработка создана под влиянием Facebook? Многие знают об усилиях Facebook по обслуживанию своего социального графа, потому что компания опубликовала несколько статей об инфраструктуре этого графа, который она тщательно выстроила.

                  Google рассказывала о своём графе знаний, но ничего о внутренней инфраструктуре. Однако в компании тоже есть для него специализированные подсистемы. На самом деле сейчас графу знаний уделяется большое внимание. Лично я поставил на эту лошадку минимум два своих повышения по службе — и начал работу над новым графом ещё в 2010 году.
                  Читать дальше →
                • Во что поиграть от топографического кретинизма: игры на зрительно-пространственную функцию



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

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

                      Доброго Хактоберфеста, дамы и господа. Подготовил для вас подборку самых интересных находок из опенсорса за сентябрь 2019.


                      За полным списком новых полезных инструментов, статей и докладов можно обратиться в мой телеграм канал @OpensourceFindings (по ссылке зеркало, если не открывается оригинал).


                      В сегодняшнем выпуске.
                      Технологии внутри: Python, C, Rust, Ruby, JavaScript, Go.
                      Тематика: веб разработка, администрирование, инструменты разработчика.


                      Прошлый выпуск.

                      Читать дальше →
                    • Параметризация нейросетью физической модели для решения задачи топологической оптимизации

                        Недавно на arXiv.org была загружена статья с не очень интригующим названием "Neural reparameterization improves structural optimization" [arXiv:1909.04240]. Однако оказалось, что авторы, по сути, придумали и описали весьма нетривиальный метод использования нейросети для получения решения задачи структурной/топологической оптимизации физических моделей (хотя и сами авторы говорят, что метод более универсален). Подход очень любопытный, результативный и судя по всему, — совершенно новый (впрочем, за последнее не поручусь, но ни авторы работы, ни сообщество ODS, ни я, аналогов припомнить не смогли), поэтому его может быть полезно знать интересующимся как использованием нейросетей, так и решением разнообразных задач оптимизации.
                        Читать дальше →
                      • Доказательное планирование

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

                        Разработчики программного обеспечения не любят составлять план работ. Обычно пытаются вовсе от него отказаться. «Закончу, когда закончу!», — говорят они, ожидая, что этот смелый и веселый поступок вызовет одобрение у босса, а о планировании будет успешно забыто.

                        Большая часть расписаний, с которыми вы встретитесь, будет представлять из себя бездушные отписки. Совершенно забытые, они хранятся в каком-нибудь общем каталоге. После выпуска продукта с опозданием на пару лет странный парень, в чьем офисе, говорят, видели картотеку, принесет на обсуждение причин провала старую распечатку, которую все засмеют. «Только гляньте! Мы запланировали две недели, на переписывание системы с нуля на Ruby!»
                        Читать дальше →
                      • Почему я больше не использую MVC-фреймворки

                        • Translation


                        Уважаемые хабравчане.

                        Поскольку дискуссия вокруг статьи идет весьма активно, Жан-Жак Дюбре (он читает комментарии) решил организовать чаты в gitter.

                        Вы можете пообщаться с ним лично в следующих чатах:
                        https://gitter.im/jdubray/sam
                        https://gitter.im/jdubray/sam-examples
                        https://gitter.im/jdubray/sam-architecture

                        Также автор статьи разместил примеры кода здесь: https://bitbucket.org/snippets/jdubray/

                        По поводу кода он оставил следующий комментарий:
                        I don't code for a living, so I am not the best developer, but people can get a sense of how the pattern works and that you can do the exact same thing as React + Redux + Relay with plain JavaScript functions, no need for all these bloated library (and of course you don't need GraphQL).
                        Читать дальше →
                      • Программирование — больше, чем кодинг

                        • Translation


                        Это статья-перевод Стэнфордского семинара. Но перед ней небольшое вступление. Как образуются зомби? Каждый попадал в ситуацию, когда хочется подтянуть друга или коллегу до своего уровня, а не получается. Причём «не получается» не столько у тебя, сколько у него: на одной чаше весов находится нормальная зарплата, задачи и так далее, а на другой — необходимость думать. Думать неприятно и больно. Он быстро сдаётся и продолжает писать код, совершенно не включая мозг. Ты представляешь, насколько много сил нужно потратить, чтобы преодолеть барьер выученной беспомощности, и просто не делаешь этого. Так образуются зомби, которых вроде бы можно вылечить, но вроде бы и никто этим заниматься не станет.


                        Когда я увидел, что Лесли Лэмпорт (да-да, тот самый товарищ из учебников) приезжает в Россию и делает не доклад, а сессию вопросов-ответов, я немного насторожился. На всякий случай, Лесли — всемирно известный учёный, автор основополагающих работ в распределённых вычислениях, а ещё вы его можете знать по буквам La в слове LaTeX — «Lamport TeX». Вторым настораживающим фактором является его требование: каждый, кто придёт, должен (совершенно бесплатно) заранее прослушать пару его докладов, придумать по ним минимум один вопрос и только тогда уже приходить. Решил посмотреть, что там Лэмпорт вещает — и это великолепно! Это в точности та штука, волшебная ссылка-таблетка для лечения зомбятины. Предупреждаю: от текста может знатно подгореть у любителей сверхгибких методологий и нелюбителей тестировать написанное.


                        После хаброката, собственно, начинается перевод семинара. Приятного чтения!

                        Читать дальше →
                      • Если вы не пишете программу, не используйте язык программирования

                        • Translation


                        Лесли Лэмпорт — автор основополагающих работ в распределённых вычислениях, а ещё вы его можете знать по буквам 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 — эта хабрастатья может сэкономить вам час времени на просмотр видео. На этом вступление закончено, мы передаём слово автору.




                        Когда-то давно Тони Хоар написал: «В каждой большой программе живет маленькая программа, которая пытается выбраться наружу». Я бы это перефразировал так: «В каждой большой программе живет алгоритм, который пытается выбраться наружу». Не знаю, правда, согласится ли с такой интерпретацией Тони.

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