Прикольная алгоритмическая задача, которая пригодится на собеседования кандидатов или для вящего удовольствия.
В базе данных есть заранее неизвестное количество контрагентов.
К базе можно выполнять только один вид запроса: спросить сколько контрагентов находится в выдаче на странице номер N.
При этом на странице выдается по 25 контрагентов и контрагенты всегда упорядочены одинаково. На последней странице может быть меньше контрагентов.
К запросу можно выполнить только одно действие: удалить контрагентов, выданных на странице.
При этом будут удалены только те контрагенты, по которым в базе не проходит никаких операций.
Вопрос: Как оптимально выполнить удаление всех контрагентов, которых можно удалить.
В базе данных есть заранее неизвестное количество контрагентов.
К базе можно выполнять только один вид запроса: спросить сколько контрагентов находится в выдаче на странице номер N.
При этом на странице выдается по 25 контрагентов и контрагенты всегда упорядочены одинаково. На последней странице может быть меньше контрагентов.
К запросу можно выполнить только одно действие: удалить контрагентов, выданных на странице.
При этом будут удалены только те контрагенты, по которым в базе не проходит никаких операций.
Вопрос: Как оптимально выполнить удаление всех контрагентов, которых можно удалить.
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
А во время удаления изменение состава контрагентов другими процессами возможно?
Если нет, то определить максимальную страницу - где N <= 25. Например начав с 1, далее увеличивая номер страницы в два раза, если N = 25. Дошли до предела - N = 0, половинным делением пошагово определили правильный предельный номер страницы.
Далее постранично с конца удаляем.
Если нет, то определить максимальную страницу - где N <= 25. Например начав с 1, далее увеличивая номер страницы в два раза, если N = 25. Дошли до предела - N = 0, половинным делением пошагово определили правильный предельный номер страницы.
Далее постранично с конца удаляем.
(7) нет.
зачем искать последнюю страницу, если можно начинать с первой и удалять-удалять, пока в ноль не выйдешь. но не первую удалять, а первую, вторую, третью.
Если только первую удалять есть риск, что никогда не закончится, если количество контрагентов, которых нельзя удалить больше 25.
зачем искать последнюю страницу, если можно начинать с первой и удалять-удалять, пока в ноль не выйдешь. но не первую удалять, а первую, вторую, третью.
Если только первую удалять есть риск, что никогда не закончится, если количество контрагентов, которых нельзя удалить больше 25.
(12) Насколько я понял из условия задачи, в процесс удаления мы никак вмешаться не можем и можем лишь получить некий результат.
В случае, когда на первой странице удалилось 5 из 25, то следующая итерация запроса данных первой страницы будет содержать "новые" 25 значений, среди которых будут содержаться "предыдущие" 20 неудаленных значений.
По условию задачи, не понятно, нужно проверять такой момент или нет, поэтому повторяем итерацию удаления для всех 25 значений и запрашиваем содержимое первой страницы и так пока не удалим все. Если есть задача еще и контролировать то, что мы пытались удалить, но оно по факту не удалилось, то в таком случае да, придется проверять страницы по порядку, сверяя содержимое N-ой страницы с уже обработанными элементами.
В случае, когда на первой странице удалилось 5 из 25, то следующая итерация запроса данных первой страницы будет содержать "новые" 25 значений, среди которых будут содержаться "предыдущие" 20 неудаленных значений.
По условию задачи, не понятно, нужно проверять такой момент или нет, поэтому повторяем итерацию удаления для всех 25 значений и запрашиваем содержимое первой страницы и так пока не удалим все. Если есть задача еще и контролировать то, что мы пытались удалить, но оно по факту не удалилось, то в таком случае да, придется проверять страницы по порядку, сверяя содержимое N-ой страницы с уже обработанными элементами.
(12) не придется. ты состав все равно не получаешь, ты получаешь, есть там товары или нет, ну или количество товаров.
(13) ты правильно понимаешь, но условия полностью сформулированы. Обработка должна завершиться, а если ты все время будешь удалять первую страницу, она никогда не завершится, если неудаляемых больше 25.
(13) ты правильно понимаешь, но условия полностью сформулированы. Обработка должна завершиться, а если ты все время будешь удалять первую страницу, она никогда не завершится, если неудаляемых больше 25.
(14) Ну тогда у меня вообще не будет понимания удалялось ли что-то со страницы - по сути я это пойму только после полного обхода - если у меня не поменялось количество страниц и количество на последней странице.
Т.е. минимум два обхода, и то если ничего не удалось удалить.
Первый обход страниц - удаляем все до последней - запомнили P - pages, N - количество на последней
Второй проход если P, N не изменилось - ок, закончили. Поменялось - давай по новой обходи все.
Вопрос в том перестраивается ли состав удаляемой страницы или нет. Обычно перестраивается
Т.е. минимум два обхода, и то если ничего не удалось удалить.
Первый обход страниц - удаляем все до последней - запомнили P - pages, N - количество на последней
Второй проход если P, N не изменилось - ок, закончили. Поменялось - давай по новой обходи все.
Вопрос в том перестраивается ли состав удаляемой страницы или нет. Обычно перестраивается
(19)ээээ....зачем два обхода?
1. Запросили содержимое первой страницы. Поместили в массив все 25 значений.
2. Удалил все.
3. Запросили содержимое первой страницы.
4. Сверили с массивом
5. Если есть такие, которых нет в массиве, удаляем все на первой странице.
6. Если все элементы страницы есть в массиве, запрашиваем данные следующей страницы и добавляем в массив
7. Удаляем данные n страницы и возвращаемся на п.3
1. Запросили содержимое первой страницы. Поместили в массив все 25 значений.
2. Удалил все.
3. Запросили содержимое первой страницы.
4. Сверили с массивом
5. Если есть такие, которых нет в массиве, удаляем все на первой странице.
6. Если все элементы страницы есть в массиве, запрашиваем данные следующей страницы и добавляем в массив
7. Удаляем данные n страницы и возвращаемся на п.3
(23)
Опять же если да, меняется только 1 элемент, например, и мы долбим эту страницу :)
Если бы можно сохранять в массив, то тут можно играть с количеством в массиве - удалять по нему, а сколько памяти мы можем под массив забрать и тогда страницы по несколько получать и закидывать в массив. Короче, тут слишком много поля для творчетсва, как по мне.
не придется. ты состав все равно не получаешь, ты получаешь, есть там товары или нет, ну или количество товаров.
(14)
Опять же если да, меняется только 1 элемент, например, и мы долбим эту страницу :)
Если бы можно сохранять в массив, то тут можно играть с количеством в массиве - удалять по нему, а сколько памяти мы можем под массив забрать и тогда страницы по несколько получать и закидывать в массив. Короче, тут слишком много поля для творчетсва, как по мне.
(24)хорошо, если запрос содержимого нам возвращает только количество элементов на странице, то да, нужно 2 прохода: от 1 до n и от n к 1. Точкой останова будет равенство количества до удаления и после.
если я правильно понял алгоритм работы из описания, объясняю на пальцах:
Допустим, изначально 101 запись.
запрос количества 1 страницы. Ответ - 25
Удаляем. Допустим удалилось 5 записей, но мы об этом не узнаем.
Запрос количества 2-ой страницы. Ответ - 25.
Удаляем. Допустим не удалилось ни одной записи, но мы об этом не узнаем.
Запрос количества 3-ей страницы. Ответ - 25.
Удаляем. Допустим удалилось 20 записей, но мы об этом не узнаем.
Запрос количества 4-ой страницы. Ответ - 1.
Удаляем. Удалилась 1 запись, но мы об этом не узнаем.
Запрос количества 4-ой страницы. Ответ - 0.
Запрос количества 3-ей страницы. Ответ - 25.
Удаляем. Допустим удалилось 10 записей, но мы об этом не узнаем.
Запрос количества 2-ой страницы.Ответ - 25.
Т.к. количество не поменялось после 2-х удалений, приходим к выводу, что количество не удаляемых элементов >= 50 и далее смысла пытаться удалить нет.
Если в данный момент запросить количество 3-ей страницы, то ответ должен быть - 15.
если я правильно понял алгоритм работы из описания, объясняю на пальцах:
Допустим, изначально 101 запись.
запрос количества 1 страницы. Ответ - 25
Удаляем. Допустим удалилось 5 записей, но мы об этом не узнаем.
Запрос количества 2-ой страницы. Ответ - 25.
Удаляем. Допустим не удалилось ни одной записи, но мы об этом не узнаем.
Запрос количества 3-ей страницы. Ответ - 25.
Удаляем. Допустим удалилось 20 записей, но мы об этом не узнаем.
Запрос количества 4-ой страницы. Ответ - 1.
Удаляем. Удалилась 1 запись, но мы об этом не узнаем.
Запрос количества 4-ой страницы. Ответ - 0.
Запрос количества 3-ей страницы. Ответ - 25.
Удаляем. Допустим удалилось 10 записей, но мы об этом не узнаем.
Запрос количества 2-ой страницы.Ответ - 25.
Т.к. количество не поменялось после 2-х удалений, приходим к выводу, что количество не удаляемых элементов >= 50 и далее смысла пытаться удалить нет.
Если в данный момент запросить количество 3-ей страницы, то ответ должен быть - 15.
(19) Вот тут точно не понимаю :) учитывая смещение (17) - на первой у меня могут быть записи, которые нужно удалить
Т.е. лучший случай - все удаляется - будет P обходов чтений/удалений - P/2 в каждую сторону
Худший 2 * P - ничего не удалилось - прошли туда-обратно в холостую
Получение сначала P поиском, каким либо, пускай бинарным - X * Log2(P) - Х сейчас не соображу, пускай 2, типа дошли до какой-то страницы P, увеличили в два раза, нарвались на ноль, начали искать, а оказалось что количество страниц P + 1
+ на само удаление P
Т.е. лучший случай - все удаляется - будет P обходов чтений/удалений - P/2 в каждую сторону
Худший 2 * P - ничего не удалилось - прошли туда-обратно в холостую
Получение сначала P поиском, каким либо, пускай бинарным - X * Log2(P) - Х сейчас не соображу, пускай 2, типа дошли до какой-то страницы P, увеличили в два раза, нарвались на ноль, начали искать, а оказалось что количество страниц P + 1
+ на само удаление P
(19)если 2-а обхода, в чем же оптимизация, какой смысл удалять и в первом и втором обходе, если первым обходом можно получить последнюю страницу и гарантированно все удалить за обратный проход? (17) прав, первую при таком сдвиге придется повторно удалять, потому как из страницы 2 в страницу 1 пришли 15 новых и возможно среди них есть удаляемые....
(26)а как оценить оптимальность? Вариант с проходами туда обратно при большом количестве неудаляемых будет не оптимальным. Пример - у нас 100 страниц контрагентов, при проходе туда удалилось 80%, т. е, остановились на странице 80 и делаем обратный прохд до 1, в итоге имеем 160 вызовов запроса и 160 вызовов удаления. По предложенному методу двоичного поиска последней страницы за 12 запросов находим ее и делаем обратный проход, имеем 112 вызоаов запроса и 100 вызовов удалить. И что оптисамальнее?
(28) Автор написал, что есть какой-то признак остановки при обратном проходе, чтобы не идти до начала. Но мне пока в голову ничего не приходит.
Через определенное количество итераций проверять - а не поменялась ли последняя страницы - кажись не даст какого либо результата, плюс даст доп чтения.
Через определенное количество итераций проверять - а не поменялась ли последняя страницы - кажись не даст какого либо результата, плюс даст доп чтения.
(29)основной вопрос - сдвигаются ли контрагенты вверх по страницам при удалении их с более ранних страниц, т.е. если количество контрагентов >=25 то запрос к странице 1 всегда вернет 25? если да, то мы никак не минуем повторную обработку страницы 1 при прямом проходе.
Если я правильно понял условие, то запрос нам возвращает только цифру - количество контрагентов, никаких ссылок (тогда зачем сноска про одинаковое упорядочивание?), а удаление по номеру страницы ,напимер 2, удаляет удаляющихся контрагентов с 26 по 50. Или не так?
Ну и смущает "в выдаче на странице", что такое в выдаче?
Если я правильно понял условие, то запрос нам возвращает только цифру - количество контрагентов, никаких ссылок (тогда зачем сноска про одинаковое упорядочивание?), а удаление по номеру страницы ,напимер 2, удаляет удаляющихся контрагентов с 26 по 50. Или не так?
Ну и смущает "в выдаче на странице", что такое в выдаче?
Для простоты приведу пример, где на страницу выдается 2 объекта. По 5 запросов, которые будут выдавать только есть ли на странице результат.
Все время буду запрашивать первую страницу и удалять.
Вариант 1, все элементы удаляемы:
Последовательность 1, 2, 3, 4, 5, 6, 7, 8.
Запрос ЕСТЬ (1, 2)
Запрос ЕСТЬ (3, 4)
Запрос ЕСТЬ (5, 6)
Запрос ЕСТЬ (7, 8)
Запрос НЕТ
Вариант 2, не удаляемые помечены *:
Последовательность 1, 2*, 3, 4, 5*, 6, 7, 8.
Запрос ЕСТЬ (1, 2*)
Запрос ЕСТЬ (2*, 3)
Запрос ЕСТЬ (2*, 4)
Запрос ЕСТЬ (2*, 5*)
Запрос ЕСТЬ (2*, 5*) - и так без конца если запрашивать первую страницу.
Конкретных элементов система не выдает, только признак наличия.
Задача взята из жизни, если запрашивать страницу элементов в браузере она выдает элементы, но парсить их сложно, проще определить по тексту "No elements found" страницу, на которой уже элементов нет.
Все время буду запрашивать первую страницу и удалять.
Вариант 1, все элементы удаляемы:
Последовательность 1, 2, 3, 4, 5, 6, 7, 8.
Запрос ЕСТЬ (1, 2)
Запрос ЕСТЬ (3, 4)
Запрос ЕСТЬ (5, 6)
Запрос ЕСТЬ (7, 8)
Запрос НЕТ
Вариант 2, не удаляемые помечены *:
Последовательность 1, 2*, 3, 4, 5*, 6, 7, 8.
Запрос ЕСТЬ (1, 2*)
Запрос ЕСТЬ (2*, 3)
Запрос ЕСТЬ (2*, 4)
Запрос ЕСТЬ (2*, 5*)
Запрос ЕСТЬ (2*, 5*) - и так без конца если запрашивать первую страницу.
Конкретных элементов система не выдает, только признак наличия.
Задача взята из жизни, если запрашивать страницу элементов в браузере она выдает элементы, но парсить их сложно, проще определить по тексту "No elements found" страницу, на которой уже элементов нет.
(32)
Идеальный код что-то вроде этого:
Основной принцип - "туда и обратно", метод "хоббита".
Т.е. идем вперед, пока не закончатся страницы, потом идем назад.
На практике я не стал заморачиваться и назад шел до первой страницы.
(у меня была задача удаления контрагентов в zoho.books)
Идеальный код что-то вроде этого:
НомерСтраницы = 0;
Пока истина Цикл
НомерСтраницы = НомерСтраницы + 1;
КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
Если КоличествоКонтрагентов = 0 Тогда
Прервать;
КонецЕсли;
УдалитьКонтрагентовНаТекущейСтранице(НомерСтраницы);
КонецЦикла;
Пока истина Цикл
ПредКоличествоКонтрагентов = КоличествоКонтрагентов;
КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
Если ПредКоличествоКонтрагентов = КоличествоКонтрагентов И КоличествоКонтрагентов <> 0 Тогда
Прервать;
КонецЕсли;
Если КоличествоКонтрагентов = 0 Тогда
НомерСтраницы = НомерСтраницы - 1;
Если НомерСтраницы = 0 Тогда
Прервать;
КонецЕсли;
Продолжить;
КонецЕсли;
УдалитьКонтрагентовНаТекущейСтранице(НомерСтраницы);
КонецЦикла;
ПоказатьОсновной принцип - "туда и обратно", метод "хоббита".
Т.е. идем вперед, пока не закончатся страницы, потом идем назад.
На практике я не стал заморачиваться и назад шел до первой страницы.
(у меня была задача удаления контрагентов в zoho.books)
(33) да уж... идеальный код, может я чего-то не догоняю? второй цикл жесть, во первых, если на странице при обратном цикле есть есть неудаляемые, у вас никогда не произойдет
НомерСтраницы = НомерСтраницы - 1;
потому что
КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
Если КоличествоКонтрагентов = 0 Тогда
никогда не будет 0 вы будете елозить всегда одну строку.
Во вторых, если все удаляемые, вы два раза анализируете одну строку, первый раз когда получаете количество по строке, которое не 0, затем удаляете элементы этой строки, но не переходите на предыдущую, а еще раз проверяете эту-же, чтобы убедиться что там 0...
В третьих, зачем ПредКоличествоКонтрагентов = КоличествоКонтрагентов; при переходе на строку НомерСтраницы - 1 ПредКоличествоКонтрагентов всегда будет 0, потому что у вас условие перехода на строку НомерСтраницы - 1 это КоличествоКонтрагентов = 0...
По условиям начальной задачи ТАК работать не будет
НомерСтраницы = НомерСтраницы - 1;
потому что
КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
Если КоличествоКонтрагентов = 0 Тогда
никогда не будет 0 вы будете елозить всегда одну строку.
Во вторых, если все удаляемые, вы два раза анализируете одну строку, первый раз когда получаете количество по строке, которое не 0, затем удаляете элементы этой строки, но не переходите на предыдущую, а еще раз проверяете эту-же, чтобы убедиться что там 0...
В третьих, зачем ПредКоличествоКонтрагентов = КоличествоКонтрагентов; при переходе на строку НомерСтраницы - 1 ПредКоличествоКонтрагентов всегда будет 0, потому что у вас условие перехода на строку НомерСтраницы - 1 это КоличествоКонтрагентов = 0...
По условиям начальной задачи ТАК работать не будет
(37)как в 38, могу выложить код, как и писал в примере при 100 страницах найдём нужную конечную точку не более чем за 12-14 запросов, а вот вы так и не привели алгоритм, которым при обратном проходе можно понять, что можно остановиться ранее 1 страницы (при заданных изначально условиях задачи)
пример поиска где последняя строка нам неизвестна, а она 100
стр это номер страницы
стр =1 если кол не 0
стр =стр*2=2 если кол не 0
стр =стр*2=4 если кол не 0
стр =стр*2=8 если кол не 0
стр =стр*2=16 если кол не 0
стр =стр*2=32 если кол не 0
стр =стр*2=64 если кол не 0
стр =стр*2=128 если кол = 0 !!!
т.е. искомый конец в диапазоне от 64 до 128, берем разницу = 64 и деля ее на два прибавляем к крайней нашей не нулевой строке,
стр = 64+32 = 96 (разница= (разница/2=32) кол не 0
стр = стр+16 = 112 (разница= (разница/2=16) кол = 0!!
стр = стр-8 = 106 (разница= (разница/2=8) кол = 0!!
стр = стр-4 = 102 (разница= (разница/2=4) кол = 0!!
стр = стр-2 = 100 (разница= (разница/2=2) кол не 0
стр = стр+1 = 101 (разница= (разница/2=1) кол = 0
итого искомая страница = стр =100, если бы при остатке разницы 1 было вычитание то страница = стр-1-100
14 запросов, не 100
пример поиска где последняя строка нам неизвестна, а она 100
стр это номер страницы
стр =1 если кол не 0
стр =стр*2=2 если кол не 0
стр =стр*2=4 если кол не 0
стр =стр*2=8 если кол не 0
стр =стр*2=16 если кол не 0
стр =стр*2=32 если кол не 0
стр =стр*2=64 если кол не 0
стр =стр*2=128 если кол = 0 !!!
т.е. искомый конец в диапазоне от 64 до 128, берем разницу = 64 и деля ее на два прибавляем к крайней нашей не нулевой строке,
стр = 64+32 = 96 (разница= (разница/2=32) кол не 0
стр = стр+16 = 112 (разница= (разница/2=16) кол = 0!!
стр = стр-8 = 106 (разница= (разница/2=8) кол = 0!!
стр = стр-4 = 102 (разница= (разница/2=4) кол = 0!!
стр = стр-2 = 100 (разница= (разница/2=2) кол не 0
стр = стр+1 = 101 (разница= (разница/2=1) кол = 0
итого искомая страница = стр =100, если бы при остатке разницы 1 было вычитание то страница = стр-1-100
14 запросов, не 100
(39)Это все замечательно, но дальше что? Вот вы узнали, что изначально у вас 100 страниц данных за 14 запросов.
Как это все дело удалять будете? Ведь может случится так, что ничего не удалится на каждой из страниц, поэтому будут те же 100 запросов на удаление + запросы на количество после удаления, чтобы как минимум не зациклиться.
Как это все дело удалять будете? Ведь может случится так, что ничего не удалится на каждой из страниц, поэтому будут те же 100 запросов на удаление + запросы на количество после удаления, чтобы как минимум не зациклиться.
(41)нет, за 14 запросов мы узнаем что у нас всего 100 заполненных страниц (а не 200,300или 400), и далее обратным циклом удаляем данные начиная со страницы 100 до 1, у нас есть задача удалить все что удалиться, удаляем постранично с последней, все ок. смысл как раз в том что если удаляем с конца, список не сползает вверх, все что может удалиться - удалиться
(33) То что на определенной странице уже невозможно ничего удалить, не является гарантией того, что их нельзя удалить на предыдущих.
Например, у нас изначально 80 контрагентов.
Удалили на первой странице 5, они перекочевали со второй.
На второй не важно сколько удалили, пускай 10.
Третья страница последняя, допустим там 5 неудаляемых. После повторного удаления/проверки видим что осталось 5.
По этому условию прерываем удаление?
Но на первой странице все еще есть 5 контрагентов, которых потенциально можно удалить
Например, у нас изначально 80 контрагентов.
Удалили на первой странице 5, они перекочевали со второй.
На второй не важно сколько удалили, пускай 10.
Третья страница последняя, допустим там 5 неудаляемых. После повторного удаления/проверки видим что осталось 5.
По этому условию прерываем удаление?
Но на первой странице все еще есть 5 контрагентов, которых потенциально можно удалить
Я считаю, что поиск последней страницы не дает преимуществ. Можно начинать удалять с первой и экономить на холостых прогонах. Ну а потом идти обратно. Но это уже детали оптимизации.
Суть решения - идем с начала до последней страницы с шагом +1, потом назад до первой с шагом -1.
Может это и не самое эффективное, но точно работающее решение.
Я подразумевал его. ;-)
Суть решения - идем с начала до последней страницы с шагом +1, потом назад до первой с шагом -1.
Может это и не самое эффективное, но точно работающее решение.
Я подразумевал его. ;-)
(46)вроде все уже обсудили, если неудаляемых менее 50% ваш вариант лучший, если более, то через половинное деление лучше, НО!
вы (19)
да, два обхода. С первой до последней и потом с последней назад, но не до первой, а там хитро надо остановиться
мы все ждали эту хитринку! я прям готов был снять шляпу, весь прикол задачи, как по мне, был в этом.
В любом случае, спасибо за тему! Встряхнул математику!
вы (19)
да, два обхода. С первой до последней и потом с последней назад, но не до первой, а там хитро надо остановиться
мы все ждали эту хитринку! я прям готов был снять шляпу, весь прикол задачи, как по мне, был в этом.
В любом случае, спасибо за тему! Встряхнул математику!
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот