[sonycman 0]

Привет!

Думаю, как организовать функцию GUI (типа окна File Requester) со списком нужных файлов (длинные имена) текущей директории.

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

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

 

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

 

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

 

Пока остановился на таком методе:

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

2. Юзер, перемещая курсор GUI, фактически перемещает указатель на индекс файла в таблице.

3. Затем функцией dir_seek(индекс) устанавливаем указатель FatFS, и получаем имя файла через f_readdir().

 

Вроде как таким образом избегаем прямой работы с длинными именами.

Хотя по третьему пункту не уверен, что сработает - не пробовал пока...

 

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

 

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

[AHTOXA 14]

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

написал обёртки поверх fatfs, типа:

 

int get_dir_count();

int get_file_count();

char * get_dir_name(int index);

char * get_file_name(int index);

 

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

 

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

[defunct 0]

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

 

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

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

 

Но тут скорее всего понадобится два буфера под имена.

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

[baralgin 0]

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

 

А сравнения для сортировки лучше проводить по полному имени, так как для того же mp3 нередка ситуация с именами примерно такого типа:

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

[sonycman 0]

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

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

 

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

Это не видится наиболее оптимальным методом по скорости работы...

 

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

[Dron_Gus 2]

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

 

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

[Rst7 5]

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

 

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

[sonycman 0]

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

 

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

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

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

 

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

[Rst7 5]

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

 

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

[sonycman 0]

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

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

[Dron_Gus 2]

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

[AHTOXA 14]

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

 

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

Пока остановился на таком методе:

до

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

 

тогда количество вызовов f_readdir() будет просто зашкаливать

 

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

[Rst7 5]

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

 

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

 

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

[sonycman 0]

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

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

 

Хотя небольшой вопрос - все эти методы предполагают сравнение по значению некоего "ключа".

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

 

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

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

 

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

 

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

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

[Rst7 5]

Ну покурите заодно и поразрядную сортировку из приведенной мной статьи.

 

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

 

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

 

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