Автор | Сообщение |
|
Отправлено: 16.04.22 17:38. Заголовок: №4742 (26.67) Ошибка в алгоритме
Здравствуйте! В задаче нужно найти продолжительность обработки минимального количества одновременных запросов в заданном окне. Вся задача сводится к тому, что в окне есть 5765 запросов, которые обрабатываются все окно, и нужно посчитать общее время таких моментов, когда нет дополнительных запросов. Предложенный в решении алгоритм не учитывает вариант, что некоторые запросы могут начинаться одновременно. Если такие запросы начинаются где-то внутри окна, то ничего страшного не происходит, потому что они только увеличивают счетчик. Но если эти запросы идут все окно и начинаются с левой границы (начало окна k), то тогда алгоритм дает сбой, потому что он высчитывает время работы между соседними началами запросов maxTime += abs(t) - abs(data[i-1]) Соответственно нам нужно минимум 2 запроса, которые начинаются одновременно с левой границы и идут все окно. При первом запросе алгоритм инкрементирует счетчик и запоминает его значение в переменной prev, на втором запросе счетчик снова увеличивается и считается прошлый период времени (время между двумя началами), но поскольку начала находятся в одной точке (равны), то время работы будет равно нулю. А поскольку два запроса идут весь интервал, то счетчик никогда не будет меньше или равен найденному минимальному значению и время обработки запросов так и останется равно нулю. Проблема тут заключается в том, что данные представляются в дискретном виде и обрабатываются пошагово, когда на самом деле события происходят одновременно. Чтобы этого не происходило, нужно убеждаться не в том, что мы перешли от одной точки к другой, а в том, что мы сместились по времени от одного момента, к другому. Чтобы убедиться на практике в чем проблема и понять как это работает, достаточно расширить данные двумя отрезками data.extend([START, -END]) data.extend([START, -END]) Алгоритм выдаст 5766 одновременных запросов обрабатываемых 0 мс, когда на самом деле их 5767 и обрабатываются они так же 22703 мс. Нужно либо группировать начала (и концы, что не обязательно, поскольку с правой стороны идет постоянное уменьшение и счетчик будет обновляться) отрезков, либо дополнительно проверять, что произошел сдвиг в пространстве и все одновременные события обработаны.
| |
|
Ответов - 5
[только новые]
|
|
|
Отправлено: 16.04.22 18:23. Заголовок: Если в окне не будет..
Если в окне не будет ни одного запроса, который обрабатывается все окно, но и не будет момента, когда никаких запросов не обрабатывается вовсе, то могут возникнуть проблемы с правого конца. Например, на начало k обрабатывалось 3 запроса, в середине окна они одновременно завершаются и начинаются одновременно обрабатываться 4 запроса до конца окна. Тогда, во-первых, пока дискретно будет уменьшаться счетчик с 3 до 0, потеряется время работы этих 3 запросов и снова возьмется разность между двумя одинаковыми концами (в итоге будет 0 запросов 0 мс), а во-вторых, при сортировке по модулю нет гарантии, что вначале пойдут все концы (числа с минусом), а потом начала новых запросов (положительные числа). Они могут оказаться смешанными между собой, тогда счетчик может показать в моменте большее количество обрабатываемых запросов, чем есть или наоборот стать отрицательным. Как не посмотри, не лучший алгоритм предложен в решении. В соседней задаче с поиском максимума (66) вроде эти проблемы не проявляются из-за максимума, но все равно остается проблема сортировки одновременных концов и начал вызовов.
| |
|
|
| Администратор
|
Сообщение: 3480
|
|
Отправлено: 16.04.22 20:34. Заголовок: Согласен с вашими до..
Согласен с вашими доводами. Тут проблема, конечно, только в одновременности двух или нескольких событий. Изменил решение на такое: with open('26-66.txt') as f: N, START = map(int, f.readline().split()) END = START + 24*3600*1000 data = [] for i in range(N): t0, t1 = map(int, f.readline().split()) if t0 == START: t0 -= 1 if t1 == END: t1 += 1 if t1 == 0: t1 = 10**10 data.extend( [t0, -t1] ) data.extend( [START, -START] ) # учесть первый интервал data.append( END ) # учесть последний интервал data.sort( key = abs ) nProc = 0 allChunks = [] for i, t in enumerate(data): nProc += 1 if t >= 0 else -1 if START <= abs(t) <= END: if allChunks and allChunks[-1][1] == abs(t): allChunks.pop() allChunks.append( (nProc, abs(t)) ) minProc, maxTime = 10**10, 0 for i in range(len(allChunks)-1): nProc, t = allChunks[ i] if nProc < minProc: minProc = nProc maxTime = 0 if nProc == minProc: maxTime += allChunks[i+1][1] - t print( minProc, maxTime )
| |
|
|
Отправлено: 19.04.22 20:24. Заголовок: Поляков, здравствуйт..
Поляков, здравствуйте! Спасибо за ответ. Я не очень понимаю, почему Вы полагаетесь на сортировку из библиотеки, она же ненадежная для этой задачи. Например, у меня выходит следующее: arr = [-1, 1, -1] arr.sort(key=abs) print(arr) #[-1, 1, -1] В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму. Еще непонятно, зачем Вы уменьшаете начала и продлеваете концы по границам окна: if t0 == START: t0 -= 1 if t1 == END: t1 += 1 Если идет группировка вроде уже не обязательно формировать начальное значение счетчика до окна, потому что проверка счетчика будет после группировки точек. Опять же, если в задаче будут данные, где не будет ни одного интервала на все окно, то проблема "одномоментности" отрезков встретится внутри окна и первый вариант алгоритма не справится, а во втором варианте эти начала вначале сгруппируются, а уже потом будут проверяться. Тут только вопрос к сортировке, при сортировке по модулю вполне могут смешаться между собой "начала" и "концы" вместо того, чтобы последовательно вначале были концы старых отрезков, а потом начала новых отрезков.
| |
|
|
| Администратор
|
Сообщение: 3493
|
|
Отправлено: 20.04.22 12:24. Заголовок: beep пишет: В таком ..
beep пишет: цитата: | В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму. |
|
Приведите пример, пожалуйста. цитата: | Если идет группировка вроде уже не обязательно формировать начальное значение счетчика до окна |
|
Согласен.
| |
|
|
Отправлено: 21.04.22 14:41. Заголовок: Поляков, извините, м..
Поляков, извините, пожалуйста, моя невнимательность. Я не заметил, что Вы группируете в чанки по модулю, поэтому и последовательность неважна. Я идеи из старого алгоритма, где отдельно начала и концы перенес на новый, а тут уже просто узловые точки идут. Вопрос снимается, спасибо за ответы!
| |
|
|
|