Yandex Contest как избавиться от ошибки Memory Limit/Time Limit?

Question

[dmitriyivvvv]

Имеется следующая задача: yandex contest
Имееются 2-а решения:

//Решение 1:
const fs = require('fs');
const readline = require('readline');

const rl = readline.createInterface({
  input: fs.createReadStream('input.txt'),
  terminal: false
});

let prev;

rl.once('line', () => {
  rl.on('line', line => {
    if (line != prev) fs.appendFileSync('output.txt', `${prev ? '\n' : ''}${prev = line}`);
  });
});

//Решение 2:
const fs = require('fs');
const readline = require('readline');

const rl = readline.createInterface({
  input: fs.createReadStream('input.txt'),
  terminal: false
});

let prev;

rl.once('line', () => {
  rl.on('line', line => {
    if (line != prev) process.stdout.write(`${prev ? '\n' : ''}${prev = line}`);
  });
});

Проблема 1-го решения - превышен лимит времени(1s), а второго лимит памяти(20 мб). Как можно оптимизировать этот код?

Comments

[longclaps]

Имеется следующая задача: yandex contest

У меня нет желания регистрироваться на Я-контесте, и условия задачи я не вижу. Остаётся только догадываться )

[Ernest Faizullin]

то есть вы сами не пробовали оптимизировать, а сразу на тостер

на конкурсе должны побеждать сами конкурсанты, без помощи команды, иначе теряется смысл конкурса

[dmitriyivvvv]

longclaps,
Условия задачи:
Удаление дубликатов

Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.

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

Формат ввода
Первая строка входного файла содержит единственное число n, n ≤ 1000000.

На следующих n строк расположены числа — элементы массива, по одному на строку. Числа отсортированы по неубыванию.

Формат вывода
Выходной файл должен содержать следующие в порядке возрастания уникальные элементы входного массива.

Ввод
5
2
4
8
8
8

Вывод
2
4
8

[Ernest Faizullin]

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

[dmitriyivvvv]

Ernest Faizullin, Это просто пример вопросов которые задают на собеседовании, решаю для себя, решил (5/6) и застрял только на этом. Это не настоящее тестовое задание

[Lynn «Кофеман»]

В первом случае очевидно, что appendFileSync это очень дорого и долго.

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

Answer 1

[longclaps]

Псевдокод

открыл файл
a = прочитал одно число
пока файл не кончился
    b = прочитал одно число
    если a < b
        вывел a
        a = b
вывел a

Comments

[dmitriyivvvv]

Мой код делает тоже самое, читает файл строка за строкой и выводит либо сразу в process.stdout либо в output.txt. И думаю != будет лучше так как это строки и например '90' < '100' //false поэтому придется приводить их к числам(точнее один, остальной и так приведется к числу) +a < b не думаю что это быстрее

[longclaps]

dmitriyivvvv, ваш первый вариант использует блокирующий ввод-вывод. Попробуйте так

const sz = 100
buf = []
открыл файл
a = прочитал одно число
пока файл не кончился
    b = прочитал одно число
    если a < b
        buf.push(a)
        if (buf.lengh == sz)
                 вывел buf
                 buf = []
        a = b
buf.push(a)
вывел buf

[dmitriyivvvv]

longclaps, Спасибо за подсказку, помогла оптимизация первого решения, вместо обращения к выходному файлу каждый раз, я сделал это только при str.length > 100, что собственно ускорило решение в 2 раза, вот решение:

const fs = require('fs');
const readline = require('readline');

const rl = readline.createInterface({
  input: fs.createReadStream('input.txt'),
  terminal: false
});

let str = '', prev;

rl.once('line', () => {
  rl.on('line', line => {
    if (line != prev) str += `${prev = line}\n`;
    if (str.length > 100) {
      fs.appendFileSync('output.txt', str);
      str = '';
    }
  }).on('close', () => fs.appendFileSync('output.txt', str));
});

[origami1024]

dmitriyivvvv, длину буфера можно делать побольше чем 100. 150000 - около оптимального. Суммарное время выполнения с 100 у меня было 330мс, с 150000 - 130мс

Answer 2

[krong]

решение фактически сводится только к тому что бы удалить дубли из входного массива
using System;
using System.Linq;

namespace Test {
class Program {

static void Main() {
int n = Convert.ToInt32(Console.ReadLine());
int i = 0;
int[] mass = new int[n];
while (n > 0) {
mass[i] = Convert.ToInt32(Console.ReadLine());
n--; i++;
}
mass = mass.Distinct().ToArray();
GC.SuppressFinalize(n); GC.SuppressFinalize(i);
GC.Collect();
foreach (var item in mass) {
Console.WriteLine(item);
}
}
}
}