Ни о какой безапелляционности в моих высказываниях не может быть и речи!

Исключительно подробный и очень интересный (для тех, кто в теме, как минимум) пост одной дотошной индийской исследовательницы о том, как она искала работу в области языковых моделей буквально пару месяцев назад. У нее есть Ph.D. и публикации, она искала роль ML Research Scientist или что-то в этом роде.

Она рассказывает о том, как устроен процесс в AI-стартапах, в компаниях-единорогах (это стартапы, выросшие до размеров больше миллиарда долларов в оценке) и в больших техно-компаниях типа Google, Apple, Amazon, Meta итд. Дает примерные размеры предложенных зарплат включая бонусы и акции (150-200 тысяч долларов в год в стартапах, 345-400 тысяч долларов в год в больших компаниях), рассказывает о том, что прошло хорошо и что не понравилось, какие виды интервью были, какого рода вопросы задавали, как она рекомендует к интервью готовиться. В общем, интересно.

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

(может быть интересно программистам)

Некий Grant Slatton написал в Твиттере список из задач, которые давал на интервью программистам в Амазоне (группа AWS). Привожу ссылку и пишу о них не потому, что это что-то из ряда вон выходящее, а просто любопытно, можно обсудить и сравнить впечатления.

Итак, три задачи:
1) проверить, что строка из скобок типа ((())()()())) правильно сбалансирована
2) дана матрица из нулей и единиц, где 0 - вода, а 1 - суша, найти кол-во "островов". Суша соединяется по 4 направлениям, не по диагонали
3) построить структуру данных, дающую insert(value), delete(value), sample_uniform_random() -> value, все операции быстрее, чем O(N).

Я не понял, это задачи на предварительное интервью (phone screen) или "настоящее". По моему опыту из Гугла, этот набор задач немного сложнее, чем типичное предварительное, и немного легче, чем настоящее. Но в принципе годные задачи, как мне кажется.

Про первую задачу: Грант написал, что самое быстрое решение было за 10 секунд, некий соревновательный программист из Казахстана. Я подумал: объяснил за 10 секунд? - ну так и я могу. Но оказалось, что чувал буквально за 10 секунд написал код, "a Python two-liner". Это, конечно, жесть. Мне стало любопытно, и я заморочился написанием двухстрочного решения на Питоне, и через пару минут (никак не 10 секунд, да), вымучил следующее:

def balanced(a):
cnt=0; b=[cnt:=cnt+(1 if i=="(" else -1) for i in a]
return not any([c<0 for c in b])

Про вторую задачу: можно делать DFS, но я бы обошелся простым проходом по матрице с слиянием островов. Если интересует только число островов, слияние можно сделать за O(1) через уровень индирекции, без сложных структур данных.

Третью задачу можно по-разному решать, напишу свой вариант в комментах.

Сегодня узнал, почему код на SQL принято писать заглавными буквами, хотя в принципе язык позволяет маленькими тоже и любые сочетания: "Просто надо орать на базу данных. Она тогда немного быстрее работает."

Напоминаю, что сегодня начинается Advent of Code - испытание в виде задачек на программирование, которые даются в течение 25 первых дней декабря. Каждый день в полночь открывается новое задание, в двух частях (вторая тяжелее первой). Первые несколько дней задания легкие, потом постепенно усложняются, но не до уровня крутых соревнований. Есть состязание между теми, кто присылает решение как можно быстрее, со списками лидеров, которые ждут полуночи и в течение пары минут шлют ответ, но я советую не обращать внимания на эти гонки, а просто решать в свое удовольствие.

Многие используют Advent of Code, чтобы научиться писать на новом для себя языке. Я так делал дважды в прошлом, и хочу попробовать и в этот раз, но пока не решил, на каком языке. Хотя я не писал нетривиальное количество кода на Rust и Go, мне кажется, что достаточно знаю о них из прочитанного с годами, что не хочется сейчас - лучше что-то более незнакомое. На Zig делал этот конкурс пару лет назад. Относительно известные "старые" языки: Lisp, Haskell, Forth, SmallTalk - когда-то знал или пробовал. Пока что размышляю между OCaml и Crystal. Хотите посоветовать мне что-то другое?

(для программистов и сочувствующих)

Слетали летом в командировку в Америку, получили много экспериментальных данных разных людей, привезли обратно в Израиль и стали анализировать. Данные занимают примерно два терабайта, уместились на одном SSD-диске. В Америке у партнеров осталась оригинальная копия (странное словосочетание, если задуматься).

Через пару месяцев обнаружили, что данные слегла подпорчены. Там на 99% бинарные файлы, а 1% - большие файлы .CSV с числами, числами, числами внутри. По ряду причин все данные хранятся как обычная большая файловая иерархия (а не, скажем, zip-архивы или база данных).

