Перемешивание строк / Delphi/RAD XE4

[Kirilis2018]

Ребята как переделать вот этот код - под чтение построчно. Что бы не загружать в память.

var
  s: TStringList;
  z, p, q: Integer;
begin
  s := TStringList.Create;
  s.LoadFromFile('C:\text.txt');
  z := 50;
  while (z > 0) do begin
    p := random(s.Count); q := random(s.Count);
    s.Exchange(p, q);
    dec(z);
  end;
  s.SaveToFile('c:\text.txt');
  s.Free;
end;

Начал переделывать вот так (но вот в регуляровкой рандом не дружу):

var
    z, p, q: Integer;
    ft, ft2: TextFile;
    s:string;
 
begin
  if OpenDialog1.Execute then begin
  AssignFile(ft, OpenDialog1.FileName);
  Reset(ft);
  AssignFile(ft2, ExtractFileDir(OpenDialog1.FileName)+'\rez.txt');
  Rewrite(ft2); // чтобы создался новый, если нету, или перезаписался с нуля
  Append(ft2); // чтобы можно было добавлять строки, а не перезаписывать каждый раз
 begin
while not eof(ft) do
 begin
readln(ft,s);
//////////////////////////////////////
Вот тут не знаю что дописать ?
//////////////////////////////////////
writeln(ft2,s)
 end;
closefile(ft);
closefile(ft2);
end;
end;
end;

Подскажите кто сможет ?
То есть решение задачи: перемешивание строк в текстовом файле размером 500 - 700 мегабайт.

[MBo]

На SO ты сонм своих однообразных вопросов под женским ником пишешь.
Раздвоение личности мешает разобраться однажды и навсегда?

[^D^ima]

Цитата Kirilis2018 @ 07.03.18, 12:59

  Rewrite(ft2); // чтобы создался новый, если нету, или перезаписался с нуля
  Append(ft2); // чтобы можно было добавлять строки, а не перезаписывать каждый раз

Так не прокатит.

If FileExist(ft2) Then Append(ft2) else  Rewrite(ft2);

[Kirilis2018]

Цитата MBo @ 07.03.18, 13:13

На SO ты сонм своих однообразных вопросов под женским ником пишешь.
Раздвоение личности мешает разобраться однажды и навсегда?

То я с сестрой по очереди. Учим вместе Delphi, потому так (один аккаунт на двоих).

Добавлено 07.03.18, 13:16
^D^ima
А как тогда проще сделать ? Подскажите пожалуйста.

Сообщение отредактировано: Kirilis2018 - 07.03.18, 13:19

[Славян]

Пока самым оптимальным вариантом вижу такой:
1. Открываем файл со строками в двоичном режиме.
2. Читаем файл побайтно(пословно, если уникод), узнавая где строки начинаются, занося в память (в таблицу) начало каждой новой строки.
3. Создаём массив номеров строк в памяти.
4. Перемешиваем этот массив тем случайным способом.
5. Аккуратно идём по этим перемешаным номерам, понимаем какая строка нужна сюда и двоично читаем её из того файла со смещением из таблицы, пишем в результат.
Всё.

П.С. тьма двоичных перемещений по файлу со строками всё равно останется. Что весьма печально. Но памяти будет расходоваться крайне мало!

[^D^ima]

Цитата Kirilis2018 @ 07.03.18, 13:15

А как тогда проще сделать ? Подскажите пожалуйста.

Тогда нужно понимать из чего состоит файл, из строк фиксированной длины или чего-то ещё?

[Kirilis2018]

Цитата ^D^ima @ 07.03.18, 13:32

Тогда нужно понимать из чего состоит файл, из строк фиксированной длины или чего-то ещё?

Файл состоит из строк разной длины. Разные предложения и цифры.

[^D^ima]

Это самый плохой вариант в данном случаи. Возможно меня коллеги поправят но я думаю что стратегия зсключается в считывании в случайном порядке строк из входящего файла и последовательной записи в исходялий. Для этого нужно составить карту файла и найти смещения и длину всех строк. Данные записать в массив. Массив перемешать и перемещаясь по файлу согласно даному массиву вычитывать файл. Если бы строки былибы фиксированной длины, былобы проще в разы

[^D^ima]

примерно так:

procedure TForm1.Button1Click(Sender: TObject);
Type
  TRec = record
           SeekBegin:Longint;
           StringLength:Longint;
         end;
Var
FInMap:TextFile;
FIn,FOut:File;
S:String;
 
StringCount,NumRead:Longint;
 
FileMap:array[0..1000] of TRec;
 
C:array[1..2048] of char;
 
