Сформировать список

← →
NieL © (2011-02-02 15:06) [0]

в каталоге помимо прочих файлов, хранятся файлы в формате test1.txt, test6.txt, test11.txt test24.txt, ... Нужно сформировать список имен файлов в таком формате и отсортировать его по целочисленному значению в имени файла. Как грамотнее сделать:

[1-й вариант]: сортировать после сформированный список

1. FindFirst/FindNext формируем TStringList
2. Пишем функцию сортировки (MySortProc)
3. Вызываем TStringList.CustomSort(MySortProc)

[2-й вариант]: сортировать на момент формирования списка

Как лучше?

← →
Ega23 © (2011-02-02 15:09) [1]

> Как лучше?

От задачи зависит. Тупо, дёшево и в лоб - 1-й вариант.

← →
Игорь Шевченко © (2011-02-02 15:09) [2]

сортировать сформированный. на момент test11 будет перед test2

← →
Ega23 © (2011-02-02 15:11) [3]

> на момент test11 будет перед test2

Ну дык. Надо же с нуля начинать. 01, 02, ..., 09, 10, 11, 12, ...
тогда всё нормуль будет.

← →
niel © (2011-02-02 15:28) [4]

вот набросал если делать по варианту 2:
И еще: мне переодически нужно будет сравнивать значения в именах файла, можем стоит сделать целочисленный список для удобства, а когда необходимо полное имя файла, только добавлять приставку "test" и окончание ".txt".

procedure TForm1.Button1Click(Sender: TObject); var find_data: WIN32_FIND_DATA; hFind: Cardinal; X, N: Integer; Prepared: TList<Integer>; begin Prepared := TList<Integer>.Create( TComparer<Integer>.Construct( function (const AVal1, AVal2: Integer): Integer begin Result := CompareValue(AVal1, AVal2); end )); try hFind := FindFirstFile(PChar(Fwork_dir + "test*.txt"), find_data); if hFind <> INVALID_HANDLE_VALUE then try repeat get_num(find_data.cFileName, X); Prepared.BinarySearch(X, N); Prepared.Insert(N, X); until not FindNextFile(hFind, find_data); finally FindClose(hFind); end; // ... что-то делаем finally Prepared.Free; end; end;

← →
KSergey © (2011-02-02 15:30) [5]

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

← →
Ega23 © (2011-02-02 15:33) [6]

> отсортировать готовый список - то быстрее, чем пересортировывать
> список при каждой вставке,

Ой-ли?

← →
Anatoly Podgoretsky © (2011-02-02 22:17) [7]

> Ega23 (02.02.2011 15:11:03) [3]

0000022
2000000

← →
Anatoly Podgoretsky © (2011-02-02 22:18) [8]

> NieL (02.02.2011 15:06:00) [0]

Как угодно, результат одинаковый, лишь бы правильно.

← →
Ega23 © (2011-02-02 22:28) [9]

> 0000022
> 2000000

Ну и чо, нормально. Как раз.

← →
Anatoly Podgoretsky © (2011-02-02 22:56) [10]

> Ega23 (02.02.2011 22:28:09) [9]

Это нормально когда известно сколько и когда калькулятор есть.

← →
Servy © (2011-02-02 23:50) [11]

> Как лучше?

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

С другой стороны, оно вам надо оптимизировать этот процесс? Я сильно сомневаюсь, что у вас там больше 100000 файлов в одной папке, а сортировка такого количества записей займет пусть 50 милисекунд. Вам правда нужно быстрее? :) Ну тогда можно дерево туда прибабахать, вставка в дерево не приводит к необходимости перемещать элементы, однако дерево неплохо бы балансировать...

Кстати, раз уж у вас есть generic"и, у вас там и IOUtils.pas должен быть, а в нем для поиска файлов обертки написали, чтобы с вин апи не мучиться. Таким образом, для простоты и краткости кода, если сильно не заморачиваться с производительностью, можно было написать как-нибудь так:

function GetNum(S: string): Integer; begin Result := StrToInt(Copy(ChangeFileExt(ExtractFileName(S), ""), 5, High(Integer))); end; var S: TStringDynArray; ... S := TDirectory.GetFiles(FWork_dir, "test*.txt", TSearchOption.soTopDirectoryOnly); TArray.Sort<string>(S, TComparer<String>.Construct( function (const AVal1, AVal2: string): Integer begin Result := GetNum(AVal1) - GetNum(AVal2); end ));

