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

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] 

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

<p>The input file is already sorted.</p>

<p>With the corrections suggested by <a href="https://stackoverflow.com/questions/6475/faster-way-to-find-duplicates-conditioned-by-time#6869">jj33</a> I made a new version with better treatment of dates, still maintaining a low profile for incorporating more operations: </p>


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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Answer 6

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

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