29 апреля 2026
Анатолийтекст ещё не в индексе
Лучше другой инвариант, topK подходящих на каждый запрос, это лучше чем отдать нерелевантных
Egor ChistiakovВопрос не продуктовый а алгоритмический
я к тому что топ к это не оптимизация а и так ясно
Arsenhttps://t.me/l33tcode/531627
Ссылка
нажмите — покажем
нажмите — покажем
Задайте уточняющие вопросы ) я попытался формализовать https://t.me/l33tcode/531599
Egor ChistiakovЗадайте уточняющие вопросы ) я попытался формализовать https://t.me/l33tcode/531599
Если серьезно, могу только попробовать пример описать чуть лучше
Допустим дейтинг
В памяти мапа 10^6 структур Person
У каждой набор из 4 полей
Name, HairColor(Enum{Blond, Black, Ginger}, Age(int), Sex(Enum){Male, Female}
Приходит сразу пачка из 100 запросов с произвольным набором предикатов но в пределах 4 полей
Example
Name=any, HairColor=Ginger, Age=32;
Sex=Male, age>=100;
Надо в результате вернуть map reuest->[]answers где лежит до 100 подходящих записей если они есть
—-
Если обрабатывать каждый запрос по одному то все понятно, но в сумме сложность все равно получится Q*A*P
Можно ли как-то сделать это быстрее если не строить heap на каждый запрос в батче?
30 апреля 2026
Dimaтекст ещё не в индексе
Heapsort — O(n log n) tc, O(1) sc
Результат сам по себе не считается, но если его абузить под промеужточные вычисления — спорно; я такое стараюсь комментировать :-)
Ещё есть задачки, в которых надо возвратить результат in-place
Egor ChistiakovЕсли серьезно, могу только попробовать пример описать чуть лучше
Допустим дейтинг
В памяти мапа 10^6 структур Person
У каждой набор из 4 полей
Name, HairColor(Enum{Blond, Black, Ginger}, Age(int), Sex(Enum){Male, Female}
Приходит сразу пачка из 100 запросов с произвольным набором предикатов но
по сайтам знакомств из личного опыта могу сказать, что часто встречал кеширование поисковых запросов, ты первые 100 выдаешь поиском, но он на самом деле сразу ищет больше потом уже выдаешь закешированные результаты!
Egor ChistiakovЕсли серьезно, могу только попробовать пример описать чуть лучше
Допустим дейтинг
В памяти мапа 10^6 структур Person
У каждой набор из 4 полей
Name, HairColor(Enum{Blond, Black, Ginger}, Age(int), Sex(Enum){Male, Female}
Приходит сразу пачка из 100 запросов с произвольным набором предикатов но
Самое реалистичное это btree индексы для inmemory db с TC: O(q * loga) для запроса в примере (HairColor, Sex, Age) include (name) тогда будет index only scan
Наверное из нереалистичного супер оптимизированного можно сделать 2 шарда для sex (если мы в непрогрессивной стране, в прогрессивной можно сделать 3 шарда), в каждом шарде партицирование по age и hash индекс по волосам. Тогда можно будет пробежаться только по партиции нужного age проверяя в индексе волосы. Сложность будет O(q) нам нужно просто собрать ответ будет
завтрашний дейлик https://leetcode.com/problems/rotate-function
class Solution:
def maxRotateFunction(self, a: List[int]) -> int:
s=sum(a);f=sum(map(mul,a,count()));return max(f,*(f:=f+s-v*len(a)for v in a[::-1]))
Egor ChistiakovЕсли серьезно, могу только попробовать пример описать чуть лучше
Допустим дейтинг
В памяти мапа 10^6 структур Person
У каждой набор из 4 полей
Name, HairColor(Enum{Blond, Black, Ginger}, Age(int), Sex(Enum){Male, Female}
Приходит сразу пачка из 100 запросов с произвольным набором предикатов но
Сделать это в inMemory базе, хоть в sqlite, построить там индексы по HairColor, Age,
Sex, name и всем комбинациям их наличия в запросе (это 16 штук вроде)
Sql запрос с where HairColor=Ginger, Age=32;
Sex=Male, age>=100 limit 100 выдаст при наличии HairColor, Age,Sex, индекса список за миллисекунды