begin
  assignfile(FInMap,'c:\123.txt');
  Reset(FInMap);
  StringCount:=1;
    While not eof(FInMap) do
      Begin
        Readln(FInMap,s);
        FileMap[StringCount].SeekBegin:=FileMap[StringCount-1].SeekBegin+FileMap[StringCount-1].StringLength;
        FileMap[StringCount].StringLength:=Length(s)+2;
        Inc(StringCount);
      End;
  FileMap[StringCount].StringLength:=FileMap[StringCount].StringLength-2;
  CloseFile(FInMap);
 
//тут перемешиваем   FileMap
 
 
  assignfile(FIn,'c:\123.txt');
  assignfile(FOut,'c:\321.txt');
  Reset(FIn,1);
  Rewrite(FOut,1);
 
    For StringCount:=1 To StringCount-1 do
      Begin
      Seek(FIn,FileMap[StringCount].SeekBegin);
        BlockRead(FIn,C,FileMap[StringCount].StringLength,NumRead);
        BlockWrite(FOut,C,NumRead);
      End;
  CloseFile(FOut);
  CloseFile(FIn);
end;

Тут такая особенность работы с текстовыми файлами: Каждая строка заканчивается невидимым символом в блокноте CRLF, поэтому работая через поблочное чтение\запись учитываем 2 байта. Везде кроме последней строки. Так что при перемешивании учитываем такую особенность.Или не перемешивать последнюю сроку или отслеживать самостоятельо данный момент. Возможен вариант когда уже в поблочной записи вставляются эти символы. В коде не отработаен вариант с динамическим масивом FileMap, а его нужно делать по хорошему динамическим иначе может быть вариант когда кол-во строк ыайла выше 1000, или любого другого значения. который мы поставим.

Добавлено 07.03.18, 19:10
Ну и да, нет самого перемешивания массива

[LMM]

Цитата Kirilis2018 @ 07.03.18, 12:59

в регуляровкой рандом не дружу

Random() и Randomoze() - http://delphi-help.ru/index.php?option=com...hislah-v-delphi
Пример на С++ Builder, сорри, думаю - разберёшься. Или тут помогут переписать.

  TStringList *src = new TStringList(); // источник
  TStringList *dst = new TStringList(); // приёмник
  src->LoadFromFile("src.txt");
  int count = src->Count; // начальное количество строк - значение счётчика
  Randomize();
  int pos = Random(count); // случайнаяпозиция строки для копирования
  while (coumt >= 0) {
    dst->Add(src->Strings[pos]); // скопировать из источника в приёмник
    dst->Delete(pos); // УДАЛИТЬ строку из источника, она уже есть в приёмнике
    count--; // уменьшить счётчик
    pos = Random(count); // получить новую случайную позицию в мсточнике
  }
  dst->SaveToFile("dst.txt");
  detete src;
  delete dst;

[leo]

Цитата Kirilis2018 @ 07.03.18, 12:59

решение задачи: перемешивание строк в текстовом файле размером 500 - 700 мегабайт.

Судя по тому, что у тебя в нескольких темах фигурирует размер файла (именно) до 700 Мб и платформа Delphi\RAD XE4, то это похоже на "вопрос на засыпку".
Дело в том, что если текстовый файл представлен в кодировке ANSI (что скорее всего), то на старом\добром Delphi 7 загрузка 700 Мб в TStringList не должна представлять особых проблем. А в версиях Delphi\RAD, использующих по умолчанию юникод, скорее всего будут проблемы в 32-битных приложениях, т.к. при преобразовании ANSI в юникод объем занимаемой памяти (тупо\бестолково) возрастает в два раза. Поэтому, если речь идет о размерах файла до 500-700 Мб (а не о "страшных" гигабайтах, которые явно невозможно загрузить в память в 32-битных приложениях), то решением "проблемы" может быть загрузка строк не в стандартный TStringList, хранящий string в формате юникод, а в некий TList (обычный или дженерик), хранящий AnsiString.

[Славян]

И всё же, leo, наибольший интерес представляет именно сортировка текстового файла с количеством строк в миллионы..миллиарды. Именно такое красивое решение я бы, как преподаватель, оценил=похвалил. А пока никто такового не предложил.

[leo]

Цитата Славян @ 08.03.18, 10:16

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

А я считаю, что текстовые файлы размером даже в сотни Мб - это уже нонсенс и верх тупости\идиотизма. А заниматься тупой "сортировкой" таких файлов (без преобразования формата, создания вспомогательных индексных файлов и т.п.) - это еще большая тупость\идиотизм

[LMM]

leo, кабы сортировка! У ТС надо просто перемешать. А на... э-э-э, зачем???

[^D^ima]

LMM
Так в задании сказано что нельзя копироввть в память

[leo]

Цитата ^D^ima @ 08.03.18, 11:14

Так в задании сказано что нельзя копироввть в память

