Подскажите по алгоритму обработки массива с дырками.

Можно в массиве хранить сразу два значения, длину поля данных и сами данные. Тогда следующий элемент доступен по смещению. Вроде бы просто, но, возможно, не слишком быстро.

Увы, исходные данные поступают из вне и я не могу задать их формат, поэтому я решил сделать промежуточный массив, в котором хранятся только смещения.

А как тогда всякие файловые менеджеры пишутся? Мониторят текущий каталог на предмет изменений, чтобы, например, при копировании/перемещении файлов «в главном окне, за диалогом копирования/перемещения», показывать изменения на панелях?

А как тогда назвать структуру, которая наоборот - большинство элементов значимые, а небольшое количество «дефолтные»?

Если «дырок» немного то надо просто быть готовым что они есть, но менять под это саму структуру я смысла не вижу.

А как тогда всякие файловые менеджеры пишутся?

Я сильно сомневаюсь что можно придумать что-то лучше чем getdents() + inotify.

Тогда подскажи алгоритм. Вот у меня есть список на экране. Каждый пункт меню нумеруется по порядку от 0 и до конца экрана. Там нет дырок. А во входных данных они есть. Если не промежуточный массив, то что?

Это наверное зависит от реализации, а не от алгоритма. Есть же в конкретном языке необходимые методы? Я бы предложил фильтровать входные данные.

Если не промежуточный массив, то что?

Ну, что-то промежуточное будет точно. Вот только что именно не сильно от вас зависит - чего от вас ваш «любимый» UI framework / toolkit хочет, в том виде скармливать ему и придётся. Сколько тех элементов на экране одновременно помещается? Ну пусть 100. Такой вектор создать ничего не стОит.

чего от вас ваш «любимый» UI framework / toolkit хочет

Мой любимый toolkit дёргает функцию обратного вызова и передаёт в неё порядковый номер элемента и буфер, в который я могу напечатать что-то. Это что-то и будет представлять элемент списка на экране. Таким образом реализована полная абстракция.

Если не промежуточный массив, то что?

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

Мой любимый toolkit дёргает функцию обратного вызова и передаёт в неё порядковый номер элемента и буфер

Я не до конца понимаю откуда у вас дырки берутся. Но думается мне что в контексте директорий (dentries переменной длины) индексировать (создавать вектор смещений в массив dentries) всё равно придётся, на этом этапе и избавитесь от дырок. Самое простое, кмк.

поэтому я решил сделать промежуточный массив, в котором хранятся только смещения.

… как, собственно, вы и собирались.

Я не до конца понимаю откуда у вас дырки берутся

Другой пример. Есть модем, который управляется с помощью АТ-команд. В сим-карте есть 220 слотов для записей контактов. Каждый слот имеет свой порядковый номер. Выборка записей идёт по порядковому номеру слота. Теперь ситуация. Я создал 3 контакта: Маша, Петя и Вася. Они заняли 1, 2 и 3 слот. Потом я посрался с Петей и удалил его. В итоге образовалась дырка под индексом 2.

Я создал 3 контакта: Маша, Петя и Вася. Они заняли 1, 2 и 3 слот. Потом я посрался с Петей и удалил его. В итоге образовалась дырка под индексом 2.

Free-list. Если записи фиксированной длины - вообще тривиально делается. С плавающей длиной появляются варианты различной степени извращённости. Но индексировать всё равно придётся :)

Но индексировать всё равно придётся :)

Вот я и занимаюсь индексированием как и написал в шапке.

Я тут писал, что у меня менее 150к оперативки. Вот точные данные

I (543) heap_init: Initializing. RAM available for dynamic allocation:
I (550) heap_init: At 3FFAFF10 len 000000F0 (0 KiB): DRAM
I (556) heap_init: At 3FFB6388 len 00001C78 (7 KiB): DRAM
I (562) heap_init: At 3FFB9A20 len 00004108 (16 KiB): DRAM
I (569) heap_init: At 3FFC5B50 len 0001A4B0 (105 KiB): DRAM
I (575) heap_init: At 3FFE0440 len 00003AE0 (14 KiB): D/IRAM
I (581) heap_init: At 3FFE4350 len 0001BCB0 (111 KiB): D/IRAM
I (588) heap_init: At 4009AA60 len 000055A0 (21 KiB): IRAM

Это список доступных куч. IRAM лучше не использовать под данные, т.к. в ней можно расположить код. Остаётся DRAM. Но дело ещё осложняется тем, что может не быть доступен весь объём в виде непрерывного куска. Поэтому я буду упарываться и экономить каждый байт до тех пор, пока скорость остаётся приемлемой (а она таковой остаётся) :)

200 записей можно тупо в цикле перебирать.

Поэтому я буду упарываться и экономить каждый байт

Подкину идею: вовсе необязательно индексировать всё, достаточно держать в индексе только то что потенциально может быть отображено на UI прямо сейчас. Плюс возможность его относительно быстро пере/достраивать по необходимости (при условном «скролле»).

Про это уже думал. Такое актуально будет в файловом менеджере, например, где файлов в каталоге может быть много.

Перед функцией, которая обрабатывает данные, ставишь фильтр, убирающий лишние значения.

user> (def users ["Маша" nil "Вася"])
#'user/users
user> (->> users (filter not-empty) println)
(Маша Вася)

(Маша Вася)

Ок, теперь я хочу отредактировать контакт Вася. Я должен использовать индекс 3, а в этом списке это 2 (там нумерация с 1 идёт вроде… не важно). Напомню, что ресурсы памяти значительно ограничены, поэтому грузить всё в память - не вариант ;)

Я должен использовать индекс 3, а в этом списке это 2

В данном конкретном случае это односвязный список, индексов у него вообще нету. А в вашем явно какая-то императивщина под капотом. Тогда объект-структура-запись Вася может находиться в разных массивах под разными индексами, отчего бы собственно и нет?

односвязный список

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