mnncorrect.hpp

Go to the documentation of this file.

#ifndef MNNCORRECT_HPP
#define MNNCORRECT_HPP
 
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdexcept>
#include <cstddef>
 
#include "knncolle/knncolle.hpp"
#include "sanisizer/sanisizer.hpp"
 
#include "Coordinator.hpp"
#include "reorder_matrix_in_place.hpp"
#include "utils.hpp"
 
namespace mnncorrect {
 
template<typename Index_, typename Float_, class Matrix_ = knncolle::Matrix<Index_, Float_> >
struct Options {
    int num_neighbors = 15;
 
    int num_steps = 1;
 
    std::shared_ptr<knncolle::Builder<Index_, Float_, Float_, Matrix_> > builder;
 
    MergePolicy merge_policy = MergePolicy::RSS;
 
    int num_threads = 1;
};
 
template<typename Index_, typename Float_, class Matrix_>
void compute_internal(
    const std::size_t num_dim,
    const Index_ num_total,
    const std::vector<Batch<Index_> >& batches,
    Float_* const data,
    const Options<Index_, Float_, Matrix_>& options
) {
    auto builder = options.builder;
    if (!builder) {
        typedef knncolle::EuclideanDistance<Float_, Float_> Euclidean;
        builder.reset(new knncolle::VptreeBuilder<Index_, Float_, Float_, Matrix_, Euclidean>(std::make_shared<Euclidean>()));
    }
 
    Coordinator<Index_, Float_, Matrix_> runner(
        num_dim,
        num_total,
        batches,
        data,
        *builder,
        options.num_neighbors,
        options.num_steps,
        options.merge_policy,
        options.num_threads
    );
 
    runner.merge();
}
template<typename Index_, typename Float_, class Matrix_>
void compute(const std::size_t num_dim, const std::vector<Batch<Index_> >& batches, Float_* const data, const Options<Index_, Float_, Matrix_>& options) {
    Index_ num_total = 0;
    for (const auto& batch : batches) {
        num_total = sanisizer::sum<Index_>(num_total, batch.size);
    }
    compute_internal(num_dim, num_total, batches, data, options);
}
 
template<typename Index_, typename Float_, typename Batch_, class Matrix_>
void compute(
    const std::size_t num_dim,
    const Index_ num_obs,
    Float_* const data,
    const Batch_* const batch,
    const BatchIndex num_batches,
    const Options<Index_, Float_, Matrix_>& options
) {
    // Avoiding allocation of a temporary buffer if we're already dealing with contiguous batches.
    auto batches = sanisizer::create<std::vector<Batch<Index_> > >(num_batches);
    Index_ non_contiguous = 0;
    for (Index_ o = 0; o < num_obs; ++o) {
        auto& curbatch = batches[batch[o]];
        if (curbatch.size == 0) {
            curbatch.start = o;
            curbatch.size = 1;
        } else {
            non_contiguous += (o != curbatch.start + curbatch.size);
            ++curbatch.size;
        }
    }
 
    if (non_contiguous == 0) {
        compute_internal(num_dim, num_obs, batches, data, options);
        return;
    }
 
    // Otherwise, we reorganize the data so that observations from the same batch are in a single block.
    Index_ accumulated = 0;
    auto offsets = sanisizer::create<std::vector<Index_> >(num_batches);
    for (BatchIndex b = 0; b < num_batches; ++b) {
        offsets[b] = accumulated;
        batches[b].start = accumulated;
        accumulated += batches[b].size; // this won't overflow as know that num_obs fits in an Index_.
    }
 
    auto reordered = sanisizer::create<std::vector<Index_> >(num_obs);
    for (Index_ o = 0; o < num_obs; ++o) {
        auto& offset = offsets[batch[o]];
        reordered[offset] = o;
        ++offset;
    }
    auto mbuffer = sanisizer::create<std::vector<Float_> >(num_dim); 
    reorder_matrix_in_place(num_dim, num_obs, reordered, data, mbuffer);
 
    compute_internal(num_dim, num_obs, batches, data, options);
 
    // Reorganizing back to the original ordering.
    for (BatchIndex b = 0; b < num_batches; ++b) {
        offsets[b] = batches[b].start;
    }
    for (Index_ o = 0; o < num_obs; ++o) {
        auto& offset = offsets[batch[o]];
        reordered[o] = offset;
        ++offset;
    }
    reorder_matrix_in_place(num_dim, num_obs, reordered, data, mbuffer);
}
 
}
 
#endif