Удалить подстроку из очень большой строки (больше 2 ГБ )

← →
*Ray* © (2007-09-07 18:42) [0]

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

Я сделал так:
Function Del_Str (longstring, string: string):string;
begin
while pos(str, longsting)>0 do
begin
del(longstring, pos(str, longstring), length(str)) ;
end;
result:=longstring;
end;

Функция работает, но одно даже присваивание result значение longstring займет в памяти 4 Гб, если строка 2 Гб. Не говря уже о других операциях. Надо что-то придумать.

Заранее всем ольшое спасибо за предложенные варианты!

← →
Riply © (2007-09-07 18:47) [1]

> [0] *Ray* © (07.09.07 18:42)
А с маленькими строками она работает ?

← →
Юрий Зотов © (2007-09-07 18:55) [2]

> *Ray* © (07.09.07 18:42)

> одно даже присваивание result значение longstring займет в памяти 4 Гб,
> если строка 2 Гб.

Не займет. При присваивании строковых переменных копия строки не создается, просто увеличивается счетчик ссылок на строку.

← →
DVM © (2007-09-07 18:56) [3]

> *Ray* ©

Лучше строку хранить в файле на диске и далее создать временный файл и переписывать туда все, кроме того, что требуется удалять. После переименовать исходный файл, на его место переименовать временный и если все ок, то удалить исходный.

← →
Инс © (2007-09-07 18:57) [4]

> Задача проста: Нужно написать функцию, удаляющую все вхождение
> подстроки в строке. Но есть одно условие: строка очень большая
> - около 2 Гб, может и больше

И как же она уместится в виртуальном адресном пространстве процесса на Win32?

> Функция работает, но одно даже присваивание result значение
> longstring займет в памяти 4 Гб, если строка 2 Гб.

Нет. result:=longstring; - это просто копирование указателя.

← →
*Ray* © (2007-09-07 18:59) [5]

А если обойтись без файла, можно как то дополнительно оптимизировать? ПУсть даже хоть немного, но лучше? Чтобы быстрее работало.

← →
Riply © (2007-09-07 19:01) [6]

> [5] *Ray* © (07.09.07 18:59)
Например, не считать pos(str, longstring) два раза :)

← →
Инс © (2007-09-07 19:01) [7]

> [5] *Ray* © (07.09.07 18:59)

Оно вообще не будет работать на Win32. Только если проецировать строку в память из файла частями.

← →
Palladin © (2007-09-07 19:02) [8]

> Юрий Зотов © (07.09.07 18:55) [2]

есть одно но... даже несколько...
во первых функции Del_Str (longstring, string: string) существовать не может, бо string reserved word, во вторых операция со строкой не переданной как var приводит к ее дубляжу и модификации дубликата... особенно при выполнении del()... информация переданная в идентификаторе параметром должна остаться не тронутой...

экзампл

procedure pp(s:String); Begin s:=copy(s,1,1); showmessage(s); End; procedure TForm1.Button1Click(Sender: TObject); var s:String; begin s:="12345"; pp(s); showmessage(s); end;

что бы удалить что то из подстроки, без лишнего расхода памяти придется таки использовать var в описании параметров процедуры или функции

← →
DVM © (2007-09-07 19:08) [9]

> А если обойтись без файла, можно как то дополнительно оптимизировать?

То, что ты написал переписать вообще. Кстати, ты ведь ищешь что-то фиксированное, если да, то можно написать функции, работющие быстрее Pos().

А насчет файла. Зачем тебе такая строка в памяти. Ты же ее все равно потом сохранять будешь. Или нет?

← →
*Ray* © (2007-09-07 19:13) [10]

to Riply:

Например, не считать pos(str, longstring) два раза :)

to Palladin:

> что бы удалить что то из подстроки, без лишнего расхода
> памяти придется таки использовать var в описании параметров
> процедуры или функции

тогда получается так:

Function Del_Str (var longstring, str: string):string;
var k:integer;
begin
k:=pos(str, longsting);
while k>0 do
begin
del(longstring, k, length(str)) ;
end;
result:=longstring;
end;

Что-нибудь еще можно улучшить?

← →
Инс © (2007-09-07 19:15) [11]

> [10] *Ray* © (07.09.07 19:13)

Вы читать вообще умеете? [4] и [7] прочтите еще раз. Будут вопросы по этому поводу - задавайте.

← →
*Ray* © (2007-09-07 19:15) [12]

точнее
Function Del_Str (var longstring, str: string):string;
var k:integer;
begin
k:=pos(str, longsting);
while k>0 do
begin
del(longstring, k, length(str)) ;
k:=pos(str, longsting);
end;
result:=longstring;
end;

← →
Palladin © (2007-09-07 19:16) [13]

ну во первых вопрос, тебе только одну подстроку str (кстати тоже не рекомендую использовать идентификатор с таким названием) удалить из строки или все?

← →
*Ray* © (2007-09-07 19:19) [14]

