Страницы: 1
RSS
"Статичный" фильтр. Как ускорить фильтрацию двумерного массива, Static Filter. How to SpeedUp Filter of 2D-Array
 
Приветствую!
Заинтересовался такой задачей: как можно ускорить фильтрацию двумерного массива?
Далее под "фильтрацией таблицы" будет иметься в виду отбор строк двумерного массива, согласно критериев.
Давайте разбираться, что такое отбор/фильтрация на примере двумерного массива из таблицы

    Я решил разобрать [относительно] простой случай: Отбор не более, чем по одному значению — для каждого поля. Проверка осуществляется на строгое равенство, с учётом регистра. Алгоритм ускорения позволяет осуществить, также, проверку без учёта регистра и/или на НЕравенство, но в примере это не отражено.

Итак, как же ускорить?
    Чтобы ускорить, нужно как-то избавиться от цикла по всем строкам таблицы. Для этого нужно как-то запомнить строки для каждого критерия в фильтруемых столбцах и хранить их в ОЗУ (использовать статичные переменные). То есть, в любом случае, нужно собрать уникальные списки для каждого поля, которое хотим фильтровать.
Далее существует, минимум, 2 сценария:

    Слабые места алгоритма, которые я хотел бы ускорить (существующими методами или библой bedvit'а):
         • сцепка по ключу (не очень страшно и есть альтернативы).
    Чтобы собрать номера строк в массив я использую накопительную строку, формируемую по принципу s = s & sSep & iRow. Есть и другие варианты ( Mid$(s, …) = sSep & iRow кажется самым быстрым, но сложнее в реализации).
         • определение общих значений (отсортированные целые числа) для N массивов.
    Тут я применил всё, что знал. Используется массив в качестве "словаря" для быстрой проверки и используется самый малый по размеру массив (т.к. если в нём нет номера строки, то она уже никак не может быть общей для всех массивов). Описывать очень долго — кто в теме, тот поймёт. Какие-то моменты всегда можно спросить и я отвечу.
    Так вот, для этого процесса мне бы очень не помешал специальный инструмент из библы — такие штуки на плюсах должны быть сильно быстрее. Думаю, что его применение может быть довольно широким.

    Возможно, есть и другие способы, как ускорить отбор. Прошу поделиться  :idea:

    В файле 2 листа: исходная таблица для фильтрации и тестовый.
    В таблице можно добавлять/удалять строки. При уходе с листа произойдёт обновление.
    На тестовом можно выбрать от 1 до 4ёх критериев фильтра и нажать(даблклик) FILTER — справа выведется отфильтрованная таблица или сообщение, что под заданные параметры ничего не найдено.

Скрины
Файл
Код
Изменено: Jack Famous - 27.04.2024 17:26:11
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Jack Famous, привет!
По твоей теме, можно кратко:
1.Почему не подходит фильтр из нашей библы?
2.Какой инструмент написанный на С++, ты думаешь будет широким в применении, кратко, концепцию?
Изменено: bedvit - 27.04.2024 18:47:52
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, привет и спасибо за внимание к теме!

1. Задача может быть решена с использованием библы или без неё. Без неё я показал. Наверняка, можно что-то ускорить, но кардинально отличаться может только другой подход.
С помощью твоего фильтра всё будет гораздо проще. Более того, на малых и средних объёмах он, скорее всего, будет быстрее. И уж точно удобнее и проще. Также, не нужно будет тратить время на подготовку данных и их обновление — всё будет браться актуальное. Всегда.
Однако, на больших объёмах он вполне может уступить (надо протестировать).
Есть такие задачи, когла временем подготовки данных можно пожертвовать или даже пренебречь — лишь бы потом можно было очень быстро по этим данным получать необходимую информацию. Такой была задача по словарю лемм (решилась с помощью твоего метода загрузки пар через одномерный массив). Такая задача и тут.

Если бы не волшебная комбинаторика, то задача свелась к бы к получению всех комбинаций (не хватает скорости плюсов, а у тебя нет ничего по этой теме) с номерами строк — в твоей карте. Но, боюсь, что количество комбинаций может быть просто невообразимо огромным и средняя ОЗУ просто не вывезет.
Нужно что-то другое.

2. Если просто повторить мой алгоритм, то скорость нужна в 3ёх местах:
- получение пар "критерий — массив номеров" (для каждого заданного поля.
- определение общих номеров (пересечения) из заданного массива массивов (номеров)
- быстрый пересбор двумерного массива по заданному списку строк. Кстати, вообще, такой инструмент пересбора был бы очень полезен. На твоей стороне это намного быстрее происходит.

Возможно, другой подход изменит и потребности.
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
Однако, на больших объёмах он вполне может уступить (надо протестировать).
Интересен результат, жду тестов.

Цитата
Jack Famous написал:
2. Если просто повторить
повторить не выйдет из-за разной концепции доступа к данным в памяти в VBA и С++ и соответственно разной реализации нужного функционала.
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit написал:
быстрый пересбор двумерного массива по заданному списку строк
это уже реализованно в фильтре в нашей библе - по строкам проходящих заданные условия.
Изменено: bedvit - 27.04.2024 21:32:27
«Бритва Оккама» или «Принцип Калашникова»?
 
Цитата
bedvit: это уже реализованно в фильтре в нашей библе
ты лукавишь)
Понятно, что фильтр может возвратить отфильтрованный массив. А может вернуть индексы. А, также, индексы могут быть получены другим путём. Нет самого инструмента для пересбора. Отдельно. Мне кажется, на плюсах будет быстрее, чем на VBA. К тому же, можно добавить аргумент массива номеров столбцов и отобрать не только по строкам, а ещё и по столбцам (не все взять и/или в другом порядке и/или задублировать). Кстати, задублировать можно и строки, повторяя индексы.

Очень не хватает твоей реализации сцепки по условию. Я пока придумал только попутно со словарём собирать 2 одномерных массива (строковый для сцепок и лонг для последней заполненной позиции). Наполнить строковый буферными строками большой длины и заполнять их МИДом, запоминая последнюю позицию в лонг-массив. В конце, обрезать все строки по известную позицию. Тут демонстрировать не стал, а то и так непростой код.

Мне очень понравился мой вариант определения пересечения элементов массива — прямо здорово получилось  :)

