mq
на примере сплея как раз и сегмент три битс
Size: a a a
2020 May 22
mq
Я не спорю с тем, что у сплея хорошая верхняя граница. Но она не лучше времени работы асимптотики декартача.
да прелесть сплея не в том, что у него обычный лог в асимптотике
mq
а в том что на самом деле там можно доказать при разумных предположениях что оно будет работать быстрее лога
mq
если у тебя хороший паттерн доступа
mq
а в самом худшем случае будет лог амортизированный
MB
а в том что на самом деле там можно доказать при разумных предположениях что оно будет работать быстрее лога
Я написал
> То, что сплей может работать за O(N)
Ты написал
> так он не может работать за О(н)
Почему-то аргументируя это тем, что
> там амортайзд лог
А теперь сам убеждаешь меня в том, что сплей может работать за O(N) при удачных паттернах доступа.
....
А, я понял. В исходном утвеждении я имел в виду O(N) суммарно, а не на один запрос. А ты проинтепретировал это как "O(N) на запрос"
> То, что сплей может работать за O(N)
Ты написал
> так он не может работать за О(н)
Почему-то аргументируя это тем, что
> там амортайзд лог
А теперь сам убеждаешь меня в том, что сплей может работать за O(N) при удачных паттернах доступа.
....
А, я понял. В исходном утвеждении я имел в виду O(N) суммарно, а не на один запрос. А ты проинтепретировал это как "O(N) на запрос"
mq
да
mq
ну и собственно вопрос почему сплеи никто почти не использует если они такие классные
K
типа против него контртестов не придумать, как против декартача
а как против декартача контртесты находить?
K
атака на сид?
mq
а как против декартача контртесты находить?
я не очень силен в взломе рандома, но люди умеют
K
я не очень силен в взломе рандома, но люди умеют
это какой-то кодефорс-специфик, что ли?
mq
это какой-то кодефорс-специфик, что ли?
да
MB
Против __rdtsc и прочих high-resolution clocks приема нет
mq
настолько умеют что если пишешь анордеред мап в контесте то ты пососешь почти наверное
AD
ну и собственно вопрос почему сплеи никто почти не использует если они такие классные
1. неплохо бы разобраться, как работает, но лень
2. надо написать много кода, чтоб его потом пастить в решение, но лень
3. декартовое явно проще как для понимания, так и для написания
2. надо написать много кода, чтоб его потом пастить в решение, но лень
3. декартовое явно проще как для понимания, так и для написания
K
Против __rdtsc и прочих high-resolution clocks приема нет
ага, только хотел написать
new Random(System.currentTimeMillis())
new Random(System.currentTimeMillis())
K
настолько умеют что если пишешь анордеред мап в контесте то ты пососешь почти наверное
может, брутфорсят?
mq
1. неплохо бы разобраться, как работает, но лень
2. надо написать много кода, чтоб его потом пастить в решение, но лень
3. декартовое явно проще как для понимания, так и для написания
2. надо написать много кода, чтоб его потом пастить в решение, но лень
3. декартовое явно проще как для понимания, так и для написания
мне сейчас интересно just for giggles сдать сплеем задачу где авторы намеренно отсекали декартач
mq
может, брутфорсят?
не думаю