2 Palladin:

> ну во первых вопрос, тебе только одну подстроку str (кстати
> тоже не рекомендую использовать идентификатор с таким названием)
> удалить из строки или все?

нужно удалить все вхождения подстроки. А почему нельзя использовать даже "str?

← →
Юрий Зотов © (2007-09-07 19:20) [15]

> Palladin © (07.09.07 19:02) [8]

Тоже есть одно но... я говорил о присвоении (на что явно указал цитатой) и нигде ни разу не говорил об изменении.

Что же касаетеся изменений (т.е., сабжа), то сама постановка задачи представляется настолько странной, что лучше промолчать. Вот почему.

4 Гб - вся память. Из них верхние 2 Гб и нижние 64 Кб резервируются системой. Минус статическая память и стек. Под хип остается явно менее 2 Гб и поэтому непонятно, откуда вообще взялась строка длиной "около 2 Гб, может и больше".

Тут явно что-то недосказано, поэтому - какие можно дать рекомендации, не зная задачи?

← →
*Ray* © (2007-09-07 19:20) [16]

to Инс

> Оно вообще не будет работать на Win32. Только если проецировать
> строку в память из файла частями.

Объясните пожалуйста поподробнее. Прошу прощения, что сразу не заметил.

← →
Вася Правильный (2007-09-07 19:21) [17]

> большой строки (больше 2 ГБ )

из справки
String types Type Maximum length Memory required Used for ShortString 255 characters 2 to 256 bytes backward compatibility AnsiString ~2^31 characters 4 bytes to 2GB 8-bit (ANSI) characters, DBCS ANSI, MBCS ANSI, etc. WideString ~2^30 characters 4 bytes to 2GB Unicode characters; multi-user servers and multi-language applications

← →
Dib@zol © (2007-09-07 19:22) [18]

Ваще убит наповал... ОТКУДА берутся такие строки???????

← →
*Ray* © (2007-09-07 19:23) [19]

to Юрий Зотов:

Вполне возможно, что с 2 Гб я преувеличил. Я просто хотел сказать, что строка очень большая, и при обработке строки будет занято много ресурсов и поэтому даже малейшая оптимизация будет существенна.

← →
*Ray* © (2007-09-07 19:26) [20]

Спасибо всем большое за новые знания! Я понял что 2 Гб-это нереально. Может вы напишите как Вы бы работали просто с очень большой строкой, не будет конкретизировать размер. Может это совсем будет по-другому, чем у меня.

← →
Riply © (2007-09-07 19:27) [21]

> [20] *Ray* © (07.09.07 19:26)
Можно попробовать посчитать кол-во вхождений SubStr в LongString при помощи PosEx
Один раз сделать SetLength(Result,..) , и в него переместить подстроки Move()

← →
oxffff © (2007-09-07 19:28) [22]

function FastDel(const A:string;Pos,Count:integer):boolean;
var pi:pinteger;
begin
result:=false;
if (length(a)+1<pos+count) or (pos<1) then exit;
CopyMemory(pointer(DWORD(A)+Pos-1),pointer(DWORD(A)+Pos+Count-1),length(a)-pos-count+2);
pi:=pointer(a);
dec(pi);
PI^:=PI^-count;
result:=true;
end;

procedure TForm1.Button1Click(Sender: TObject);
var a,b:string;
c:pointer;
begin
a:="abc"+"dfs";
b:=a+"asdf";
FastDel(b,3,8);
showmessage(b);
end;

← →
Palladin © (2007-09-07 19:33) [23]

> *Ray* ©

я не сказал нельзя, я сказал, что не рекомендую, бо str одно из стандартных ключевых слов Паскаля... да и 2Гб это вполне реально, на 64x системах и 64x приложениях..
у Riply © (07.09.07 19:27) [21] хорошо описан механизм "дефрагментации" строки... нужно его релизовать используя > oxffff © (07.09.07 19:28) [22]

> Юрий Зотов © (07.09.07 19:20) [15]

"но" принято... 1 : 0.5 :)

← →
Denis_ © (2007-09-07 19:40) [24]

> Dib@zol © (07.09.07 19:22) [18]
> Ваще убит наповал... ОТКУДА берутся такие строки???????

Тебя что то смущает? (с)Anatoly Podgoretsky

← →
Rial © (2007-09-07 19:48) [25]

procedure DelInsides(Var sValue : String; Const sSubString : String); Var L : Integer; LS : Integer; Tmp : Integer; P : Integer; P1 : Integer; P2 : Integer; PS : Integer; begin L :=Length(sValue); LS :=Length(sSubString); Tmp :=L - LS + 1; P1 :=1; P :=1; While (P1 <= Tmp)do begin PS :=1; P2 :=P1; While(PS <= LS)and(sValue[P2] = sSubString[PS]) do begin Inc(P2); Inc(PS); end; If(PS > LS)then begin P1 :=P2; end else begin sValue[P] :=sValue[P1]; Inc(P1); Inc(P); end; end; If(P1 < L)then begin Tmp :=L - P1 + 1; Move(sValue[P1], sValue[P], Tmp); Inc(P, Tmp); end; SetLength(sValue, P - 1); end;

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

