LINUX.ORG.RU

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

 ,


0

2

Допустим, есть некий массив вида

{ data, data, NULL, data, data, NULL, data }

То есть это как бы обычный массив с данными, но в нём есть «дырки». Пытаюсь организовать доступ к этому массиву так, чтоб он был виден как массив без дырок

{ data, data, data, data, data }

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

{ 0, 1, 3, 4, 6 }

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

★★

Если по примитиву то.

Ты знаешь длину массива, просто при доступе пропускай NULL и всё. Lookup таблица трансляции что ты хочешь сделать хорошее решение для небольших массивов в случае прямого обращения к индексу/ключу, её быстро перестроить при изменении и доступ за O(1).

Но так-то, как сказал выше делаешь функцию итератор, которая зная длинну, обходит значения и выдаёт их просто пропуская NULLы

LINUX-ORG-RU ★★★★★
()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)

Также буду благодарен, если накидаете умных слов

ну так и делается - либо поверх делается массив с нужными индексами, либо список с нужными индексами. зависит от конкретики.

alysnix ★★★
()
Ответ на: комментарий от LINUX-ORG-RU

все эти sparse штучки делают именно через массив непустых индексов, особо широко применяется на sparse матрицах при расчете электронных цепей например.

alysnix ★★★
()

Подскажите, как грамотно называются такие массивы

Разреженный массив

Также буду благодарен, если накидаете умных слов по теме для самообучения и литературу, где описываются методы работы с такими данными.

Вы не указали используемый ЯП. Гуглите переопределение next() у Iterator в вашем ЯП. Если итераторов в вашем ЯП нет - гуглите работу с search cursor. Если и этого нет - ищите yeld, если не нашли - map/filter in stream вам в помощь. Если ничего этого нет - используйте свой вариант с индексами элементов.

Obezyan
()
Ответ на: комментарий от u5er

Разреженный вектор хорош тем что ты можешь не использовать цикл 0..N, а можешь проходиться исключительно по элементам которые присутствуют, если дырок очень много, то это позволит значительно сократить количество итераций. И хранить меньше элементов, работать с векторами которые в ином случае не уместились бы в память.

Предлагаю попробовать переосмыслить алгоритм, что бы он мог использовать это преимущество, и не забирать лишние нули.

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

MOPKOBKA ★★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 3)
Ответ на: комментарий от u5er

Тогда твой язык должен позволять переопределять поведение семантики синтаксиса. Ну или ты пишешь свой язык, если свой, то внутри реализации можешь опять же сделать итератор или хранить данные в односвязном списке, или в хеш таблице, или в дереве, или в чём угодно по сути. Язык свой или язык готовый? =)

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от LINUX-ORG-RU

ты пишешь свой язык

Свою ос xD

язык готовый

Си. Суть в том, что масив я тут привёл лишь для упрощения понимания. Я делаю аналог listView. Мне нужен виджет, который будет иметь слой абстракции, чтоб можно было представить любые данные в виде списка на экране. Это могут быть не только статические и динамичекие массивы, но и массив структур, список файлов и папок, выбора из баз данных и т.д. и т.п.. При этом, всё это дело будет работать на микроконтроллере, где нельзя последовать совету типичного лоровца «просто докупи оперативы - она сейчас дешёвая». Как-то так :)

Вот, например, есть набор функций для работы с каталогами opendir, readdir, seekdir и т.д.. В начале я такой думаю - сделать файловый менеджер? Пф, да изи! Начал кодить и выяснилось, что список файлов и каталогов предсталяет из себя разреженный массив. Попробуй в цикле читать каталог, предварительно вызывая seekdir :)

u5er ★★
() автор топика
Ответ на: комментарий от u5er

Если нужен доступ по индексу, и надо учесть возможность работы с большими массивами и замену данных на дырки и обратно, я бы сделал индексное btree (в каждой ноде храним количество не-null элементов под ней) примерно так же как твой вспомогательный массив индексов, но чуть гибче.

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

