mayton2019

Линейная зависимость. Бери некий 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.

Дело в том что HSV - это полярная система коррдинат. Цилиндр по сути. И один из параметров цветового тона (угол вращения) может циклически повторяться неся одинаковый смысл. И может быть любым находясь в центре цилиндра.

Поэтому такая формула не будет никогда однозначной.

Игнорируй младшие коэффициенты - вот и будет сжатие. Так оно и работает. Честно-честно.

Я обычно оцениваю на глазок просто мысленно предполагая что данных очень много.
Например строка длиной 2 млрд символов.
В этом случае 3 линейных поиска по ней (indexOf) дадут нам формулу

O(n)

Это в негативном сценарии когда мы не нашли скобочек трех типов.

Но в позитивном сценарии если мы нашли - начинает работать еще более хардкорная логика
реплейсмента которая ... ну я не знаю как работает. replace(..) которая под капотом тоже имеет
свою complexity. Наверное тоже линейную если стоит билдер строк. Получается что линейная вложена
в другую линейную. Получается квадратичная.

o(n^2)

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

Линейная регрессия.

Коробочное решение - это библиотеки обработки текста Apache Lucene, Sphinx. Но их нужно программировать - следовательно вам надо искать разработчика.

ElasticSearch/Solr (под капотом это тот-же Lucene) - вариант но вам надо будет его конфигурировать и тщательно подбирать настройки Analyzer чтоб не получать ложно-позитивных срабатываний. Возможно в дефолтном варианте он слишком умный и делает стемминг там где не надо.

Если самостоятельно программировать то мы имеем такую complexity : 100 000 слов проверить в 150 текстах - это примерно 15 миллиардов тривиальных проверок. Типа поиска строки в строке. Хочется от этого уйти. Поэтому надо искать какие-то структуры данных работающие на exists(..). Например Фильтры Блума. При 150 тыщ элементов он будет достаточно компактен. Или сортирующие и хеширующие структуры (R&B Trees). Тогда вместо 15 млрд мы сведем к 100 либо к 150 тыс циклов по одному из измерений как будет выбрано.

Какое-то время я посвятил играм с простыми числами. В студенчестве еще.
Вот тут не надо каждый раз прибавлять единичку.
if (K % (i + 1) == 0) {
Ее просто надо учесть в условиях цикла.
if (K % i == 0) {
Далее. Если нужно найти первый попавшийся делитель - то не надо перебирать все числа. Достаточно только 2 и все нечетные. Или даже лучше задать хард-кодом таблицу простых чисел до 2^16. Это как раз будет половина разрядной сетки int32.
int primes[] = { 2,3,5,7,11,13,17...... 65521 }
Это даст хорошее ускорение для поиска. Хотя время загрузки executable может увеличится. Кстати у меня много вопросов к бенчмаркам где стоит запредельно короткое время инициализации (0.25 s). Здесь - практически невозможно вычленить где время занимает алгоритм а где - просто запуск процесса операционки. Обычно когда меряют что-то подобное - меряют длительные процессы хотя-бы порядка минут но никак не секунд.