Задачи с собеседований: считаем слова в файле

В процессе трудоустройства на должность PHP-разработчика вы можете столкнуться с довольно популярной задачей, на которой любят «ловить» многих кандидатов. Это задача подсчёта слов, которая имеет довольно много вариаций. Мы рассмотрим ту из них, которая освещает наибольшее количество подводных камней. Поговорим про yield, потоковое чтение и расход памяти.

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

Как и в большинстве случаев, бросаться за написание кода сразу не стоит. Надо немного порассуждать о тонкостях выполнения задачи. Именно здесь отваливаются наиболее лютые предположения о реализации вместе с их кандидатами. Кто-то начинает строить базу данных, кто-то пытается включать in-memory хранилище. Ничего подобного здесь не будет. Только консоль — только хардкор!

Теперь подумаем о том, как будет обрабатываться файл. Решение о чтении данных из файла в одну большую строку довольно быстро отметут. Представьте, что вам надо будет обрабатывать файлы с текстом по несколько мегабайт (а для текста это уже довольно много и повлечёт за собой большой расход памяти). Поэтому здесь будет довольно неплохо вспомнить о том, что PHP предлагает инструменты чтения текстовых файлов побайтно. А это значит, что мы будем хранить в памяти только текущий байт из файла для того, чтобы с ним что-то сделать на уровне логики.

while($data = fread($handler, 1)){
    // тут будет происходить некая логическая магия
}

Теперь мы можем поговорить про логику. Возвращаясь в начало решения задачи, неплохим маркером будет спросить: «А что есть слово?». Можно делить слова по пробелам, знакам препинания, переводам строки и пр. Разные компании могут дать разные вариации решения. Можно просто перечислить символы, которые будут считаться разделителями, а можно написать регулярное выражение, которое будет определять, является ли символ разделителем (то есть он не является буквой или цифрой). В регулярке это будет выражаться довольно простой формой:

\W

Теперь, когда мы определились с вводными, можно описать логику каждой итерации: 1. До начала цикла создаём переменную, которая будет накапливать текущее слово. 2. Читаем байт данных из файла. 3. Проверяем его на равенство разделителю. 4. Если он не равен разделителю, добавляем байт в переменную-накопитель. 5. Если это разделитель, то фиксируем слово и отдаём его в массив всех слов для подсчёта.

Должно получиться нечто подобное

public function readFile(){
        $handler = fopen($this->fileLocation, "r");

        $word = '';
        while($data = fread($handler, 1)){
            if(preg_match("/\W/", $data)){
                if(strlen(trim($word)) > 0 && !preg_match("/\W/", trim($word)))
                    // здесь надо передавать слово в массив накопления

                $word = '';
            }
            else{
                $word .= $data;
            }
        }

        // если последнее накопленное слово непустое, то его тоже надо отправлять в массив
        if(strlen(trim($word)) > 0 && !preg_match("/\W/", trim($word)))
            // здесь надо передавать слово в массив накопления


        fclose($handler);
}

И здесь появляется новая подзадача — как собирать массив слов для последующего составления чарта. Можно, конечно, собрать его внутри метода и передать дальше в метод сортировки. Но тогда мы начинаем чрезмерно расходовать память на хранение лишних дублирующихся данных. Если мы говорим про современные версии PHP, то в PHP 7 появляется такой замечательный инструмент, как генераторы (yield). Они будут отдавать данные по мере поступления. А обработка этого «поступления» будет организована итератором, что в свою очередь позволит в один момент времени работать только с одним словом. Поэтому давайте добавим в код эту прекрасную конструкцию.

public function readFile(){
        $handler = fopen($this->fileLocation, "r");

        $word = '';
        while($data = fread($handler, 1)){
            if(preg_match("/\W/", $data)){
                if(strlen(trim($word)) > 0 && !preg_match("/\W/", trim($word)))
                    yield trim($word);

                $word = '';
            }
            else{
                $word .= $data;
            }
        }

        // если последнее накопленное слово непустое, то его тоже надо отправлять в массив
        if(strlen(trim($word)) > 0 && !preg_match("/\W/", trim($word)))
            yield trim($word);

        fclose($handler);
}

Теперь, когда мы собрали метод чтения файла в оптимальной манере, т. е. организовав постепенное чтение документа, можно реализовать сбор и подсчёт слов. Поскольку наш метод readFile не возвращает привычный всем результат через return, а использует генераторы, то для обработки его результатов нам понадобится итератор. Далее этот итератор будет обрабатывать каждое новое сформированное генератором слово, производя подсчёт вхождений. Здесь уже можно собирать результат в массив (хотя, можно заморочиться и с SPL-структурами, что на деле может не дать выигрыш, но это неточно). В качестве ключа в массиве будем использовать само слово, благо в UTF-8 в PHP можно положить туда хотя бы и кириллицу. Значением же будет количество вхождений, что даёт нам массив пар «Слово — Количество вхождений».

class WordsCount
{
    private $wordsChart;
    private $reader;

    public function __construct($fileAddress)
    {
        $this->reader = new FileReader($fileAddress);
        $this->wordsChart = [];
    }

    public function countWords()
    {
        $iterator = $this->reader->readFile();

        foreach ($iterator as $item){
            // кладём слово в массив
            $count = 1;

            if(array_key_exists($item, $this->wordsChart)){
                $count = $this->wordsChart[$item] + 1;
            }

            $this->wordsChart[$item] = $count;
        }
    }
}

Дальше остаётся дело за малым — отсортировать массив по убыванию значений и взять первые пять штук. Здесь вы можете блеснуть знаниями в сортировках, либо можете воспользоваться встроенной функцией arsort, которая использует реализацию алгоритма быстрой сортировки, также известной как сортировка Хоара.

    public function getTopFive(){
        arsort($this->wordsChart);
        return array_slice($this->wordsChart, 0, 5);
    }

Основным преимуществом разработанной логики будет постоянный и небольшой расход памяти. Для примера на моей виртуалке c 1 ядром и 2 гигами оперативной памяти скрипт в пике забирает 0,7 мегабайта RAM вне зависимости от размера файла. К минусам алгоритма точно нужно отнести время его работы, которое следует из побайтного чтения. Время можно сократить, если увеличить читаемый за одну итерацию пакет данных, но тогда будет меняться алгоритм определения слова. Поэтому решение такой задачки — совсем другая история. Если создадите такое решение, присылайте ссылки в комментарии!

Код решения доступен на GitHub.

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