Форум: "Прочее";
Текущий архив: 2007.01.21;
Скачать: [xml.tar.bz2];
ВнизПятничная задачка ;) Найти похожие ветки
← →
Kerk © (2006-12-29 14:52) [0]Дана строка:
82.198.111.111 - username - [01/Nov/2006:02:26:06 +0300] "GET /cgi-bin/board.cgi?page=8 HTTP/1.0" 404 5029 "-" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)"
Нужно разбить ее на подстроки:
1) 82.198.111.111
2) username
3) 01/Nov/2006:02:26:06 +0300
4) GET
5) /cgi-bin/board.cgi?page=8
6) HTTP/1.0
7) 404
8) 5029
9) -
10) Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)
Сделать это оптимально с точки зрения быстродействия. Может, что-то хитрее обычного прохода по строке можно придумать?
← →
tesseract © (2006-12-29 14:54) [1]Если поля фиксированной длины то можно system.move.
Но лучше проход по строке автоматом.
← →
Kerk © (2006-12-29 14:54) [2]> [1] tesseract © (29.12.06 14:54)
Нефиксированной они длины конечно
← →
Dmitrij_K (2006-12-29 15:03) [3]
(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}) - (.*) - \x5B(.*)\x5D "(.*) (.*) (.*)" (\d{3}) (\d*) "(.*)" "(.*)"
http://www.regexpstudio.com/RU/TRegExpr/TRegExpr.html
ку?
← →
Kerk © (2006-12-29 15:04) [4]> [3] Dmitrij_K (29.12.06 15:03)
Ну зачем ради парсинга одной строки таскать с собой это? Лучше уж я самостоятельно конечный автомат изображу.
← →
DiamondShark © (2006-12-29 15:06) [5]
> Может, что-то хитрее обычного прохода по строке можно придумать?
Зачем?
Что может быть быстрее алгоритма, который каждый символ просматривает ровно один раз?
← →
pasha_golub © (2006-12-29 15:17) [6]
> DiamondShark © (29.12.06 15:06) [5]
> Зачем?
> Что может быть быстрее алгоритма, который каждый символ
> просматривает ровно один раз?
А именно так "конченный" автомат и поступает.
> Kerk © (29.12.06 15:04) [4]
>
> > [3] Dmitrij_K (29.12.06 15:03)
>
> Ну зачем ради парсинга одной строки таскать с собой это?
> Лучше уж я самостоятельно конечный автомат изображу.
А вот тут ты не прав. Тасать там особо нечего. Зато функционал неоценим. Например, валидация вводимых юзером значений.
← →
oldman © (2006-12-29 16:03) [7]1) от начала до первого вхождения " - "
2) от первого вхождения " - " до первого вхождения " - ["
3) от первого вхождения " - [" до превого вхождения "]"
и т.д...
Ну а поиск подстроки в строке ты уж сам :)
← →
Kerk © (2006-12-29 17:56) [8]Родил вот такую вещь.
Критика по быстродействию и вообще привествуется
type
TParserState = (psIP, psUserName, psDateTime, psMethod, psUrl,
psProtocol, psErrorCode, psDataSize, psReferer, psUserAgent);
TLogParams = array [TParserState] of Variant;
procedure ParseLogString(LogStr: string; var LogParams: TLogParams);
implementation
procedure ParseLogString(LogStr: string; var LogParams: TLogParams);
const
ParamDelimeter: array [TParserState] of Char = (" ","-","]"," "," ","""," "," ",""",""");
ParamDelta: array [TParserState] of Integer = (0,2,3,3,1,1,2,1,2,3);
var
CharIndex: Integer;
CurStr: string;
ParserState: TParserState;
begin
ParserState := psIP; CurStr := ""; CharIndex := 1;
while CharIndex <= Length(LogStr) do
if LogStr[CharIndex] <> ParamDelimeter[ParserState] then
begin
CurStr := CurStr + LogStr[CharIndex];
Inc(CharIndex);
end else
begin
LogParams[ParserState] := CurStr;
CurStr := "";
Inc(ParserState);
CharIndex := CharIndex + ParamDelta[ParserState];
end;
LogParams[psUserName] := Trim(LogParams[psUserName]);
end;
← →
Kerk © (2006-12-29 17:57) [9]тег не тот блин, вот нормально:
type
TParserState = (psIP, psUserName, psDateTime, psMethod, psUrl,
psProtocol, psErrorCode, psDataSize, psReferer, psUserAgent);
TLogParams = array [TParserState] of Variant;
procedure ParseLogString(LogStr: string; var LogParams: TLogParams);
implementation
procedure ParseLogString(LogStr: string; var LogParams: TLogParams);
const
ParamDelimeter: array [TParserState] of Char = (" ","-","]"," "," ","""," "," ",""",""");
ParamDelta: array [TParserState] of Integer = (0,2,3,3,1,1,2,1,2,3);
var
CharIndex: Integer;
CurStr: string;
ParserState: TParserState;
begin
ParserState := psIP; CurStr := ""; CharIndex := 1;
while CharIndex <= Length(LogStr) do
if LogStr[CharIndex] <> ParamDelimeter[ParserState] then
begin
CurStr := CurStr + LogStr[CharIndex];
Inc(CharIndex);
end else
begin
LogParams[ParserState] := CurStr;
CurStr := "";
Inc(ParserState);
CharIndex := CharIndex + ParamDelta[ParserState];
end;
LogParams[psUserName] := Trim(LogParams[psUserName]);
end;
← →
umbra © (2006-12-29 18:13) [10]если структура строки заранее известна и не меняется, то зачем проходить ее посимвольно, да еще постоянно перераспределять память
CurStr := CurStr + LogStr[CharIndex];
?
← →
Kerk © (2006-12-29 18:21) [11]> [10] umbra © (29.12.06 18:13)
Где ж она заранее известна? Размеры полей все время разные
← →
default © (2006-12-29 18:33) [12]что та заладил про "таскать"?:)
это не катит:)
← →
Kerk © (2006-12-30 14:05) [13]Слишком долго :(
17 тысяч строк за 23 секунды
← →
Sha © (2006-12-30 16:36) [14]> Kerk © (30.12.06 14:05) [13]
> Слишком долго :(
см. [10]
← →
default © (2006-12-30 17:16) [15]похоже надо PosEx+Copy:) детский сад:)
← →
Kerk © (2006-12-31 11:21) [16]Ну и чем Pos отличается от посимвольного сравнения? Или в эту функцию встроен телепатор? Насчет перераспределения памяти согласен
← →
Sha © (2006-12-31 11:41) [17]> Kerk © (31.12.06 11:21) [16]
> Насчет перераспределения памяти согласен
Отлично.
Там есть еще куча скрытых перераспределений, которые выполняются
при вызове функции, в операторах присваивания и в Trim.
Избавишься от них и будет щастье.
Успехов в новом году :)
← →
default © (2006-12-31 12:17) [18]ты не понял
PosEx по разделителям и Copy для получения подстрок
задача даже сильно до олимпиадной не дотягивает....
← →
default © (2006-12-31 13:59) [19]то есть какая твоя задача? сделать в алгоритме столько распределений памяти под подстроки сколько самих подстрок - это можно сделать через Copy
а параметры для Copy сообразишь как обеспечить
можно искать разделители через PosEx, можно просто циклом по символам строки - это не принципиально(опять же будут использованы твои ParamDelimeter, ParamDelta)
С Новым Годом!
← →
Sha © (2006-12-31 14:08) [20]> default © (31.12.06 13:59) [19]
> то есть какая твоя задача? сделать в алгоритме столько
> распределений памяти под подстроки сколько самих подстрок
А лучше 0.
С Новым Годом!
← →
default © (2006-12-31 14:23) [21]Sha © (31.12.06 14:08) [20]
> А лучше 0.
пусть закажет это деду морозу!
и авось под ёлкой найдёт листинг с соответствующим кодом!
в Новый Год чудеса возможны!:)
← →
Sha © (2006-12-31 14:43) [22]> default © (31.12.06 14:23) [21]
Я серьезно.
← →
default © (2006-12-31 15:25) [23]Sha © (31.12.06 14:43) [22]
ну ему надо же поместить эти подстроки в какой-то внешний контейнер, а не просто найти их
← →
Sha © (2006-12-31 15:37) [24]Я понимаю. Но:
- контейнером может служить достаточно большой буфер,
- можно просто вернуть указатели и длины,
используя в качестве контейнера входную строку,
- можно помещать данные в строки, никогда не уменьшая
размер выделенной под них памяти.
← →
Kerk © (2006-12-31 15:48) [25]PosEx и олимпиадные задачки тут не в тему совсем. default, отстань, иди отмечать новый год. Вот Sha дело говорит.
← →
default © (2006-12-31 15:57) [26]Sha © (31.12.06 15:37) [24]
> - контейнером может служить достаточно большой буфер,
где-то под этот буфер память распределяется
> - можно просто вернуть указатели и длины,
> используя в качестве контейнера входную строку,
опять же нужно хоть одно распределение под такую структуру
> - можно помещать данные в строки, никогда не уменьшая
> размер выделенной под них памяти.
не понял
> Kerk © (31.12.06 15:48) [25]
c PosEx код лаконичнее, вероятно
я же сказал ранее, что это не принципиально, можно и обычным циклом
а про олимпиадные я сказал к тому, что задача тривиально
минут на 10 на самом-то деле....
← →
default © (2006-12-31 15:59) [27]Kerk © (31.12.06 15:48) [25]
он говорит про частности
про выходную форму результата
кто ж тут знает в какой форме тебе нужно получить результат!
а про перераспределения уже давно указывали...
← →
default © (2006-12-31 16:03) [28]
> - можно помещать данные в строки, никогда не уменьшая
> размер выделенной под них памяти.
если это про что-то навроде классов динамических строк, то опять же одно распределение как минимум
Вы указали 0
нуля быть не может
← →
Sha © (2006-12-31 16:26) [29]default © (31.12.06 15:57) [26]
> > - контейнером может служить достаточно большой буфер,
> где-то под этот буфер память распределяется
Один раз при инициализации. 0 раз в цикле.
> > - можно просто вернуть указатели и длины,
> > используя в качестве контейнера входную строку,
> опять же нужно хоть одно распределение под такую структуру
см. выше
> > - можно помещать данные в строки, никогда не уменьшая
> > размер выделенной под них памяти.
> не понял
Например, вместоSetString(s.p,len);
писать че-нить вродеif stlen<len then begin; SetLength(s,len); stlen:=len; end;
Move(p^,pointer(s)^,len);
pInteger(pchar(pointer(s))-4):=len;
с инициализацией типаs:="abc";
stlen:=3;
UniqueString(s);
Естественно, надо понимать, что если строка
неуникальна, то подобные выкрутасы могут изменить
значения всех экземпляров.
> нуля быть не может
Ты как программист, конечно понимаешь, что речь идет о количестве
перераспределений памяти в цикле.
В момент начала работы программы вся память принадлежит ОС,
и хотя бы раз ее придется взять.
Ты, конечно, знаешь это :)
← →
default © (2006-12-31 16:58) [30]Sha © (31.12.06 16:26) [29]
я всё это знаю!
но выделять с запасом считаю дурным тоном, я бы так делал только в случае необохдимости
в его случае надо сначала убрать очевидные перераспределения о которых ему твердят который день, а вот если не поможет, можно уже и к Вашим выкрутасам переходить
← →
Sha © (2006-12-31 17:07) [31]> default © (31.12.06 16:58) [30]
> но выделять с запасом считаю дурным тоном
Зависит от задачи.
Иногда увеличение производительности в 100 раз важнее.
← →
default © (2006-12-31 17:20) [32]Sha © (31.12.06 17:07) [31]
ага
но вообще его задача очень проста, вариантов оптимизации куча
я поэтому и удивился почему у него возникли трудности...
← →
Sha © (2006-12-31 17:37) [33]> Kerk © (29.12.06 17:57) [9]
> TLogParams = array [TParserState] of Variant
Забудь про этот тип.
← →
GrayFace © (2007-01-01 01:48) [34]Sha © (31.12.06 16:26) [29]
Тогда уж идти дальше: прямо в парсящююся строку писать счетчик ссылок, длину кусочка и 0-байт на конец. Опять же при условии, что каждая подстрока сразу же подается в каку-нибудь функцию, где не запоминается, и после этого никак не нужна. Иначе оптимизировать в SetString нечего, разве что выделить под все общий буфер и зашкалить счетчики ссылок.
← →
Sha © (2007-01-01 12:10) [35]> GrayFace © (01.01.07 01:48) [34]
> Тогда уж идти дальше: прямо в парсящююся строку...
Очень сильно не рекомендую. Вдруг придется парсить проекцию файла.
Хотел в свое время так сделать в XML-парсере, но вовремя остановился.
В итоге ща безразлично, что парсить: строки, буфера, стримы.
Выгода неоспорима, а потери быстродействия на стримах - всего несколько процентов.
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2007.01.21;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.053 c