Хотя сама идея, создавать сотни файликов типа testXXX.txt не кажется мне верхом гениальности. Может, ну их нафиг, эти горы файликов, и записать все в одну базу данных, например? Впрочем, тут сильно зависит от задачи.

← →
Ega23 © (2011-02-03 00:27) [12]

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

Это смотря как организовать. Берём обычный array of string, а рядом кладём TList с отсортированными индексами массива.
Таким образом перетряхиваются только индексы массива, а в самом массиве данные лежат в порядке добавления.

← →
Servy © (2011-02-03 01:12) [13]

> Это смотря как организовать. Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.
>
> Таким образом перетряхиваются только индексы массива, а
> в самом массиве данные лежат в порядке добавления.

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

Тормоза в том, что Insert в начало TList"а (хоть строк, хоть индексов) приводит к необходимости сдвинуть все находящиеся правее места вставки элементы, которых может быть дохрена.

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

← →
Германн © (2011-02-03 01:25) [14]

> Так как строка суть указатель, принципиально перемещение
> строк (без их изменения) от перемещения индексов не отличается.

Отсюда пожалуйста подробнее.

← →
Servy © (2011-02-03 01:34) [15]

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

Всегда к вашим услугам. Какая часть моего утверждения подвергается сомнению?

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

← →
Германн © (2011-02-03 03:23) [16]

> Какая часть моего утверждения подвергается сомнению

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

← →
Servy © (2011-02-03 03:59) [17]

> > Какая часть моего утверждения подвергается сомнению
>
> Наличие или отсутствие алгоритма сортировки строк по их
> указателям с учетом их значений.

Вы точно ответили на тот вопрос, который процитировали? Где я говорил о наличии или отсутствии алгоритма сортировки строк?

Впрочем, раз вы хотите обсудить данный вопрос - очевидно, что алгоритмы сортировки наличествуют, у Кнута вон про них целый том написан. В том числе, они позволяют сортировать строки (вы главное функцию сравнения определите).

Теперь давайте для улучшения взаимопонимания, я проведу краткий экскурс в историю данной ветки:

[0]. Автор сообщает, что придумал 2 метода решения своей задачи:
1. Собрать список файлов в массив и отсортировать оный массив
2. Вставлять очередной найденный файл в нужное место в массиве, таким образом, сохраняя массив все время в отсортированном состоянии и позволяя находить позицию для вставки очередного элемента бинарным поиском. Реализацию автор привел в [4].

[11]. Я говорю:

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

[12]. Ega23 возражает на приведенную выше часть моего сообщения:

> Это смотря как организовать. Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.
>
> Таким образом перетряхиваются только индексы массива, а
> в самом массиве данные лежат в порядке добавления.

[13]. Я отвечаю, что:
1. В применении к первому варианту, его совет не даст выигрыша, так как сортировка массива строк принципиально не отличается от сортировки массива индексов строк, так как строка суть указатель.
2. Проблема второго варианта заключается в наличии сдвига элементов при вставке в начало списка, и она тоже не решается приведенным Ega23 методом, так как сдвигать элементы при использовании массива (а не, скажем, связанного списка или дерева) придется в любом случае, а размер указателя на строку равен размеру индекса.

Далее появляетесь вы, и просите объяснить что-то подробнее (правда, не уточняя что), как бы намекая, что видите в моих рассуждениях какую-то неточность, что заставляет меня задуматься, не ляпнул ли я где очевидную глупость. Однако обнаружить таковую мне не удалось.

Если наше взаимонепонимание все еще не исчезло, постарайтесь уточнить, что именно вам показалось ошибочным и почему.

← →
Ega23 © (2011-02-03 08:43) [18]

> а размер указателя на строку равен размеру индекса.

Размер указателя на строку - да. Размер TStringListItem - нет.

← →
han_malign (2011-02-03 09:28) [19]

> Размер указателя на строку - да. Размер TStringListItem - нет.

- не придирайся - сильно оно утянуло, что тормоза начнутся не на 100 тысячах записей а на 50... И тогда уж - нафига индексы в линейном списке сортировать, если с тем же успехом можно красно-черное дерево построить...

Метод вставок хорош если входной поток квази-сортирован в правильную сторону, терпим для случайного распределения, ну и есть еще запущенный случай... А последовательность входных данных нам, в случае NTFS, более-менее известна - 1, 10, 100, 11, ... , 199, 2, 20 ...

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

← →
clickmaker © (2011-02-03 11:18) [20]

