mayton2019

Тебе нужна функция цветовой дистанции между двумя цветами. Типа

double getDistance(int rgb1, int rgb2) {
    ....
}

Формула будет похожа на взвешенную сумму цвета как ты писал выше. Только в цветах
нужны будут разности r1 - r2 e.t.c. И взять декартово расстояние.

Она будет возрващать от 0 до некоторого максимального вещественного. Если 0 - то цвета идентичны.

Задаешь порог чувствительности например 5% и если цвета rgb1 и rgb2 близки - то соотв. считаешь
что совпадение было. Сравнивать по знаку == цвета нельзя в фотографиях. Там очень редко
бывает численное совпадение. Практически - никогда не бывает.

Тебе не нужно сортировать все 10 000 000 элементов чтоб взять два минимальных. Достаточно одного прохода
с отслеживанием двух наименьших {m1,m2} . И кейсов сравнений будет немного. Новый элемент больше - игнорируем. Новый элемент меньше обоих - вставляем в голову. Новый между ними - вставляем в центр.

Тут все биты - перевернуты.
На псевдокоде как-то так.

int a = 0b0010_1101;
for(i in (1..8)) {
 b |= a & 0b0000_0001
 b <<= 1;
}

Я-бы предложил для начала уйти от этого странного способа описанию деревьев к инверсному списку
По сути - добавить еще одну колонку которая указывает на родителя.

id name     path  parent
-----------------------
1  Беларусь 1     null
2  Россия   2     null
3  Минск    1.3   1
4  Москва   2.4   2
5  СПБ      2.5   2
6  Невский  2.5.6 5

Ну а дальше - select... connect prior и получим ранжированый курсор по дереву. Там-же будет
доступно виртуальное поле level. И обходом этого курсора можно сделать JSON документ.
Если level растет - то увеличиваем indentation и открываем вложенный элемент соотв.

Если go-lang поддерживает stremable json writers то даже лучше.

Здесь правда подходит любой алгоритм генерации лабиринтов с одним условием. Беря во внимание полярные координаты, ширина проходов в центральной части лабиринта должна быть примерно соизмерима с шириной проходов у края круга. Этого нельзя добиться просто заменив один прямоугольник на боковую поверхность цилиндра (бублика). Нужна коррекция. Корреция с учотом дистанции к центру этого бублика.

Это мне кажется интересная часть задачи которую можно обсудить. Остальное - уже решено.

Мне кажется шахматисты-теоретики давно расковыряли коня со всех сторон. DFS/BFS - это игра вслепую.
А может быть есть некий сет стратегий которые ведут к победе. Например.
- один конь делает нейтральные шаги туда-сюда.
- второй конь целенаправленно двигается к этим двум шагам.
- если промахнулся и не встретил - делает 3 или 5 тоже нейтральных шагов по кругу чтобы на нечетности поймать другого коня.

UPD.

Я никогда не слышал чтоб кто-то читал чистые алгоритмы. Обычно программа более конкретная. Например алгоритмы игровой логики. Алгоритмы маш-обучения. Обобщенные алгоритмы какого-то языка (C++) etc.

Чистые алгоритмы - это Кнут, Кормен. Короче сферическая лошадь в космосе.

Линейная зависимость. Бери некий box, который ограничиает карточки. Его размеры - это экран минус margins.
И внутри этого бокса надо разложить карточки с одинаковым шагом. Беря во внимание что карточка тоже имеет
размер - вычитаем ширину карточки из ширины бокса. Также с высотой. Оставшееся - делим на 4 и получаем шаг.

Я-бы строил граф. Тогда задача сводится к поиску пар верин имеющих 4х одинаковых соседей.

Впрочем такое ограничение как 10 url дает возможность отобразить граф на матрицу. Хотя чисто эстетически мне граф кажется более наглядным и общим.

Ваше решение O(ln(n)) - это очень хорошее решение. Пускай оно и будет.

Для других оптимизаций нужно строить дополнительные структуры данных. Например хеш таблица которая режет пространство отрезков на линейную последовательность равных кусков и для каждого куска хранит просто список ваших отрезков. Будет некоторая избыточность зато у вас есть почти O(1) и есть механика плавного регулятора. Тоесть вы можете балансировать сколько вам отдать памяти под хеш таблицу и сделать результат более точным. Или наоборот сэкономить но сделать чуть-чуть O(n). Мне почему-то фантазия подсказывает какие-то золотые сечения и теорему Котельникова ... ну вобщем у вас есть широкое пространство для творчества.

Данный вопрос безсмысенно обсуждать только в разделе АЛГОРИТМЫ.

Дело в том что в каждом языке программирования есть своя реализация хеш-таблиц со своими преференциями.
Например в Java создается по умолчанию пустая табличка с 16 buckets и с фактором загрузки 0.75.

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

Для случая автора число 42. Мы считаем остаток от деления на 16 это будет 10. Тоесть мы запишем в 10 бакет. А после того как в табличку зайдет большое число ключей и и соотношение ключей и емкости станет больше чем 0.75 - будет создана новая таблица с 32 бакетами и старые данные будут скопированы туда с реогранизацией ключей. Это тяжеловатая процедура поэтому изначально хеш-таблицу рекомендуется создавать уже с заранее известным capacity. Если хотите хранить 6 млрд социальных номеров людей планеты земля - то создавайте соотв такую таблицу. Тогда реорганизации не будет. И load factor можно сделать близким к 1.0.

(Старая таблица с 16 бакетами после этой процедуры будет уничтожена)

