Задача у меня — быстро разбивать околомегобайтные строки на коллекции строк.
Причем разделитель приходит параметром откуда-то из вне моей библиотеки.
Что я вижу:
StrinBuilder.Split — не совсем.
String.Split — не работает со строками, а только с символами, то есть, например,
— по "\r\n" ничего не разделить, так что-б на отдельные '\r' и '\n' не реагировало.
Сейчас работаю с Regex.Split, но проблема в том, что мне может прийти в качестве разделителя нечто вроде "[2345]+", что Regex поймет весьма по-своему.
Попытка написать "в-лоб" комбинацию IndefOf/SubString показала, что выходит медленно.
Hello, Nikolay_P_I!
NP> Сейчас работаю с Regex.Split, но проблема в том, что мне может прийти в NP> качестве разделителя нечто вроде "[2345]+", что Regex поймет NP> весьма по-своему.
N_P>Попытка написать "в-лоб" комбинацию IndefOf/SubString показала, что выходит медленно.
Ты в indexof передаешь предыдущее мето, где нашел вхождение или ищешь с начала? Покажи код.
Кстати, а indexof как устроен — он по-тупому ищет или все-таки умеет по Бойеру-Муру?
Здравствуйте, Nikolay_P_I, Вы писали:
N_P>Сейчас работаю с Regex.Split, но проблема в том, что мне может прийти в качестве разделителя нечто вроде "[2345]+", что Regex поймет весьма по-своему.
А если эти "весьма" символы обработать "специальным" образом, их ведь не так много..
<< RSDN@Home 1.1.2 stable >>
Нельзя ничего сказать о глубине лужи, пока не попадешь в нее.
Вот тестовый пример. Не оптимизированный под скорость (хотя очень быстрый)
using System;
using System.Collections.Specialized;
using System.Text;
namespace RSDNRegex
{
using CSharpTest2;
/// <summary>
/// Summary description for Class.
/// </summary>public class CSVHalper
{
enum StateEnum
{
FieldStart, ScanField, ScanQuoted, EndQuoted
}
public static void ExtractFields(string S,
ref StringCollection aList)
{
ExtractFields(S,ref aList,',','"');
}
public static void ExtractFields(string S,
ref StringCollection aList, char Delimiter, char QuoteChar)
{
//{initialize by clearing the string list, and
// starting in FieldStart state}
// Assert(aList <> nil, 'TDExtractFields: list is nil');if (aList == null)
throw new Exception("?? ???????? ?????? ??? StringCollection ");
aList.Clear();
if ( (S==null) || (S.Length ==0 ))
{
aList.Add(string.Empty);
return;
}
StateEnum State = StateEnum.FieldStart;
RStringBuilder SB= new RStringBuilder();
int StartPos=0;
int EndPos=S.Length;
int Inx=0;
// {read through all the characters in the string}while (Inx <EndPos)
{
// {get the next character}char Ch = S[Inx];
// {switch processing on the state}switch (State)
{
case StateEnum.FieldStart :
if ( Ch == QuoteChar)
{
State = StateEnum.ScanQuoted;
StartPos=Inx+1;
SB.Length=0;
}
else
if ( Ch == Delimiter)
aList.Add(string.Empty);
else
{
State = StateEnum.ScanField;
StartPos=Inx;
}
break;
case StateEnum.ScanField :
if ( Ch == Delimiter )
{
int CopyCount=Inx-StartPos;
aList.Add(S.Substring(StartPos,CopyCount));
State = StateEnum.FieldStart;
}
break;
case StateEnum.ScanQuoted :
if ( Ch == QuoteChar)
{
State = StateEnum.EndQuoted;
int CopyCount=Inx-StartPos;
SB.Append(S,StartPos,CopyCount);
}
break;
case StateEnum.EndQuoted :
if (Ch == Delimiter)
{
aList.Add(SB.ToString());
State = StateEnum.FieldStart;
}
else
if (Ch == QuoteChar)
{
State = StateEnum.ScanQuoted;
SB.Append(QuoteChar);
StartPos=Inx+1;
}
else
throw new Exception("??? "+Delimiter+ "? ??????? ="+Inx.ToString() );
break;
}
Inx++;
}
// {if we are in the ScanQUoted or GotError state at the end
// of the string, there was a problem with a closing quote}if (State == StateEnum.ScanQuoted)
throw new Exception("??? ??????????? ?????? ?? ???="+(StartPos-1).ToString()+
" ?? ????? ??????");
// {if the current field is not empty, add it to the list}if (State == StateEnum.EndQuoted)
aList.Add(SB.ToString());
else if (State == StateEnum.ScanField)
{
int CopyCount=Inx-StartPos;
aList.Add(S.Substring(StartPos,CopyCount));
}
}
public static string Split(StringCollection aList)
{
return Split(aList,',',
'"');
}
public static string Split(StringCollection aList, char Delimiter,
char QuoteChar)
{
if (( (aList==null) || (aList.Count == 0)) ||
((aList.Count ==1 ) && (aList[1].Length==0)))
{
return string.Concat(QuoteChar,QuoteChar);
}
RStringBuilder Sb= new RStringBuilder();
//int Pos;for ( int j=0; j<aList.Count;j++)
{
string S=aList[j];
int Pos=-1;
int LenStr=S.Length;
if (j>0)
Sb.Append(Delimiter);
for (int i=0; i< LenStr; i++)
{
char Ch=S[i];
if (( Ch == Delimiter) || (Ch == QuoteChar) || (Ch<33) )
{
Sb.Append(QuoteChar);
Sb.Append(S,0,i);
Pos=i;
break;
}
}
if (Pos==-1)
Sb.Append(S);
else
{
for (int i=Pos; i<LenStr; i++)
if ( S[i] == QuoteChar)
{
Sb.Append(S,Pos,i-Pos+1);
Sb.Append(QuoteChar);
Pos=i+1;
}
if (Pos<LenStr)
Sb.Append(S,Pos,LenStr-Pos);
Sb.Append(QuoteChar);
}
}
return Sb.ToString();
}
public static void ExtractFields(string S,
ref StringList aList)
{
ExtractFields(S,ref aList,',','"');
}
public static void ExtractFields(string S,
ref StringList aList, char Delimiter, char QuoteChar)
{
//{initialize by clearing the string list, and
// starting in FieldStart state}
// Assert(aList <> nil, 'TDExtractFields: list is nil');if (aList == null)
throw new Exception("?? ???????? ?????? ??? StringCollection ");
aList.Clear();
if ( (S==null) || (S.Length ==0 ))
{
aList.Add(string.Empty);
return;
}
StateEnum State = StateEnum.FieldStart;
RStringBuilder SB= new RStringBuilder();
int StartPos=0;
int EndPos=S.Length;
int Inx=0;
// {read through all the characters in the string}while (Inx <EndPos)
{
// {get the next character}char Ch = S[Inx];
// {switch processing on the state}switch (State)
{
case StateEnum.FieldStart :
if ( Ch == QuoteChar)
{
State = StateEnum.ScanQuoted;
StartPos=Inx+1;
SB.Length=0;
}
else
if ( Ch == Delimiter)
aList.Add(string.Empty);
else
{
State = StateEnum.ScanField;
StartPos=Inx;
}
break;
case StateEnum.ScanField :
if ( Ch == Delimiter )
{
int CopyCount=Inx-StartPos;
aList.Add(S.Substring(StartPos,CopyCount));
State = StateEnum.FieldStart;
}
break;
case StateEnum.ScanQuoted :
if ( Ch == QuoteChar)
{
State = StateEnum.EndQuoted;
int CopyCount=Inx-StartPos;
SB.Append(S,StartPos,CopyCount);
}
break;
case StateEnum.EndQuoted :
if (Ch == Delimiter)
{
aList.Add(SB.ToString());
State = StateEnum.FieldStart;
}
else
if (Ch == QuoteChar)
{
State = StateEnum.ScanQuoted;
SB.Append(QuoteChar);
StartPos=Inx+1;
}
else
throw new Exception("??? "+Delimiter+ "? ??????? ="+Inx.ToString() );
break;
}
Inx++;
}
// {if we are in the ScanQUoted or GotError state at the end
// of the string, there was a problem with a closing quote}if (State == StateEnum.ScanQuoted)
throw new Exception("??? ??????????? ?????? ?? ???="+(StartPos-1).ToString()+
" ?? ????? ??????");
// {if the current field is not empty, add it to the list}if (State == StateEnum.EndQuoted)
aList.Add(SB.ToString());
else if (State == StateEnum.ScanField)
{
int CopyCount=Inx-StartPos;
aList.Add(S.Substring(StartPos,CopyCount));
}
}
public static string Split(StringList aList)
{
return Split(aList,',',
'"');
}
public static string Split(StringList aList, char Delimiter,
char QuoteChar)
{
if (( (aList==null) || (aList.Count == 0)) ||
((aList.Count ==1 ) && (aList[1].Length==0)))
{
return string.Concat(QuoteChar,QuoteChar);
}
RStringBuilder Sb= new RStringBuilder();
//int Pos;for ( int j=0; j<aList.Count;j++)
{
string S=aList[j];
int Pos=-1;
int LenStr=S.Length;
if (j>0)
Sb.Append(Delimiter);
for (int i=0; i< LenStr; i++)
{
char Ch=S[i];
if (( Ch == Delimiter) || (Ch == QuoteChar) || (Ch<33) )
{
Sb.Append(QuoteChar);
Sb.Append(S,0,i);
Pos=i;
break;
}
}
if (Pos==-1)
Sb.Append(S);
else
{
for (int i=Pos; i<LenStr; i++)
if ( S[i] == QuoteChar)
{
Sb.Append(S,Pos,i-Pos+1);
Sb.Append(QuoteChar);
Pos=i+1;
}
if (Pos<LenStr)
Sb.Append(S,Pos,LenStr-Pos);
Sb.Append(QuoteChar);
}
}
return Sb.ToString();
}
}
}
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Если у тебя текст типа Comma Separator Value то этот тестовый класс тебе подойдет. Только замени RStringBuilder на обычный аналог.
типа 2,"10409МОС","10350МОС","""Лучше пузо от пива , чем горб от работы ! ""
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Igor Trofimov, Вы писали:
N_P>>Попытка написать "в-лоб" комбинацию IndefOf/SubString показала, что выходит медленно.
iT>Ты в indexof передаешь предыдущее мето, где нашел вхождение или ищешь с начала? Покажи код. iT>Кстати, а indexof как устроен — он по-тупому ищет или все-таки умеет по Бойеру-Муру?
Да и без Бойеру-Муру в лоб скорость порядка 500 мб/сек. Правда у Бойеру-Муру будет большое премущество на больших объемах при IgnoreCase==true.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Nikolay_P_I, Вы писали:
N_P>Сейчас работаю с Regex.Split, но проблема в том, что мне может прийти в качестве разделителя нечто вроде "[2345]+", что Regex поймет весьма по-своему.
В регексах есть функция Escep (или что-то в этом роде). Пропускай свои разделители через нее и будет все пучком.
... << RSDN@Home 1.1.3 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Nikolay_P_I, Вы писали:
N_P>StrinBuilder.Split — не совсем.
N_P>String.Split — не работает со строками, а только с символами, то есть, например, N_P>- по "\r\n" ничего не разделить, так что-б на отдельные '\r' и '\n' не реагировало.
string str = "123\r\n456\r789\n346\r\n234";
string[] sa = str.Replace("\r\n", "\0").Split('\0');
foreach (string s in sa)
Console.WriteLine("---{0}---", s.Replace("\r", "\\r").Replace("\n", "\\n"));
Если нам не помогут, то мы тоже никого не пощадим.
String.Replace('\0', '\b'); //Убираю изначальные 0, они не нужны, но могут быть
String.Replace(razdelitel, "\0")
String.Split('\0');
В чем хохма ?
На малом тесте (5мБ) выигрыш получился в 20(!) раз.
При реальной же работе (100Мб) получаются тормоза в 3(!) раза
Единственное что я заметил — вариант с Regex есть 40-80Мб памяти, вариант с Строками — 60-120Мб. Скорость точно замерить не получилось тк у моего профайлера сбивает крышу на таких
объемах информации.
Здравствуйте, Nikolay_P_I, Вы писали:
N_P>Задача у меня — быстро разбивать околомегобайтные строки на коллекции строк.
N_P>Причем разделитель приходит параметром откуда-то из вне моей библиотеки.
N_P>Что я вижу:
N_P>StrinBuilder.Split — не совсем.
N_P>String.Split — не работает со строками, а только с символами, то есть, например, N_P>- по "\r\n" ничего не разделить, так что-б на отдельные '\r' и '\n' не реагировало.
public string[] Split(params char[] separator);
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
public class IntBuilder
{
private int _count;
private int _capacity;
public int [] IntArray;
public IntBuilder()
{
_capacity=64;
_count=0;
IntArray = new int[_capacity];
}
public void Add(int value)
{
if (_count ==_capacity)
{
_capacity*=2;
int[] TempArray= new int[_capacity];
Array.Copy(IntArray,0,TempArray,0,_count);
IntArray=TempArray;
}
IntArray[_count]=value;
_count++;
}
public int Count
{
get {return _count;}
}
public int this[int I]
{
get { return IntArray[I];}
set { IntArray[I]= value;}
}
}
А обработка строк типа
int[] ar =IB.IntArray;
string[] Result new string[IB.Count+1];
int pos=0;
int IndexInOrigString=0;
for ( int i=0; i<IB.Count; i++)
{
int PosMetaChar=ar[i];
if (PosMetaChar=IndexInOrigString)
{
Result[pos]= String.Empty;
}
else
{
int CopyCount=PosMetaChar-IndexInOrigString;
Result[pos]= str.SubString(IndexInOrigString,CopyCount)
}
pos++;
IndexInOrigString=PosMetaChar+Separator.Length;
}
if (IndexInOrigString <str.Length)
Result[pos]= str.SubString(IndexInOrigString,str.Length-IndexInOrigString)
Писал сходу не проверял.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
int[] ar =IB.IntArray;
string[] Result new string[IB.Count+1];
int pos=0;
int IndexInOrigString=0;
for ( int i=0; i<IB.Count; i++)
{
int PosMetaChar=ar[i];
if (PosMetaChar=IndexInOrigString)
{
Result[pos]= String.Empty;
}
else
{
int CopyCount=PosMetaChar-IndexInOrigString;
Result[pos]= str.SubString(IndexInOrigString,CopyCount)
}
pos++;
IndexInOrigString=PosMetaChar+Separator.Length;
}
if (IndexInOrigString <str.Length)
Result[pos]= str.SubString(IndexInOrigString,str.Length-IndexInOrigString);
else
Result[pos]=String.Empty;
Писал сходу не проверял.
... << RSDN@Home 1.1.0 stable >>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Nikolay_P_I, Вы писали:
N_P>В чем хохма ?
N_P>На малом тесте (5мБ) выигрыш получился в 20(!) раз. N_P>При реальной же работе (100Мб) получаются тормоза в 3(!) раза
N_P>Единственное что я заметил — вариант с Regex есть 40-80Мб памяти, вариант с Строками — 60-120Мб. Скорость точно замерить не получилось тк у моего профайлера сбивает крышу на таких объемах информации.
Дык в этом и дело. Реплэйс написан оптимальнее чем регексы, но для каждого отдельного реплэйса нужно занимать память. В большом тесте ты вылитаешь из кэша и попадаешь на своп.
Если ты работаешь с действительно большими объемами, то лучше работать с потоками или резать обрабоку на части.
... << RSDN@Home 1.1.3 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Если нам не помогут, то мы тоже никого не пощадим.
