<commit_before># This function samples k indices from 1:n starting with very dense sampling
# (every value) and then getting more and more sparse

#' Sampling for qq plots
#' 
#' Returns k indices between 1:n such that sampling is very dense at the start and much less dense at the end.
#' 
#' @export
thin <- function(n, k=2000) {
  if ( n < k ) {
    return (1:n)
  }
  
  # Figure out how many groups we need to divide n into
  # so that we end up with k values
  # We want each group to be twice as big as the previous group
  # We want to sample every index in the first group
  x <- 2
  while ( (2*x-2)/(2^x-2) > k/n ) { x <- x + 1 }
  
  # Each group is twice as big as the previous group
  end.idx <- c(round(2^(1:(x-1))*n/(2^x-2)), n)
  start.idx <- c(1, end.idx[-x]+1)
  
  # Sample the same number of values from each group
  sample.size <- ceiling(k/x)
  thin.idx <- NULL
  
  for ( i in 1:x ) {
    if ( end.idx[i] - start.idx[i] < sample.size) {
      # If there aren't enough values use all indices in group i
      thin.idx <- c(thin.idx, start.idx[i]:end.idx[i])
      # Adjust sample size accordingly
      sample.size <- ceiling((k-length(thin.idx))/(x-i))
    } else {
      # Sample from group i
      thin.idx <- c(thin.idx, sort(sample(start.idx[i]:end.idx[i], sample.size)))
    }
  }
  
  # Return the list of indices
  return ( thin.idx )
}

#' Fast QQ plots
#' 
#' QQ plots with lots of points can be slow. Since most of the points overlap
#' we don't actually have to plot all of them (and in many cases the output
#' will be identical.)
#' 
#' This function will either take a set of indices or a value k (default 2000)
#' and sample that many pvalues, then plot the log observed vs expected pvals
#' in a nice way.
#' <commit_msg>Complete rewrite of thin(n, k) to be much, MUCH faster and memory efficient when n is large (>1e10)<commit_after># This function samples k indices from 1:n starting with very dense sampling
# (every value) and then getting more and more sparse

#' Sampling for qq plots
#' 
#' Returns k indices between 1:n such that sampling is very dense at the start and much less dense at the end.
#' 
#' @export
thin <- function(n, k=2000) {
  if ( n < k ) {
    return (1:n)
  }
  
  # Generate k samples x such that exp(n-x) is uniformly distributed
  rx <- sort(log(runif(k)), decreasing=TRUE)
  x <- round(n-(rx-min(rx))/(max(rx)-min(rx))*(n-1))
  
  # Ensure each x is unique (Equivalently, diff(x) != 0)
  i <- 1
  j <- 1
  dx <- diff(x)
  
  while ( any(dx[i:(k-1)] == 0) ) {
    i <- i - 1 + which.max(dx[i:(k-1)] == 0)
    if ( dx[j] <= 1 )
      j <- j - 1 + which.max(dx[j:(k-1)] > 1)
    
    dx[i] <- dx[i] + 1
    dx[j] <- dx[j] - 1
  }
  
  cumsum(c(1, dx))
}

#' Fast QQ plots
#' 
#' QQ plots with lots of points can be slow. Since most of the points overlap
#' we don't actually have to plot all of them (and in many cases the output
#' will be identical.)
#' 
#' This function will either take a set of indices or a value k (default 2000)
#' and sample that many pvalues, then plot the log observed vs expected pvals
#' in a nice way.
#' 
{'fraction_non_alphanumeric': 0.12983247422680413, 'fraction_numerical': 0.017719072164948453, 'mean_word_length': 2.819188191881919, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 6, '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': '1005419', 'n_tokens_mistral': 1159, 'n_tokens_neox': 1044, 'n_words': 441}