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

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

Давайте посмотрим на пример:

nums1 = [1, 3, 5, 1, 7, 9, 3]

nums2 = [2, 1, 9, 7, 1, 3]

Пересечение между ними:

[1, 1, 9, 7, 3]

У нас есть два экземпляра 1, один экземпляр 7 и один экземпляр 9. 3 появляется в результате только один раз, несмотря на то, что в nums1 встречается дважды, потому что nums2 имеет только один экземпляр 3.

Наивное решение

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

Это будет выглядеть примерно так:

function naiveIntersection(nums1: number[], nums2: number[]): number[] {
    // iterate over nums1
    return nums1.reduce((intersection, valueInNums1) => { 
        // search for the current value in nums2 
        const index = nums2.indexOf(valueInNums1); 
        // if we found one
        if (index > -1) { 
            // push the number to the intersection array
            intersection.push(valueInNums1); 
            // get the number out of nums2
            nums2.splice(index, 1); 
        }
        return intersection;
    }, []);
};

Сложность O(n*m), где n — длина одного массива, а m — длина второго массива. Это потому, что у нас есть вложенный цикл (reduce и indexOf перебирают набор данных).

Оптимизированное решение

Вы могли бы сказать — пусть сначала перебирается более длинный массив, и тогда цикл, который повторяется, будет работать более эффективно. Ну… это по-прежнему O(n*m), поэтому мы не получим большой выгоды от этой стратегии.

Мы можем получить сложность O(n+m), используя другой подход. Если мы пройдемся по nums1 один раз и сохраним счетчик для каждого числа в хэш-таблице (хеш-таблица — причудливое имя для объекта), мы сможем создать массив пересечений за один проход по nums2. Один цикл для nums1 и другой для nums2 — никаких вложенных циклов, лучшая сложность, верно?

Вот реализация для этого:

function optimizedIntersection(nums1: number[], nums2: number[]): number[] {
    // create the frequency map in one sweep of nums1
    const nums1Counter = nums1.reduce((counterMap, value) => {
        counterMap.set(value, counterMap.get(value) ? counterMap.get(value) + 1 : 1);
        return counterMap;
    }, new Map());
    // create the new array in one sweep of nums2
    return nums2.reduce((intersection, val) => {
        if (nums1Counter.get(val)) {
            intersection.push(val);
            nums1Counter.set(val, nums1Counter.get(val) - 1);
        }
        return intersection;
    }, []);
}

Это простое решение намного эффективнее, когда речь идет о более длинных массивах. Сколько? При тестировании на nums1.length => 10 и nums2.length => 1000 разница заключалась в том, что оптимизированное решение работало примерно на 75 % быстрее (рис. 1).

Поиграться с тестом производительности можно здесь (например, изменить размеры массивов).

Решение для небольших чисел

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

function frequencyMap(nums: number[]) {
    const map = new Map<number, number>();
    for (const num of nums) {
        map.set(num, map.has(num) ? map.get(num) + 1 : 1);
    }
    return map;
}
function intersect(nums1: number[], nums2: number[]): number[] {
    const nums1CounterMap = frequencyMap(nums1);
    const nums2CounterMap = frequencyMap(nums2);
    
    let intersection = [];
    
    for (const [num, count] of nums1CounterMap.entries()) {
        if (nums2CounterMap.has(num)) {
            const commonCount = Math.min(count, nums2CounterMap.get(num));
            intersection = [...intersection, ...new Array(commonCount).fill(num)];
        }
    }
    
    return intersection;
};

Магия здесь происходит в цикле, который перебирает nums1CounterMap.entries(). Если nums2CounterMap тоже имеет это число, мы находим, сколько раз оно повторяется, и просто добавляем целый массив повторяющихся чисел за один раз в массив пересечений.

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

Обратите внимание, что мы по-прежнему просматриваем данные O(m+n), поэтому мы не повышали сложность — мы просто использовали трюк для характеристик конкретных возможных данных.

На рисунках 2, 3 и 4 показаны различия при оптимизации определенных характеристик данных. Вы можете видеть, что изменение характеристик данных влияет на то, насколько лучше работают различные алгоритмы. В конце концов, для больших чисел оптимизированное решение и малые числа примерно одинаковы. Играть с цифрами можно здесь.

