Обновить
1087.84

Программирование *

Искусство создания компьютерных программ

Сначала показывать
Период
Уровень сложности

Доказательство некорректности алгоритма сортировки Android, Java и Python

Время на прочтение13 мин
Охват и читатели77K
Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

Опыт применения Go в продакшене Яндекса

Время на прочтение7 мин
Охват и читатели75K
Хочу поделиться опытом использования языка Go в продакшн-системах Яндекса. Вообще мы здесь довольно консервативно относимся к тому, какие языки использовать для реальных систем. И это лишь добавляет полезности тому опыту, который мы получили в этот раз.

Мы начали разрабатывать на Go летом прошлого года. Тогда появился фреймворк Go для облачной платформы Cocaine. До этого приложения серверного API Браузера писались в основном на C++ и Python. Серверный API в это время как раз переходил на облачную платформу, и мы по большей части только определялись с тем, какие технологии использовать в будущем для него. API выполняет следующие функции: получить данные, обработать, отправить во внутренний сервис Яндекса, ещё раз обработать, отдать назад Браузеру. Набор простых приложений.



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

Создание API: в рамку и на стену

Время на прочтение5 мин
Охват и читатели57K
Каждый программист — проектировщик API. Хорошие программы состоят из модулей, а протокол взаимодействия модулей — это тоже API. Хорошие модули используются повторно.

API — это большая сила и большая ответственность. У хорошего API будут благодарные пользователи; поддержка плохого превратится в кошмар.

Публичный API — не воробей, опубликуешь — не уберешь. Есть только одна попытка сделать все правильно, поэтому постарайся.

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

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

Перед разработкой API собери требования с долей здорового скептицизма. Осознай общие задачи и реши их.

Оформляй требования как шаблоны использования API. Сверяйся с ними в процессе проектирования.
Читать дальше →

Как я завалил собеседование в Twitter

Время на прочтение4 мин
Охват и читатели178K
image


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

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.
Читать дальше →

Excel, будь ты проклят: “1/2”+1=45660

Время на прочтение5 мин
Охват и читатели33K

Пишу этот текст совершенно без намерения оскорбить авторов Excel. Это фантастически успешный софт, который по праву считается золотым стандартом среди табличных редакторов. Тем не менее, в этом году Excel уже стукнуло 40. В таком почтенном возрасте его семантика всерьёз страдает из-за костылей, которые накапливались не один десяток лет, обеспечивая обратную совместимость.

Одно из самых интересных дел, которыми мне приходится заниматься на работе — это обратная разработка Excel. Я выискиваю причуды в его поведении и решаю, как поступать с ними в нашем фирменном табличном редакторе. Благодаря моему повседневному труду, наши пользователи, возможно, и не подозревают, сколько недокументированных грехов совершила Microsoft ради совместимости. Приглашаю вас одним глазком взглянуть на те ужасы, с которыми мне приходится тягаться — и тогда вы тоже станете бояться Microsoft Excel — не потому, что чего-то не знаете, а наоборот, так как знаете слишком много.

Читать далее

Сожги и начни заново

Время на прочтение5 мин
Охват и читатели45K

Во многих мошеннических схемах используется очень простая и действенная идея: когда человек вкладывается во что-то, это что-то обретает для него ценность, даже если по факту это пустышка. Например, всякие фейковые опросы, где человек тратит 2 часа времени, чтобы ответить на 500 вопросов, потом в личный кабинет падает 300кк рублей, но нужно заплатить 500р "комиссии" за вывод средств. Никто никогда бы не поверил в эту чушь, но когда потрачено 2 часа и кажется, что от награды отделяет самая малость... Или же человек играет в покер и проиграл уже все деньги, дом и кота, но нужно продолжать, потому что "столько проиграно, нужно отыграть".

Вчера я чуть не попался на это. Не на мошенничество, нет - я чуть не попал в упомянутую психологическую ловушку "слишком много вложил, чтобы бросить", которую сам себе и построил. Но моя история совсем не уникальна, поэтому помимо неё я собрал тут коллекцию историй и применил ORDER BY scale ASC, чтобы вы оценили: эта ловушка живёт на всех масштабах - от маленьких сиюминутных решений до целых жизней.

Читать далее

Встречайте, IntelliJ IDEA 14 уже здесь