А тест я, конечно, сделаю — мне и самому очень интересно.
Изменено: Jack Famous - 27.04.2024 21:50:42
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
Jack Famous написал:
инструмента для пересбора
Здесь понятно.
Цитата
Jack Famous написал:
Очень не хватает твоей реализации сцепки по условию
А здесь нет.
«Бритва Оккама» или «Принцип Калашникова»?
 
bedvit, подробно рассмотрим в моей будущей теме
Изменено: Jack Famous - 02.05.2024 17:14:45
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
     Промежуточные тесты показывают, что за фильтром от BedVit'а мне не угнаться даже при "статичном подходе"  :D

    Учитывая новое удобство передачи критериев, огромные трудозатраты по организации "статичных" параметров и, конечно же, при всём этом, недостаточную для конкуренции скорость, я бы решал подобную задачу так:
    1. Собираем все необходимые (присутствующие на листе или ещё как) комбинации параметров. Осуществляем это обновление по кнопке или событию.
    2. Пропускаем их через фильтр из библы, запоминая в карту (по ключу комбинации) индексы строк или собирая значения сразу, как нужно. Осуществляем это обновление по кнопке или событию. Оно может быть как синхронизировано с п.1, так и нет (зависит от логики задачи).
    3. Выгружаем на лист калькуляции где и когда это нужно. Если нужен вариант через функцию листа, то в функции просто извлекаем необходимое из карты и отображаем на листе.

    В принципе, этого должно хватить для абсолютного большинства всех случаев. Как (и, если) понадобиться переосмыслить подход — вернусь к теме.

bedvit, ещё раз огромное спасибо за библу (в целом) и фильтр (в частности)!  :idea:
Изменено: Jack Famous - 08.05.2024 16:51:30
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Страницы: 1
Наверх