Пятничная задачка ;)

← →
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]

Я понимаю. Но:
- контейнером может служить достаточно большой буфер,
- можно просто вернуть указатели и длины,
используя в качестве контейнера входную строку,
- можно помещать данные в строки, никогда не уменьшая
размер выделенной под них памяти.

PosEx и олимпиадные задачки тут не в тему совсем. default, отстань, иди отмечать новый год. Вот Sha дело говорит.

Sha © (31.12.06 15:37) [24]

> - контейнером может служить достаточно большой буфер,

где-то под этот буфер память распределяется

> - можно просто вернуть указатели и длины,
> используя в качестве контейнера входную строку,

опять же нужно хоть одно распределение под такую структуру

> - можно помещать данные в строки, никогда не уменьшая
> размер выделенной под них памяти.

не понял

> Kerk © (31.12.06 15:48) [25]

c PosEx код лаконичнее, вероятно
я же сказал ранее, что это не принципиально, можно и обычным циклом

а про олимпиадные я сказал к тому, что задача тривиально
минут на 10 на самом-то деле....

Kerk © (31.12.06 15:48) [25]
он говорит про частности
про выходную форму результата
кто ж тут знает в какой форме тебе нужно получить результат!
а про перераспределения уже давно указывали...

> - можно помещать данные в строки, никогда не уменьшая
> размер выделенной под них памяти.

если это про что-то навроде классов динамических строк, то опять же одно распределение как минимум
Вы указали 0
нуля быть не может

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);

Естественно, надо понимать, что если строка
неуникальна, то подобные выкрутасы могут изменить
значения всех экземпляров.

> нуля быть не может

Ты как программист, конечно понимаешь, что речь идет о количестве
перераспределений памяти в цикле.
В момент начала работы программы вся память принадлежит ОС,
и хотя бы раз ее придется взять.
Ты, конечно, знаешь это :)

Sha © (31.12.06 16:26) [29]
я всё это знаю!
но выделять с запасом считаю дурным тоном, я бы так делал только в случае необохдимости
в его случае надо сначала убрать очевидные перераспределения о которых ему твердят который день, а вот если не поможет, можно уже и к Вашим выкрутасам переходить

> default © (31.12.06 16:58) [30]
> но выделять с запасом считаю дурным тоном

Зависит от задачи.
Иногда увеличение производительности в 100 раз важнее.

Sha © (31.12.06 17:07) [31]
ага
но вообще его задача очень проста, вариантов оптимизации куча
я поэтому и удивился почему у него возникли трудности...

Sha © (31.12.06 16:26) [29]
Тогда уж идти дальше: прямо в парсящююся строку писать счетчик ссылок, длину кусочка и 0-байт на конец. Опять же при условии, что каждая подстрока сразу же подается в каку-нибудь функцию, где не запоминается, и после этого никак не нужна. Иначе оптимизировать в SetString нечего, разве что выделить под все общий буфер и зашкалить счетчики ссылок.

> GrayFace © (01.01.07 01:48) [34]
> Тогда уж идти дальше: прямо в парсящююся строку...

Очень сильно не рекомендую. Вдруг придется парсить проекцию файла.

Хотел в свое время так сделать в XML-парсере, но вовремя остановился.
В итоге ща безразлично, что парсить: строки, буфера, стримы.
Выгода неоспорима, а потери быстродействия на стримах - всего несколько процентов.

Пятничная задачка ;) Найти похожие ветки