Гуру-тест: Постраничное удаление контрагентов

1. 4015 08.04.20 19:49 Сейчас в теме
Прикольная алгоритмическая задача, которая пригодится на собеседования кандидатов или для вящего удовольствия.

В базе данных есть заранее неизвестное количество контрагентов.

К базе можно выполнять только один вид запроса: спросить сколько контрагентов находится в выдаче на странице номер N.

При этом на странице выдается по 25 контрагентов и контрагенты всегда упорядочены одинаково. На последней странице может быть меньше контрагентов.

К запросу можно выполнить только одно действие: удалить контрагентов, выданных на странице.

При этом будут удалены только те контрагенты, по которым в базе не проходит никаких операций.

Вопрос: Как оптимально выполнить удаление всех контрагентов, которых можно удалить.
Ответы
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
2. user856012 13 08.04.20 19:57 Сейчас в теме
Встречный вопрос: КГ/АМ?
3. davealone 149 09.04.20 08:37 Сейчас в теме
А во время удаления изменение состава контрагентов другими процессами возможно?
Если нет, то определить максимальную страницу - где N <= 25. Например начав с 1, далее увеличивая номер страницы в два раза, если N = 25. Дошли до предела - N = 0, половинным делением пошагово определили правильный предельный номер страницы.
Далее постранично с конца удаляем.
4. fixin 4015 09.04.20 09:06 Сейчас в теме
(3) есть метод эффективнее чутка, без половинного деления. База в нашем монопольном доступе
5. davealone 149 09.04.20 09:20 Сейчас в теме
(4) Эффективнее в части поиска последней страницы или удаления с конца?
6. fixin 4015 09.04.20 14:06 Сейчас в теме
(5) искать последнюю страницу не эффективно. Если просто искать. Понимаешь?
7. davealone 149 09.04.20 17:57 Сейчас в теме
(6) неа :)
Если поиск страницы вернул ответ, удалить контрагентов на этой странице?

Может дело еще в этом "контрагенты всегда упорядочены одинаково"? Зная поле сортировки можно примерно определить шаг поиска и ускорить?
8. fixin 4015 09.04.20 18:13 Сейчас в теме
(7) нет.
зачем искать последнюю страницу, если можно начинать с первой и удалять-удалять, пока в ноль не выйдешь. но не первую удалять, а первую, вторую, третью.
Если только первую удалять есть риск, что никогда не закончится, если количество контрагентов, которых нельзя удалить больше 25.
9. nomad_irk 51 09.04.20 18:20 Сейчас в теме
(8)К чему тогда уточненения по поводу количества контрагентов на странице? тупо удаляй все, что вернул запрос необходимое количество итераций и все.
В чем подвох?
10. fixin 4015 09.04.20 19:11 Сейчас в теме
(9) Ну нужно знать, есть что-то на странице или нет. В принципе, минимальный запрос для решения запроса выдавал бы, есть контрагенты на странице или нет.
11. nomad_irk 51 09.04.20 19:15 Сейчас в теме
(10)я о том и баю.
Получается, если запрос вернул что-то, то это все можно смело удалять. Другой вопрос, когда это уже удаляли, но оно не удалилось по какой-то там причине, и поэтому следующий запрос опять вернет это якобы удаленное.
12. davealone 149 09.04.20 19:20 Сейчас в теме
(8) А при таком подходе разве не придется запросить каждую страницу минимум дважды? Чтобы проверить, что состав после удаления не поменялся?
Типа удалил с 1 страницы 5 из 25, значит на ней появилось 5 новых.
13. nomad_irk 51 09.04.20 19:53 Сейчас в теме
(12) Насколько я понял из условия задачи, в процесс удаления мы никак вмешаться не можем и можем лишь получить некий результат.
В случае, когда на первой странице удалилось 5 из 25, то следующая итерация запроса данных первой страницы будет содержать "новые" 25 значений, среди которых будут содержаться "предыдущие" 20 неудаленных значений.
По условию задачи, не понятно, нужно проверять такой момент или нет, поэтому повторяем итерацию удаления для всех 25 значений и запрашиваем содержимое первой страницы и так пока не удалим все. Если есть задача еще и контролировать то, что мы пытались удалить, но оно по факту не удалилось, то в таком случае да, придется проверять страницы по порядку, сверяя содержимое N-ой страницы с уже обработанными элементами.
14. fixin 4015 09.04.20 20:10 Сейчас в теме
(12) не придется. ты состав все равно не получаешь, ты получаешь, есть там товары или нет, ну или количество товаров.
(13) ты правильно понимаешь, но условия полностью сформулированы. Обработка должна завершиться, а если ты все время будешь удалять первую страницу, она никогда не завершится, если неудаляемых больше 25.
15. davealone 149 09.04.20 20:27 Сейчас в теме
(14) Ну тогда у меня вообще не будет понимания удалялось ли что-то со страницы - по сути я это пойму только после полного обхода - если у меня не поменялось количество страниц и количество на последней странице.
Т.е. минимум два обхода, и то если ничего не удалось удалить.

