Файл и динамический массив

← →
d3777 © (2006-04-05 18:07) [0]

есть текстовый файл. в нём матрица чисел(несколько столбцов- m, и много-много строк - n). вопрос: как динамически выделить под него массив, точнее как определить размер этого массива?
для определения кол-ва стобцов делал read(F, W[m]) до конца первой строки - но это помоему не выход.
а со строками вообще не понял как. просто устанавливал с запасом. но это тоже не выход: так как кол-во строк от файла к фалу изменяется от 2 до 1048576.
заранее спасибо

← →
Jeer © (2006-04-05 19:11) [1]

arX[i,j]
i - число строк текстового файла
j - число столбцов через парсинг строки по разграничителю.

arX: array of array of ..
SetLength()

← →
Джо © (2006-04-05 19:13) [2]

Ну, если структуру файла изменить нельзя, то, имхо, лучше не придумаешь, чем "выделять с запасом". Но делать это "по уму". Например, можно предложить такую стратегию: выделяем каждый раз в два раза больше, чем было выделено в предыдущий. В конце корректируем размер. Реальную стратегию нужно будет подобрать эмпирически на реальных (среднестатических, так сказать) данных.
Если это не подходит, то нужно изменять логику разбора содержимого файла. Например, вначале "пробегать" по всему файлу, подсчитывая строки и колонки. Затем выделить память под массив, и только после этого считывать значения.

← →
Anatoly Podgoretsky © (2006-04-05 19:45) [3]

С поправкой, вначале можно приблизительно оченить количество строк через размер файла, если взять средний размер числа + пробел
Кроме того нужна более подробная информация о файле, а вдруг колонки выровнены по ширине, тогда размер определяется просто и точно.

← →
Юрий Зотов © (2006-04-05 21:11) [4]

> как определить размер этого массива?

1. Читаем первую строку целиком в строчную переменную S. Элементарный парсинг этой строки даст кол-во столбцов в массиве (кол-во разделителей плюс единица).

2. Присваиваем счетчику 1 и в цикле while not EoF читаем в ту же переменную S остальные строки, каждый раз увеличивая счетчик на 1. Привыходе из цикла его значение даст кол-во строк в массиве.

3. Теперь пишем SetLength и повторно читаем файл уже в массив.

← →
d3777 © (2006-04-05 22:57) [5]

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

прокомментируйте пожалуйста

← →
Джо © (2006-04-05 23:01) [6]

> [5] d3777 © (05.04.06 22:57)
> только насколько я знаю при увеличении размера массива старые
> данные остаются и поэтому можно сначала задать массив 1х1,
> прочитать первую строку до конца каждый раз увеличивая
> колво столбцов на единицу, а потом с циклом с размером колва
> столбцоов читать до конца файла каждай раз увеличивая массив
> на одну строку.

Очень плохое решение.

Память под массив выделяется сплошным непрерывным блоком. Если размер нового массива не помещается в выделенную память (хоть на 1 байт ;), то
1. Менеджер памяти начнет искать блок подходящего размера
2. Зарезервирует в нем место
3. Скопирует все данных их старого блока в новый.

Вообще, стоит взять за правило: своди к минимуму кол-во вызовов SetLength.

← →
Anatoly Podgoretsky © (2006-04-05 23:02) [7]

d3777 © (05.04.06 22:57) [5]
И через некоторое время получишь сообщение об нехватке памяти. Память надо выделить сразу под весь массив.

← →
Джо © (2006-04-05 23:03) [8]

В идеале, должен быть вообще один вызов SetLength, а именно, при первоначальной инициализации :) Т.е, самая лучшая стратегия: заранее узнавать размер массива.

← →
Anatoly Podgoretsky © (2006-04-05 23:05) [9]

Джо © (05.04.06 23:03) [8]
Если узнать нельзя, то можно оценить и выделить в два раза больше, по окончанию скорректировать.

← →
Anatoly Podgoretsky © (2006-04-05 23:06) [10]

Оценить можно так, прочитать первые сто строк и аппроксимировать на весь размер файла.

← →
d3777 © (2006-04-05 23:12) [11]

хм...... спорный выход считать первые сто строк и апроксимировать........
можно не получить точное кол-во строк.

а если сначала выделить мах значение (оно известно), а потом скорректировать? будет ли в таком случае менеджер памяти весь этот массив иаскать или просто отрежет лишнее?

← →
Джо © (2006-04-05 23:31) [12]

> [9] Anatoly Podgoretsky © (05.04.06 23:05)
> Если узнать нельзя, то можно оценить и выделить в два раза
> больше, по окончанию скорректировать.

Угу, я именно нечто такое и предлагал в [2].

← →
Джо © (2006-04-05 23:32) [13]

> [11] d3777 © (05.04.06 23:12)
> будет ли в таком случае менеджер памяти
> весь этот массив иаскать или просто отрежет лишнее?