Насколько я понял, задание в #1 выделено жирным шрифтом, и там ничего не сказано о том, что можно, а что нельзя. Но у ТС это не первое задание на обработку текстовых файлов размером до 500-700 Мб, и все его попытки использовать TStringList в XE4 приводят к out of memory. Причина, надеюсь, всем понятна - удвоение занимаемой памяти при (тупом, и в данном случае совершенно ненужном) преобразовании AnsiString в юникод. Если бы стояла задача решить проблему только на уровне работы с файлами без их полной загрузки в память, то можно было бы сразу задать размер файла в 2 и более Гб. Но поскольку речь идет именно о 500-700 Мб, то это явно вопрос "на засыпку", который предполагает, что данную задачу можно решить и с загрузкой всего файла в память.

[Fr0sT]

Как вообще при наличии свопа может взбухать out of memory на жалких полтора гига? Тем паче что это не один кусок, а куча независимых строк.

Автору: задача явно учебная, ибо осмысленности в ней ноль, поэтому надо сразу указывать четкую формулировку.

По сабжу:
- первый проход - чтение построчно, сохранение для каждой строки смещений относительно начала файла
- перемешивание - создание второго массива смещений, наполнение его рандомными элементами из первого массива. Либо проход по каждому элементу исходного массива и обмен значениями текущего элемента с рандомным
- выдача результата - проход по перемешанному массиву, позиционирование+readln(f_src, s)+writeln(f_dst, s)

Сообщение отредактировано: Fr0sT - 12.03.18, 12:14

[leo]

Цитата Fr0sT @ 12.03.18, 12:12

Как вообще при наличии свопа может взбухать out of memory на жалких полтора гига? Тем паче что это не один кусок, а куча независимых строк.

Ты знаешь, как работает TStrings.LoadFromFile\Stream?
В D7 весь файл читается в локальную переменную s:AnsiString и затем формируется список строк простым вызовом Strings.Text:=s. При размере файла до 700 Мб и более, это уже может вызвать проблемы в 32-битном приложении, т.к. из-за фрагментации адресного пространства (АП) может просто не оказаться непрерывного диапазона адресов такого размера (из-за некоторых дурных dll, норовящих загрузиться в середину АП).
Но в современных XE это реализовано еще тупее - сначала весь файл читается в дин.массив TBytes, а затем вызовом TEncoding.GetString из этого массива формируется юникод-строка (удвоенного размера, если файл представлен в ANSI), которая затем используется для формирования списка тем же Strings.Text:=s. Сам понимаешь, что в 32 битном приложении два непрерывных куска памяти по 700 и 1400 Мб, плюс более 1400 Мб отдельных строк - уже ни в какие ворота не лезут. Отсюда и out of memory. И никакой своп тут ни при чем, т.к. просто\банально не хватает нужного адресного пространства.

PS: Такая реализация прекрасно работает для текстовых файлов "нормального" размера. Поэтому это не тупость Борланда\Эмбаркадеро, а тупость тех, кто пытается использовать TStrings.LoadFromFile для текстовых файлов нереально большого размера.

[Fr0sT]

leo, да, про момент загрузки я забыл, каюсь. К сожалению, с покусочным чтением не стали заморачиваться (хотя Эмбы и не одни в этом - даже более специализированный редактор Akelpad тоже грешит таким неоптимальным механизмом).
Связка TFileStream+TStreamReader (либо старый добрый Readln) поможет избежать перерасхода памяти

[leo]

Цитата Fr0sT @ 13.03.18, 07:15

Связка TFileStream+TStreamReader (либо старый добрый Readln) поможет избежать перерасхода памяти

В том-то и дело. По моему, эта задачка не школьно-учебная, а скорее тестовая\конкурсная. Да, можно ее решить универсально с индексацией строк файла и его повторным рандомным чтением. Но тут можно нарваться на ужасные тормоза при рандомном чтении файла (а можно и не нарваться, если винда при наличии свободной физ. памяти закэширует весь файл при первом чтении). Хотя 700 Мб (не одним куском, а в виде отдельных строк), это действительно не много, поэтому эту задачку можно решить и с загрузкой всех строк в память, но не на основе стандартного TStringList, а на основе TList или дин.массива AnsiString с блочным чтением файла (хоть тем же Readln, хотя для увеличения скорости и "крутизны" я бы добавил к нему SetTextBuf размером в 8-16 кБ).

Сообщение отредактировано: leo - 13.03.18, 07:53

[^D^ima]

Друзья, тут
https://stackoverflow.com/questions/2700790...arge-text-files

предлагают использовать TStreamReader
Я правильно понимаю что он считывает кусками, и ему не нужна память одним куском?

Добавлено 13.03.18, 08:17
Т.е. можно просто в коде из первого поста поменять строку?

Цитата Kirilis2018 @ 07.03.18, 12:59

s.LoadFromFile('C:\text.txt');