Первый обход страниц - удаляем все до последней - запомнили P - pages, N - количество на последней
Второй проход если P, N не изменилось - ок, закончили. Поменялось - давай по новой обходи все.

Вопрос в том перестраивается ли состав удаляемой страницы или нет. Обычно перестраивается
16. fixin 4015 09.04.20 20:28 Сейчас в теме
(15) ошибаешься, по новой обходить не надо, когда до последней дошел.
т.е. потом не с первой надо начинать, сечешь? Не?
17. davealone 149 09.04.20 20:32 Сейчас в теме
(16) С первой
У меня
Страница 1 - 15 удаляемых 10 нет - я их удалил
Страница 2 - 20 удаляемых 5 нет - я их удалил

Но 15 удаленных со страницы 1 освободили место 15 новым из страницы 2 - те перешли на страницу 1
- ее нужно повторно чекнуть во втором обходе
18. davealone 149 09.04.20 20:33 Сейчас в теме
(16) или теперь с последней пойти? но опять же это два обхода?
19. fixin 4015 09.04.20 21:25 Сейчас в теме
(18) да, два обхода. С первой до последней и потом с последней назад, но не до первой, а там хитро надо остановиться
20. nomad_irk 51 09.04.20 21:34 Сейчас в теме
(19)ээээ....зачем два обхода?
1. Запросили содержимое первой страницы. Поместили в массив все 25 значений.
2. Удалил все.
3. Запросили содержимое первой страницы.
4. Сверили с массивом
5. Если есть такие, которых нет в массиве, удаляем все на первой странице.
6. Если все элементы страницы есть в массиве, запрашиваем данные следующей страницы и добавляем в массив
7. Удаляем данные n страницы и возвращаемся на п.3
22. davealone 149 09.04.20 21:37 Сейчас в теме
(20) из обсуждения вышло, что
а) результат страницы - это только количество - нельзя сравнивать
б) если было бы даже можно - допустим удаляется только 25-й контрагент, по одному удалять будет долго )))
23. nomad_irk 51 09.04.20 21:40 Сейчас в теме
(22)насколько я понял, удалять можно пакетно, но реально удаляются не все.
И так же понял, что запрос содержимого страницы возвращает таки набор самих элементов, которые мы можем попробовать удалить
24. davealone 149 09.04.20 21:46 Сейчас в теме
(23)
не придется. ты состав все равно не получаешь, ты получаешь, есть там товары или нет, ну или количество товаров.
(14)

