Алгоритм проверки последовательности чисел

[serzh-z]

Имеется некий ряд чисел. Допустим первым числом является 21, а последним - 99. Между этими числами могут быть как последовательные значения (22, 23,.. 97, 98), так и встретиться разрыв (22, 23, 24, 47, 48,.. или даже 22, 23, 29, 30, 31, 24, 25,..). Необходимо понять, что в этом ряде есть такая вот лажа. Просто линейная проверка не подходит из-за своей тяжеловесности.

Подозреваю, что есть существующие алгоритмы, для определения разрывов в ряде. Кто-нибудь знает про такие?

[ffldove]

Имеется некий ряд чисел. Допустим первым числом является 21, а последним - 99. Между этими числами могут быть как последовательные значения (22, 23,.. 97, 98), так и встретиться разрыв (22, 23, 24, 47, 48,.. или даже 22, 23, 29, 30, 31, 24, 25,..). Необходимо понять, что в этом ряде есть такая вот лажа. Просто линейная проверка не подходит из-за своей тяжеловесности.

Подозреваю, что есть существующие алгоритмы, для определения разрывов в ряде. Кто-нибудь знает про такие?

если числа в массиве, то можно локализовать разрыв например так:
Например массив из 100 чисел, вычитаем из massiv[99]-massiv[0] если =100 разрыва нет, если не равно делим массив на 2 по 50, делаем аналогично с каждой частью, так можно дойти до искомого участка.
переделать метод под задачу

[Uncle_Theodore]

Код: Выделить всё

int n; //количество элементов в ряде
int arr[n]; //сам ряд

if(arr[n-1] - arr[0] != n-1)
  printf("Есть разрыв!!\n");

Не пойдет?

[Warlornhor]

Так если это целые числа, то почему бы просто не сравнивать нужное количество (Nn - N1) и количество чисел в ряде? Или я не понял задачи?

PS Долго писал.. :)

[deadhead]

Именно сам факт наличия "лажи" или еще с указанием места?

[diesel]

Имеется некий ряд чисел. Допустим первым числом является 21, а последним - 99. Между этими числами могут быть как последовательные значения (22, 23,.. 97, 98), так и встретиться разрыв (22, 23, 24, 47, 48,.. или даже 22, 23, 29, 30, 31, 24, 25,..). Необходимо понять, что в этом ряде есть такая вот лажа. Просто линейная проверка не подходит из-за своей тяжеловесности.

длина ряда четко задана? то есть в идеальном случае это скажем 21,22,...99, или i,i+1,(i+1)+1...n-1, n, где i>=21, n<=99?
может ли быть ситуация когда 22,23,24,35,47,48,49,50 ... если у нас ряд с разрывом посредине, и в нем не хватает части числе, то можно просто посмотреть на длину.

[ffldove]

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

a[0]=55
a[1]=56
a[2]=57
a[3]=61
a[4]=62
a[5]=58
a[6]=59
a[7]=60
a[8]=63
a[9]=64
n=a[n]-a[0]+1

Здесь так просто не прокатит.
Разве что блоками анализировать, чем меньше блок тем меньше вероятности что там пропустили ошибку, но 100% результата таким методом не достигнуть.

[serzh-z]

Именно сам факт наличия "лажи" или еще с указанием места?

Факт наличия.

Uncle_Theodore
Количество чисел неизвестно.

Немного усложню задачу и приближу её к реальности, то что было выше - это была попытка объяснить на пальцах и без привязки к предметной области. Никаких массивов нет. Нужен лишь правильный алгоритм для *быстрого* и с предсказуемой надёжностью (100%-я надёжность не требуется) сканированию всего ряда.

Есть видео, размером от нескольких мегабайт, до нескольких гигабайт. В нём зашиты метаданные (таймкоды), привязанные к каждому кадру этого видео. Изначально в файл встроены таймкоды от "00:00:00.00" до, скажем, "23:59:59.25" (час:минута:секунда:номер_кадра), но после того, как видеоматериал побывал в студии и прошёл через руки нескольких редакторов, в нёго встраиваются новые куски из другого видео, какие-то куски пропадают.

В итоге после обработки может получиться так, что таймкоды нескольких первых и последних кадров остались прежними (а может и не остались), а из середины или из других мест часть кадров была удалена - т.е. появились "дыры" или просто заменена - вместо, скажем, кадров с таймкодами 00:01:00:20-00:02:00:00 подсунули кадры (из другого видео) с таймкодами 01:00:00:00-02:00:00:00.