на

  AssignFile(F,'C:\text.txt');
  Reset(F);
    While not EOF(f) do
      Begin
        ReadLn(F,St);
        s.Add(St);
      End;
  CloseFile(F);

?

[leo]

Цитата ^D^ima @ 13.03.18, 08:07

предлагают использовать TStreamReader
Я правильно понимаю что он считывает кусками, и ему не нужна память одним куском?

Да. Судя по всему размер буфера по умолчанию составляет 4 Кб.

PS: В принципе и у обычного TextFile есть буфер по умолчанию в 128 байт, который можно заменить на свой собственный любого размера через SetTextBuf.

Цитата ^D^ima @ 13.03.18, 08:07

Т.е. можно просто в коде из первого поста поменять строку?

Можно, но в современных юникодных дельфях это будет приводить к бестолковому увеличению занимаемой памяти в 2 раза (если исходный файл в ANSI). Хотя 700*2 Мб (в виде отдельных строк, а не одним непрерывным блоком) должны выделяться без особых проблем.
Но все же правильнее\лучше не расходовать попусту память и реализовать свой список или массив AnsiString на основе TList или динамического массива.

[Pavia]

^D^ima

Цитата ^D^ima @ 13.03.18, 08:07

предлагают использовать TStreamReader
Я правильно понимаю что он считывает кусками, и ему не нужна память одним куском?

Когда последний раз его изучал это было не так. Может и допилили.


leo

Цитата leo @ 13.03.18, 08:44

к бестолковому увеличению занимаемой памяти в 2 раза (если исходный файл в ANSI).

Пока современный дельфи моськой не ткнёшь он не конвертирует строки, а хранит в начале номер кодовой страницы.

[Fr0sT]

Цитата leo @ 13.03.18, 07:52

Да, можно ее решить универсально с индексацией строк файла и его повторным рандомным чтением. Но тут можно нарваться на ужасные тормоза при рандомном чтении файла (а можно и не нарваться, если винда при наличии свободной физ. памяти закэширует весь файл при первом чтении).

Условия не озвучены, а значит, на тормоза пофиг...

Цитата ^D^ima @ 13.03.18, 08:07

Я правильно понимаю что он считывает кусками, и ему не нужна память одним куском?

Да. Именно для этого стримы и предназначены.

Цитата Pavia @ 13.03.18, 09:36

Пока современный дельфи моськой не ткнёшь он не конвертирует строки, а хранит в начале номер кодовой страницы.

Зависит от. Readln уже возвращает wide строку. Правда, возможно, есть и оверлоад вариант для ansi

Сообщение отредактировано: Fr0sT - 13.03.18, 11:31

[leo]

Цитата Pavia @ 13.03.18, 09:36

Пока современный дельфи моськой не ткнёшь он не конвертирует строки, а хранит в начале номер кодовой страницы.

Pavia, при всем уважении - либо ты не ту траву куришь (не те доки или блоги читаешь), либо говоришь о каких-то супер-пупер "современных дельфи", которых еще ни у кого нет
Вот пришлось проверить твои заявления на недавней халявной D 10.1 Берлин-Хеми:
1) если читаем Readln в AnsiString, то ес-но и получаем AnsiString в однобайтовой кодировке;
2) если читаем просто в String, то также ес-но получаем юникод-строку с двухбайтовой кодировкой;
3) если добавляем AnsiString в TStringList, то она автоматом преобразуется в юникод с двухбайтовой кодировкой.

Ну и где тут "моська"? А-у-у?

[leo]

Цитата Fr0sT @ 13.03.18, 11:30

Условия не озвучены, а значит, на тормоза пофиг...

Какой-то странный подход...
Ну и "Какой ты, нафиг, танкист?!"(С), ведь "Таких не берут в космонавты!" (С)

В догонку к вопросу by ^D^ima из #21

Цитата ^D^ima @ 13.03.18, 08:07

Т.е. можно просто в коде из первого поста поменять строку?

По хорошему еще нужно:
1) Заменить тип St на AnsiString, а s с TStringList на дженерик TList<AnsiString>
2) Выделить буфер чтения Buf:array[0..4096*2-1] of byte и установить его через SetTextBuf сразу после Reset(F)
3) Я бы еще дополнительно задал TList.Capacity:=GetFileSize(TTextRec(F).Handle) div N, (где N = 8-16), чтобы не гонять попусту данные при последовательном наращивании длины массива указателей в TList.

Сообщение отредактировано: leo - 13.03.18, 12:39

[Fr0sT]

Цитата leo @ 13.03.18, 12:32

Какой-то странный подход...
Ну и "Какой ты, нафиг, танкист?!"(С), ведь "Таких не берут в космонавты!" (С)

А смысл пузыриться оптимизировать, если задание учебное и в требованиях ничего не прописано?