← →
Denis_ © (2007-09-07 19:49) [26]

> небольшой длины

2 ГБ?!

← →
Инс © (2007-09-07 20:14) [27]

> Объясните пожалуйста поподробнее. Прошу прощения, что сразу
> не заметил.

Юрий Зотов уже объяснил. 2 Гб адресного пространства всего доступно приложению в Win32 (еще два - система забирает под свои нужды). Из этих двух часть будет уже занята.

← →
Rial © (2007-09-07 20:15) [28]

> [26] Denis_ © (07.09.07 19:49)
> > небольшой длины
> 2 ГБ?!

2 ГБ - строка средних размеров. Используется, например,
в качестве заголовка окна.
На строках большой длины (от 4 ГБ) не проверял, так как
почти не приходилось работать с именами файлов. %)

> Инс © (07.09.07 20:14) [27]

Юрий акцентирует внимание на циферках потому, что человек (в природе у него заложено, зря писал чтоли :) ) не может абсолютно принять несущественность своей реплики и его ответ конечно автору не посуществу...

его пост абсолютно верен, но понимания происходящего приносит гораздо меньше чем мое замечание...

и я Юрия понимаю потому что сам такой же :)
да не обидится на меня мэтр :)

> [29] Palladin © (07.09.07 20:22)

Не совсем понял смысл Вашего комментария. Я в своем ответе сослался на уважаемого тезку из-за того, что меня попросили объяснить мои посты [4] и [7]. Заметив, что все, что хотел по этому поводу сказать я, уже сказано, мне нечего другого не оставалось, как сослаться на это. Да и добавить в общем то нечего, как мне этого не хотелось.

> не может абсолютно принять несущественность своей реплики
> и его ответ конечно автору не посуществу...

Кстати, совершенно с этим несогласен. Считаю, что в изначальной формулеровке, любой ответ не по существу (даже более того - неверный), кроме того, что на Win32 это невозможно, потому что (см. выше).

> Инс © (07.09.07 20:27) [30]

объясню...

[4], [7] это рассказ автору о том, что он описывает что то не реальное и такого вообще быть не может...

[8],[21],[22] объяснение ситуации и практические рекомендации по работе с большими объемами данных... потому что портировать функциональность move (Copy/Move Mem на работу с файлами большого объема не составляет труда)

> [8],[21],[22] объяснение ситуации и практические рекомендации
> по работе с большими объемами данных... потому что портировать
> функциональность move (Copy/Move Mem на работу с файлами
> большого объема не составляет труда)

Плохое объяснение, так как неверное, а именно:

> во вторых операция со строкой не переданной как var приводит
> к ее дубляжу и модификации дубликата

Здесь причина дубляжа - это операция Copy, а не передача строки в процедуру. При передачи строки дубляж не происходит, копируется указатель. В доказательство - код:
procedure pp(s:String); Begin PChar(s)^:="!"; End; procedure TForm1.Button1Click(Sender: TObject); var s:String; begin s:=Caption; pp(s); showmessage(s); end;

А если сделаете не так:
s:=Caption;
а так:
s:="12345";
то получите AV. Знаете почему? ;)

:) я что то не пойму... что этот код должен показать? ну вышло у меня сообщение "Form1", так я это и (до/по)казывал вообще то :)

в своем коде я показывал то, что работы по модифицированию string параметров процедуры передаваемых не по ссылке (var не указанно в параметрах) обязательно будут проводить к созданию другого string (а так оно и есть по все канонимам паскаля), другое дело что, если модифицирование строки переданной без var не происходит, тут Юрий прав абсолютно счетчик просто увеличивается... потому и 1 : 0.5

> ну вышло у меня сообщение "Form1", так я это и (до/по)казывал
> вообще то :)

Что, скопировать не смогли правильно??? Ну-ка еще раз ;) Или может голосование устроим, какое сообщение появилось :)))

> ну естественно,что дальше то? надеюсь ты понимаешь разницу
> между String и PChar?

Какое сообщение выскачило, прежде чем двигаться дальше?

ЗЫ: Я то понимаю ))

Кстати, не нравится PChar, давайте сделаем так:
PByte(s)^:=Ord("!");

суть не изменится

> ЗЫ: Я то понимаю ))

неужели? а с чего ты вдруг параметр объявленный как String приводишь к PChar и присваиваешь по указателю Pointer(s) (где s:String) какоето значение? я вообще не понимаю каким боком PChar сюда притесался то? пресловутая совместимость PChar и String не так совместима как ты думаешь... String это отнюдь не указатель на что то в памяти...

Удалить подстроку из очень большой строки (больше 2 ГБ ) Найти похожие ветки