Опять же если да, меняется только 1 элемент, например, и мы долбим эту страницу :)
Если бы можно сохранять в массив, то тут можно играть с количеством в массиве - удалять по нему, а сколько памяти мы можем под массив забрать и тогда страницы по несколько получать и закидывать в массив. Короче, тут слишком много поля для творчетсва, как по мне.
27. nomad_irk 51 09.04.20 22:09 Сейчас в теме
(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.
21. davealone 149 09.04.20 21:35 Сейчас в теме
(19) Вот тут точно не понимаю :) учитывая смещение (17) - на первой у меня могут быть записи, которые нужно удалить

Т.е. лучший случай - все удаляется - будет P обходов чтений/удалений - P/2 в каждую сторону
Худший 2 * P - ничего не удалилось - прошли туда-обратно в холостую

Получение сначала P поиском, каким либо, пускай бинарным - X * Log2(P) - Х сейчас не соображу, пускай 2, типа дошли до какой-то страницы P, увеличили в два раза, нарвались на ноль, начали искать, а оказалось что количество страниц P + 1
+ на само удаление P
25. karamazoff 58 09.04.20 21:52 Сейчас в теме
(19)если 2-а обхода, в чем же оптимизация, какой смысл удалять и в первом и втором обходе, если первым обходом можно получить последнюю страницу и гарантированно все удалить за обратный проход? (17) прав, первую при таком сдвиге придется повторно удалять, потому как из страницы 2 в страницу 1 пришли 15 новых и возможно среди них есть удаляемые....
26. davealone 149 09.04.20 21:56 Сейчас в теме
(25) если все удаляется при обходе, то будет по сути 1 обход:
было 10 страниц - пока шли удаляли, 5 удалилось - 5 осталось - удалили в обратном обходе

а вот по поводу (17), ждем, может я чего-то не уловил )))
28. karamazoff 58 10.04.20 09:16 Сейчас в теме
(26)а как оценить оптимальность? Вариант с проходами туда обратно при большом количестве неудаляемых будет не оптимальным. Пример - у нас 100 страниц контрагентов, при проходе туда удалилось 80%, т. е, остановились на странице 80 и делаем обратный прохд до 1, в итоге имеем 160 вызовов запроса и 160 вызовов удаления. По предложенному методу двоичного поиска последней страницы за 12 запросов находим ее и делаем обратный проход, имеем 112 вызоаов запроса и 100 вызовов удалить. И что оптисамальнее?
29. davealone 149 10.04.20 09:56 Сейчас в теме
(28) Автор написал, что есть какой-то признак остановки при обратном проходе, чтобы не идти до начала. Но мне пока в голову ничего не приходит.
Через определенное количество итераций проверять - а не поменялась ли последняя страницы - кажись не даст какого либо результата, плюс даст доп чтения.
30. karamazoff 58 10.04.20 10:05 Сейчас в теме
(29)основной вопрос - сдвигаются ли контрагенты вверх по страницам при удалении их с более ранних страниц, т.е. если количество контрагентов >=25 то запрос к странице 1 всегда вернет 25? если да, то мы никак не минуем повторную обработку страницы 1 при прямом проходе.
Если я правильно понял условие, то запрос нам возвращает только цифру - количество контрагентов, никаких ссылок (тогда зачем сноска про одинаковое упорядочивание?), а удаление по номеру страницы ,напимер 2, удаляет удаляющихся контрагентов с 26 по 50. Или не так?
Ну и смущает "в выдаче на странице", что такое в выдаче?
31. fixin 4015 10.04.20 11: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" страницу, на которой уже элементов нет.
32. karamazoff 58 10.04.20 12:26 Сейчас в теме
(31)примеров в ветке уже кучу привели, хотелось бы увидеть решение для варианта 2, где есть неудаляемые с прямым проходом по страницам до конца и с обратным НЕ до 1-й страницы, как вы писали в (19)
33. fixin 4015 10.04.20 13:56 Сейчас в теме
(32)
Идеальный код что-то вроде этого:
НомерСтраницы = 0;

