gpu_boundary_detector.cpp - master - nik2703/boundary_approx

gpu_boundary_detector.cpp
112 строк6 KB
nik2703
upload files
07 окт 2025, 17:29
07 окт 2025, 17:2932b847a
#include "gpu_boundary_detector.h"
#include <faiss/IndexFlat.h>
#include <faiss/gpu/GpuIndexFlat.h>
#include <faiss/gpu/utils/DeviceUtils.h>
#include <iostream>
#include <unordered_map>
#include <cassert>

GPUBoundaryDetector::GPUBoundaryDetector(int gpu_id) : gpu_id_(gpu_id) {
    // Инициализация ресурсов GPU для FAISS
    faiss::gpu::setCurrentDevice(gpu_id);
    gpu_res_ = std::make_unique<faiss::gpu::StandardGpuResources>();
}

GPUBoundaryDetector::~GPUBoundaryDetector() = default;

std::vector<BoundarySegmentTask> GPUBoundaryDetector::detectAllBoundaries(
    const std::vector<DataPoint>& data_points,
    int k,
    int threshold
) {
    if (data_points.empty()) return {};

    size_t num_points = data_points.size();
    size_t dim = data_points[0].coords.size();

    // 1. Подготовка данных в формате, понятном FAISS (плоский массив float)
    std::vector<float> dataset_flat(num_points * dim);
    std::vector<int> cluster_ids(num_points);

    for (size_t i = 0; i < num_points; ++i) {
        for (size_t d = 0; d < dim; ++d) {
            dataset_flat[i * dim + d] = data_points[i].coords[d];
        }
        cluster_ids[i] = data_points[i].cluster_id;
    }

    // 2. Создание и обучение индекса FAISS на GPU
    // Используем простой плоский индекс (brute-force), так как он наиболее точен для нашей задачи.
    // Для очень больших наборов можно использовать приближенные индексы (IVF, HNSW).
    faiss::IndexFlatL2 cpu_index(dim); // L2 (евклидово расстояние) на CPU
    faiss::gpu::GpuIndexFlatConfig config;
    config.device = gpu_id_;
    faiss::gpu::GpuIndexFlatL2 gpu_index(gpu_res_.get(), dim, config);

    // Копируем данные на GPU и строим индекс
    gpu_index.add(num_points, dataset_flat.data());

    // 3. Выполнение поиска k-NN для всех точек за один вызов (очень эффективно!)
    // `distances` и `indices` будут содержать результаты для всех точек.
    std::vector<faiss::idx_t> indices(num_points * k);
    std::vector<float> distances(num_points * k);

    gpu_index.search(num_points, dataset_flat.data(), k + 1, distances.data(), indices.data());
    // Запрашиваем k+1, потому что ближайшим соседом каждой точки будет она сама (расстояние 0).

    // 4. Анализ результатов поиска и идентификация граничных точек
    // Сначала соберем все уникальные кластеры
    std::set<int> unique_clusters(cluster_ids.begin(), cluster_ids.end());
    std::vector<BoundarySegmentTask> all_tasks;

    // Создадим карту для быстрого доступа к ID кластера по индексу точки
    // (cluster_ids уже является такой картой)

    // Для каждой пары кластеров
    for (auto it_i = unique_clusters.begin(); it_i != unique_clusters.end(); ++it_i) {
        for (auto it_j = std::next(it_i); it_j != unique_clusters.end(); ++it_j) {
            int cluster_i = *it_i;
            int cluster_j = *it_j;
            BoundarySegmentTask task;
            task.cluster_i = cluster_i;
            task.cluster_j = cluster_j;

            // Проходим по всем точкам
            for (size_t point_idx = 0; point_idx < num_points; ++point_idx) {
                // Пропускаем точки, не принадлежащие кластерам i или j
                if (cluster_ids[point_idx] != cluster_i && cluster_ids[point_idx] != cluster_j) {
                    continue;
                }

                int count_neighbors_from_other_cluster = 0;
                // Анализируем k+1 ближайших соседей
                for (int n = 0; n <= k; ++n) {
                    faiss::idx_t neighbor_idx = indices[point_idx * (k + 1) + n];
                    // Пропускаем саму точку (расстояние 0)
                    if (neighbor_idx == static_cast<faiss::idx_t>(point_idx)) {
                        continue;
                    }
                    // Проверяем, принадлежит ли сосед к "другому" кластеру
                    if ((cluster_ids[point_idx] == cluster_i && cluster_ids[neighbor_idx] == cluster_j) ||
                        (cluster_ids[point_idx] == cluster_j && cluster_ids[neighbor_idx] == cluster_i)) {
                        count_neighbors_from_other_cluster++;
                    }
                }

                // Если количество соседей из другого кластера достаточно, точка - граничная
                if (count_neighbors_from_other_cluster >= threshold) {
                    task.boundary_points.push_back(data_points[point_idx]);
                }
            }

            if (!task.boundary_points.empty()) {
                all_tasks.push_back(std::move(task));
                std::cout << "Найдено " << task.boundary_points.size() 
                          << " граничных точек между кластерами " 
                          << cluster_i << " и " << cluster_j << ".\n";
            }
        }
    }

    return all_tasks;
}