<commit_before>// -*- mode: c++; coding: utf-8 -*-
#pragma once
#ifndef WTL_PRANDOM_HPP_
#define WTL_PRANDOM_HPP_

#include <random>
#include <unordered_set>

/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////
namespace wtl {
/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////

template <class Iter, class RNG> inline
Iter choice(Iter begin_, Iter end_, RNG& rng) {
    using diff_t = decltype(std::distance(begin_, end_));
    std::uniform_int_distribution<diff_t> uniform(0, std::distance(begin_, end_) - 1);
    std::advance(begin_, uniform(rng));
    return begin_;
}

template <class Container, class RNG> inline
Container sample(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (100 * k < n) {return sample_set(src, k, rng);}
    else if (5 * k < n) {return sample_fisher(src, k, rng);}
    else {return sample_knuth(src, k, rng);}
}

//! fast if k << n
template <class Container, class RNG> inline
Container sample_set(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    std::unordered_set<size_t> existing_indices;
    Container dst;
    dst.reserve(k);
    std::uniform_int_distribution<size_t> uniform(0, n - 1);
    size_t idx = 0;
    for (size_t i=0; i<k; ++i) {
        do {
            idx = uniform(rng);
        } while (!std::get<1>(existing_indices.insert(idx)));
        dst.push_back(src[idx]);
    }
    return dst;
}

//! Fisher-Yates algorithm; Durstenfeld; Knuth's P
//! consistently fast; note that whole src is copied first
template <class Container, class RNG> inline
Container sample_fisher(Container src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    const size_t last = n - 1;
    for (size_t i=0; i<k; ++i) {
        std::swap(src[std::uniform_int_distribution<size_t>(i, last)(rng)], src[i]);
    }
    src.resize(k);
    return src;
}

//! Knuth's algorithm S
//! fast if k / n is large
//! The order is not random
template <class Container, class RNG> inline
Container sample_knuth(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    Container samples;
    samples.reserve(k);
    size_t i = 0;
    for (; i<k; ++i) {
        samples.push_back(src[i]);
    }
    std::uniform_int_distribution<size_t> uniform(0, k - 1);
    while (i < n) {
        if (std::bernoulli_distribution((1.0 / ++i) * k)(rng)) {
            samples[uniform(rng)] = src[i - 1];
        }
    }
    return samples;
}

/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////<commit_msg>Let sample() accept valarray and return vector<commit_after>// -*- mode: c++; coding: utf-8 -*-
#pragma once
#ifndef WTL_PRANDOM_HPP_
#define WTL_PRANDOM_HPP_

#include <vector>
#include <random>
#include <unordered_set>

/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////
namespace wtl {
/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////

template <class Iter, class RNG> inline
Iter choice(Iter begin_, Iter end_, RNG& rng) {
    using diff_t = decltype(std::distance(begin_, end_));
    std::uniform_int_distribution<diff_t> uniform(0, std::distance(begin_, end_) - 1);
    std::advance(begin_, uniform(rng));
    return begin_;
}

template <class Container, class RNG> inline
std::vector<typename Container::value_type>
sample(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (100 * k < n) {return sample_set(src, k, rng);}
    else if (5 * k < n) {return sample_fisher(src, k, rng);}
    else {return sample_knuth(src, k, rng);}
}

//! fast if k << n
template <class Container, class RNG> inline
std::vector<typename Container::value_type>
sample_set(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    std::unordered_set<size_t> existing_indices;
    std::vector<typename Container::value_type> dst;
    dst.reserve(k);
    std::uniform_int_distribution<size_t> uniform(0, n - 1);
    size_t idx = 0;
    for (size_t i=0; i<k; ++i) {
        do {
            idx = uniform(rng);
        } while (!std::get<1>(existing_indices.insert(idx)));
        dst.push_back(src[idx]);
    }
    return dst;
}

//! Fisher-Yates algorithm; Durstenfeld; Knuth's P
//! consistently fast; note that whole src is copied first
template <class Container, class RNG> inline
std::vector<typename Container::value_type>
sample_fisher(const Container& src, const size_t k, RNG& rng) {
    std::vector<typename Container::value_type> dst(std::begin(src), std::end(src));
    const size_t n = dst.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    const size_t last = n - 1;
    for (size_t i=0; i<k; ++i) {
        std::swap(dst[std::uniform_int_distribution<size_t>(i, last)(rng)], dst[i]);
    }
    dst.resize(k);
    return dst;
}

//! Knuth's algorithm S
//! fast if k / n is large
//! The order is not random
template <class Container, class RNG> inline
std::vector<typename Container::value_type>
sample_knuth(const Container& src, const size_t k, RNG& rng) {
    const size_t n = src.size();
    if (n < k) throw std::runtime_error(std::string(__PRETTY_FUNCTION__) + ": n < k");
    std::vector<typename Container::value_type> dst;
    dst.reserve(k);
    size_t i = 0;
    for (; i<k; ++i) {
        dst.push_back(src[i]);
    }
    std::uniform_int_distribution<size_t> uniform(0, k - 1);
    while (i < n) {
        if (std::bernoulli_distribution((1.0 / ++i) * k)(rng)) {
            dst[uniform(rng)] = src[i - 1];
        }
    }
    return dst;
}

/////////1/////////2/////////3/////////4/////////5/////////6/////////7/////////
{'fraction_non_alphanumeric': 0.21184622999505032, 'fraction_numerical': 0.013529120607160534, 'mean_word_length': 2.6606280193236715, 'pattern_counts': {'":': 6, '<': 65, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2424861', 'n_tokens_mistral': 2168, 'n_tokens_neox': 2115, 'n_words': 544}