Будет. Откуда он знает, что там "лишнее"?

← →
d3777 © (2006-04-05 23:34) [14]

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

← →
Джо © (2006-04-05 23:34) [15]

> [11] d3777 © (05.04.06 23:12)
> хм...... спорный выход считать первые сто строк и апроксимировать........
>
> можно не получить точное кол-во строк.

А почему не хочешь обдумать вариант с двух-проходной стратегией? Вот Ю. Зотов набросал примерную схему.

← →
Джо © (2006-04-05 23:36) [16]

> [14] d3777 © (05.04.06 23:34)
> ок. всем огромное спасибо
> остановлюсь я на выделении мах

Также не очень хороший подход :)

← →
d3777 © (2006-04-05 23:39) [17]

хм..... лан
попробую оба способа с двумя файлами: один с мах колвом строк, а другой с мах/2. замеряю время обработки.

(у первого сразу виден минус - в начале скачёк объёма используемой памяти)
пробовал второй вариант, но читал поэлементно, а не строками - скорость на нуле, короче, практика покажет :)

← →
Юрий Зотов © (2006-04-05 23:42) [18]

Если узнать нельзя...

Почему нельзя? Чем плох способ [4]? Все сработает железно и точно, нет никаких проблем. И схема это не примерная, а точная, осталось лишь написать пару десятков строк простейшего кода.

← →
Джо © (2006-04-05 23:51) [19]

> d3777

Кстати, чтобы железным образом и окончательно убедить в пагубности постоянного изменения размера массива, вот код для оценки :)

type TByteArray = array of Byte; var LastTicks: Cardinal; procedure StartTickTimer; begin LastTicks := GetTickCount end; function TicksElapsed: Cardinal; begin Result := GetTickCount - LastTicks end; {$O-} procedure TForm1.Button1Click(Sender: TObject); const MAX_LN = 100000000; // 100 million var Bytes: TByteArray; I: Integer; begin // Сразу задаем размер массива StartTickTimer; SetLength (Bytes,MAX_LN); ShowMessageFmt("Tick elapsed: %d",[TicksElapsed]); Bytes := nil; // На каждой итерации увеличиваем размер на единицу StartTickTimer; for I := 1 to MAX_LN do SetLength (Bytes,Length(Bytes)+1); ShowMessageFmt("Tick elapsed: %d",[TicksElapsed]); end; {$O+}

Попробуй и сразу ощутишь разницу :)
На моей машине первый вариант выполнился за 93 тика, а второй за 13375 . Т.е,почти в 150 раз дольше ;)

← →
Джо © (2006-04-05 23:56) [20]

> [19] Джо © (05.04.06 23:51)

Для "чистоты эксперимента" можно даже во втором варианте поставить SetLength (Bytes,I);

← →
d3777 © (2006-04-06 00:16) [21]

замерил.........хех.............практика показала что второй вариант отметается сразу же (только у меня значения у первого около 1000тиков, у второго около 20000)

а иеперь глупый вопрос (просто никогда этим раньше не занимался):
1. Читаем первую строку целиком в строчную переменную S. Элементарный парсинг этой строки даст кол-во столбцов в массиве (кол-во разделителей плюс единица).
реализацию вот этого. точнее как табы искать в строке? и вообще, как определить вдруг там не таб, а несколько пробелов?

← →
Anatoly Podgoretsky © (2006-04-06 00:18) [22]

Привел бы формат файла, строк так 10 и максимальный предполагаемый размер файла. А то чего гадать.

← →
d3777 © (2006-04-06 00:20) [23]

2Anatoly Podgoretsky
уже привёл в другом месте :)

← →
Anatoly Podgoretsky © (2006-04-06 00:45) [24]

Тогда аппроксимирование размера файла на количество строк, например по первым ста строкам с запасом на ошибку, например умножить расчетную величину на 1.3-1.5 и обрезанием по окончанию. Пересылки не будет, перераспределения не будет. Формат файла у тебя характерный длина чисел меняется незначительно. В конце концов размер файла деленый на количество элементов в строке * 2 (один символ на пробел), сработает даже для односимволным чисел. Все что нужно это избежать перераспределение памяти в процессе чтения файла. Будет максимальная скорость и не будет резкого расхода памяти при перераспределении при каждой иттерации. Просто нужен разумный алгоритм.

← →
Джо © (2006-04-06 00:47) [25]

> и вообще, как определить вдруг там не таб, а несколько
> пробелов?

Символ табулятора имеет код 9, пробела — 32.

← →
d3777 © (2006-04-06 00:57) [26]

2Anatoly Podgoretsky

Вот это не очень понятно:
"В конце концов размер файла деленый на количество элементов в строке * 2 (один символ на пробел)"

может количество символов в строке подсчитывать?
но попадаются и односимвольные элементы массива (например просто 0),
но наверно коэффициент запаса всё сгладит.......

