200 000 объектов за 2 мс: как выбирать топ-K без полной сортировки

В real-time играх и серверах часто возникает задача: из N объектов нужно выбрать K лучших, чтобы обновить их в этом кадре.

• AI для NPC: из 50 000 врагов обновить только 1000 самых важных.

• Анимации: из 10 000 персонажей показать детальные анимации только для 200 ближайших к камере.

• VFX: из 5000 частиц обновить только те, что в поле зрения.

• Сетка LOD: из 100 000 объектов выбрать 5000 для высокого качества.

Типичный подход — посчитать оценку для каждого объекта, затем отсортировать весь массив и взять первые K элементов.

// Наивный подход: полная сортировкаfloat[] scores = new float[N];for (int i = 0; i < N; i++)    scores[i] = Dot(features[i], weights);Array.Sort(scores, ids); // O(N log N)// Берём первые K

Проблема: сортировка 200 000 элементов занимает ~16 мс. Это весь бюджет кадра при 60 FPS. А ведь ещё нужно рендерить, обрабатывать физику, тикать AI.

Почему полная сортировка — это перебор

Сложность O(N log N). Для N = 200 000 это примерно 200 000 × 18 = 3.6 млн сравнений. Плюс аллокации временных массивов. Плюс GC-паузы.

А вам нужно всего K = 2000 элементов. Вы выбрасываете 198 000 отcортированных элементов. Это 99% потраченной работы впустую.

Дополнительная проблема: групповые квоты

Часто нужно не просто топ-K, а справедливое распределение между группами:

• Анимации: не более 200 объектов

• AI: не более 500 объектов

• VFX: не более 300 объектов

• Физика: не более 200 объектов

Сумма квот = K = 1200. Но если отсортировать общий список, одна группа (например, враги) может занять все топ-1200 мест, а другие группы (союзники, нейтралы) не получат ничего.

Правильное решение: отобрать топ-K с учётом квот на группу. Но как это сделать без многократной сортировки?

Решение: SIMD + селекция без полной сортировки

GameBudget.Net — библиотека для .NET 8.0+, которая решает обе задачи:

• Топ-K через heap-селекцию: O(N log K) вместо O(N log N)

• Групповые квоты через per-group heap: O(N log qᵍ) (где qᵍ — квота группы)

• SIMD-умножение матриц для скоринга через SlidingRank.FastOps

dotnet add package GameBudget.Net --version 1.0.0

Ключевые идеи

1. Heap-селекция (без полной сортировки)

   • Проходим по всем N объектам.

   • Поддерживаем min-heap размером K.

   • Если новый элемент лучше худшего в куче — заменяем.

   • В конце heap содержит топ-K, извлекаем в отсортированном порядке.

2. Per-group селекция с квотами

   • Для каждой группы свой min-heap размером с квоту группы.

   • Каждый элемент попадает только в heap своей группы.

   • В конце собираем результат: сначала группа 0, затем группа 1, и т.д.

3. SIMD для массового скоринга

   • Вместо scalar-цикла — SIMD-умножение (AVX2, SSE).

   • 16, 32, 64 признака обрабатываются за несколько инструкций.

Отличие от существующих решений

Подробнее о различиях

1. LINQ / Array.Sort

// Типичный LINQ-подходvar topK = items    .Select(i => new { Id = i.Id, Score = Dot(i.Features, weights) })    .OrderByDescending(x => x.Score)    .Take(500)    .ToArray(); // Множественные аллокации

Проблемы: аллокации на каждый элемент (анонимный тип), полная сортировка, делегаты на каждом шаге.

2. PriorityQueue из .NET

var heap = new PriorityQueue<int, float>();for (int i = 0; i < N; i++){    float score = Dot(features[i], weights);    if (heap.Count < K)        heap.Enqueue(i, -score);    else if (score > -heap.PeekPriority())    {        heap.Dequeue();        heap.Enqueue(i, -score);    }}

Проблемы: нет SIMD (скалярный dot), аллокации узлов внутри PriorityQueue, нет групповых квот.

3. QuickSelect (частичная сортировка)

// O(N) в среднем, но O(N²) в худшемQuickSelect(scores, k);var topK = scores.Take(k);

Проблемы: модифицирует исходный массив (нежелательно), нет SIMD, не поддерживает групповые квоты, нет стабильности между кадрами.

Быстрый старт

Шаг 1. Подготовка данных

