C# Помогите оптимизировать приложение, в погоне за скоростью не уложился в память, memory limit ecx
Что где можно позакрывать и как лучше? Никогда этим не занимался, всегда хватало памяти
Задача:
Ограничение времени 1.5 секунд
Ограничение памяти 64Mb
Ввод input.txt
Вывод output.txt
Дано целое положительное число k. Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл "1", если в последовательности есть два числа сумма, которых равна значению k или "0" если таких нет.
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<Int32> m = new List<Int32>();
Int32 k = 0;
using (StreamReader sr = new StreamReader("input.txt"))
{
k = Convert.ToInt32(sr.ReadLine());
m = sr.ReadLine().Split(' ').Select(Int32.Parse).ToList();
// m = s.Cast<Int32>();
sr.Close();
}
m.Sort();
bool flag = false;
//убираем большие числа
IEnumerable<Int32> queryOptim;
if (k % 2 == 0) // чётное
{
queryOptim =
from i in m
where i < k
select i;
m = queryOptim.ToList();
List<Int32> rep = new List<Int32>();//отдельно прогоним повторы
var set = new HashSet<Int32>();
foreach (Int32 i in m)
{
if (!set.Add(i))
rep.Add(i);
}
foreach (Int32 i in rep)
{
if (i+i==k)
{
using (StreamWriter sw = new StreamWriter("output.txt"))
{
sw.WriteLine(1);
}
return;
}
}
queryOptim =
from i in m
where i % 2 == 0
select i;
List<Int32> m1 = queryOptim.Distinct().ToList(); //все чётные
queryOptim =
from i in m
where i % 2 == 1
select i;
m = queryOptim.Distinct().ToList(); //все нечётные
int max = m.Count();
for (int i = 0; i < max; i++)
{
if (flag)
break;
for (int j = i + 1; j < max; j++)
{
if (m[i] + m[j] > k)
{
max = j - 1;
break;
}
else
if (m[i] + m[j] == k)
{
flag = true;
break;
}
}
}
if (!flag)
{
max = m1.Count();
for (int i = 0; i < max; i++)
{
if (flag)
break;
for (int j = i + 1; j < max; j++)
{
if (m1[i] + m1[j] > k)
{
max = j - 1;
break;
}
else
if (m1[i] + m1[j] == k)
{
flag = true;
break;
}
}
}
}
}
else // нечётное
{
queryOptim =
from i in m
where i < k
select i;
m = queryOptim.Distinct().ToList();
queryOptim =
from i in m
where i % 2 == 0
select i;
List<Int32> m1 = queryOptim.Distinct().ToList(); //все чётные
queryOptim =
from i in m
where i % 2 == 1
select i;
m = queryOptim.ToList(); //все нечётные
int max = m.Count();
int max1 = m1.Count();
for (int i = 0; i < max; i++)
{
if (flag)
break;
for (int j = 0; j < max1; j++)
{
if (m[i] + m1[j] > k)
{
max1 = j - 1;
break;
}
else
if (m[i] + m1[j] == k)
{
flag = true;
break;
}
}
}
}
//m = queryOptim.ToList();
using (StreamWriter sw = new StreamWriter("output.txt"))
{
if (flag)
sw.WriteLine(1);
else
sw.WriteLine(0);
}
// Console.ReadKey();
}
}
}
Новая программа , проблема та-же
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<Int32> m = new List<Int32>();
Int32 k = 0;
using (StreamReader sr = new StreamReader("input.txt"))
{
k = Convert.ToInt32(sr.ReadLine());
m = sr.ReadLine().Split(' ').Select(Int32.Parse).ToList();
// m = s.Cast<Int32>();
sr.Close();
}
m.Sort();
bool flag = false;
//убираем большие числа
IEnumerable<Int32> queryOptim;
queryOptim =
from i in m
where i < k
select i;
m = queryOptim.ToList();
List<Int32> rep = new List<Int32>();//отдельно прогоним повторы
var set = new HashSet<Int32>();
foreach (Int32 i in m)
{
if (!set.Add(i))
rep.Add(i);
}
set = null;
foreach (Int32 i in rep)
{
if (i + i == k)
{
using (StreamWriter sw = new StreamWriter("output.txt"))
{
sw.WriteLine(1);
}
return;
}
}
rep = null;
m = m.Distinct().ToList();
int j = 0;
if(m.Count==0)
{
using (StreamWriter sw = new StreamWriter("output.txt"))
{
sw.WriteLine(0);
}
return;
}
while ((m[j] * 2) < k )
{
if (m.Contains(k-m[j]))
{
flag = true;
break;
}
j++;
if (j >= m.Count)
break;
}
using (StreamWriter sw = new StreamWriter("output.txt"))
{
if (flag)
sw.WriteLine(1);
else
sw.WriteLine(0);
}
// Console.ReadKey();
}
}
}
3-я версия
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<Int32> m = new List<Int32>();
Int32 k = 0;
using (StreamReader sr = new StreamReader("input.txt"))
{
k = Convert.ToInt32(sr.ReadLine());
m = sr.ReadLine().Split(' ').Select(Int32.Parse).ToList();
// m = s.Cast<Int32>();
sr.Close();
}
bool flag = false;
HashSet<int> set = new HashSet<int>();
foreach (var i in m)
{
if (set.Contains(k - i))
{
flag = true;
break;
}
set.Add(i);
}
using (StreamWriter sw = new StreamWriter("output.txt"))
{
if (flag)
sw.WriteLine(1);
else
sw.WriteLine(0);
}
}
}
}
Ответы (2 шт):
1) Прочитали k и список чисел
2) Прошли по списку, игнорируя числа, большие k.
Для очередного числа x проверяем наличие k-x в мапе.
Если есть, выводим 1.
Добавляем x в мап (если он уже есть - пофиг)
3) Дошли до конца - выводим 0
Все остальные действия с сортировкой, отбором и хранением повторов - лишние.
Если есть другая возможность быстро выделять числа из входной строки (как олимпиадники на C# 'это делают?), то даже иметь и хранить список не нужно.
Что то вы перемудрили.
Вариант с хешсетом. И не надо никаких сортировок нигде, оно работает как на сортированных, так и на не сортированных массивах.
public bool Solve(int k, int[] m)
{
HashSet<int> set = new HashSet<int>();
foreach(var i in m){
if (set.Contains(k-i)) return true;
set.Add(i);
}
return false;
}
Как проверить
int[] m = new int[] { 1, 2, 2, 2, 2, 2, 2, 3 };
Console.WriteLine(Solve(1, m));
Console.WriteLine(Solve(2, m));
Console.WriteLine(Solve(3, m));
Console.WriteLine(Solve(4, m));
Вывод
False
False
True
True
UPD
Если мы экономим память, то можно читать число по одному из потока, но имейте ввиду, что работа с файлами без буфера будет медленной операцией.
Нам понадобятся:
Метод, который по коду символа распознает число
private bool IsDigit(int c) => c >= '0' && c <= '9';
Метод, который умеет считывать число из потока
private int readNumber(StreamReader sr)
{
int c = 0;
int number = 0;
while (!sr.EndOfStream)
{
c = sr.Read();
if (IsDigit(c))
{
number = c - '0';
while (!sr.EndOfStream)
{
c = sr.Read();
if (IsDigit(c)) number = number * 10 + (c - '0');
else
{
return number;
}
}
}
}
return number;
}
Основая часть алгоритма
var fname = @"D:\temp\_test\qqqq.txt";
using (var sr = new StreamReader(new BufferedStream(File.OpenRead(fname), 1024*1024))) // небольшой буфер
{
int k = readNumber(sr);
var set = new HashSet<int>();
while (!sr.EndOfStream)
{
int number = readNumber(sr);
if (set.Contains(k-number)) {
Console.WriteLine("YES");
return;
}
set.Add(number);
}
Console.WriteLine("NO");
}
Файл на входе
60
1 2 3000001 4 5 6 7000002 8 9 051
Вывод
YES