Более быстрый способ найти дубликаты, обусловленные временем

Question

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

Я реализовал этот фильтр с помощью AWK и работают очень хорошо, но мне нужно решение гораздо быстрее:

 
# Generar lista de Duplicados 
awk 'BEGIN { 
FS="," 
} 
/OK/ { 
    old[$8] = f[$8]; 
    f[$8] = mktime($4, $3, $2, $5, $6, $7); 
    x[$8]++; 
} 
/OK/ && x[$8]>1 && f[$8]-old[$8] 

Any suggestions? Are there ways to improve the environment (preloading the file or someting like that)?
 

The input file is already sorted.
 

With the corrections suggested by jj33 I made a new version with better treatment of dates, still maintaining a low profile for incorporating more operations:
 


awk 'BEGIN { 
    FS=","; 
    SECSPERMINUTE=60; 
    SECSPERHOUR=3600; 
    SECSPERDAY=86400; 
    split("0 31 59 90 120 151 181 212 243 273 304 334", DAYSTOMONTH, " "); 
    split("0 366 731 1096 1461 1827 2192 2557 2922 3288 3653 4018 4383 4749 5114 5479 5844 6210 6575 6940 7305", DAYSTOYEAR, " "); 
} 
/OK/ { 
    old[$8] = f[$8]; 
    f[$8] = mktime($4, $3, $2, $5, $6, $7); 
    x[$8]++; 
} 
/OK/ && x[$8]>1 && f[$8]-old[$8] 2) && (((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0))) { 
     d2m = d2m + 1; 
    } 
    d2y = DAYSTOYEAR[ y - 1999 ]; 
    return ss + (mm*SECSPERMINUTE) + (hh*SECSPEROUR) + (d*SECSPERDAY) + (d2m*SECSPERDAY) + (d2y*SECSPERDAY); 
} 
' 

Answer 1

Если файл данных содержит все записи (т.е. она включает в себя записи, которые не имеют dupicate идентификаторы в пределах файл), вы можете предварительно обработать его и создать файл, содержащий только записи с дубликатом (ids).

Если это так, это уменьшит размер файла, который необходимо обработать с помощью вашей программы AWK.

Answer 2

Как сортируется входной файл? Например, файл cat | сортировать или сортировать по отдельному определенному полю или по нескольким полям? Если несколько полей, какие поля и какой порядок? Похоже, часовые поля - это 24-часовые часы, а не 12, верно? Все поля даты/времени заполнены нулями (будет ли 9am «9» или «09»?)

Без учета производительности похоже, что ваш код имеет проблемы с границами месяца, поскольку он предполагает, что все месяцы составляют 30 дней длинный. Возьмите две даты 2008-05-31/12: 00: 00 и 2008-06-01: 12: 00: 00. Это 24 часа друг от друга, но ваш код дает одинаковый код времени для обоих (63339969600)

Answer 3

Думаю, вам нужно будет учитывать високосные годы. Я не делал математику, но я думаю, что в високосном году с жестким кодом в 28 дней для feb сравнение полудня с 2/29 и полудня на 3/1 приведет к тому же дублирующему штампу времени, что и раньше , Хотя похоже, что вы этого не реализовали. Как вы его реализовали, я думаю, что у вас все еще есть проблема, но это между датами 12/31 от $ leapyear и 1/1 $ leapyear + 1.

Я думаю, вы также можете столкнуться с некоторыми конфликтами во время изменения времени, если ваш код должен обрабатывать временные зоны, которые обрабатывают их.

Файл действительно не сортируется ни при каких обстоятельствах. Я предполагаю, что поле $ 1 - это какой-то статус («ОК», который вы проверяете). Таким образом, он сортируется по статусу записи, затем по Дню, затем МЕСЯЦ, ГОД, ЧАСЫ, МИНУТЫ, СЕКУНДЫ. Если бы это был год, месяц, день, я думаю, там могут быть некоторые оптимизации. Все еще может быть, но мой мозг идет в другом направлении прямо сейчас.

Если имеется небольшое количество дубликатов ключей по отношению к общему количеству строк, я думаю, что лучше всего уменьшить файл, который ваш скрипт awk работает, чтобы просто дублировать ключи (как David said). Вы также можете предварительно обработать файл, поэтому единственными строками являются строки/OK /. Я думаю, что я сделаю это с конвейером, где первый скрипт awk будет печатать только строки с дублирующимися идентификаторами, а второй скрипт awk в основном тот, что выше, но оптимизирован, чтобы не искать/OK/и с учетом того, что любой присутствующий ключ является дублирующий ключ.

Если вы знаете заранее, что все или большинство линий будут иметь повторяющиеся ключи, это, вероятно, не стоит возиться. Я бы кусала пулю и записывала ее в C. Tons больше строк кода, намного быстрее, чем awk-скрипт.

Answer 4

На многих сайтах unixen вы можете сортировать сортировку по определенному столбцу или полю. Поэтому, сортируя файл по идентификатору, а затем по дате, вам больше не нужно сохранять ассоциативный массив, когда вы в последний раз видели каждый идентификатор. Весь контекст находится в порядке файла.

На моем Mac, который имеет GNU рода, это:

sort -k 8 <input.txt> output.txt 

сортировать по полю ID. Вы можете сортировать и на втором поле, говоря (например) 8,3 вместо этого, но ТОЛЬКО 2 поля. Таким образом, временная метка time_t в стиле unix может быть плохой идеей в файле - ее легко сортировать и экономит все эти расчеты даты. Кроме того, (опять же, по крайней мере, в GNU awk) есть mktime function, который делает time_t для вас из компонентов.

Answer 5

@AnotherHowie, я думал, что вся препроцессия может быть выполнена с помощью сортировки и uniq. Проблема в том, что данные OP, по-видимому, разделены запятой и (Solaris 8) uniq не позволяет вам каким-либо образом указывать разделитель записей, поэтому не было супер чистого способа выполнить предварительную обработку с использованием стандартных инструментов unix. Я не думаю, что это будет быстрее, так что я не собираюсь искать точные варианты, но вы могли бы сделать что-то вроде:

cut -d, -f8 <infile.txt | sort | uniq -d | xargs -i grep {} infile.txt >outfile.txt 

Это не очень хорошо, потому что он выполняет Grep для каждой строки, содержащей дублирующий ключ. Вы могли бы, вероятно, массировать вывод uniq в одно регулярное выражение для подачи на grep, но преимущество было бы известно только в том случае, если в сообщениях OP ожидалось отношение строк, содержащих подозрительные повторяющиеся ключи, к общим строкам в файле.

Answer 6

Это звучит как работа для реальной базы данных. Даже что-то вроде SQLite, возможно, поможет вам в этом. Большая проблема, которую я вижу, - это ваше определение «в течение 4 часов». Это проблема с скользящим окном, а это означает, что вы не можете просто квантовать все данные на 4-часовые сегменты ... вам нужно вычислить все «ближайшие» элементы для каждого другого элемента отдельно. Тьфу.