Dron_Gus 4 July 23, 2009 Posted July 23, 2009 · Report post Хотя небольшой вопрос - все эти методы предполагают сравнение по значению некоего "ключа". Но как получить этот "ключ" (например, в виде байта) из длиннющего имени файла? Поразрядная сортировка подразумевает сортировку "по разрядам". Для имен файлов - это буквы. Начиная с последней. Т.к. у Вас названия файлов имеют разную длинну, то с последней начинать не стоит, т.к. может быть всего один файл с таким длинным именем. А надо хотя бы два. Вообщем, в статье написанно достатоно подробно и понятно. К сожалению, она не годится для рассматриваемого случая. Не вижу препятствий. Обьясните, плиз, чем не годится. Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Обьясните, плиз, чем не годится. Слишком много обращений к данным. Несмотря на то, что не производятся сравнения самих данных, их значения очень интесивно читаются. Quote Share this post Link to post Share on other sites More sharing options...
sonycman 2 July 23, 2009 Posted July 23, 2009 · Report post Не все. А только log2(n). Массив ведь сортирован, значит, оптимальным будет бинарный поиск - берем элемент по центру массива, сравниваем, в зависимости от того, больше или меньше - переходим к верхней или нижней половине, и повторяем. Если элементов в массиве, например, от 128 до 256, то необходимо будет выполнить 8 сравнений и соответственно, 8 извлечений. Точно, я уже даже сам :) догадался, что сравнивать надо не последовательно, а деля массив пополам... Спасибо, возьму этот вариант за основу! Будете в Тольятти - ящик с меня :beer: Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Спасибо, возьму этот вариант за основу! Пожалуйста :) Мне кажется, это будет оптимальный вариант - 256 байт на индексы плюс буфера на текущее имя файла и буфер, в который будет читаться обрабатываемое имя файла. Quote Share this post Link to post Share on other sites More sharing options...
Dron_Gus 4 July 23, 2009 Posted July 23, 2009 · Report post Слишком много обращений к данным. Несмотря на то, что не производятся сравнения самих данных, их значения очень интесивно читаются. Понятно дело, что ради одной буквы из имени в ФАТ лезть не стоит. Можно буферизировать по 5 букв из имени каждого файла. Или если буфер заранее задан, то в зависимоти от количества файлов. Тогда на всю сортировку будет не так и много обращений. Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Можно буферизировать по 5 букв из имени каждого файла. Или если буфер заранее задан, то в зависимоти от количества файлов. Тогда на всю сортировку будет не так и много обращений. 5 букв да на 256 файлов - не дофига ли ОЗУ надо ;) И кстати, если все файлы с длиннючими именами, то очень скоро количество обращений превысит 1800 для моего алгоритма. Quote Share this post Link to post Share on other sites More sharing options...
Dron_Gus 4 July 23, 2009 Posted July 23, 2009 · Report post Согласен. Было бы неплохо этот алгоритм "развернуть". Т.е. начинать с первых букв, тогда можно не идти до конца имен, если перестановки закончились. Но это уже близко к бинарному дереву. :) Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Было бы неплохо этот алгоритм "развернуть" Да зачем? На таком малом количестве (до тысячи файлов) он точно будет хуже описанного мною бинарного поиска с последующей вставкой (обратите внимание на графики по Вашей ссылке, где поразрядная сортировка начинает обгонять quicksort, да еще и учтите, что STL - далеко не образец оптимизации по скорости). Либо по ОЗУ, либо по количеству считываний. Если хотите, реализуйте предложенный Вами алгоритм и устроим фаллосометрию. Для моего случая не более 1800 обращений к функции получения имени файла по индексу и 256 байт ОЗУ (2 буфера для строк не считаем, Вам они тоже понадобятся). Quote Share this post Link to post Share on other sites More sharing options...
zltigo 4 July 23, 2009 Posted July 23, 2009 · Report post Точно, я уже даже сам :) догадался, что сравнивать надо не последовательно, а деля массив пополам... Пополам, не самый эффективный вариант :)- делить надо http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%...%BD%D0%B8%D1%8F Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Пополам, не самый эффективный вариант - делить надо Для максимум-то восьми сравнений "отэтот гемморой"? Да ну нафиг ;) Тем более, получится больше считываний. Тут как раз BS рулит по полной. Quote Share this post Link to post Share on other sites More sharing options...
zltigo 4 July 23, 2009 Posted July 23, 2009 · Report post Для максимум-то восьми сравнений "отэтот гемморой"? Да ну нафиг ;) Трудностей никаких и нет, а массивы не только размером 256 записей бывают, а индексный массив не только в RAM лежать может, но и на той-же файловой системе - лишние обращения никчему. Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 23, 2009 Posted July 23, 2009 · Report post Трудностей никаких и нет, а массивы не только размером 256 записей бывают, а индексный массив не только в RAM лежать может, но и на той-же файловой системе - лишние обращения никчему. Я предпочитаю иметь детерминированное количество обращений (для BS - log2(n)), а для золотого сечения - еще зависит от входного набора данных (т.е. от поведения целевой функции). Часто это хуже, чем мифический выигрыш. Кстати, асимптотически и BS, и золотое сечение - O(log(n)). Но это мы уже плавно переходим на обсуждение глобальных теорий... Ну его в сад ;) Кстати, по большому счету волшебные буквы "ARM" к обсуждаемой теме не имеют никакого отношения, и тему, по науке, надо бы перенести в раздел для обсуждения алгоритмов. Quote Share this post Link to post Share on other sites More sharing options...
Dron_Gus 4 July 24, 2009 Posted July 24, 2009 · Report post Если хотите, реализуйте предложенный Вами алгоритм и устроим фаллосометрию. Нее. Спасибо. Думаю, Ваш алгоритм действительно "длинее"... В смысле лучше. :) З.Ы. если разберусь с глюками своей поделки на str912 тоже буду делать плеер. Тогда, может, и попробую сравнить алгоритмы. Quote Share this post Link to post Share on other sites More sharing options...
sonycman 2 July 24, 2009 Posted July 24, 2009 · Report post В принципе, вместо имени файла можно юзать ID3 тэги. Тут только придётся, кроме чтения имени из FAT, ещё и первый сектор файла читать... Quote Share this post Link to post Share on other sites More sharing options...
Rst7 5 July 24, 2009 Posted July 24, 2009 · Report post В принципе, вместо имени файла можно юзать ID3 тэги. Тут только придётся, кроме чтения имени из FAT, ещё и первый сектор файла читать... Это даже более красиво с точки зрения интерфейса. Просто надо заменить список индексов в каталоге на список первых секторов. Кстати, заметно быстрее будет сортировка (все-таки чтение имени из каталога - весьма небыстрое занятие), но надо хачить работу с ФС - сделать функцию получения номера первого сектора файла. Quote Share this post Link to post Share on other sites More sharing options...
