Python, реализация очереди

Question

Python, реализация очереди

Рейтинг: 0Ответов: 1Опубликовано: 17.06.2023

Имеется файл заведомо огромный, прочесть полностью нельзя- оперативы если и хватит то мне не простят расточительности. Мне надо забрать из файла последние N строк (что б в дальнейшем усреднить данные в этих строках по N). Если они будут в каком то непоследовательном и неупорядоченном виде то я Ок с этим, главное что б это были точно последние N штук из файла.

Идея моей реализации: для поиска я пользуюсь генератором .readline(). Думаю реализовать очередь, инициализируемую пустой с ограничителем N штук элементов в ней. Списком с использованием pop и insert не хочу пользоваться, поскольку он будет кучу раз перезаписываться в памяти. Поэтому хочу заполнять очередь, как только в ней будет N элементов начну убирать первый и присоединять новый как последний.

Написал класс Line:

class Line:
    def __init__(self, line, child_l=None, child_r=None):
        self.line = line
        self.child_l = child_l
        self.child_r = child_r

Теперь нужен сам class для очереди, которая будет заполняться экземплярами Line с нужными строками. НО! Если это будет какая то очередь а не дерево то встает вопрос рекурсии, а че если N = 1000000000, предел рекурсии и все дела. А если это дерево, то как каждый раз убирать первый? придётся кучу раз его перестраивать.

python дерево структуры-данных очередь

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

В комментариях предложен отличный вариант с collections.deque. Идея в том чтобы читать весь файл построчно в буфер ограниченной длины. В конце в буфере остануться последние n строк:

import collections
import sys


fname = sys.argv[1]
n = int(sys.argv[2])
with open(fname) as f:
    tail = collections.deque(f, n)

print(*tail, sep='', end='')

Можно ли сделать лучше? Можно, если не читать весь файл. Нам нужны несколько строк из конца. Прочитаем кусок файла из конца и сосчитаем в нём строки. Если хватило, выведем их, иначе увеличим кусок в два раза и повторим. Через логарифмическое число попыток задача решена.

Нужно решить следующие проблемы:

чтение только в двоичном режиме. Текстовые файлы обычно в кодировке UTF-8. Она многобайтовая. Если начать читать из середины символа, процедура декодирования выбросит ошибку. Лучше обойтись без обработки этих ошибок.
различные переводы строки, на разных операционных системах. В текстовом режиме Питон сам транслирует окончания строк. У нас режим двоичный, в код вставлена обработка '\n' (Unix, MacOSX) и '\r\n' (Windows).
последняя пустая строка. По правилам хорошего тона текстовый файл должен заканчиваться переводом строки. Если обрабатывать файл по простому - разбивать на строки по разделителю - в списке строк в конце будет пустая строка. Опять-таки Питон её удаляет в текстовом режиме. Нам тоже надо так делать.

import locale
import os
import sys


def get_tail(f, n):
    f.seek(0, 2)
    max_size = f.tell()
    size = 1
    while True:
        if size >= max_size:
            f.seek(0, 0)
            tail = f.read()
            break
        f.seek(-size, 2)
        tail = f.read() 
        assert len(tail) == size
        if tail.count(b'\n') > n + 1:
            break
        size *= 2

    lines = tail.split(b'\n')[-(n + 1):]
    e = locale.getpreferredencoding()
    tail = [
        line.removesuffix(b'\r').decode(e)
        for line in lines
    ]

    if tail[-1] == '':
        tail.pop()
    if len(tail) > n:
        tail.pop(0)

    assert len(tail) <= n
    return tail


def main():
    fname = sys.argv[1]
    n = int(sys.argv[2])

    with open(fname, 'rb') as f:
        tail = get_tail(f, n)

    print(*tail, sep='\n')


main()

Результат стоит усилий. Извлекаем последнюю тысячу строк из файлов разных размеров. Сравните:

число строк     время работы     время работы
в файле            deque       чтения из хвоста

    1_000_000      0.072c           0.031с
   10_000_000      0.476c           0.031с
  100_000_000      4.211c           0.036с
1_000_000_000     43.123c           0.030с

P.S. Быстрее всего решать задачу на уровне операционной системы. В Unix это утилита tail. В Windows в PowerShell есть аналогичная функциональность.

Python, реализация очереди

Ответы