Поиск алгоритма
Да это верно. Загрузка файла сделана через запрос POST, и запросы в целом подвергаются тайм-ауту. Необходимо смочь реконфигурировать среду для более долгого тайм-аута запроса.
4 ответа
Очень простой алгоритм будет выглядеть следующим образом (в Python, но не должно быть проблем с переводом в Javascript):
def check(a, width):
'''check if there is a repeated pattern of length |width|'''
for j in range(width, len(a)):
if a[j] != a[j-width]:
return False
return True
def repeated(a):
'''find the shortest repeated pattern'''
for width in range(1, len(a)):
if check(a, width):
return a[:width]
return []
Это также должно быть довольно эффективным, поскольку в большинстве случаев цикл в check () вернется прямо на первой итерации, так что вы в основном выполняете итерацию по списку только один раз.
Попробуйте создать свою первоначальную группировку, начиная с самого начала, добавляя номер в группу, пока не дойдете до номера, который совпадает с первым в группе (предыдущий номер завершает шаблон). Используйте это как свой тестовый образец и продолжайте, сопоставляя его, пока не получите отказ. Если вы сопоставите всю коллекцию (с вашей специальной обработкой конечного шаблона), это один кандидат. Вернитесь к тому месту, где вы нашли первое совпадение, затем продолжайте создавать свою группу, пока не дойдете до другого числа, совпадающего с первым в вашем шаблоне. Повторяйте, заменяя вашего кандидата всякий раз, когда вы найдете более длинного. Когда ваш узор такой же длины, что и остановка сбора (этот не совпадает). Если у вас есть кандидат, это будет самый длинный образец.
Вы можете оптимизировать поиск, заметив, что длина вашей коллекции должна быть кратной длине вашего шаблона. Если размер вашей коллекции является простым, единственная возможная длина шаблона - 1, то есть все элементы должны быть идентичны!
Я думаю, вы могли бы подойти к этой проблеме, рассматривая период шаблона. Период последовательности A [] - это наименьшее целое число T такое, что A [i + T] = A [i] для всех i. В вашем случае, когда вы найдете период T, все готово, поскольку A [0..T-1] - это самый короткий шаблон, который вы ищете. Итак, начните с наименьшего возможного периода T = 1 и проверьте, удовлетворяет ли последовательность свойству периодичности. Если да, то все готово (на самом деле это происходит только тогда, когда все элементы идентичны). Для любого большего T вам необходимо проверить, является ли A [i + T] = A [i] для i = 0..A.len-T-1. Это просто простой цикл.