З.Ы. вот я и пытаюсь найти этот разумный алгоритм :)

← →
Юрий Зотов © (2006-04-06 01:51) [27]

procedure TForm1.FormCreate(Sender: TObject); const FileName = "C:\Numbers.txt"; Separators = [ #9, " "]; // Добавьте сюда любые возможные разделители var F: TextFile; i, j, M, N: integer; S: string; A: array of array of integer; begin // 1. Создаем файл, не вручную же его набивать AssignFile(F, FileName); Rewrite(F); for i := 0 to 99 do // 100 строк begin for j := 0 to 8 do // 9 столбцов Write(F, i, j, " "); WriteLn(F, i, 9) // и еще один, 10-й столбец end; CloseFile(F); // 2. Определяем кол-во столбцов N AssignFile(F, FileName); Reset(F); ReadLn(F, S); i := 1; N := 0; repeat while (i <= Length(S)) and (S[i] in Separators) do Inc(i); if i <= Length(S) then begin Inc(N); while (i <= Length(S)) and not (S[i] in Separators) do Inc(i) end until i > Length(S); // 3. Определяем кол-во строк M M := 1; while not EoF(F) do begin ReadLn(F, S); Inc(M) end; CloseFile(F); // 4. Заполняем массив повторным чтением файла. AssignFile(F, FileName); Reset(F); SetLength(A, M, N); for i := 0 to M - 1 do begin for j := 0 to N - 1 do Read(F, A[i, j]); ReadLn(F) end; CloseFile(F) end;

И какие проблемы? Задачка для школьников, как видите.

← →
d3777 © (2006-04-06 02:01) [28]

2Юрий Зотов ОГРОМНЕЙШЕЕ СПАСИБО за этот листинг!!!!!!!!!!!!!!!!!!!!!!!!!

но только вот есть по моему маленькая загвоздка - столбцы могут быть разделены несколькими пробелами :(

извиняюсь!!!!!!!!!! разобрался!!!!!! нет проблем :)

> d3777 © (06.04.06 02:01) [28]

Хоть ста пробелами, тысячей табуляторов и еще чем угодно в каком угодно количестве, хоть одновременно, хоть в любом наборе.

Внимательно посмотрите код, там есть цикл:
while (i <= Length(S)) and (S[i] in Separators) do Inc(i);
который пропустит любой набор любых разделителей в любом сочетании.

ещё раз спасибо!!!!! и ещё раз извиняюсь за свою невнимательность

> d3777 © (06.04.06 02:01) [28]
>
> 2Юрий Зотов ОГРОМНЕЙШЕЕ СПАСИБО за этот листинг!!!!!!!!
> !!!!!!!!!!!!!!!!!
>
> но только вот есть по моему маленькая загвоздка - столбцы
> могут быть разделены несколькими пробелами :(
>

А ты уверен, что загвоздка есть?
По-моему строка while (i <= Length(S)) and (S[i] in Separators) do
Inc(i);
её решает.

Оп-ля :(
А как это? Прочитал, ответил. И узнал, что уже в прошлом веке все прочитали и кто-то ответил???

в ручную надо страницу периодически обновлять

> d3777 © (06.04.06 02:27) [34]
>
> в ручную надо страницу периодически обновлять

Через сколько ms советуешь её обновлять?

d3777 © (06.04.06 00:57) [26]
"В конце концов размер файла деленый на количество элементов в строке * 2 (один символ на пробел)"

может количество символов в строке подсчитывать?
но попадаются и односимвольные элементы массива (например просто 0),
0 один символ, разделитель 1 символ, итого два и еще есть запас за счет разделителей строк. Так ты не мудри а прочитай первые сто (или сколько считаешь нужным) строк, аппроксимируй и результат умножь на коэффициент.

Юрий Зотов © (06.04.06 01:51) [27]
Не то слово

Можно организовать одномерные массивы соотвествующие строкам. Такой массив создается при чтении строки. А сам массив добалять в список. При таком решении получится список массивов и однопроходная схема загрузки. Думаю что с памятью больших накладок не получится.
Можно еще попробовать определившись со структурой файла отобразить часть его в память и работать с ним как с готовым массивом.
Хотя наверное это вариант слишком сложен. Из пушки по воробьям, однако. Зато решается проблема нехватки памяти при большом файле.

← →
Algol (2006-04-06 12:31) [38]

2ЮЗ
А зачем вы каждый раз открываете/закрываете файл?
Мне кажется во-первых это лишние операции, занимающие время, а во-вторых, это может помешать операционке оптимизировать доступ к файлу, при повторном его чтении. Я не прав?

> Algol (06.04.06 12:31) [38]

Это пример, а не рабочая программа. Основное требование к примеру - он должен быть как можно более понятным. Так он и написан.

> Algol (06.04.06 12:31) [38]

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

Файл и динамический массив Найти похожие ветки