Привет!
Думаю, как организовать функцию GUI (типа окна File Requester) со списком нужных файлов (длинные имена) текущей директории.
К примеру, для выбора .mp3 файлов для последующего воспроизведения, или любого другого требуемого типа из большого количества различных представленных - думаю, пока что должна быть возможность работать с 250-тью файлами (вместе с субдиректориями) максимум.
В окошке будет курсор, свободно перемещаемый по вертикальному списку.

Контроллер STM32 с 20к оперативы, поэтому затрачивать более 1к на нужды функции не вижу смысла.

Файловая система FatFS от Чана.

Пока остановился на таком методе:
1. Функцией f_readdir() последовательно вычитываем содержимое, индексы (порядковые номера) файлов с нужным расширением и субдиректорий сохраняем в таблице размером 250 байт. При этом остальные (не .mp3) файлы пропускаем, а индексы директорий записываем в начало таблицы, чтобы директории шли первыми.
2. Юзер, перемещая курсор GUI, фактически перемещает указатель на индекс файла в таблице.
3. Затем функцией dir_seek(индекс) устанавливаем указатель FatFS, и получаем имя файла через f_readdir().

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

Что скажете, уважаемые?

ЗЫ: вообще, конечно, хотелось бы формировать список в алфавитном порядке, но не вижу способа реализовать это на контроллере без большого кол-ва оперативки...

Поскольку юзер-интерфейс - штука неторопливая, то я бы сделал так:
написал обёртки поверх fatfs, типа:

int get_dir_count();
int get_file_count();
char * get_dir_name(int index);
char * get_file_name(int index);

Далее всё понятно. Имена в памяти держать не надо, при отрисовке каждый раз вызываем get_xx_name().

Сортировка с малыми затратами памяти тоже возможна, нужно лишь сортировать массив индексов. Но тут скорее всего понадобится два буфера под имена. Для экономии можно сравнивать по нескольким первым символам.

Согласен с АНТОХА


массив из 250 элементов, где каждый элемент - байт (номер файла в каталоге), и функция сравнения имен по индексу, запросто уложатся в 1kb.


Можно в стеке выделить, на время сортировки. Лучше уж стек увеличить на размер этих двух буферов.

Можно отсортировать без буферов под имена вообще, но такой способ, возможно, окажется слишком задумчивым: Массив с индексами сортировать каким-нибудь лёгким(в смысле памяти) алгоритмом( пузырёк ? ), на этапе сравнения вызывать каждый раз функцию f_readdir() (или предложенную char * get_file_name(int index)). Скорость сортировки будет упираться в вызовы этой самой функции.

А сравнения для сортировки лучше проводить по полному имени, так как для того же mp3 нередка ситуация с именами примерно такого типа:
"<Артист> - <альбом> - <номер трэка> - <трэк>.mp3" - очевидно, что добраться до значащих символов будет непросто...

Только мне не понятно, что нового предложил уважаемый Антоха?

По поводу алфавитной сортировки - сравнивать надо обязательно по полному имени (как справедливо заметил baralgin), это можно сделать и без больших затрат оперативы, но тогда количество вызовов f_readdir() будет просто зашкаливать: сначала путём сравнения имён ВСЕХ файлов директории выявляем самый "верхний" файл, затем, путём сравнения имён ВСЕХ-1 файлов директории выявляем второй файл и т.д.
Это не видится наиболее оптимальным методом по скорости работы...

А как можно сделать иначе?

Вот тут есть небольшая статья со сравнениями производительности различных алгоритмов. http://algolist.manual.ru/sort/

Пузырек - самы тормозной.

Способов - масса. Начните курить отсюда, благо способов сортировки как грязи

Не так важна скорость сортировки, когда все имена одновременно находятся в оперативе - прочитал, сохранил, отсортировал.
Сортировка в оперативке в любом случае займёт минимум времени по сравнению с чтением имени каждый раз непосредственно с диска\карты памяти...

Но не вижу другого способа, при отсутствии достаточного кол-ва памяти...

Не согласен. Бинарная сортировка приведет к количеству операций O(n*log2(n)). Точнее, сортировку достаточно будет заменить построением бинарного дерева - на это потребуется такой-же порядок операций. Для 256 узлов достаточно будет 768 байт памяти (left, right, значение). Если реализовывать красно-черное дерево, то памяти нужно будет примерно килобайт (если мне не изменяет память, для вменяемого по скорости построения красночерного дерева необходимо хранить еще и parent).

Спасибо, буду "курить" бинарную сортировку

Ну покурите заодно и поразрядную сортировку из приведенной мной статьи. На мой взгляд очень неплоха. Обращений к ФС нимимум, можно сортировать на нужную "глубину".

Просто уважаемый Антоха отвечал на ещё не отредактированное сообщение. Там ещё не было строк от
Пока остановился на таком методе:
до
Что скажете, уважаемые?



Ну тут уж либо скорость, либо память. Попробуйте, возможно всё будет не так уж и медленно.

Погодите курить, есть проще способ, с тем же результатом O(n*log2(n)). Попробую объяснить на пальцах.

У Вас есть массив индексов имен. Соответственно, любое имя однозначно определяется индексом. Допустим, массив уже отсортирован по возрастанию (не индексов, а имен). Тогда поиск места для добавления элемента будет занимать O(log2(n)), где n - текущий размер массива, это - банальный бинарный поиск. Операций извлечения настоящих имен будет требоваться столько-же. После того, как Вы нашли место, Вы в это место вставляете новый индекс. В результате массив увеличивается на один элемент и он остается отсортированным. Далее процесс повторяется. Суммарно это потребует всего лишь порядка 1800 операций извлечения имени файла на каталог из 256 файлов (если я не обсчитался). И в результате - у Вас отсортированный массив индексов, без всяких деревьев.

Спасибо, почитаю.

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


А, тогда понятно


То есть все индексы массива, предшествующие вставке нового, будут считыватся через f_readdir() и сравниваться?

К сожалению, она не годится для рассматриваемого случая.



Не все. А только log2(n). Массив ведь сортирован, значит, оптимальным будет бинарный поиск - берем элемент по центру массива, сравниваем, в зависимости от того, больше или меньше - переходим к верхней или нижней половине, и повторяем. Если элементов в массиве, например, от 128 до 256, то необходимо будет выполнить 8 сравнений и соответственно, 8 извлечений.

Поразрядная сортировка подразумевает сортировку "по разрядам". Для имен файлов - это буквы. Начиная с последней. Т.к. у Вас названия файлов имеют разную длинну, то с последней начинать не стоит, т.к. может быть всего один файл с таким длинным именем. А надо хотя бы два. Вообщем, в статье написанно достатоно подробно и понятно.



Не вижу препятствий. Обьясните, плиз, чем не годится.

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

Точно, я уже даже сам догадался, что сравнивать надо не последовательно, а деля массив пополам...
Спасибо, возьму этот вариант за основу!
Будете в Тольятти - ящик с меня

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

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

5 букв да на 256 файлов - не дофига ли ОЗУ надо И кстати, если все файлы с длиннючими именами, то очень скоро количество обращений превысит 1800 для моего алгоритма.

Согласен. Было бы неплохо этот алгоритм "развернуть". Т.е. начинать с первых букв, тогда можно не идти до конца имен, если перестановки закончились. Но это уже близко к бинарному дереву.

Да зачем? На таком малом количестве (до тысячи файлов) он точно будет хуже описанного мною бинарного поиска с последующей вставкой (обратите внимание на графики по Вашей ссылке, где поразрядная сортировка начинает обгонять quicksort, да еще и учтите, что STL - далеко не образец оптимизации по скорости). Либо по ОЗУ, либо по количеству считываний. Если хотите, реализуйте предложенный Вами алгоритм и устроим фаллосометрию. Для моего случая не более 1800 обращений к функции получения имени файла по индексу и 256 байт ОЗУ (2 буфера для строк не считаем, Вам они тоже понадобятся).

Пополам, не самый эффективный вариант - делить надо http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%...%BD%D0%B8%D1%8F

Для максимум-то восьми сравнений "отэтот гемморой"? Да ну нафиг

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

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

Я предпочитаю иметь детерминированное количество обращений (для BS - log2(n)), а для золотого сечения - еще зависит от входного набора данных (т.е. от поведения целевой функции). Часто это хуже, чем мифический выигрыш. Кстати, асимптотически и BS, и золотое сечение - O(log(n)).

Но это мы уже плавно переходим на обсуждение глобальных теорий... Ну его в сад

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

Нее. Спасибо. Думаю, Ваш алгоритм действительно "длинее"... В смысле лучше.

З.Ы. если разберусь с глюками своей поделки на str912 тоже буду делать плеер. Тогда, может, и попробую сравнить алгоритмы.

В принципе, вместо имени файла можно юзать ID3 тэги. Тут только придётся, кроме чтения имени из FAT, ещё и первый сектор файла читать...

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