> отсортировать его по целочисленному значению в имени файла

для сравнения можно юзать StrCmpLogicalW

← →
Anatoly Podgoretsky © (2011-02-03 12:06) [21]

> Servy (03.02.2011 01:34:15) [15]

Только то что, строка это не указатель, а умный указатель, что приводит к
накладным расходам, да и влететь на ошибках можно.

> Servy (03.02.2011 03:59:17) [17]

Кстати а ничего, что внутри это тот же TList

> Размер указателя на строку - да. Размер TStringListItem
> - нет.

Кто такой TStringListItem и какое он имеет отношение к обсуждавшемуся:

> Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.

?

> Только то что, строка это не указатель, а умный указатель,
> что приводит к
> накладным расходам, да и влететь на ошибках можно.

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

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

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

> Кстати а ничего, что внутри это тот же TList

Ничего. Правда, я не понял, что именно в моем посте вызвало такую реакцию, но c TList"ом, будь он внутри или снаружи, все окей.

> Кто такой TStringListItem и какое он имеет отношение к обсуждавшемуся:

Он имеет отношение к TStringList из первого варианта. Если бы в стринглисте были голые строки - то да, никакой разницы.

> Servy (03.02.2011 14:00:23) [23]

Какие дополнительные накладные расходы для указателя целых, там же нет
никаких счетчиков ссылок и нет необходимости их корректировать, нет
необходимости создавать новую структуру и удалять ее, как у строк. С целыми
обычная пересылка C := A. A := B; B := C; простое копирование, а со строками
придется создать новую структуру С со счетчиком ссылок, Освободить память и
уменьшить ссылку, при этом откорректировать счетчик в С, далее повторить это
для B.
В общем грустно это делать для обмена строк.

> а со строками
> придется создать новую структуру С со счетчиком ссылок,
> Освободить память и
> уменьшить ссылку, при этом откорректировать счетчик в С,
> далее повторить это
> для B.

Какую память вы собрались освобождать? Ваш пример, если A, B, C типа string:

> C := A. A := B; B := C;

// C изначально указатель на nil - пустая строка
C := A; // C и A указывают на одно и то же место, счетчик ссылок равен 2
A := B; // Счетчик ссылок у C уменьшается до единицы, A и B указывают на одно и то же место, счетчик ссылок у них равен 2
B := C; // Счетчик ссылок у A уменьшается до единицы, B указывает туда же, куда и C, счетчик ссылок у них равен 2

// при выходе из области видимости C (так как это видимо временная переменная) счетчик ссылок у B уменьшится до единицы

Нет тут никаких перераспределений памяти, простая арифметика со счетчиками. А если обменять эти переменные местами игнорируя их умность (с помощью Move, например, так как мы знаем, что в результате операции обмена количество ссылок на строки A и B не должно измениться), то вообще никаких дополнительных расходов не наблюдается.

С другой стороны, когда вы используете дополнительный массив индексов для их сортировки, вы вынуждены сравнивать:

StrArray[IndexArray[A]] и StrArray[IndexArray[B]]

вместо

StrArray[A] и StrArray[B].

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

> Он имеет отношение к TStringList из первого варианта. Если
> бы в стринглисте были голые строки - то да, никакой разницы.

Да, вы правы, там еще связанный Object хранится, таким образом можно сдвигать 4х байтовые целые, а не восьмибайтовые структуры. Это кстати еще одно отличие для недавней ветке про отличия TStringList от TList<string>. Хотя мне все-равно видится сомнительной такая оптимизация, но теперь я понимаю, что вы имели в виду.

> но теперь я понимаю, что вы имели в виду.

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

> Servy (03.02.2011 17:34:26) [26]

Ты уже столько операций нарисовал, что страх берет

> Ты уже столько операций нарисовал, что страх берет

Я прочту это как "Я признаю, что зря утверждал о необходимости выделения и освобождения памяти при пересылке строк, однако мой тезис о необходимости дополнительных действий при такой операции (с которым вы и не спорили) по сравнению с пересылкой целых чисел остается в силе". Засим, считаю нашу дискуссию оконченной к обоюдному удовольствию.

> Но тут уже сам принцип интересен, когда у тебя сортируются
> не сущности, а индексы сущностей.

Сам принцип полезен, и знать о нем нужно обязательно, так что упомянули вы его в этой ветке не напрасно. Я просто выше пытался отметить, что алгоритмам из [0] он не сильно поможет.

Сформировать список Найти похожие ветки