Других эффективных вариантов скорее всего нет.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от u5er

Ну значит ты будешь писать функцию итератор, у тебя выбора нет. А вот на счёт внутреннего представления и явного индексирования тут надо, с учётом что у тебя микроконтроллер, играться, хештабля может быть жирной для вычислений, связный список потребует lookup таблицу для индексирования, но её нужно перестраивать.

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

Могу лишь пожелать успехов =)

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от u5er

в цикле читать каталог, предварительно вызывая seekdir

Что-то очень странное. Странные алгоритмы требуют странные структуры данных.

anonymous
()
Ответ на: комментарий от u5er

Если речь про чтение списка файлов, то лучше использовать настоящие индексы, без вырезания пустых записей, т.к. твои оптимизированные индексы будут рандомно меняться при добавлении/убирании файла и для seek соответственно непригодны.

firkax ★★★★★
()
Ответ на: комментарий от firkax

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

u5er ★★
() автор топика
Ответ на: комментарий от u5er

Если у тебя список файлов уже выведен на экран, он должен быть сохранён (закеширован, если хочешь) в твоём собственном массиве со всеми нужными данными. Делать seekdir-readdir по нажатию на них не надо, это получится забагованная чушь.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Ты это говоришь в контексте обычного компьютера, а я говорю в контексте микроконтроллера, где объём оперативки сильно ограничен.

Делать seekdir-readdir по нажатию на них не надо, это получится забагованная чушь.

Разверни мысль.

u5er ★★
() автор топика
Ответ на: комментарий от u5er

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

Ах, да: «преждевременная оптимизация - корень всех зол».

anonymous
()
Ответ на: комментарий от anonymous

Оптимизация чего, простите? Моя задача - организовать абстракцию таким образом, чтоб можно было работать с данными как с обычным массивом с доступом по индексу. Я нигде в шапке не писал про оптимизацию.

u5er ★★
() автор топика

Нужен доступ по индексу.

из вашего описания задачи нельзя понять, как элементы массива ассоциируются с индексом. Допустим:

arr = [0, null, 1, 2, null]

если массив индексируется в нуля, то что вернет arr[1] и arr[4]? Что вернет len(arr)?

FishHook
()
Ответ на: комментарий от FishHook

чтоб можно было работать с данными как с обычным массивом с доступом по индексу

отфильтруйте к черту эти нулы, они в вашей задаче (если вы её корректно описали) никакой информации не несут

FishHook
()

а тупо пройтись по массиву и «поднять» NON-NULL значения и обрезать по последнему значению длину массива ? Если данные будут использоваться многократно - это более оптимально чем извращаться с online-корректировкой.

Atlant ★★★★★
()
Ответ на: комментарий от FishHook

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

u5er ★★
() автор топика
Ответ на: комментарий от u5er

Разверни мысль.

Ты вывел у себя в интерфейсе некий file1, потом его кто-то удалил и на его месте создал file2. Ты в интерфейсе делаешь что-то с file1, например хочешь его удалить, жмёшь удаление, через seekdir readdir узнаёшь что файл с таким именем - file2 и удаляешь его. Не говоря уж о менее критичных вещах.

где объём оперативки сильно ограничен.

Настолько, что список файлов в неё не влезает? Значит в файловом менеджере пиши «файлов слишком много, лишние проигнорированы» и выводи (и сохраняй) первые 100 найденных.

firkax ★★★★★
()
Ответ на: комментарий от u5er

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

Но мы говорим про массив в памяти полученный на основанни исходных данных или про сами исходные данные?

FishHook
()
Ответ на: комментарий от firkax

кто-то удалил

Значит создалось событие и в интерфейсе это отобразислось. Всё просто. Ещё варианты?

Настолько, что список файлов в неё не влезает?

Ну имя файла может занимать до 256 байт в структуре dirent. У меня всего менее 150к свободной оперативки. Посчитай сам, сколько это файлов. Я хочу избегать использования памяти настолько, насколько это возможно.