Код на питоне читает CSV-файлы с помощью библиотеки Pandas, которая подбирает для каждой колонки наиболее узкий тип данных - т.е. если в файле в 3-й колонке везде числа с плавающей точкой, это будет float, а если иногда что-то другое, будет string для всех. Обнаружилось, что в некоторых файлах числовые данные читаются как string, что потом приводит к странным результам, когда с ними делают числовые операции. Когда я стал разбираться, почему так, обнаружил, что мегабайтном файле, целиком состоящем из чисел, записано в одном месте "число" -0.053208=523, и этот знак = все портит. Всего таких испорченных csv-файлов оказалось мало, около 3%. Но я не знал, есть ли подобные ошибки также в бинарных файлах.

Если бы данных было меньше, я бы просто скопировал из Америки. Но копировать 2TB было немного болезненно, и заодно хотелось разобраться, откуда взялась порча и сколько ее. Поэтому я сделал следующее:

- запустил рекурсивный md5sum на все дерево в Америке и дома (10 миллионов файлов)
- скопировал файлы с контрольными суммами в одно место и сравнил, нашел, сколько файлов отличаются по сумме (300 тысяч), сгенерировал список этих файлов
- в Америке сделал zip-архив только с оригиналами испорченных файлов (80GB), скопировал в Израиль, раскрыл
- набросал скрипт, который прошелся по оригиналам, сравнил с испорченными копиями.

Оказалось следующее:

- испорчен примерно один байт из каждых 300 килобайт, т.е. 0.0003% данных
- порча есть в файлах всех типов, и бинарных, и CSV, просто в CSV заметили раньше
- порча всегда одного вида: третий бит с конца становится 1, неважно, был он до того 0 или 1. Т.е. значение байта увеличивается на 4 (или не меняется, если и так этот бит стоял).
- при этом в файлах CSV, состоящих почти целиком из цифр и запятых, происходит следующее. Запятые не меняются, их ASCII-код содержит этот бит. Цифры 0,1,2,3 переходят в 4,5,6,7 и мы эту порчу не заметили. Цифры 4,5,6,7 остаются как есть. И только 8,9 переходят в <,= и это дает вышеописанный эффект в чтении файла из питона. Поэтому только когда очень редкая порча попадает именно на текстовый файл, и в нем на одну из этих двух цифр, получается испорченный файл, который мы замечаем.

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

Урок на будущее: после копирования большого кол-ва данных отдельно проверить, что копия идентична оригиналу, с помощью программы сравнения файлов/директорий.

(Сначала я хотел написать "копировать архивами, даже и без сжатия можно, просто чтобы была контрольная сумма", но если порчу вносит плохой бит в памяти во время *чтения* с диска, то архиватор создаст отличный архив с правильной суммой и плохими данными)

Прикольно.

Вас попросили дать оценку, когда будет выполнено задание, которое должно с вероятностью 90% занять один день, и 10% - два месяца. Ваш ответ?

Много думал о двух статьях о программировании, которые недавно прочитал - об объектно-ориентированном программировании и не только.

William R. Cook. On Understanding Data Abstraction, Revisited: https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

Jonathan Aldrich. The Power of Interoperability: Why Objects Are Inevitable:
https://www.cs.cmu.edu/~aldrich/papers/objects-essay.pdf

Статья Кука посвящена разграничению двух похожих, но фундаментально разных понятий, которые (согласно ему) часто путают - Абстрактных Типов Данных (АТД) и объектов. Статья Алдрича развивает эту тему, но в основном аргументирует, что "объекты" - намного более важное понятие, чем "АТД", и что повсеместное использование объектов в современных языках программирования и больших проектах не случайно.

Я сначала прочитал статью Кука (2009), много с ней спорил в голове, сформулировал какой-то ответ, а потом обнаружил к некоторому замешательству, что по большей части этот ответ содержится в статье Алдрича (2014). Тем не менее хочу попробовать упорядочить свои мысли на эти темы.

Начну с Кука. Он аккуратно определяет и проясняет, что имеет в виду под Абстрактными Типами Данных и объектами, и на первый взгляд это не выглядит особо интересным, потому что в современных языках программирования и то и другое воплощают обычно с помощью объектов. Но если его разграничение действительно улавливает некую существенную разницу между двумя естественными категориями - а я склонен с этим согласиться - то это все равно может оказаться интересным и полезным.

Абстрактный Тип Данных - это когда объявляется новый тип данных, доступ к которым возможен не через операторы языка, типа + или -, а исключительно через набор функций, которые обрабатывают скрытую репрезентацию этих данных. Самый естественный пример, на мой взгляд (не тот, что приводит Кук) - это BigInt. Опытные программисты наверняка встречались с имплементациями целых чисел неограниченной длины в разных языках. Обычно мы используем BigInt через некий API, который дает нам возможность создать такое число с обычным целым значением, делать с ними арифметические операции, печатать, вынимать значение по частям, итд. Функции, которые имлементируют этот API, опираются на какое-то внутреннее представление, например через массив целых чисел, но мы подробности этого представления не знаем и обычно знать не хотим.

В языке типа C такой АТД, как BigInt, скорее всего будет воплощен как структура и набор функций для манипуляции ее содержимым. Но в C++, Java итд. это будет класс, каждый объект которого будет конкретным большим числом: хранить внутри себя репрезентацию и давать возможность вызвать методы Add, Multiply, Create итд.

