| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Сформировать список
NieL © (2011-02-02 15:06:00)в каталоге помимо прочих файлов, хранятся файлы в формате test1.txt, test6.txt, test11.txt test24.txt, ... Нужно сформировать список имен файлов в таком формате и отсортировать его по целочисленному значению в имени файла. Как грамотнее сделать:
[1-й вариант]: сортировать после сформированный список
1. FindFirst/FindNext формируем TStringList
2. Пишем функцию сортировки (MySortProc)
3. Вызываем TStringList.CustomSort(MySortProc)
[2-й вариант]: сортировать на момент формирования списка
Как лучше?
Servy (2011-02-03 22:42:00) [1]
> Ты уже столько операций нарисовал, что страх берет
Я прочту это как "Я признаю, что зря утверждал о необходимости выделения и освобождения памяти при пересылке строк, однако мой тезис о необходимости дополнительных действий при такой операции (с которым вы и не спорили) по сравнению с пересылкой целых чисел остается в силе". Засим, считаю нашу дискуссию оконченной к обоюдному удовольствию.
> Но тут уже сам принцип интересен, когда у тебя сортируются
> не сущности, а индексы сущностей.
Сам принцип полезен, и знать о нем нужно обязательно, так что упомянули вы его в этой ветке не напрасно. Я просто выше пытался отметить, что алгоритмам из [0] он не сильно поможет.
Anatoly Podgoretsky (2011-02-03 19:49:00) [2]> Servy (03.02.2011 17:34:26) [26]
Ты уже столько операций нарисовал, что страх берет
Ega23 (2011-02-03 17:57:00) [3]
> но теперь я понимаю, что вы имели в виду.
На самом деле это мелочи, han_malign правильно сказал, что я придираюсь.
Но тут уже сам принцип интересен, когда у тебя сортируются не сущности, а индексы сущностей.
Servy (2011-02-03 17:48:00) [4]
> Он имеет отношение к TStringList из первого варианта. Если
> бы в стринглисте были голые строки - то да, никакой разницы.
Да, вы правы, там еще связанный Object хранится, таким образом можно сдвигать 4х байтовые целые, а не восьмибайтовые структуры. Это кстати еще одно отличие для недавней ветке про отличия TStringList от TList<string>. Хотя мне все-равно видится сомнительной такая оптимизация, но теперь я понимаю, что вы имели в виду.
Servy (2011-02-03 17:34:00) [5]
> а со строками
> придется создать новую структуру С со счетчиком ссылок,
> Освободить память и
> уменьшить ссылку, при этом откорректировать счетчик в С,
> далее повторить это
> для 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].
Что по-моему не сильно лучше вышеприведенных операций со счетчиками.
Anatoly Podgoretsky (2011-02-03 15:47:00) [6]> Servy (03.02.2011 14:00:23) [23]
Какие дополнительные накладные расходы для указателя целых, там же нет
никаких счетчиков ссылок и нет необходимости их корректировать, нет
необходимости создавать новую структуру и удалять ее, как у строк. С целыми
обычная пересылка C := A. A := B; B := C; простое копирование, а со строками
придется создать новую структуру С со счетчиком ссылок, Освободить память и
уменьшить ссылку, при этом откорректировать счетчик в С, далее повторить это
для B.
В общем грустно это делать для обмена строк.
Ega23 (2011-02-03 14:16:00) [7]
> Кто такой TStringListItem и какое он имеет отношение к обсуждавшемуся:
Он имеет отношение к TStringList из первого варианта. Если бы в стринглисте были голые строки - то да, никакой разницы.
Servy (2011-02-03 14:00:00) [8]
> Размер указателя на строку - да. Размер TStringListItem
> - нет.
Кто такой TStringListItem и какое он имеет отношение к обсуждавшемуся:
> Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.
?
> Только то что, строка это не указатель, а умный указатель,
> что приводит к
> накладным расходам, да и влететь на ошибках можно.
Вместо обращения к умному указателю, обращение к массиву целых чисел, в котором храниться индекс правильного указателя, как предлагал Ega23, тоже приводит к накладным расходам. И они столь же незначительны. Влететь на ошибках можно всегда.
> главная проблема, что - либо парсить имя на предмет номера
> при каждом сравнении(хотя возможен тупой вариант со сравнением
> сначала длинны), либо таки накапливать номера - что даст
> выигрыш и по памяти, и по производительности...
Абсолютно верное замечание. Правда, сомнения в необходимости оптимизации решения данной задачи уже высказывались.
> Кстати а ничего, что внутри это тот же TList
Ничего. Правда, я не понял, что именно в моем посте вызвало такую реакцию, но c TList'ом, будь он внутри или снаружи, все окей.
Anatoly Podgoretsky (2011-02-03 12:08:00) [9]> Servy (03.02.2011 03:59:17) [17]
Кстати а ничего, что внутри это тот же TList
Anatoly Podgoretsky (2011-02-03 12:06:00) [10]> Servy (03.02.2011 01:34:15) [15]
Только то что, строка это не указатель, а умный указатель, что приводит к
накладным расходам, да и влететь на ошибках можно.
clickmaker (2011-02-03 11:18:00) [11]> отсортировать его по целочисленному значению в имени файла
для сравнения можно юзать StrCmpLogicalW
han_malign (2011-02-03 09:28:00) [12]
> Размер указателя на строку - да. Размер TStringListItem - нет.
- не придирайся - сильно оно утянуло, что тормоза начнутся не на 100 тысячах записей а на 50... И тогда уж - нафига индексы в линейном списке сортировать, если с тем же успехом можно красно-черное дерево построить...
Метод вставок хорош если входной поток квази-сортирован в правильную сторону, терпим для случайного распределения, ну и есть еще запущенный случай... А последовательность входных данных нам, в случае NTFS, более-менее известна - 1, 10, 100, 11, ... , 199, 2, 20 ...
Помимо этого - в данной конкретной задаче, если не отвлекаться на советы изменить формат имени файла(хотя он и абсолютно верный), главная проблема, что - либо парсить имя на предмет номера при каждом сравнении(хотя возможен тупой вариант со сравнением сначала длинны), либо таки накапливать номера - что даст выигрыш и по памяти, и по производительности...
Ega23 (2011-02-03 08:43:00) [13]
> а размер указателя на строку равен размеру индекса.
Размер указателя на строку - да. Размер TStringListItem - нет.
Servy (2011-02-03 03:59:00) [14]
> > Какая часть моего утверждения подвергается сомнению
>
> Наличие или отсутствие алгоритма сортировки строк по их
> указателям с учетом их значений.
Вы точно ответили на тот вопрос, который процитировали? Где я говорил о наличии или отсутствии алгоритма сортировки строк?
Впрочем, раз вы хотите обсудить данный вопрос - очевидно, что алгоритмы сортировки наличествуют, у Кнута вон про них целый том написан. В том числе, они позволяют сортировать строки (вы главное функцию сравнения определите).
Теперь давайте для улучшения взаимопонимания, я проведу краткий экскурс в историю данной ветки:
[0]. Автор сообщает, что придумал 2 метода решения своей задачи:
1. Собрать список файлов в массив и отсортировать оный массив
2. Вставлять очередной найденный файл в нужное место в массиве, таким образом, сохраняя массив все время в отсортированном состоянии и позволяя находить позицию для вставки очередного элемента бинарным поиском. Реализацию автор привел в [4].
[11]. Я говорю:
> Во втором варианте у вас при вставке в начало списка будут
> сдвиги большого количества элементов, которых можно было
> бы избежать в первом варианте. С другой стороны, не требуется
> последующая сортировка. Какой из вариантов будет работать
> быстрее навскидку сказать сложно, да и зависит от входных
> данных
[12]. Ega23 возражает на приведенную выше часть моего сообщения:
> Это смотря как организовать. Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.
>
> Таким образом перетряхиваются только индексы массива, а
> в самом массиве данные лежат в порядке добавления.
[13]. Я отвечаю, что:
1. В применении к первому варианту, его совет не даст выигрыша, так как сортировка массива строк принципиально не отличается от сортировки массива индексов строк, так как строка суть указатель.
2. Проблема второго варианта заключается в наличии сдвига элементов при вставке в начало списка, и она тоже не решается приведенным Ega23 методом, так как сдвигать элементы при использовании массива (а не, скажем, связанного списка или дерева) придется в любом случае, а размер указателя на строку равен размеру индекса.
Далее появляетесь вы, и просите объяснить что-то подробнее (правда, не уточняя что), как бы намекая, что видите в моих рассуждениях какую-то неточность, что заставляет меня задуматься, не ляпнул ли я где очевидную глупость. Однако обнаружить таковую мне не удалось.
Если наше взаимонепонимание все еще не исчезло, постарайтесь уточнить, что именно вам показалось ошибочным и почему.
Германн (2011-02-03 03:23:00) [15]
> Какая часть моего утверждения подвергается сомнению
Наличие или отсутствие алгоритма сортировки строк по их указателям с учетом их значений.
Servy (2011-02-03 01:34:00) [16]
> > Так как строка суть указатель, принципиально перемещение
>
> > строк (без их изменения) от перемещения индексов не отличается.
>
>
> Отсюда пожалуйста подробнее.
Всегда к вашим услугам. Какая часть моего утверждения подвергается сомнению?
То, что строка - умный указатель я думаю очевидно. То, что работать с четырехбайтовыми указателями столь же эффективно, как с четырехбайтовыми индексами, содержащими номера этих указателей в соседнем массиве - вроде бы тоже.
Германн (2011-02-03 01:25:00) [17]
> Так как строка суть указатель, принципиально перемещение
> строк (без их изменения) от перемещения индексов не отличается.
Отсюда пожалуйста подробнее.
Servy (2011-02-03 01:12:00) [18]
> Это смотря как организовать. Берём обычный array of string,
> а рядом кладём TList с отсортированными индексами массива.
>
> Таким образом перетряхиваются только индексы массива, а
> в самом массиве данные лежат в порядке добавления.
Так как строка суть указатель, принципиально перемещение строк (без их изменения) от перемещения индексов не отличается.
Тормоза в том, что Insert в начало TList'а (хоть строк, хоть индексов) приводит к необходимости сдвинуть все находящиеся правее места вставки элементы, которых может быть дохрена.
Впрочем, как уже упоминалось, создавать миллион файлов в папке - моветон, а меньшие количества и так отсортируются достаточно быстро, чтобы имело смысл выдумывать более изощренные методы.
Ega23 (2011-02-03 00:27:00) [19]
> Во втором варианте у вас при вставке в начало списка будут
> сдвиги большого количества элементов, которых можно было
> бы избежать в первом варианте. С другой стороны, не требуется
> последующая сортировка. Какой из вариантов будет работать
> быстрее навскидку сказать сложно, да и зависит от входных
> данных.
Это смотря как организовать. Берём обычный array of string, а рядом кладём TList с отсортированными индексами массива.
Таким образом перетряхиваются только индексы массива, а в самом массиве данные лежат в порядке добавления.
Servy (2011-02-02 23:50:00) [20]
> Как лучше?
Во втором варианте у вас при вставке в начало списка будут сдвиги большого количества элементов, которых можно было бы избежать в первом варианте. С другой стороны, не требуется последующая сортировка. Какой из вариантов будет работать быстрее навскидку сказать сложно, да и зависит от входных данных.
С другой стороны, оно вам надо оптимизировать этот процесс? Я сильно сомневаюсь, что у вас там больше 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 не кажется мне верхом гениальности. Может, ну их нафиг, эти горы файликов, и записать все в одну базу данных, например? Впрочем, тут сильно зависит от задачи.
| |
Страницы: 