Форум » Массивы, сортировка, работа с файлами » №4742 (26.67) Ошибка в алгоритме » Ответить

№4742 (26.67) Ошибка в алгоритме

beep: Здравствуйте! В задаче нужно найти продолжительность обработки минимального количества одновременных запросов в заданном окне. Вся задача сводится к тому, что в окне есть 5765 запросов, которые обрабатываются все окно, и нужно посчитать общее время таких моментов, когда нет дополнительных запросов. Предложенный в решении алгоритм не учитывает вариант, что некоторые запросы могут начинаться одновременно. Если такие запросы начинаются где-то внутри окна, то ничего страшного не происходит, потому что они только увеличивают счетчик. Но если эти запросы идут все окно и начинаются с левой границы (начало окна k), то тогда алгоритм дает сбой, потому что он высчитывает время работы между соседними началами запросов [pre] maxTime += abs(t) - abs(data[i-1]) [/pre] Соответственно нам нужно минимум 2 запроса, которые начинаются одновременно с левой границы и идут все окно. При первом запросе алгоритм инкрементирует счетчик и запоминает его значение в переменной prev, на втором запросе счетчик снова увеличивается и считается прошлый период времени (время между двумя началами), но поскольку начала находятся в одной точке (равны), то время работы будет равно нулю. А поскольку два запроса идут весь интервал, то счетчик никогда не будет меньше или равен найденному минимальному значению и время обработки запросов так и останется равно нулю. Проблема тут заключается в том, что данные представляются в дискретном виде и обрабатываются пошагово, когда на самом деле события происходят одновременно. Чтобы этого не происходило, нужно убеждаться не в том, что мы перешли от одной точки к другой, а в том, что мы сместились по времени от одного момента, к другому. Чтобы убедиться на практике в чем проблема и понять как это работает, достаточно расширить данные двумя отрезками [pre] data.extend([START, -END]) data.extend([START, -END]) [/pre] Алгоритм выдаст 5766 одновременных запросов обрабатываемых 0 мс, когда на самом деле их 5767 и обрабатываются они так же 22703 мс. Нужно либо группировать начала (и концы, что не обязательно, поскольку с правой стороны идет постоянное уменьшение и счетчик будет обновляться) отрезков, либо дополнительно проверять, что произошел сдвиг в пространстве и все одновременные события обработаны.

Ответов - 5

beep: Если в окне не будет ни одного запроса, который обрабатывается все окно, но и не будет момента, когда никаких запросов не обрабатывается вовсе, то могут возникнуть проблемы с правого конца. Например, на начало k обрабатывалось 3 запроса, в середине окна они одновременно завершаются и начинаются одновременно обрабатываться 4 запроса до конца окна. Тогда, во-первых, пока дискретно будет уменьшаться счетчик с 3 до 0, потеряется время работы этих 3 запросов и снова возьмется разность между двумя одинаковыми концами (в итоге будет 0 запросов 0 мс), а во-вторых, при сортировке по модулю нет гарантии, что вначале пойдут все концы (числа с минусом), а потом начала новых запросов (положительные числа). Они могут оказаться смешанными между собой, тогда счетчик может показать в моменте большее количество обрабатываемых запросов, чем есть или наоборот стать отрицательным. Как не посмотри, не лучший алгоритм предложен в решении. В соседней задаче с поиском максимума (66) вроде эти проблемы не проявляются из-за максимума, но все равно остается проблема сортировки одновременных концов и начал вызовов.

Поляков: Согласен с вашими доводами. Тут проблема, конечно, только в одновременности двух или нескольких событий. Изменил решение на такое: [pre2] 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 )[/pre2]

beep: Поляков, здравствуйте! Спасибо за ответ. Я не очень понимаю, почему Вы полагаетесь на сортировку из библиотеки, она же ненадежная для этой задачи. Например, у меня выходит следующее: [pre2] arr = [-1, 1, -1] arr.sort(key=abs) print(arr) #[-1, 1, -1] [/pre2] В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму. Еще непонятно, зачем Вы уменьшаете начала и продлеваете концы по границам окна: [pre2] if t0 == START: t0 -= 1 if t1 == END: t1 += 1 [/pre2] Если идет группировка вроде уже не обязательно формировать начальное значение счетчика до окна, потому что проверка счетчика будет после группировки точек. Опять же, если в задаче будут данные, где не будет ни одного интервала на все окно, то проблема "одномоментности" отрезков встретится внутри окна и первый вариант алгоритма не справится, а во втором варианте эти начала вначале сгруппируются, а уже потом будут проверяться. Тут только вопрос к сортировке, при сортировке по модулю вполне могут смешаться между собой "начала" и "концы" вместо того, чтобы последовательно вначале были концы старых отрезков, а потом начала новых отрезков.


Поляков: beep пишет: В таком случае алгоритм промахнется с chunks и не сгруппирует до конца правильно все начала и концы, соответственно, будет неправильно определено их количество, что может привести к неправильному минимуму или максимуму. Приведите пример, пожалуйста. Если идет группировка вроде уже не обязательно формировать начальное значение счетчика до окна Согласен.

beep: Поляков, извините, пожалуйста, моя невнимательность. Я не заметил, что Вы группируете в чанки по модулю, поэтому и последовательность неважна. Я идеи из старого алгоритма, где отдельно начала и концы перенес на новый, а тут уже просто узловые точки идут. Вопрос снимается, спасибо за ответы!



полная версия страницы