Пока истина Цикл
    НомерСтраницы = НомерСтраницы + 1;
    КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
    Если КоличествоКонтрагентов = 0 Тогда
        Прервать;
    КонецЕсли;
    УдалитьКонтрагентовНаТекущейСтранице(НомерСтраницы);
КонецЦикла;

Пока истина Цикл
    ПредКоличествоКонтрагентов = КоличествоКонтрагентов;
    КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
    Если ПредКоличествоКонтрагентов = КоличествоКонтрагентов И КоличествоКонтрагентов <> 0 Тогда
        Прервать;
    КонецЕсли;
    Если КоличествоКонтрагентов = 0 Тогда
        НомерСтраницы = НомерСтраницы - 1;
        Если НомерСтраницы = 0 Тогда
            Прервать;
        КонецЕсли;
        Продолжить;
    КонецЕсли;
    УдалитьКонтрагентовНаТекущейСтранице(НомерСтраницы);
КонецЦикла;
Показать

Основной принцип - "туда и обратно", метод "хоббита".
Т.е. идем вперед, пока не закончатся страницы, потом идем назад.
На практике я не стал заморачиваться и назад шел до первой страницы.
(у меня была задача удаления контрагентов в zoho.books)
34. karamazoff 58 10.04.20 14:27 Сейчас в теме
(33) да уж... идеальный код, может я чего-то не догоняю? второй цикл жесть, во первых, если на странице при обратном цикле есть есть неудаляемые, у вас никогда не произойдет
НомерСтраницы = НомерСтраницы - 1;
потому что
КоличествоКонтрагентов = ПоказатьСтраницу(НомерСтраницы);
Если КоличествоКонтрагентов = 0 Тогда
никогда не будет 0 вы будете елозить всегда одну строку.
Во вторых, если все удаляемые, вы два раза анализируете одну строку, первый раз когда получаете количество по строке, которое не 0, затем удаляете элементы этой строки, но не переходите на предыдущую, а еще раз проверяете эту-же, чтобы убедиться что там 0...
В третьих, зачем ПредКоличествоКонтрагентов = КоличествоКонтрагентов; при переходе на строку НомерСтраницы - 1 ПредКоличествоКонтрагентов всегда будет 0, потому что у вас условие перехода на строку НомерСтраницы - 1 это КоличествоКонтрагентов = 0...

По условиям начальной задачи ТАК работать не будет
35. fixin 4015 10.04.20 16:07 Сейчас в теме
(34) ну "идеальный" был по смыслу, а не в мелочах. Короче, там есть простор для оптимизации при обратном ходе, но можно просто дойти до первой страницы.
36. karamazoff 58 10.04.20 16:16 Сейчас в теме
(35)при наличие неудаляемых и неизвестном количестве этих неудаляемых, считаю намного эффективнее метод поиска последнего половинным делением и одним обратным проходом без всяких условий. Это ИМХО, у каждого свои идеалы :)
37. fixin 4015 10.04.20 19:44 Сейчас в теме
(36) Половинное деление говоришь? А что за максимальную точку брать будешь, если тебе система об этом не говорит? Т.е. с какой страницы стартовать будешь? с 10? 100? 1000?
Или сначала тестишь 2, потом 4, потом 16, потом 256 и т.п.?
38. davealone 149 10.04.20 20:37 Сейчас в теме
(37) 2, 4, 8, 16, и т.д. а потом в обратном на разницу, я же писал в (21)
получается 2 * log2(P) на сколько я понимаю

т. е. одинаково при ~8 страниц кажись

