Сортировка — смерть производительности. Часть 1.
В Power Query функции сортировки Table.Sort, List.Sort — одни из самых "дорогих" операций.
❌ Имеют вычислительную сложность O(n log n).
❌ Прерывают потоковую обработку данных.
❌ Ломают ленивые вычисления.
❌ Заставляют систему загружать все данные в оперативную память.
❌ При использовании в циклах быстро превращаются в вычислительную сложность O(n²) и хуже.
❌ Часто ломают Query Folding (свертывание запросов) — относится только к SQL запросам, а не к лежащим на ПК файлам.
Эксперты BI индустрии сортировку используют только в крайних случаях.
————
Категоризация альтернатив сортировке.
Ниже перечислены функции, которые выполняют задачи поиска и отбора данных быстрее, чем сортировка.
1️⃣ Функции поиска экстремумов (максимума/минимума) для таблиц — сложность O(n).
Вместо упорядочивания всего списка ради одного значения используются агрегатные функции.
⚫️ Table.Max — поиск строки с максимальным значением по столбцу.
Сложность: O(n).
Применение: Вместо Table.Sort + Table.First. Например, чтобы не оставлять только одну строку с максимальным расходом для каждой рекламной кампании, где сложность — O(n²) или O(n log n).
⚫️ Table.Min — поиск строки с минимальным значением по столбцу.
Сложность: O(n).
Применение: Вместо Table.Sort + Table.First
————
2️⃣ Получение элементов списка по позиции — сложность O(1).
Если данные уже имеют структуру, сортировка не нужна.
⚫️ List.First — первый элемент списка.
Сложность: O(1). Мгновенное взятие первого элемента.
Применение: Быстрый доступ к началу списка.
⚫️ List.Last — последний элемент списка.
Сложность: O(1).
Применение: Быстрый доступ к концу списка.
————
3️⃣ Топ-N без полной сортировки списка
⚫️ List.MaxN — N максимальных элементов из списка.
Сложность: O(n × k).
Применение: Частичная сортировка для топ-элементов.
⚫️ List.MinN — N минимальных элементов из списка.
Сложность: O(n × k).
Применение: Поиск топ-элементов.
⚫️ List.FirstN — первые N элементов.
Сложность: O(n).
Применение: Срез данных с начала.
⚫️ List.LastN — последние N элементов.
Сложность: O(n).
Применение: Срез данных с конца.
————
4️⃣ Получение элементов таблицы по позиции.
Если данные уже имеют структуру, сортировка не нужна.
⚫️ Table.First — первая строка таблицы.
Сложность: O(1).
Применение: Получение первой строки без сортировки.
⚫️ Table.Last — последняя строка таблицы.
Сложность: O(1).
Применение: Последняя строка без сортировки.
⚫️ Table.FirstN — первые N строк таблицы.
Сложность: O(n).
Применение: Выборка строк с начала.
⚫️ Table.LastN — последние N строк таблицы.
Сложность: O(n).
Применение: Выборка строк с конца.
————
5️⃣ Топ-N без полной сортировки таблицы
⚫️ Table.MaxN — поиск N строк с наибольшими значениями.
Сложность: O(n × k), где k — количество элементов (обычно k
Предыдущие посты серии:
1. Документация по промптам.
2. Выбор нейронок.
3. Подготовка к разработке.
4. Оптимизация кода.
5. Если код не "летает".
6. Минимизируем вычисления.
7. Фатальный пример вычислений.
8. Порядок обработки данных.
В Power Query функции сортировки Table.Sort, List.Sort — одни из самых "дорогих" операций.
❌ Имеют вычислительную сложность O(n log n).
❌ Прерывают потоковую обработку данных.
❌ Ломают ленивые вычисления.
❌ Заставляют систему загружать все данные в оперативную память.
❌ При использовании в циклах быстро превращаются в вычислительную сложность O(n²) и хуже.
❌ Часто ломают Query Folding (свертывание запросов) — относится только к SQL запросам, а не к лежащим на ПК файлам.
Эксперты BI индустрии сортировку используют только в крайних случаях.
————
Категоризация альтернатив сортировке.
Ниже перечислены функции, которые выполняют задачи поиска и отбора данных быстрее, чем сортировка.
1️⃣ Функции поиска экстремумов (максимума/минимума) для таблиц — сложность O(n).
Вместо упорядочивания всего списка ради одного значения используются агрегатные функции.
⚫️ Table.Max — поиск строки с максимальным значением по столбцу.
Сложность: O(n).
Применение: Вместо Table.Sort + Table.First. Например, чтобы не оставлять только одну строку с максимальным расходом для каждой рекламной кампании, где сложность — O(n²) или O(n log n).
⚫️ Table.Min — поиск строки с минимальным значением по столбцу.
Сложность: O(n).
Применение: Вместо Table.Sort + Table.First
————
2️⃣ Получение элементов списка по позиции — сложность O(1).
Если данные уже имеют структуру, сортировка не нужна.
⚫️ List.First — первый элемент списка.
Сложность: O(1). Мгновенное взятие первого элемента.
Применение: Быстрый доступ к началу списка.
⚫️ List.Last — последний элемент списка.
Сложность: O(1).
Применение: Быстрый доступ к концу списка.
————
3️⃣ Топ-N без полной сортировки списка
⚫️ List.MaxN — N максимальных элементов из списка.
Сложность: O(n × k).
Применение: Частичная сортировка для топ-элементов.
⚫️ List.MinN — N минимальных элементов из списка.
Сложность: O(n × k).
Применение: Поиск топ-элементов.
⚫️ List.FirstN — первые N элементов.
Сложность: O(n).
Применение: Срез данных с начала.
⚫️ List.LastN — последние N элементов.
Сложность: O(n).
Применение: Срез данных с конца.
————
4️⃣ Получение элементов таблицы по позиции.
Если данные уже имеют структуру, сортировка не нужна.
⚫️ Table.First — первая строка таблицы.
Сложность: O(1).
Применение: Получение первой строки без сортировки.
⚫️ Table.Last — последняя строка таблицы.
Сложность: O(1).
Применение: Последняя строка без сортировки.
⚫️ Table.FirstN — первые N строк таблицы.
Сложность: O(n).
Применение: Выборка строк с начала.
⚫️ Table.LastN — последние N строк таблицы.
Сложность: O(n).
Применение: Выборка строк с конца.
————
5️⃣ Топ-N без полной сортировки таблицы
⚫️ Table.MaxN — поиск N строк с наибольшими значениями.
Сложность: O(n × k), где k — количество элементов (обычно k