Пока мысли были в сторону метода, аналогичному методу, который предложил ffldove. Т.е. повыхватывать наугад из файла несколько таймкодов, деля отрезок на двое, и таким образом, определить нарушение порядка таймкодов.

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

Да. Именно.

[ffldove]

Ну учитывая последнии данные, очень мало вероятно что к примеру из 10 минут вырезали 5 минут 22 секунды и 22 сотых а потом вставили другой видео ряд с точно такой же длинной и тайминг с реальным временем совпадет!??? Думаю что в таких величинах возможность ошибки становиться еще меньше если воспользоваться этим алгоритмом.

[Warlornhor]

Был написан бред. А можно же сначала нормировать этот ряд, чтобы в начале был 0, а в конце максимум, а потом уже проверять по алгоритму выше.

[diesel]

Пока мысли были в сторону метода, аналогичному методу, который предложил ffldove. Т.е. повыхватывать наугад из файла несколько таймкодов, деля отрезок на двое, и таким образом, определить нарушение порядка таймкодов.

то есть в случае "ничего не подсунули" ты получишь тот же линейный перебор только хитрее сделанный. смотреть надо ведь на оба куска отрезка.
используя прошлую аналогию с числами, если a[i+m] - a[i] != m, где m==1 - слишком долго, увеличь m, и эта m и будет фактически колличеством вставок которые ты мог не заметить.

[drBatty]

serzh-z
ИМХО в любом случае необходимо анализировать дельту, отклонение этой дельты от 1 и есть лажа.
или не от один, а от среднего скажем по соседним 10 (+-5) значениям

[ffldove]

Пока мысли были в сторону метода, аналогичному методу, который предложил ffldove. Т.е. повыхватывать наугад из файла несколько таймкодов, деля отрезок на двое, и таким образом, определить нарушение порядка таймкодов.

то есть в случае "ничего не подсунули" ты получишь тот же линейный перебор только хитрее сделанный. смотреть надо ведь на оба куска отрезка.
используя прошлую аналогию с цифрами, если a[i+m] - a[i] != m, где m==1 - слишком долго, увеличь m, и эта m и будет фактически колличеством вставок которые ты мог не заметить.

Здесь уже нужно смотреть на требуемую точность поиска (25 кадр мы же не видем так что его можно не отслеживать )))), m меньше точность больше и наоборот.

[Warlornhor]

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

[serzh-z]

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

Нельзя.

то есть в случае "ничего не подсунули" ты получишь тот же линейный перебор только хитрее сделанный. смотреть надо ведь на оба куска отрезка.
используя прошлую аналогию с цифрами, если a[i+m] - a[i] != m, где m==1 - слишком долго, увеличь m, и эта m и будет фактически колличеством вставок которые ты мог не заметить.

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

[t.t]

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

Если исходить только из временнЫх меток, то такого алгоритма быть не может. Грубо говоря, количество меток, которые будут проверены и максимальное количество изменённых меток, которые могут проскочить незамеченными, в сумме _всегда_ будут равны длине файла. А для того, чтобы говорить не о максимуме, а о матожидании пропущенных "замен", нужны хотя бы предположения о принципах их разброса; если "от балды", то говорить не о чем.

[serzh-z]

А для того, чтобы говорить не о максимуме, а о матожидании пропущенных "замен", нужны хотя бы предположения о принципах их разброса; если "от балды", то говорить не о чем.

Понятно. Статистики разброса меток, с которой можно было бы свериться при анализе, нет - разброс может быть "от балды", а может и не быть вообще. Собственно подобный ответ тоже устраивает.

переделать метод под задачу

Хотя бы деперь знаю правильное название этого метода. =) Спс.

[Crazy]

Просто линейная проверка не подходит из-за своей тяжеловесности.

Какой критерий тяжеловесности?

[begin2009]

А почему, действительно, не прогнать подряд? Разница (от таймера же!) одинаковая. А скачек будет виден сразу. Если долго - выбирать куски для проверки случайным образом. Но вероятность_полного_успеха=длина_просмотренного/вся_длина.

[serzh-z]

Crazy
begin2009
Это не устраивает заказчика. Скорость работы системы должна быть ненамного ниже той, которая была до введения кода анализа на разрывность таймкодов. Прочитать весь, скажем, 2-гб видеофайл - это слишком накладно.

[begin2009]