u5er ★★
() автор топика
Ответ на: комментарий от u5er

У тебя хуки на все операции с файлами в гуи ведут?

1) это сомнительная идея уже с точки зрения удобства - пользователь собирается нажать что-то на file1, и видит как оно неожиданно подменяется на file2 и происходит не то что надо.

2) даже если про удобство не писать, всё это происходит не одномоментно, получаются всякие race conditions и опять не то что нужно

firkax ★★★★★
()
Ответ на: комментарий от u5er

Про сами данные. Массив - это всего лишь представление. Абстракция.

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

FishHook
()
Ответ на: комментарий от firkax

Ты фантазируешь. Само по себе ничего удалиться не может. Если какая-то функция соберётся что-то удалить, то она може заранее сообщить об этом. Если я сам удаляю файл, то я потом просто перезагружу список.

u5er ★★
() автор топика
Ответ на: комментарий от u5er

Си. Суть в том, что масив я тут привёл лишь для упрощения понимания. Я делаю аналог listView. Мне нужен виджет, который будет иметь слой абстракции, чтоб можно было представить любые данные в виде списка на экране.

Реализуй итератор, для получения отображаемого списка (чтобы возвращал значение + индекс) и методы get/set, которые будут возвращать/устанавливать значение по индексу (и корректно себя вести если значения нет).

Norgat ★★★★★
()
Последнее исправление: Norgat (всего исправлений: 1)

Допустим, в качестве исходных данных у нас база данных. В базе данных есть две таблицы - таблица с товарами и таблица с городами. Каждый товар ассоциирован с одним городом или не ассоциирован ни с одним (нуллабл поле). У нас есть виджет, который отображает список городов в которых есть товар.

select c.id, c.name from product p inner join city c on c.id = p.city_id

Логично? Нам нужен ИД элемента в исходных данных и данные необходимые для представления.

FishHook
()
Ответ на: комментарий от u5er

И суть в том, что id могут идти с «пропусками».

В моем примере это как раз ИД с пропусками. Но ведь в виджете вам эти пропуски не нужны. Поэтому вы извлекаете из исходных данных только нужные данные (без пропусков) и отображаете их. И дополнительно извлекаете ИД (или индекс, или имя, или еще что угодно) для обратной привязки данных в виджете к исходным данным. Я хоть убей не понимаю проблему.

FishHook
()
Ответ на: комментарий от FishHook

Я хоть убей не понимаю проблему.

Так а проблемы не было :) Прочитай первый пост ещё раз. Я просто в самом начале подумал, что моё решение может быть не самым оптимальным, поэтому решил поинтересоваться тут.

u5er ★★
() автор топика
Ответ на: комментарий от u5er

Свою ос xD

Амбициозненько :)

выяснилось, что список файлов и каталогов предсталяет из себя разреженный массив

Вас довольно жестоко обманули уже несколько раз: обычно под разряжёнными массивами понимают компактное представление большой структуры с небольшим количеством значимых (не дефолтных) элементов, а не наоборот.

есть набор функций для работы с каталогами opendir, readdir, seekdir

Настоящее веселье начнётся с осознанием того что dir может под вами (в общем случае) непредсказуемо меняться во время чтения :)

bugfixer ★★★★★
()

про sparce сказали, но почти гарантировано что никакого выигрыша кроме повышения ЧСВ не будет. Итоговая программа не станет ни быстрее, ни меньше, ни надёжнее.

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

MKuznetsov ★★★★★
()
Ответ на: комментарий от bugfixer

представление большой структуры с небольшим количеством значимых (не дефолтных) элементов, а не наоборот.

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

Настоящее веселье начнётся с осознанием того что dir может под вами (в общем случае) непредсказуемо меняться во время чтения :)

Сама по себе или после записи? Если второе, то это уже нельзя назвать непредсказуемо.

u5er ★★
() автор топика