using GameBudget.Net;using SlidingRank.FastOps;int n = 50_000;      // количество объектовint d = 32;          // количество признаковint k = 1000;        // сколько выбрать// Матрица признаков: row-major (каждый объект — d чисел)float[] featuresData = new float[n * d];// Веса признаковfloat[] weights = new float[d];// ID объектов (опционально)int[] ids = new int[n];for (int i = 0; i < n; i++) ids[i] = i;// ... заполняем данные ...var features = new EmbeddingMatrix(featuresData, n, d);

Шаг 2. Топ-K без групповых квот

using var scheduler = new FrameBudgetScheduler(maxEntities: n);int[] outIds = new int[k];float[] outScores = new float[k];int got = scheduler.SelectTopK(    features: features,    weights: weights,    ids: ids,    k: k,    outIds: outIds,    outScores: outScores);// outIds и outScores содержат топ-K, отсортированные по убыванию оценкиfor (int i = 0; i < got; i++){    Console.WriteLine($"Rank {i}: ID={outIds[i]}, Score={outScores[i]:F4}");}

Шаг 3. Топ-K с групповыми квотами

int groups = 8;              // количество группint[] groupIds = new int[n]; // ID группы для каждого объектаint[] quotas = new int[groups]; // сколько выбрать из каждой группы// Пример: равномерное распределениеfor (int g = 0; g < groups; g++)    quotas[g] = k / groups;quotas[0] += k - (k / groups) * groups; // остаток в первую группуusing var scheduler = new FrameBudgetScheduler(maxEntities: n, maxGroups: groups);int[] outIds = new int[k];float[] outScores = new float[k];int got = scheduler.SelectWithQuotas(    features: features,    weights: weights,    ids: ids,    groupId: groupIds,    quotas: quotas,    outIds: outIds,    outScores: outScores);// Результат сгруппирован: сначала все объекты группы 0 (отсортированы по score), // затем группы 1, и т.д.

Полный рабочий пример