Время на прочтение6 мин
Охват и читатели127K
Закончились праздники и выходные, но не поводы радоваться. Что может быть приятнее, чем узнать о долгожданном обновлении любимой Java IDE? Мы с нетерпением ждали четыре долгих дня, чтобы удивить вас этим приятным сюрпризом. Встречайте IntelliJ IDEA 14!

image

Рассказывая о том, чем мы занимались большую часть года, мы всякий раз переживаем и волнуемся. Каждая новая версия IntelliJ IDEA поднимает планку всеобщих ожиданий. И все-таки каждое обновление — еще один шанс для нас доказать, что совершенству нет предела. Удалось ли на этот раз — судить вам!

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

16-, 8- и 4-битные форматы чисел с плавающей запятой

Уровень сложностиСредний
Время на прочтение15 мин
Охват и читатели42K

Уже лет 50, со времён выхода первого издания «Языка программирования Си» Кернигана и Ритчи, известно, что «числа с плавающей запятой» одинарной точности имеют размер 32 бита, а числа двойной точности — 64 бита. Существуют ещё и 80-битные числа расширенной точности типа «long double». Эти типы данных покрывали почти все нужды обработки вещественных чисел. Но в последние несколько лет, с наступлением эпохи больших нейросетевых моделей, у разработчиков появилась потребность в типах данных, которые не «больше», а «меньше» существующих, потребность в том, чтобы как можно сильнее «сжать» типы данных, представляющие числа с плавающей запятой.

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

Читать далее

О «раздутом пузыре» нейросетей

Уровень сложностиСредний
Время на прочтение8 мин
Охват и читатели104K

На днях я наткнулся на одно любопытное видео.

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

Утверждения:

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

2. Нейросетевые модели внедряются слишком медленно.

3. Ответы нейросетевых моделей неконтролируемы и неинтерпретируемы.

Дальше обсудим каждое из них.

Читать далее

Почему уходят из 1С?

Время на прочтение29 мин
Охват и читатели163K

Скромная "ответочка" на статью про то, что 1С-ники гораздо умнее коллег из других ЯП.

Как IT специалист, знакомый с теми и другими, постараюсь оппонировать утверждениям из оригинальной статьи.

Читать далее

Самые позорные ошибки в моей карьере программиста (на текущий момент)

Время на прочтение8 мин
Охват и читатели126K

Как говорится, если тебе не стыдно за свой старый код, значит, ты не растешь как программист — и я согласна с таким мнением. Я начала программировать для развлечения более 40 лет назад, а 30 лет назад и профессионально, так что ошибок у меня набралось очень много. Будучи профессором информатики, я учу своих студентов извлекать уроки из ошибок — своих, моих, чужих. Думаю, пришло время рассказать о моих ошибках, чтобы не растерять скромность. Надеюсь, кому-то они окажутся полезны.
Читать дальше →

Почему я сворачиваю свою работу над Debian

Время на прочтение9 мин
Охват и читатели111K


От переводчика: этот текст — перевод записи в личном блоге Михаэля Штапельберга (Michael Stapelberg) видного open source-разработчика (профиль GitHub), который внес значительный вклад в развитие Debian.



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

Debian был частью моей жизни на протяжении 10 лет.

Несколько недель назад, на посвященной Debian встрече, проходившей в Цюрихе, я встретился со своими старыми друзьями, которых не видел много лет. Когда я уже ехал домой на велосипеде, меня осенило, что все обсуждаемые нами темы так или иначе сводились к тому, что мы обсуждали с ними в прошлый раз. Мы дискутировали о достоинствах systemd, который вновь привлек внимание участников open source сообщества, затронули тему процессов в Debian. Кульминацией стало обсуждение демократии как таковой и соответствующие теоретические и практические ошибки. Но, на самом деле, это уже чисто швейцарская тема.

Это не обзор прошедшего митапа, я просто хочу объяснить, что побудило меня задуматься о своем текущем отношении к Debian и подходит ли он мне.

Итак, я принял решение, которое должен был принять давно: я сворачиваю свое участие в развитии Debian.
Читать дальше →

Через тернии к Haskell. 1/2

Время на прочтение25 мин
Охват и читатели243K

Ближайшие события

Как не надо писать факториал в Java

Время на прочтение10 мин
Охват и читатели106K
Перевод этой статьи уже был однажды опубликован на хабре, но там почему-то осталась за кадром самая важная часть. Ниже — полный перевод.

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