А что если подряд, но через 10, 100 (или 1000 - подобрать можно по скорости). Ну в общем пробегать большими шагами. Споткнулся - анализ от последней точки по-подробнее. Но опасность: если очень большой шаг, то можно проморгать склейку внутри.

Добавлено: сморозил глупость. Все-равно при следующем шаге будет скачек.
Добавил-2: В смысле глупость, что можно проморгать. А вот действительно, анализ через определенный промежуток ( к примеру 1000 000). Скачек: от предыдущего анализируем по-чаще (к примеру 10 000). И т.д. Нашли. И от следующей точки опять быстрыми шагами до следующего скачка.

[smaharbA]

Не просче отсортировать по Шеллу или еще как ?

хотя да, не увидел про файл в 2 Гб
т.е. нужна именно "последовательно кусочная" проверка

[Crazy]

serzh-z формат файла позволяет читать только таймы?

[serzh-z]

serzh-z формат файла позволяет читать только таймы?

Да причём тут формат... Что можно прочитать - зависит от используемого SDK, в текущий момент - это Windows Media SDK. Вопрос был в алгоритме, но t.t объяснил уже что без статистики и базы знаний ничего умного не сделаешь. Сейчас ещё смотрю в сторону "золотого сечения".

[ffldove]

serzh-z формат файла позволяет читать только таймы?

Да причём тут формат... Что можно прочитать - зависит от используемого SDK, в текущий момент - это Windows Media SDK. Вопрос был в алгоритме, но t.t объяснил уже что без статистики и базы знаний ничего умного не сделаешь. Сейчас ещё смотрю в сторону "золотого сечения".

ИМХО
В принципе "золотого сечения" лежит тот же общий принцип деления всего отрезка на части и рассмотрения его частей, с той лиш разницей что делиться на части по золотому сечению, в вашем случае от золотого сечения в общем случае выигрыша не будет т.к. точка "лажи" не одна и не известно сколько и где.
По моему мнению в данном конкртеном случае нужно подобрать коэфициент (шаг) который будет завичить от общего обьема файлов и от нужной скорости выполнения задачи.
К примеру задача должна в любом случае выполняться не дольше 10 секунд, тогда файл в 20 минут можно сканить с шагом (если 1 шаг выполняется за 1 секунду), 20/10=2 минуты шаг.
В другом варианте коэфициентом может послужить не шаг а глубина просмотра т.е. колличество делений всего файла на 2, при этом отбрасывая отрезки удовлетворяющие критерию. В этом же варианте получается что у нас в запасе 10 итераций (10 секунд на задачу по 1 секунде итерация). т.е. 10 раз делим сомнительные отрезки на 2.
Это все при условие когда время выполнение алгоритма становиться важнее точности (при каждой итерации точность выше, а в вашем случае мы идем не до заданной точночсти а до заданного времени выполнения).

[begin2009]

По моему мнению в данном конкртеном случае нужно подобрать коэфициент (шаг) который будет завичить от общего обьема файлов и от нужной скорости выполнения задачи.
К примеру задача должна в любом случае выполняться не дольше 10 секунд, тогда файл в 20 минут можно сканить с шагом (если 1 шаг выполняется за 1 секунду), 20/10=2 минуты шаг.
В другом варианте коэфициентом может послужить не шаг а глубина просмотра т.е. колличество делений всего файла на 2, при этом отбрасывая отрезки удовлетворяющие критерию. В этом же варианте получается что у нас в запасе 10 итераций (10 секунд на задачу по 1 секунде итерация). т.е. 10 раз делим сомнительные отрезки на 2.
Это все при условие когда время выполнение алгоритма становиться важнее точности (при каждой итерации точность выше, а в вашем случае мы идем не до заданной точночсти а до заданного времени выполнения).

Вот про это я и толковал в посте №21 может только косноязычно. А вообще кошерно точность заранее задавать. Типа: есть время - просмотрим по-подробнее, нет - пробежимся быстрее, но точность не та.

[serzh-z]

По моему мнению в данном конкртеном случае нужно подобрать коэфициент (шаг) который будет завичить от общего обьема файлов и от нужной скорости выполнения задачи.

Коэффициент планируется настраивать через конфиг, руками админа. В зависимости от используемых, в данной компании, размеров файлов.

[Crazy]

Может лучше от длины видео выбирать?
Использовать метод деления над последовательностью, к которой нет прямого доступа за постоянное время забавно.