using GameBudget.Net;using SlidingRank.FastOps;public class AILODScheduler{    private FrameBudgetScheduler _scheduler;    private int[] _outIds;    private float[] _outScores;        public AILODScheduler(int maxEntities, int maxK)    {        _scheduler = new FrameBudgetScheduler(maxEntities);        _outIds = new int[maxK];        _outScores = new float[maxK];    }        public int[] SelectTopNpc(        float[] featuresData,  // row-major: NpcCount × FeatureDim        float[] weights,       // FeatureDim        int[] npcIds,          // NpcCount        int featureDim,        int k)    {        int npcCount = npcIds.Length;        var features = new EmbeddingMatrix(featuresData, npcCount, featureDim);                int selected = _scheduler.SelectTopK(            features, weights, npcIds, k,            _outIds, _outScores        );                return _outIds[0..selected];    }        public void Dispose() => _scheduler.Dispose();}// Использованиеvar scheduler = new AILODScheduler(maxEntities: 50_000, maxK: 2000);// Каждый кадрint[] importantNpcs = scheduler.SelectTopNpc(    featuresData: npcFeatures,    weights: importanceWeights,    npcIds: allNpcIds,    featureDim: 32,    k: 500);// Обновляем AI только для importantNpcsforeach (int id in importantNpcs){    UpdateAI(id);}

Производительность

Тестовый стенд: Intel Core i5-11400F, Windows 11, .NET 8, BenchmarkDotNet

Топ-K (dot + селекция)

Групповые квоты (dot + селекция с квотами)

Что это значит для игры:

• 200 000 объектов, выбор топ-2000 с квотами → 2.94 мс вместо 35 мс

• Экономия ~32 мс на кадр

• При 60 FPS это разница между 16 мс (успели) и 35 мс (фреймдроп)

Zero-аллокации: как это работает

В отличие от LINQ и стандартных коллекций, GameBudget.Net не создаёт мусора в горячем пути.

Что аллоцируется один раз при создании FrameBudgetScheduler:

• Внутренние буферы для хранения временных данных

• Heaps для каждой группы (при использовании квот)

Что не аллоцируется на кадр:

• Массивы для результатов (вы передаёте свои)

• Временные массивы для оценок (переиспользуются)

• Объекты в куче (все структуры)

Как достичь zero-аллокаций:

// Плохо: аллокации на кадрint[] ids = Enumerable.Range(0, N).ToArray(); // новая аллокацияfloat[] scores = new float[N];                 // новая аллокация// Хорошо: переиспользование буферовint[] ids = _cachedIds;       // переиспользуетсяfloat[] scores = _cachedScores; // переиспользуетсяArray.Clear(scores);           // без аллокаций

Сценарии использования

Сценарий 1: LOD для AI (тысячи NPC)

Из 50 000 NPC выбираем 1000 самых важных для обновления AI.

// Признаки: расстояние до игрока, здоровье, угроза, участие в боюfloat[] npcFeatures = new float[npcCount * featureDim];// ... заполняемvar importantNpcs = scheduler.SelectTopK(    features, importanceWeights, npcIds, k: 1000,    outIds, outScores);

Сценарий 2: Анимации с групповыми квотами

Из 10 000 персонажей выбираем 500 для детальных анимаций, но с квотами: не более 200 врагов, не более 200 союзников, не более 100 нейтралов.

int[] quotas = new int[] { 200, 200, 100 }; // враги, союзники, нейтралыint[] selected = scheduler.SelectWithQuotas(    features, animationWeights, characterIds, groupIds, quotas,    outIds, outScores);

Сценарий 3: VFX и частицы

Из 5000 систем частиц обновляем только 300 самых важных (близких к камере или с высокой интенсивностью).

Сценарий 4: Сетка LOD в открытом мире

Из 200 000 объектов выбираем 10 000 для высокого качества рендеринга.

Сравнение с конкурентами (честно)

Когда стоит выбрать Unity Burst вместо GameBudget.Net

• Вы работаете исключительно в Unity и уже используете Burst.

• Вам нужно максимальное SIMD-ускорение за счёт нативного кода.

• Вы готовы писать кастомную реализацию селектора под свою задачу.

Когда стоит выбрать GameBudget.Net

• Вы работаете на чистом .NET (не Unity, или Unity без Burst).

• Нужна поддержка групповых квот.

• Важен zero-аллокации API.

• Нужна простая интеграция без изучения Burst.

Интеграция с Unity

using UnityEngine;using GameBudget.Net;using SlidingRank.FastOps;public class AILODManager : MonoBehaviour{    private FrameBudgetScheduler _scheduler;    private int[] _npcIds;    private float[] _featuresData;    private float[] _weights;        void Start()    {        int npcCount = 50000;        int featureDim = 32;                _scheduler = new FrameBudgetScheduler(maxEntities: npcCount);        _npcIds = new int[npcCount];        _featuresData = new float[npcCount * featureDim];        _weights = new float[featureDim];                // Инициализация...    }        void Update()    {        // Обновляем признаки (расстояние до игрока, здоровье, угроза)        UpdateFeatures();                // Выбираем топ-500 NPC для AI-обновления        int[] outIds = new int[500];        float[] outScores = new float[500];                var features = new EmbeddingMatrix(_featuresData, _npcIds.Length, _weights.Length);                int selected = _scheduler.SelectTopK(            features, _weights, _npcIds, 500,            outIds, outScores        );                // Обновляем AI только для выбранных        for (int i = 0; i < selected; i++)        {            UpdateAIForNpc(outIds[i]);        }    }        void OnDestroy() => _scheduler.Dispose();}

Бесплатное тестирование — без ограничений. Коммерческое использование требует лицензии.

NuGet: https://www.nuget.org/packages/GameBudget.Net

GitHub (бенчмарки): https://github.com/likeslines-maker/GameBudget.Net

GameBudget.Net — это библиотека для быстрой селекции топ-K объектов с поддержкой групповых квот.

В отличие от полной сортировки (Array.Sort, LINQ) она:

• Работает за O(N log K) вместо O(N log N)

• Использует SIMD для массового скоринга

• Не создаёт аллокаций на кадр

• Поддерживает групповые квоты (честное распределение между категориями)

В отличие от PriorityQueue из коробки:

• Даёт готовый zero-аллокации API

• Поддерживает групповые квоты

• Использует SIMD dot вместо скалярного

В отличие от Unity Burst:

• Работает на любом .NET (не только Unity)

• Не требует изучения Burst и HPC#

• Даёт простой API с групповыми квотами

Если ваш фрейм-бюджет страдает от полной сортировки тысяч объектов — попробуйте GameBudget.Net. Сортировка 200 000 объектов за 16 мс — это слишком дорого для того, чтобы выбросить 99% результата.