HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Флуд (https://hlfx.ru/forum/forumdisplay.php?forumid=11)
-- Сортировка массива строк ( больше 2 млн позиций ) (https://hlfx.ru/forum/showthread.php?threadid=5264)

Сортировка массива строк ( больше 2 млн позиций )

Куку фсем кисям данного форума! Имею окала трёх миллионов строк разной длины ( имена файлов, записаны в блоки по пять мегабайт ( могу поменять их размер на какой угодно ) ). Из них нужно выбрать все записи с определённым расширением ( расширения храню в отдельной области памяти ). И тута у мну вообще моск вскипел ( хотя у мну ево и нет ). Как лучше и проще сделать за разумное время ( вообще не представляю, какое тут время может быть разумным )? Вычислять сначала хеши расширений, затем итерацией по каждй строке файлового блока вычислять налету хеши расширений файлов, и сравнивать уже их? Или в кокую сторону капать тута? Совсем запутолсо. Добролюди, памахити советом позязя! Фсем лафки чмафки авансом
З.Ы. Без использования баз данных, они тута вообще ни в каком виде не учавствуют. Пишу на дульфи, но это для справки. Никаких питонов, рубинов на рельсах и прочей непотребщины с кучей встроенных сартировок на все случаи жызни ( и смерти ) не имеем.

Позови Мастера на фриланс, сортировка строк - его конёк!

__________________
Ты топчешь мир своими ботинками,
Не замечая куда наступаешь,
А время от тебя уходит цветными картинками,
Но ты даже этого не понимаешь.

Компрометирую данные своей учётной записи.
ЛОГИН: Ghoul [BB]
ПАРОЛЬ: paladin_solo

За разумное время обычно предполагается сортировать что-то такое, что надо выполнять не один раз, а прямо тысячу раз в секунду. А если надо всего один раз, то любое время будет разумным. В разумных пределах конечно.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

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

__________________

А на каком этапе-то здесь сортировка?

__________________
http://www.moddb.com/mods/monorail-quest

__________________
I tell you to enjoy life

Дядя Миша
XaeroX
Вот это вот как раз и загвоздка. Данные надо передать в последующую обработку как можно быстрее, такое условие ( оно изменению не подлежит, заказчику приспичило выпустить очередной универсальный всемогутер-индексатер-архиватер всего шо только можно, да и ещё со световой скоростью ). Построчное сравнение ( даже если делать чисто сишными средствами memcmp/функцией прохода по массиву, сравнивая всё это дело посимвольно с конца ) займёт туеву хучу времени, на таком количестве данных это ощущается остро, данный лист изначально формируется порядка 15-20 минут стандартными виндовыми FindFirstFile, и это я ещё свои контейнеры-бассейны туды впилил, ибо дульфя по умолчанию не умеет в списки с фиксированным пулом. Поэтому и спрашиваю у тех, кто разбирается в сложности алгоритмов, как с этой ситуации выйти. На форумах даже англоязычных я способов ускорения для такой задачи найти не смог
Если это и не поможет, то придётся писать свой парсер для Жырнича32 и НТФС. Может выиграю на изначальном построении дерева, но и это ещё бабка на двоих нассала, информацию по файловым системам приходится зубами выгрузать из мсдн. Прямо-руки опускаются.
thambs
Сортировка мне ещё в идеале нужна по размеру файла. Но я так подозреваю ( аки та собака ) что на таком объёме данных это невозможно.

__________________
Ты топчешь мир своими ботинками,
Не замечая куда наступаешь,
А время от тебя уходит цветными картинками,
Но ты даже этого не понимаешь.

Компрометирую данные своей учётной записи.
ЛОГИН: Ghoul [BB]
ПАРОЛЬ: paladin_solo

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме