Самый эффективный способ поиска последних x строк файла в python

Question

У меня есть файл, и я не знаю, насколько большим он будет (он может быть довольно большим, но размер будет сильно различаться). Я хочу найти последние 10 строк или около того, чтобы увидеть, соответствует ли какая-либо из них строке. Мне нужно сделать это как можно быстрее и эффективнее, и мне было интересно, есть ли что-нибудь лучше, чем:

s = "foo"
last_bit = fileObj.readlines()[-10:]
for line in last_bit:
    if line == s:
        print "FOUND"

Answer 1

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

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

По сравнению с нерестом "хвост", он самодостаточен. (Но «хвост» лучше, если он у вас есть.)

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

import os

def reversed_lines(file):
    "Generate the lines of file in reverse order."
    part = ''
    for block in reversed_blocks(file):
        for c in reversed(block):
            if c == '\n' and part:
                yield part[::-1]
                part = ''
            part += c
    if part: yield part[::-1]

def reversed_blocks(file, blocksize=4096):
    "Generate blocks of file's contents in reverse order."
    file.seek(0, os.SEEK_END)
    here = file.tell()
    while 0 < here:
        delta = min(blocksize, here)
        here -= delta
        file.seek(here, os.SEEK_SET)
        yield file.read(delta)

Для использования по запросу:

from itertools import islice

def check_last_10_lines(file, key):
    for line in islice(reversed_lines(file), 10):
        if line.rstrip('\n') == key:
            print 'FOUND'
            break

Редактировать: изменил карту () на itertools.imap () в head (). Редактировать 2: упрощенный reversed_blocks (). Редактировать 3: избегать повторного сканирования хвоста для новых строк. Редактировать 4: переписал reversed_lines (), потому что str.splitlines () игнорирует финальный '\ n', как заметил BrianB (спасибо).

Обратите внимание, что в очень старых версиях Python конкатенация строк в цикле занимает квадратичное время. CPython, по крайней мере в последние несколько лет, автоматически решает эту проблему.

Answer 2

# Tail
from __future__ import with_statement

find_str = "FIREFOX"                    # String to find
fname = "g:/autoIt/ActiveWin.log_2"     # File to check

with open(fname, "r") as f:
    f.seek (0, 2)           # Seek @ EOF
    fsize = f.tell()        # Get Size
    f.seek (max (fsize-1024, 0), 0) # Set pos @ last n chars
    lines = f.readlines()       # Read to end

lines = lines[-10:]    # Get last 10 lines

# This returns True if any line is exactly find_str + "\n"
print find_str + "\n" in lines

# If you're searching for a substring
for line in lines:
    if find_str in line:
        print True
        break

Answer 3

Если вы используете Python в системе POSIX, вы можете использовать 'tail -10' для получения последних нескольких строк. Это может быть быстрее, чем писать собственный код Python, чтобы получить последние 10 строк. Вместо того, чтобы открывать файл напрямую, откройте канал с помощью команды «tail -10 filename». Если вы уверены в выводе журнала, хотя (например, вы знаете, что никогда нет очень длинных строк длиной в сотни или тысячи символов), используйте один из подходов «прочитайте последние 2 КБ» в списке будет хорошо.

Answer 4

Я думаю, что чтение последних 2 КБ или около того файла должно гарантировать, что вы получите 10 строк, и не должно быть слишком много ресурсов.

file_handle = open("somefile")
file_size = file_handle.tell()
file_handle.seek(max(file_size - 2*1024, 0))

# this will get rid of trailing newlines, unlike readlines()
last_10 = file_handle.read().splitlines()[-10:]

assert len(last_10) == 10, "Only read %d lines" % len(last_10)

Answer 5

Вот версия, использующая mmap, которая кажется довольно эффективной. Большим плюсом является то, что mmap автоматически обработает для вас требования к файлам подкачки памяти.

import os
from mmap import mmap

