Ситуация следующая: мне нужно в файлах искать вхождения некоторых данных. Раньше файлы были маленькие и данных были в одном экземпляре (т.е. требовалось найти вхождение одних и тех же данных), сейчас же условия изменились и нужно найти разные данные, плюс к этому файлы очень сильно выросли (около 1Гб).
Задачу я решил (код ниже), но т.к. время время позволяет, то я решил попробовать написать в функциональном стиле, но как не пишу, всё равно получается, то, что есть.
Помогите, пожалуйста, переписать этот код. Я пытался и на F# (недавно начал изучать) и на C#, никак не выходит.
Для C# написал только такой код, а что дальше с ним делать — не понятно
IEnumerable<byte> GetBytes(string fileName)
{
int bytesReaden;
byte[]buffer = new byte[4096];
using (var file = File.OpenRead(fileName))
while ((bytesReaden = file.Read(buffer, 0, buffer.Length))>0)
{
for (int i = 0; i < bytesReaden; i++)
{
yield return buffer[i];
}
}
}
А вот существующий код:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Text;
namespace TestProgram
{
internal class Entry
{
public string Item;
public int Offset;
}
internal class Program
{
private static void Main(string[] args)
{
string fileName = new StackTrace(true).GetFrame(0).GetFileName();
var entries = new[]
{
"Microsoft.Build.Conversion.v3.5.xml",
"Microsoft.Build.Engine.xml",
"Microsoft.Build.Framework.xml",
"Microsoft.Build.Utilities.v3.5.xml",
"Microsoft.VisualC.STLCLR.xml",
"System.AddIn.Contract.xml",
"System.AddIn.xml",
"System.Core.xml",
"System.Data.DataSetExtensions.xml",
"System.Data.Linq.xml",
"System.DirectoryServices.AccountManagement.xml",
"System.Management.Instrumentation.xml",
"System.Net.xml",
"System.ServiceModel.Web.xml",
"System.Web.Extensions.Design.xml",
"System.Web.Extensions.xml",
"System.Windows.Presentation.xml",
"System.WorkflowServices.xml",
"System.Xml.Linq.xml",
};
var list = new List<Entry>();
list.AddRange(FindEntries(fileName, entries));
Console.WriteLine("list: {0}", list.Count);
}
private static IEnumerable<Entry> FindEntries(string fileName, string[] entries)
{
var list = new List<Entry>();
using (FileStream file = File.OpenRead(fileName))
{
foreach (string entryString in entries)
{
file.Seek(0, SeekOrigin.Begin);
var buffer = new byte[4096];
int bytesReaden;
int offset = 0;
byte[] entryBytes = Encoding.ASCII.GetBytes(entryString);
int curPos = 0;
while ((bytesReaden = file.Read(buffer, offset, buffer.Length - offset)) > 0)
{
bytesReaden += offset;
for (int i = 0; i < bytesReaden - entryBytes.Length; i++)
{
bool match = true;
for (int j = 0; j < entryBytes.Length; j++)
{
if (buffer[i + j] != entryBytes[j])
{
match = false;
break;
}
}
if (match)
{
var entry = new Entry
{
Item = entryString,
Offset = curPos + i
};
i += entryBytes.Length;
list.Add(entry);
}
}
offset = entryBytes.Length;
curPos += bytesReaden - offset;
for (int i = 0; i < entryBytes.Length; i++)
{
buffer[i] = buffer[bytesReaden - entryBytes.Length + i];
}
}
}
}
return list;
}
}
}
//"Microsoft.Build.Conversion.v3.5.xml",
Здравствуйте, Аноним, Вы писали:
А>Помогите, пожалуйста, переписать этот код. Я пытался и на F# (недавно начал изучать) и на C#, никак не выходит.
Лучше потратьте это время на изучение алгоритмов поиска подстроки. Например, есть алгоритмы, не требующие возвращаться "назад".
Когда вы реализуете этот алгоритм у себя, будет гораздо проще понять, куда тут можно применить функциональное программирование. В частности, потом может получиться что-то типа Rx
Здравствуйте, Аноним, Вы писали:
А>Задачу я решил (код ниже), но т.к. время время позволяет, то я решил попробовать написать в функциональном стиле, но как не пишу, всё равно получается, то, что есть. А>Помогите, пожалуйста, переписать этот код. Я пытался и на F# (недавно начал изучать) и на C#, никак не выходит.
Как-то вот так.
//System.AddIn.xmlusing System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
namespace ConsoleApplication7 {
internal class Program {
internal class Entry {
public string Item;
public int Offset;
public override string ToString() {
return new { Item, Offset }.ToString();
}
}
private static Action<T> GetMatcher<T>(IEnumerable<T> pattern, Action found) {
IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
var states = new List<int>();
return next => {
for (int i = 0; i < states.Count; i++) {
states[i]++;
}
states.RemoveAll(n => !comparer.Equals(pattern.ElementAt(n), next));
if (states.Count > 0 && states[0] == pattern.Count() - 1) {
found();
states.RemoveAt(0);
}
if (comparer.Equals(pattern.ElementAt(0), next)) {
states.Add(0);
}
};
}
private static Action<T> Compose<T>(IEnumerable<Action<T>> actions) {
return t => {
foreach (var action in actions) {
action(t);
}
};
}
private static void Main() {
string fileName = new StackTrace(true).GetFrame(0).GetFileName();
var entries = new[] {
"Microsoft.Build.Conversion.v3.5.xml",
"Microsoft.Build.Engine.xml",
"Microsoft.Build.Framework.xml",
"Microsoft.Build.Utilities.v3.5.xml",
"Microsoft.VisualC.STLCLR.xml",
"System.AddIn.Contract.xml",
"System.AddIn.xml",
"System.Core.xml",
"System.Data.DataSetExtensions.xml",
"System.Data.Linq.xml",
"System.DirectoryServices.AccountManagement.xml",
"System.Management.Instrumentation.xml",
"System.Net.xml",
"System.ServiceModel.Web.xml",
"System.Web.Extensions.Design.xml",
"System.Web.Extensions.xml",
"System.Windows.Presentation.xml",
"System.WorkflowServices.xml",
"System.Xml.Linq.xml",
};
var log = new List<Entry>();
using (var stream = File.OpenRead(fileName))
using (var reader = new StreamReader(stream)) {
int pos = 0;
var q = from e in entries
select GetMatcher(e, () => log.Add(new Entry { Item = e, Offset = pos - e.Length }));
Action<char> composite = Compose(q.ToArray());
while (!reader.EndOfStream) {
string line = reader.ReadLine();
foreach (var ch in line) {
composite(ch);
pos++;
}
}
}
}
}
}
//"Microsoft.Build.Conversion.v3.5.xml",
Здравствуйте, Аноним, Вы писали:
А>Я пытался и на F# (недавно начал изучать).
Если забить на многие факторы, то отлично ложиться на F#
(* Microsoft.Build.Conversion.v3.5.xml *)open System.Diagnostics
open System.IO
let main () =
let fileName =
StackTrace(true).GetFrame(0).GetFileName()
let entries =
[ "Microsoft.Build.Conversion.v3.5.xml";
"Microsoft.Build.Engine.xml";
"Microsoft.Build.Framework.xml";
"Microsoft.Build.Utilities.v3.5.xml";
"Microsoft.VisualC.STLCLR.xml";
"System.AddIn.Contract.xml";
"System.AddIn.xml";
"System.Core.xml";
"System.Data.DataSetExtensions.xml";
"System.Data.Linq.xml";
"System.DirectoryServices.AccountManagement.xml";
"System.Management.Instrumentation.xml";
"System.Net.xml";
"System.ServiceModel.Web.xml";
"System.Web.Extensions.Design.xml";
"System.Web.Extensions.xml";
"System.Windows.Presentation.xml";
"System.WorkflowServices.xml";
"System.Xml.Linq.xml"; ]
(* построчное чтение файла *)
seq { use file = File.OpenRead(fileName)
use reader = new StreamReader(file)
while not reader.EndOfStream do
yield reader.ReadLine() }
(* добавление позиции начала строк *)
|> Seq.scan (fun (p,o:string) s -> p+o.Length, s) (0,"")
|> Seq.skip 1
(* отображение в последовательности совпадений *)
|> Seq.map (fun (pos,line) ->
entries
|> Seq.map (fun e -> (* поиск entry в строке *)
e, line.IndexOf(e, System.StringComparison.Ordinal))
|> Seq.filter (snd >> (<=) 0) (* отбираем совпадения *)
|> Seq.map (fun (e,m) -> e, m+pos) (* корректируем позицию *)
)
(* соединение в единую последовательность и вывод на экран *)
|> Seq.concat
|> Seq.iter (printfn "%A")
На первый взгляд сразу видно что оно не умеет:
1. Не найдёт два совпадения в одной строке
2. Походу не учитывает crlf при подсчёте позиции в файле...
3. Не знаю как работает String.IndexOf(), но думаю оно бэктрекится
Зато ни единого mutable closure и выглядит как единый pipe.
Здравствуйте, Пельмешко, Вы писали:
П>Зато ни единого mutable closure и выглядит как единый pipe.
1. Расход по памяти потенциально выше (кто знает, какой длины там строки, может там весь файл в одну строку выстроен)
2. Не найдет построки с переводм строки внутри.
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, Пельмешко, Вы писали:
П>>Зато ни единого mutable closure и выглядит как единый pipe.
L>1. Расход по памяти потенциально выше (кто знает, какой длины там строки, может там весь файл в одну строку выстроен) L>2. Не найдет построки с переводм строки внутри. L>)
Не спорю Меня просто прёт как выглядит
Честно говоря не понимаю зачем анониму функциональность, раз объёмы данных возросли, а сложность алгоритма выросла незначительно...
Я бы оставил императивный вариант, применив побольше декомпозиции, где это возможно...
p.s. Можно переписать чтобы находило совпадения в одной строке:
(* отображение в последовательности совпадений *)
|> Seq.map (fun (pos,line) -> seq {
for e in entries do
let rec matches (i:int) = seq {
let i = line.IndexOf(e, i)
if i >= 0 then
yield e, i + pos
yield! matches (i+1) }
yield! matches 0 })
Круто, конечно, выглядит рекурсивный генератор, но на списках короче будет и не лениво:
(* отображение в последовательности совпадений *)
|> Seq.map (fun (pos,line) ->
entries
|> Seq.map (fun e ->
let rec matches (i:int) ls =
match line.IndexOf(e,i) with
| i when i = -1 -> ls
| i -> matches (i+1) ((e,i+pos)::ls)
matches 0 []))
|> Seq.concat
p.s.s. Может кто знает, ввели в C# 4.0 yield! (yield many или хз как назвать) или нет?
Здравствуйте, Пельмешко, Вы писали:
П>Здравствуйте, Lloyd, Вы писали:
П>Честно говоря не понимаю зачем анониму функциональность, раз объёмы данных возросли, а сложность алгоритма выросла незначительно... П>Я бы оставил императивный вариант, применив побольше декомпозиции, где это возможно...
В первоначальном варианте ваще ужас-ужас. У него так файл пробегается столько раз, сколько подстрока ищется.
П>p.s.s. Может кто знает, ввели в C# 4.0 yield! (yield many или хз как назвать) или нет?
