無限再帰が発生し、最終的にスタックが深すぎると、終了する実行トレースを含むログがあります。より大きなラインブロック内に十分なラインと有効な再帰が含まれているため、繰り返される最大のブロックを識別することは困難です。この決定を下すために一部の行をフィルタリングする必要がある固有の事項はありません。
ファイル名/パス名を指定した場合、最大行セットのみを出力する良い1行/スクリプト（POSIX / OS X、Linux、およびOS Xで動作することが望ましい）は何ですか？
説明：私の例では、ログ・ファイルには432003行と80Mがあります。
$ wc -l long_log.txt
432003 long_log.txt
$ du -sm long_log.txt
80 long_log.txt
同様の入力ファイルを作成するには、これを試してください。投稿ありがとうございます。ここランダムな単語を含むファイルを作成する方法。
ruby -e 'a=STDIN.readlines;200000.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > head.txt
ruby -e 'a=STDIN.readlines;2.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > recurrence1.txt
ruby -e 'a=STDIN.readlines;20.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > recurrence2.txt
ruby -e 'a=STDIN.readlines;200000.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > tail.txt
cat head.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt tail.txt > log.txt
cat recurrence1.txt recurrence1.txt recurrence2.txt > expected.txt
その結果：
$ wc -l log.txt
400050 log.txt
$ du -sm log.txt
89 log.txt
これにより、次のことができます。
$ recurrence log.txt > actual.txt
$ diff actual.txt expected.txt
$
同じ長さの他のブロックを識別しても大丈夫です。
$ cat recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt > expected2.txt
$ diff actual.txt expected2.txt
$
2.6GHzクアッドコアIntel Core i7とOS X / Linuxの16GB RAMを使用して、10秒以内に期待した結果を見つけたらと思います。
ベストアンサー1
解決策は次のとおりです。TXR言語。
@(next :args)
@(bind rangelim nil)
@(block)
@ (cases)
@filename
@ (maybe)
@rlim
@ (set rangelim @(int-str rlim))
@ (end)
@ (eof)
@ (or)
@ (output)
arguments are: filename [ range-limit ]
@ (end)
@ (fail)
@ (end)
@(end)
@(do
(defun prefix-match (list0 list1)
(let ((c 0))
(each ((l0 list0)
(l1 list1))
(if (not (equal l0 l1))
(return c))
(inc c))
c))
(defun line-stream (s)
(let (li) (gen (set li (get-line s)) li)))
(let* ((s (line-stream (open-file filename "r")))
(lim rangelim)
(s* (if lim s nil))
(h (hash :equal-based))
(max-len 0)
(max-line nil))
(for ((ln 1)) (s) ((set s (rest s)) (inc ln))
(let ((li (first s)))
(let ((po (gethash h li))) ;; prior occurences
(each ((line [mapcar car po])
(pos [mapcar cdr po]))
(let ((ml (prefix-match pos s)))
(cond ((and
(= ml (- ln line))
(> ml max-len))
(set max-len ml)
(set max-line line))))))
(pushhash h li (cons ln s))
(if (and lim (> ln lim))
(let* ((oldli (first s*))
(po (gethash h oldli))
(po* (remove-if (op eq s* (cdr @1)) po)))
(if po*
(sethash h oldli po*)
(remhash h oldli))
(set s* (cdr s*))))))
(if max-line
(format t "~a line(s) starting at line ~a\n" max-len max-line)
(format t "no repeated blocks\n"))))
このプログラムはほぼ完全にTXRに組み込まれたLisp方言で構成されています。ここでのアプローチは、ファイルの各行をハッシュテーブルに保存することです。ファイルのどの時点でも、私たちはハッシュテーブルに「この行を以前にどこで見たことがありますか？」と尋ねることができます。その場合は、その場所で始まるファイルと現在の場所で始まる行を比較できます。一致が前の位置から現在の位置に拡張される場合、これは連続した一致があることを意味します。前の位置から現在の行までのすべてのN行は、現在の行から始まり、N行と一致します。私たちがしなければならないのは、すべての候補地の中で最も長い一致を生成する場所を見つけることです。 （接続がある場合は、最初の接続のみが報告されます。）
見て、Xorgのログファイルに2行が繰り返しリストされています。
$ txr longseq.txr /var/log/Xorg.0.log
2 line(s) starting at line 168
168行目には何がありますか？この4行は次のとおりです。
[ 19.286] (**) VBoxVideo(0): Built-in mode "VBoxDynamicMode": 56.9 MHz (scaled from 0.0 MHz), 44.3 kHz, 60.0 Hz
[ 19.286] (II) VBoxVideo(0): Modeline "VBoxDynamicMode"x0.0 56.94 1280 1282 1284 1286 732 734 736 738 (44.3 kHz)
[ 19.286] (**) VBoxVideo(0): Built-in mode "VBoxDynamicMode": 56.9 MHz (scaled from 0.0 MHz), 44.3 kHz, 60.0 Hz
[ 19.286] (II) VBoxVideo(0): Modeline "VBoxDynamicMode"x0.0 56.94 1280 1282 1284 1286 732 734 736 738 (44.3 kHz)
一方、パスワードファイルはすべて一意です。
$ txr longseq.txr /etc/passwd
no repeated blocks
2番目の引数を追加してプログラムを高速化できます。最も長い反復シーケンスが50行を超えないことがわかっている場合は、これを指定できます。これにより、プログラムは50行以上を逆追跡しません。また、メモリ使用量はファイルサイズではなく範囲サイズに比例するため、反対方向に勝ちます。