если конечно нет способа ограничить обратный обход :)
karamazoff; +1 Ответить
40. karamazoff 58 10.04.20 22:10 Сейчас в теме
(38) если конечно нет способа ограничить обратный обход :)
да нет такого способа при поставленных условиях в (0), а по коду, который привел автор, его и быть не может, ну вы же видите его код, стеб какой-то....
39. karamazoff 58 10.04.20 21:22 Сейчас в теме
(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
41. nomad_irk 51 10.04.20 23:02 Сейчас в теме
(39)Это все замечательно, но дальше что? Вот вы узнали, что изначально у вас 100 страниц данных за 14 запросов.
Как это все дело удалять будете? Ведь может случится так, что ничего не удалится на каждой из страниц, поэтому будут те же 100 запросов на удаление + запросы на количество после удаления, чтобы как минимум не зациклиться.
42. karamazoff 58 10.04.20 23:08 Сейчас в теме
(41)нет, за 14 запросов мы узнаем что у нас всего 100 заполненных страниц (а не 200,300или 400), и далее обратным циклом удаляем данные начиная со страницы 100 до 1, у нас есть задача удалить все что удалиться, удаляем постранично с последней, все ок. смысл как раз в том что если удаляем с конца, список не сползает вверх, все что может удалиться - удалиться
44. nomad_irk 51 10.04.20 23:13 Сейчас в теме
(42)Согласен с тем, что удалять нужно с конца.
50. fixin 4015 11.04.20 16:46 Сейчас в теме
(42) но тогда придется идти строго до первой страницы, чтобы удалить всё.
51. karamazoff 58 11.04.20 16:50 Сейчас в теме
(50)именно так, количество запросов и ударений будет равно количеству страниц + плюс запросы на поиск при неудаляемых более 50% это более выигрышный вариант, чем туда сюда, но вроде уже все обсудили
52. fixin 4015 11.04.20 17:09 Сейчас в теме
(51) ну в принципе да. Но это сложнее кодить, а учитывая что для меня кодить в node.js - это подвиг, я только методом туда и обратно буду кодить. ;-)
43. karamazoff 58 10.04.20 23:12 Сейчас в теме
(41)
Вот вы узнали, что изначально у вас 100 страниц данных за 14 запросов
это был пример, что если у нас 100 страниц, я определю это за 14 запросов, если будет N страниц, они определяться менее чем за N/4 запросов.
45. davealone 149 11.04.20 12:52 Сейчас в теме
(33) То что на определенной странице уже невозможно ничего удалить, не является гарантией того, что их нельзя удалить на предыдущих.

Например, у нас изначально 80 контрагентов.
Удалили на первой странице 5, они перекочевали со второй.
На второй не важно сколько удалили, пускай 10.
Третья страница последняя, допустим там 5 неудаляемых. После повторного удаления/проверки видим что осталось 5.
По этому условию прерываем удаление?
Но на первой странице все еще есть 5 контрагентов, которых потенциально можно удалить
49. fixin 4015 11.04.20 16:46 Сейчас в теме
(45) если удалять с первой с шагом + 1, то это гарантия при обратном ходе, потому что порядок объектов сохраняется.
46. fixin 4015 11.04.20 16:32 Сейчас в теме
Я считаю, что поиск последней страницы не дает преимуществ. Можно начинать удалять с первой и экономить на холостых прогонах. Ну а потом идти обратно. Но это уже детали оптимизации.
Суть решения - идем с начала до последней страницы с шагом +1, потом назад до первой с шагом -1.
Может это и не самое эффективное, но точно работающее решение.
Я подразумевал его. ;-)
47. karamazoff 58 11.04.20 16:38 Сейчас в теме
(46)вроде все уже обсудили, если неудаляемых менее 50% ваш вариант лучший, если более, то через половинное деление лучше, НО!
вы (19)
да, два обхода. С первой до последней и потом с последней назад, но не до первой, а там хитро надо остановиться

мы все ждали эту хитринку! я прям готов был снять шляпу, весь прикол задачи, как по мне, был в этом.

В любом случае, спасибо за тему! Встряхнул математику!
48. fixin 4015 11.04.20 16:45 Сейчас в теме
(47) ну я не придумал эту тему, она из жизни, просто я немного абстрагировал. ;-)
Оставьте свое сообщение
Вопросы с вознаграждением