Фото в шестнадцати красках
Видеокарта EGA показывала одновременно шестнадцать цветов. Чтобы вывести на такой экран фотографию, каждый её пиксель заменяют ближайшим цветом палитры, а потом смотрят, какие цвета понадобились и сколько. Так же переводят снимок в 216 «безопасных» цветов ранних браузеров или в краски, которые есть у печатника.
Цвет — три числа (r, g, b) от 0 до 255. Расстояние между цветами — квадрат обычного расстояния: (r1 − r2)2 + (g1 − g2)2 + (b1 − b2)2. Каждый пиксель достаётся ближайшему цвету палитры, а если ближайших несколько — тому из них, что стоит в палитре раньше. Сколько пикселей досталось каждому цвету? В тестах есть фотографии автора сайта, в том числе «Вода и горы» из статьи о векторизации.
Вход
В первой строке число цветов палитры m (1 ≤ m ≤ 256), во второй — сами цвета. Цвет записан шестью шестнадцатеричными цифрами rrggbb, строчными, как в CSS без решётки. В палитре цвета могут повторяться. Дальше ширина W и высота H снимка (W·H ≤ 2·105) и H строк по W цветов пикселей в той же записи.
Выход
m чисел через пробел: сколько пикселей досталось каждому цвету, в порядке палитры.
Примеры
Пример 1
3 202020 e0e0e0 ff0000 3 2 101010 f0f0f0 c01010 808080 7f7f7f ff8080
3 2 1
Пример 2
2 ffffff 000000 2 2 000000 404040 c0c0c0 ffffff
2 2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитайте работу: фотография — 183 тысячи пикселей, палитра — до 256 цветов, каждый пиксель сравнивается с каждым цветом. Сколько это проходов цикла Python? А если вместо цикла по пикселям и цветам считать целую таблицу «пиксель × цвет» сразу?
2Подсказка 2
Разложите квадрат расстояния: (p − c)2 = p2 − 2p·c + c2. Какая часть не зависит от цвета, а какая — от пикселя? И как посчитать все произведения p·c одной операцией?
3Идея
Векторизация по пикселям и по цветам сразу. Для каждого пикселя ближайший цвет — тот, у которого |c|2 − 2p·c наименьшее: слагаемое |p|2 одно на всю строку таблицы и выбора не меняет. Все скалярные произведения пикселей на цвета — одно умножение матриц pixels @ palette.T, ближайший цвет каждой строки — argmin, а подсчёт — np.bincount, та же гистограмма, что в статье.
4Разбор
Разбор входа — тоже целыми массивами: все пиксели склеиваются в одну шестнадцатеричную строку, bytes.fromhex превращает её в байты, а np.frombuffer — в массив N × 3. Перед вычислениями тип нужно поменять на int32.
Таблица на все пиксели сразу не нужна, и с 216 цветами она уже тяжела: 183 тысячи × 216 чисел — 158 мегабайт в int32, а рядом ещё временные массивы. Поэтому пиксели идут кусками по четыре тысячи: таблица куска — три с половиной мегабайта, а куски обрабатываются тем же векторным кодом. Накладные расходы на 45 вызовов numpy ничтожны по сравнению с работой внутри.
Ничья решается сама: argmin возвращает первый из равных минимумов, то есть цвет, стоящий в палитре раньше. Так в первом примере серый 808080, который отстоит ровно на 96 по каждому каналу от 202020 и от e0e0e0, достаётся первому из них, а повторы цвета в палитре — первой копии.
На Go векторизовать незачем: двойной цикл по пикселям и цветам — 40 миллионов сравнений — занимает десятые доли секунды.
4+Решение
5Сложность
O(N·m) при любом способе, где N = W·H. Цикл Python на фотографии с 216 цветами работает около 12 секунд, numpy — около трети секунды вместе с разбором входа и загрузкой библиотеки. Память у векторного решения — O(N + куска × m).
6Типичные ошибки
- Цикл по пикселям и цветам. Это
wrong.py. С шестнадцатью цветами он ещё укладывается во время — 0,9 секунды, — а с палитрой из 216 цветов работает около 12 секунд. - Трёхмерная разность. Очевидная векторная запись
((pixels[:, None, :] - palette[None, :, :]) ** 2).sum(axis=2)строит массив N × m × 3. Вint64для палитры из 64 цветов это 268 мегабайт, и программа падает сMemoryErrorпри ограничении в 256; для 216 цветов — почти гигабайт. Векторизация не бесплатна: каждый промежуточный массив целиком лежит в памяти. - Вычитание в
uint8. Если не перевести байты в целый тип со знаком, разность заворачивается по модулю 256: 10 − 20 даёт 246, и ближайшим окажется не тот цвет. - Ничья в свою пользу. Сравнение «≤» вместо «<» в цикле выбирает последний из ближайших цветов, а нужен первый — первый пример это ловит.