Самый быстрый способ определить последнюю «запись» .. в идеале параллельно ... (с пробелами)

Question

У меня есть приложение для интеллектуального анализа данных, которое обращается к веб-сайту для получения записей на индивидуальной основе [другой веб-сайт все еще находится в ведении моей компании, но не имеет API для доступа к нему].Я знаю, что первая запись - «1», но (без вмешательства человека) я не знаю последнюю запись.Последовательная обработка данных может занять некоторое время (например, 4000 записей = около 45 минут).Чтобы улучшить взаимодействие с пользователем, я хотел бы быстро установить процент выполнения.

В идеале я бы реализовал что-то вроде бинарного поиска, чтобы определить последнюю запись с наименьшим количеством запросов с сервера.Я случайно узнал, что эти записи созданы людьми, поэтому, если сегодня их было в общей сложности 4000, то завтра, скорее всего, это будет 4000-4020, но я бы не хотел вводить предположениек моему приложению для сбора данных, потому что это потребовало бы некоторого администрирования пользователями.

1. Какой самый быстрый способ определения «последней записи»
2. Чтобы усложнить проблему,удаленные записи выглядят так же, как и записи, еще не созданные!Хотя они ОЧЕНЬ редки, они случаются.Я определил правило ПЯТИ последовательных сбоев для извлечения после последнего успеха, чтобы указать последнюю запись.
3. У меня уже есть хорошая последовательная реализация, но я определил из-за стоимости обработки записи, что этовозможно / быстрее получить их параллельно (например, 8 за раз)

Существует ли установленный шаблон / алгоритм для такого рода поиска «последнего индекса» (с ограниченными пробелами)?Хотя я могу настойчиво (в определенной степени) сделать существующее приложение параллельным (например, возможно, в 8 раз быстрее), как я могу быстро определить продолжительность ожидания пользователя?

1. Я мог бы заставить пользователя просто ждать 1/8времени, которое они в настоящее время делают.
2. Я могу потратить первоначальные усилия, чтобы найти последнюю запись, а затем заполнить содержимое для завершения операции.

Информация о реализации, я 'Я реализую это в C # и имею доступ к LINQ, но это, я чувствую, независимый от языка алгоритм.

EDIT У меня уже есть механизм кэширования для большинства пользователей, но существующие данныеможет изменяться довольно часто (5% -10% в день), и поэтому механизм кэширования может быстро устареть.Я хочу избежать необходимости центрального кэша , чтобы эти изменения не затронули всех пользователей, кроме того, существует несколько проектов, и для кэширования может потребоваться доступ к «веб-сайтам». У меня может даже не быть доступа или сервисов.Я разрабатываю - я бы предпочел, чтобы это оставалось в «домене пользователя».Поэтому время от времени необходимо выполнять «полное обновление» как можно быстрее.

Answer 1

Ну, как вы сказали, вы можете использовать что-то вроде бинарного поиска.Вы пытаетесь найти наименьшую верхнюю границу допустимых индексов записи ( n ).Начните с n = 1 и удваивайте его, пока не дойдете до конца. n теперь является верхней границей.Теперь выполните двоичный поиск между n / 2 и n , чтобы уменьшить его до верхней границы наименьшего .

Очевидно, что это можно настроить навыпадайте по 8 или более записей за раз (и это звучит так, как будто это будет необходимо в любом случае, если единственный способ узнать, что вы вышли из-под контроля, это увидеть достаточное количество смежных пустых записей).