Если вам надо написать факториал на Java, то большинство из ваc, вероятно, начнёт с чего-нибудь
такого

Советы новичкам в карьере программиста

Уровень сложностиПростой
Время на прочтение7 мин
Охват и читатели12K

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

Читать

Мой любимый Git-коммит

Время на прочтение6 мин
Охват и читатели56K
Прим. перев.: Эта публикация британского программиста, ставшая настоящим хитом в англоязычном интернете, ссылается на Git-коммит 6-летней давности. Он был зафиксирован в одном из открытых репозиториев Government Digital Service — службы, занимающейся развитием цифровых услуг в Великобритании и поддерживающей проект GOV.UK. Сам коммит интересен не столько изменениями в коде, сколько сопровождающим их описанием…


Картинка из xkcd #1296

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

Пять способов выгореть для программиста

Время на прочтение4 мин
Охват и читатели116K
imageОт переводчика
Выгорание в жизни программиста может случиться по самым разнообразным причинам; если задаться целью перечислить все пути, которыми оно подкрадывается к нам, то одно лишь это перечисление займет немало времени. Это еще один повод, по которому не стоит недооценивать процесс выгорания — иначе однажды вам придется искать дорогу обратно, и стоить это может очень дорого. Последняя строка вовсе не голословна — мне самому однажды смогла помочь лишь любовь к коду — когда уже, казалось бы, все осточертело и ничего не хотелось, чтение подвернувшегося Макконнелла навеяло воспоминания о том, как же когда-то мне нравилось программировать. И сегодня мне нравится делать это снова.
А теперь — слово автору.

Я отошел от своего выгорания только недавно — несмотря на то, что случилось оно несколько лет назад. Да, мне было непросто… очень непросто. Когда я думаю о произошедшем, на ум приходит немало причин тому, что случилось со мной — но самое интересное заключается в том, что каждой из них я никогда раньше не придавал значения. Хотите повторить мой путь и выгореть? Пожалуйста, у меня готов целый список, как следует поступать в таком случае:

1. Думать о проекте и только о нем


Признайтесь себе: бизнес хочет, чтобы вы создавали наилучший продукт «для наших клиентов». Вы откладываете в долгий ящик какой-либо функционал из-за того, что не успеваете к дедлайну. Вы планируете проект и анализируете его со всех сторон для того, чтобы разбить на несколько «перевариваемых» частей, которые затем должны быть воплощены одним из кодеров (в роли обезьянки, или code monkey, кстати говоря, можете быть и вы один). Вы создаете рабочий прототип, затем получаете обратную связь и делаете еще одну итерацию. И все это — без единой мысли о себе любимом.
Читать дальше →

Проверка високосности года в трёх командах CPU

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели10K

Показанным ниже кодом вы можете проверить на високосность год в интервале 0 ≤ y ≤ 102499 всего примерно тремя командами CPU:

bool is_leap_year_fast(uint32_t y) {

return ((y * 1073750999) & 3221352463) <= 126976;

}

Как это работает? Ответ на удивление сложен. В статье я объясню процесс; в основном он связан с забавным битовым жонглированием. В конце мы обсудим применение этого кода на практике.

Читать далее

One-shot промптинг. Как я начал вайбкодить в 10? раз быстрее

Уровень сложностиПростой
Время на прочтение6 мин
Охват и читатели34K

Вообще, я менеджер.

Но когда-то писал код и всегда любил это занятие. Серьезно прогал мобильные приложения, и даже заработал за один из ответов на SO больше 100 звездочек.

Но с тех пор прошла куча времени.

И последнее время меня вновь увлекла эта тема. А как она может увлечь современного человека, измученного миллиардом фреймворков и отставшего от прогресса лет на 15?
Конечно-же курсором и вайб-кодингом.

И я начал кодить.

Собрал несколько ботов, потом замахнулся на CMS. Сейчас даже делаю свою тулзу для запуска LLM-пайплайнов с импортом их из n8n.

Но в процессе всего этого неизменно сталкивался с двумя проблемами

1) Cursor (и брат его Windsurf) паршивейшим образом обходится с нетипизированными и слабо-типизированными языками. Изобретает названия переменных, меняет их по ходу, и вообще, забивает на это огромный и толстый... За пределами этого кодит он неплохо. Но данная штука лично у меня порождает 90% багов.
2)...

Читать далее

Вклад авторов