Обратите внимание на две важных особенности типичного АТД. Во-первых, функции, работающие с ATD, всегда имеют доступ к внутренней репрезентации, в том числе больше, чем у одного значения. Если я вызываю number1.Multiply(number2), то код метода Multiply может смотреть на внутреннюю репрезентацию как "своего" number1, так и "дополнительного" number2, и использовать их для эффективного умножения. Это так несмотря на то, что, казалось бы, number2 - другой объект. Во-вторых, функция Multiply обычно есть только одна, и я незаинтересован в том, чтобы их было много разных, работающих с разными репрезентациями. Даже если по какой-то причине мне надо использовать одновременно два разных пакета BigInt одновременно, я не могу ожидать, что number1.Multiply(number2) будет работать, если number1 и number2 принадлежат к разным АТД.

С другой стороны, что такое "объекты", по Куку? С его точки зрения, главной особенностью объектно-ориентированного программирования следует считать связку интерфейс-объект. Интерфейс - это набор деклараций функций с какой-то общей целью, а объект - это определенное воплощение всех этих функций, упакованное в общую оболочку, через которую это конкретное воплощение функций всегда можно вызвать. Для примера, в языке Go интерфейс Reader состоит из одной функции:

Read(p []byte) (n int, err error)

Во время работы программы на Go одновременно могут существовать множество объектов с разными имплементациями интерфейса Reader.

Файлы имплементируют функцию Read одним способом, буферы памяти другим, синхронизированные каналы третьим итд. итп. Переменная типа Reader может хранить объект файла или буфера или канала, и когда через нее вызовут Read(), исполнится правильный код. Для Кука это и есть главное в объектах, а, например, классы или наследование - это второстепенное и необязательное (в Go и нет классов, собственно).

Обратите внимание на полную противоположность ситуации с АТД, где была одна функция Multiply, которая имела доступ к внутренней репрезентации данных любого значения. Тут у нас есть полным-полно разных функций Read, и разные объекты не имеют доступа к "внутренней памяти" друг друга. Скажем, два объекта-файла не более родные друг другу, чем файл и буфер; все равно все, что они могут делать друг с другом, это вызывать Read(). "Внутренняя память" - скажем, дескриптор файла или положение в буфере - вообще неважна для Кука и не является частью объекта (хоть де-факто в популярных языках программирования это не так). Объект состоит из функций, которые на худой конец всегда можно сделать замыканиями, хранящими контекст и пристраивающими его к коду настоящей функции. Наглядным проявлением этого подхода является то, что интерфейс (в языках, где он явно определяется) состоит только из методов, а не из данных - в отличие от класса.

В языках типа C++/Java и АДТ и "объект" по Куку будут объектами, но типичное использование их будет совсем разным. АДТ можно отличить по тому, что их используют через классы, не через интерфейсы. Действительно, если представить на секунду, что BigInt был бы интерфейсом, а SpecificBigInt - конкретным классом-воплощением, то совершенно непонятно, как метод Multiply этого класса будет умножать SpecificBigInt на просто BigInt - у него нет доступа к внутренней репрезентации второго множителя (в некоторых языках техническую сложность воплощения класса можно решить с помощью механизма multiple dispatch, но фундаментальная проблема разных репрезентаций остается).

По Куку, наблюдается красивая дуальность: АТД и объекты реализуют разные способы "абстракции", т.е. как спрятать от себя конкретные детали программистской работы. В случае АТД мы прячем данные (во внутреннюю репрезентацию), но то, какая функция вызывается, остается известным и детерминированным. В случае объектов мы работаем с известными данными (теми, что передаем методам объектов - "внутренняя память" тут не считается, она деталь имплементации), но какая именно функция вызывается - неизвестно, в разных случаях разная. В 1970-х было несколько языков, которые давали прямой доступ к абстракции АТД, но потом взлет популярности объектов пресек эту тенденцию, и вместо этого АТД воплощают сегодня с помощью чего-то типа классов.

Меня эта дуальность не очень впечатляет. Разница между АТД и объектами в смысле Кука действительно есть и очень важна, но для того, чтобы уложить их в симметрично-дуальные ячейки, Кук нивелирует до состояния неважной детали данные, сидящие внутри объекта, а это противоречит тому, как программисты обычно думают об объектах. Скорее я бы сказал, что АТД являются важным частным примером абстракции, а объекты в смысле Кука - т.е. взаимозаменяемые воплощения интерфейсов, опирающиеся на внутренние данные, общие для всех функций данного объекта - являются намного более общим механизмом, краеугольным камнем современных сложных программ. Примерно то же говорит в своей статье Алдрич, и об этом - в следующей записи. Продолжение следует.

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

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

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

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

Даже больше того - глаза жестко разделены везде на левый и правый. Если будет субъект с двумя глазами, но вертикально расположенными, тоже не знаю, как мы с этим справимся.

Вот такая проблема.