В данном случае нам повезло что есть линейная зависимость между номером отрезка и числом. Но бывают более ужасные случаи когда длины отрезков отличаются на много порядков (типичная ситуация для geo-spatial запросов) и тогда строят специальные структуры данныех которые делят пространство на прямоугольники (для 2д случая) такие как Q-Tree , R-Tree и далее ищут рекурсивным спуском по таким деревьям. Для одномерного случая (отрезки) алгоритм будет - тот-же самый. Только вместо прямоугольников другие отрезки или точки которые делят пространство. Эвристика будет лишь в выборе самого алгоритма.

Суть вопроса - алгоритм факторизации.

Чтобы ускорить факторизацию есть много путей. Во первых - отказаться от языка Python в пользу C++ или Rust.

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

И step надо делать не по 1 элементу а по нечётным начиная с 3.

Есть ещё алгоритм Эратосфена. Обрати внимание.

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

Нет никакого смысла страховать Кафку. Она совершенно самодостаточна. Есть настройка message delivery semantics. Почитай про нее. Вобщем идея такава что - каждый сам себе в зависимости от бизнес требований выставляет такие параноидальные настройки producer/consumer, чтобы было и быстро и надёжно одновременно.

Для расчета среднего нам нужна сумма элементов и количество. Количество - это константа.

Сумма конечно меняется. Но если у нас уже есть расчитанная сумма от 1 000 000 элементов то
следующее скользящее среднее будет не сильно отличаться. Нужно от сумма забрать первый элемент
и добавить элемент с индексом 1 000 001. Это и есть оптимизация.

Тоесть первая итерация расчитывается полностью. Следующая - на основании предыдущей. Как в численных
методах.

Скорее всего - никак. Информатика (и вычислительная техника) это все практические науки. Их надо изучать параллельно делая что-то руками. Все что вы перечислили. Теория игр. Криптография. Должно быть подкреплено реальным проектом где это используется.

В противном случае - эти знания бесполезны и забудуться. Это я по себе говорю. Такой мой опыт.

Отвечу на первую часть вопроса

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

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

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

Короче клеточный автомат имеет свойства которые невыводимы из начальной конфигурации в общем случае.

В частных случаях например когда вы знаете что такое глайдер и куда он полетит - то пожалуй можно. Но таких случаев будет мало.

Нерешенные вопросы:
1) Поле бесконечное? Как быть с конечными ресурсами оперативной памяти?
2) Поле конечное? Уничтожаем клетки (глайдеры) которые вылетают за границу поля?
3) Поле завернутое в тор (бублик)? Будем ли считать линейные трансформации поля - эквивалентными к исходному?

Данные вопросы вобщем-то тоже влияют на проблему завершения жизни Конвея.

По поводу идеи автора с удвоением времени. Может не сработать если период повтора не будет кратен двойке.
По сути надо не сравнивать x и 2x эпоху. А записывать в базу данных все x - 1 эпох и проверять все-с-последней.
Но такая сверх-задача невыполнима например с растущим бесконечным полем.

Вторая часть вопроса не так интересна. Ее можно задать отдельным вопросом в habr.

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

days(currentDate() - date('0001-01-01'))

Далее - четность-нечетность.

Тоесть от Рождества Христова до текущего дня. Вот такая вот декомпозиция задачи на простые функции.
А автору - жирный минус за то что он не может нормально постановку сделать. Какая-то гумнанитращина.
Нельзя-же так! Инженер должен уметь владеть языком функций.

И еще забыл указать какую футболку он одевает в условно первый день.

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

Немного бухгалтерии. Если взять по максимуму.

Размер одной записи должен быть порядка 60 + 32 +8 = 100 символов (байт для простоты)

При 50 млрд записей объем хранимых данных должен быть порядка

50 000 000 000 * 100 = 5 000 000 000 000 = 5 триллионов байт.

В дисковом хранении это будет примерно 4.5 терабайта. Задачка для in-memory неподъемная. Нужен диск + мемори.

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

Вобщем нужна дисковая БД которая встраивается в приложение. На требование менеджеров которые запретили использовать БД забейте. Они ничего не понимают. Делайте БД встраиваемую в приложение. В качестве таких (встраиваемых систем можно поробовать) LevelDb, BerkeleyDb, RocksDb. Они поддерживают индекс класса B+Tree и это даст возможность искать группы записей по одному ID. Для этого класса систем любую запись можно найти за 4-5 дисковых IOPS. Если какдый IOPS стоит 15 мс (это я так мерял свой собственный магнитный HDD) то любой поиск группы ключей для TTFB будет порядка 15 * 5 = 75 милисекунд. Ну если вы поставите SSD - то быстрее.

По поводу предложений хранить в файлах. До того как обсуждать это - надо уяснить требования по времени отклика. Сколько секунд вы согласны ждать - насколько можно и партицировать (или шардировать ваш файл).
В простейшем случае мы делим большой CSV файл на 512 partitions по хешу от ID и получаем соотв время фулл-скана всего файла поделенное на 512. Дальше - играйтесь с этим параметром партишенинга выводя его на доступный уровень отклика. Из недостатков - будет россыпь файлов. Надо почиать документацию на вашу файловую систему (ext4?) и тюнить ее так чтоб она не сдохла от такого числа inodes.

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

По поводу Parquet. Не взлетит. Скорее всего индекс по данному типу файла - это совсем не то что вкладывают туда релационные системы. Обычно Parquet/Orc/Delta вкладывают в индекс смысл - отбрасывания тех полосок данных (stripes) которые бесполезны при чтении всего файла. Такой индес - обычно просто либо range-признак либо карта Блума. И в случае с range - дает эффект на сортированных данных. Для прочих - будет бесполезно т.к. фулл-скан все равно обеспечен. А если фулл-скан то зачем тогда вообще индекс.

Вобщем для дизайна архитектуры нам нужны цифры. Средние длины по колонкам. И я-бы еще запросил кардинальность по полю ID.