def lastn(filename, n):
    # open the file and mmap it
    f = open(filename, 'r+')
    m = mmap(f.fileno(), os.path.getsize(f.name))

    nlcount = 0
    i = m.size() - 1 
    if m[i] == '\n': n += 1
    while nlcount < n and i > 0:
        if m[i] == '\n': nlcount += 1
        i -= 1
    if i > 0: i += 2

    return m[i:].splitlines()

target = "target string"
print [l for l in lastn('somefile', 10) if l == target]

Answer 6

Я столкнулся с этой проблемой, анализируя последний час БОЛЬШИХ файлов системного журнала, и использовал эту функцию с сайта рецептов activestate ... (http://code.activestate.com/recipes/439045/)

!/usr/bin/env python
# -*-mode: python; coding: iso-8859-1 -*-
#
# Copyright (c) Peter Astrand <astrand@cendio.se>

import os
import string

class BackwardsReader:
    """Read a file line by line, backwards"""
    BLKSIZE = 4096

    def readline(self):
        while 1:
            newline_pos = string.rfind(self.buf, "\n")
            pos = self.file.tell()
            if newline_pos != -1:
                # Found a newline
                line = self.buf[newline_pos+1:]
                self.buf = self.buf[:newline_pos]
                if pos != 0 or newline_pos != 0 or self.trailing_newline:
                    line += "\n"
                return line
            else:
                if pos == 0:
                    # Start-of-file
                    return ""
                else:
                    # Need to fill buffer
                    toread = min(self.BLKSIZE, pos)
                    self.file.seek(-toread, 1)
                    self.buf = self.file.read(toread) + self.buf
                    self.file.seek(-toread, 1)
                    if pos - toread == 0:
                        self.buf = "\n" + self.buf

    def __init__(self, file):
        self.file = file
        self.buf = ""
        self.file.seek(-1, 2)
        self.trailing_newline = 0
        lastchar = self.file.read(1)
        if lastchar == "\n":
            self.trailing_newline = 1
            self.file.seek(-1, 2)

# Example usage
br = BackwardsReader(open('bar'))

while 1:
    line = br.readline()
    if not line:
        break
    print repr(line)

Он работает очень хорошо и намного эффективнее, чем что-либо вроде fileObj.readlines () [- 10:], который заставляет python считывать весь файл в память, а затем отбрасывает последние десять строк.

Answer 7

Кажется, я помню, как адаптировал код из этого поста в блоге от Ману Гарга , когда мне пришлось сделать что-то подобное.

Answer 8

Если вы работаете в Unix, os.popen("tail -10 " + filepath).readlines(), вероятно, будет самым быстрым способом. В противном случае это зависит от того, насколько вы хотите, чтобы он был надежным. Методы, предложенные до сих пор, все рухнут, так или иначе. Для надежности и скорости в наиболее распространенном случае вам, вероятно, понадобится что-то вроде логарифмического поиска: используйте file.seek, чтобы перейти к концу файла минус 1000 символов, прочитайте его, проверьте, сколько строк в нем содержится, затем до EOF минус 3000 символов. прочитайте 2000 символов, посчитайте строки, затем EOF минус 7000, прочитайте 4000 символов, посчитайте строки и т. д., пока не получите столько строк, сколько вам нужно. Но если вы точно знаете, что он всегда будет запускаться для файлов с разумной длиной строки, это может вам и не понадобиться.

Вы также можете найти вдохновение в исходном коде для команды unix tail.

Answer 9

Вы также можете считать строки при обратном просмотре файла, вместо того, чтобы угадывать смещение в байтах.

lines = 0
chunk_size = 1024

f = file('filename')
f.seek(0, 2)
f.seek(f.tell() - chunk_size)

while True:
    s = f.read(chunk_size)
    lines += s.count('\n')
    if lines > NUM_OF_LINES:
        break
    f.seek(f.tell() - chunk_size*2)

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

Answer 10

Вы можете читать куски по 1000 байтов или около того с конца файла в буфер, пока у вас не будет 10 строк.