Очень большой массив num2

Другим вариантом этой проблемы может быть следующее: что произойдет, если nums2 извлекается из файла на диске, который слишком велик для памяти?

Один забавный факт заключается в том, что JavaScript ограничен (по умолчанию) 2 ГБ. Вы можете играть с ним с определенными флагами, но в большинстве случаев крайне не рекомендуется загружать большие наборы данных в память.

Что мы можем сделать тогда? Мы загружаем nums2 порциями и проверяем каждую порцию по сравнению с nums1.

Это означает 2 вещи:

  1. Мы не можем использовать решение Small Numbers, потому что в этом решении мы заранее подсчитываем все числа в nums2. Если все числа в nums2 уникальны, это приведет к тому, что мы снова будем хранить все nums2 в памяти (внутри counterMap).
  2. Нам нужно использовать инструмент, который позволяет нам получать файл по частям. Самый известный инструмент (и единственный, о котором я могу думать, потому что мне ничего больше не нужно) — это: Nodejs Streams.

Как передать файл в Nodejs?

Использовать потоки довольно просто. В случае чтения файла все, что вам нужно сделать, это создать файл readStream с помощью узла fs.createReadStream. Давайте сначала посмотрим код без потоковой передачи:

const fs = require('fs');
const server = require('http').createServer();
server.on('request', async (req, res) => {
    res.writeHead(200);
    fs.readFile('./data2.file', async (err, data) => {
        if (err) throw err;
        res.end(data);
    });
});
server.listen(8000);

Этот код по запросу к серверу читает файл без потока. Попытка прочитать большой файл приведет к зависанию сервера. Я сделал скриншот после ожидания сервера около 20 минут:

Легенды гласят, что этот сервер до сих пор пытается использовать этот файл ;)

Теперь сделать то же самое с потоком просто. Мы заменяем readFile на createDataStream и передаем ему res, чтобы он выводил содержимое файла, который он обрабатывает:

const fs = require('fs');
const server = require('http').createServer();
server.on('request', async (req, res) => {
    res.writeHead(200);
    const data = fs.createReadStream('./data2.file');
    data.pipe(res);
});
server.listen(8000);

На рис. 6 показано, что этот код выполнил задачу за 90 секунд:

Как использовать Streams для выполнения нашей задачи?

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

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

Однако нам придется изменить наши функции… так что давайте возьмем функцию optimizedIntersection и используем ее.

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

  1. Создайте карту частот nums1
  2. Начать потоковую передачу nums2 из файла
  3. В каждом фрагменте перебирайте текущий фрагмент и добавляйте пересекающиеся числа.
  4. Для простоты мы будем запускать это до тех пор, пока поток не закончится.

Итак, наша функция optimizedIntersection будет выглядеть так:

function optimizedIntersection(nums1: Number[], nums2Path: string) {
    // create the frequency map in one sweep of nums1
    const nums1Counter = frequencyMap(nums1);
    // create the new array while reading nums2 from file
    const nums2FileStream = fs.createReadStream(nums2Path);
    let intersection = []; // the array
    // listen to new chunks coming in and add the relevant elements to the array
    nums2FileStream.on('data', (data) => {
        const nums2 = data.toJSON().data;
        const chunkIntersection = nums2.reduce((intersection, val) => {
            if (nums1Counter.get(val)) {
                intersection.push(val);
                nums1Counter.set(val, nums1Counter.get(val) - 1);
            }
            return intersection;
        }, []);
        intersection = [...intersection, ...chunkIntersection];
    });
    
    // when we are done, we can log it or do anything else we want
    nums2FileStream.on('end', function() {
        console.log('Finished streaming stuff: ', intersection);
    });
    // we now return the stream where users can listen to some event and on stream end...
    return nums2FileStream;
}

Краткое содержание

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

В этой статье мы увидели, как классически решить проблему пересечения двух массивов. Решение O(m*n) было оптимизировано до O(m+n). Кроме того, оптимизацию можно было бы сделать лучше, если бы мы знали, как могут выглядеть наши данные. Например, есть решение, оптимизированное для случая отсортированных массивов.

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

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

Спасибо Miki Ezra Stanger за очень добрый и полезный отзыв.

Избранное фото Денис Невожай на Unsplash