Searching sorted data

Once data is sorted, you can find where any value belongs in it quickly. Kwker's searchsorted, bucketize and bucket_counts answer three versions of that question.

Where does a value go? searchsorted

searchsorted(sorted_array, values) returns, for each value, the position where it would be inserted to keep the array sorted. With side="left" (the default) the position is before any equal elements. With side="right" it is after them. It works like numpy.searchsorted.

import numpy as np
import kwker

grades = np.array([60, 70, 80, 90])          # must already be sorted
scores = np.array([55, 70, 85, 99])
print(kwker.searchsorted(grades, scores))
print(kwker.searchsorted(grades, scores, side="right"))

[0 1 3 4]
[0 2 3 4]

RustAdd kwker to Cargo.toml, then cargo run.

use kwker::{Order, Side};

fn main() {
    let grades = [60, 70, 80, 90];          // must already be sorted
    let scores = [55, 70, 85, 99];
    println!("{:?}", kwker::searchsorted(&grades, &scores, Side::Left, Order::ASCENDING));
    println!("{:?}", kwker::searchsorted(&grades, &scores, Side::Right, Order::ASCENDING));
}

Output

[0, 1, 3, 4]
[0, 2, 3, 4]

CInclude kwker.h; link with -lkwker_c.

#include <inttypes.h>
#include <stdio.h>
#include <kwker.h>

int main(void) {
    const int32_t grades[] = {60, 70, 80, 90};   /* must already be sorted */
    const int32_t scores[] = {55, 70, 85, 99};
    for (int side = 0; side <= 1; side++) {      /* 0: left, 1: right */
        uint64_t at[4];
        kwker_i32_searchsorted(grades, 4, scores, 4, KWKER_ASCENDING, side, at);
        printf("%" PRIu64 " %" PRIu64 " %" PRIu64 " %" PRIu64 "\n", at[0], at[1], at[2], at[3]);
    }
    return 0;
}

Output

0 1 3 4
0 2 3 4

C++Include kwker.hpp; link with -lkwker_c.

#include <iostream>
#include <vector>
#include <kwker.hpp>

int main() {
    std::vector<int> grades{60, 70, 80, 90};   // must already be sorted
    std::vector<int> scores{55, 70, 85, 99};
    for (bool right : {false, true}) {
        for (auto i : kwker::searchsorted(grades, scores, right)) std::cout << i << ' ';
        std::cout << '\n';
    }
}

Output

0 1 3 4
0 2 3 4

const kwk = require("kwker");

const grades = new Int32Array([60, 70, 80, 90]);   // must already be sorted
const scores = new Int32Array([55, 70, 85, 99]);
console.log(kwk.searchsorted(grades, scores));
console.log(kwk.searchsorted(grades, scores, { side: "right" }));

Uint32Array(4) [ 0, 1, 3, 4 ]
Uint32Array(4) [ 0, 2, 3, 4 ]

Gogo get kwker.io/go, then go run .

package main

import (
	"fmt"

	"kwker.io/go/kwker"
)

func main() {
	grades := []int32{60, 70, 80, 90} // must already be sorted
	scores := []int32{55, 70, 85, 99}
	fmt.Println(kwker.SearchSorted(grades, scores, false, kwker.Ascending))
	fmt.Println(kwker.SearchSorted(grades, scores, true, kwker.Ascending))
}

Output

[0 1 3 4]
[0 2 3 4]

JavaPut kwker.jar on the class path.

import io.kwker.Kwker;
import java.util.Arrays;

public class Example {
    public static void main(String[] args) {
        int[] grades = {60, 70, 80, 90};   // must already be sorted
        int[] scores = {55, 70, 85, 99};
        System.out.println(Arrays.toString(Kwker.searchSorted(grades, scores, false, Kwker.ASCENDING)));
        System.out.println(Arrays.toString(Kwker.searchSorted(grades, scores, true, Kwker.ASCENDING)));
    }
}

Output

[0, 1, 3, 4]
[0, 2, 3, 4]

C#Add the Kwker NuGet package, then dotnet run.

using Kwker;

var grades = new int[] { 60, 70, 80, 90 };   // must already be sorted
var scores = new int[] { 55, 70, 85, 99 };
Console.WriteLine(string.Join(" ", Sorter.SearchSorted(grades, scores)));
Console.WriteLine(string.Join(" ", Sorter.SearchSorted(grades, scores, Side.Right)));

Output

0 1 3 4
0 2 3 4

Which bucket? bucketize

bucketize(values, boundaries) returns the bucket number of every value, as torch.bucketize does. Bucket 0 holds values up to the first boundary, bucket 1 values up to the second, and so on. The last bucket holds values above every boundary.

import numpy as np
import kwker

age_limits = np.array([12, 19, 64])           # child, teen, adult, senior
ages = np.array([8, 15, 30, 70, 19])
print(kwker.bucketize(ages, age_limits))

[0 1 2 3 1]

RustAdd kwker to Cargo.toml, then cargo run.

use kwker::Order;

fn main() {
    let age_limits = [12, 19, 64];           // child, teen, adult, senior
    let ages = [8, 15, 30, 70, 19];
    println!("{:?}", kwker::bucketize(&ages, &age_limits, false, Order::ASCENDING));
}

Output

[0, 1, 2, 3, 1]

CInclude kwker.h; link with -lkwker_c.

#include <inttypes.h>
#include <stdio.h>
#include <kwker.h>

int main(void) {
    const int32_t age_limits[] = {12, 19, 64};   /* child, teen, adult, senior */
    const int32_t ages[] = {8, 15, 30, 70, 19};
    uint64_t bucket[5];
    /* a bucket number is where the value goes among the limits */
    kwker_i32_searchsorted(age_limits, 3, ages, 5, KWKER_ASCENDING, 0, bucket);
    for (int i = 0; i < 5; i++) printf(i ? " %" PRIu64 : "%" PRIu64, bucket[i]);
    printf("\n");
    return 0;
}

Output

0 1 2 3 1

C++Include kwker.hpp; link with -lkwker_c.

#include <iostream>
#include <vector>
#include <kwker.hpp>

int main() {
    std::vector<int> age_limits{12, 19, 64};   // child, teen, adult, senior
    std::vector<int> ages{8, 15, 30, 70, 19};
    // a bucket number is where the value goes among the limits
    for (auto b : kwker::searchsorted(age_limits, ages)) std::cout << b << ' ';
    std::cout << '\n';
}

Output

0 1 2 3 1

const kwk = require("kwker");

const ageLimits = new Int32Array([12, 19, 64]);   // child, teen, adult, senior
const ages = new Int32Array([8, 15, 30, 70, 19]);
// a bucket number is where the value goes among the limits
console.log(kwk.searchsorted(ageLimits, ages));

Uint32Array(5) [ 0, 1, 2, 3, 1 ]

Gogo get kwker.io/go, then go run .

package main

import (
	"fmt"

	"kwker.io/go/kwker"
)

func main() {
	ageLimits := []int32{12, 19, 64} // child, teen, adult, senior
	ages := []int32{8, 15, 30, 70, 19}
	// the bucket of each age: the first limit >= it (left side)
	fmt.Println(kwker.SearchSorted(ageLimits, ages, false, kwker.Ascending))
}

Output

[0 1 2 3 1]

JavaPut kwker.jar on the class path.

import io.kwker.Kwker;
import java.util.Arrays;

public class Example {
    public static void main(String[] args) {
        int[] ageLimits = {12, 19, 64};   // child, teen, adult, senior
        int[] ages = {8, 15, 30, 70, 19};
        // the bucket of each age: the first limit >= it (left side)
        System.out.println(Arrays.toString(Kwker.searchSorted(ageLimits, ages, false, Kwker.ASCENDING)));
    }
}

Output

[0, 1, 2, 3, 1]

C#Add the Kwker NuGet package, then dotnet run.

using Kwker;

var ageLimits = new int[] { 12, 19, 64 };   // child, teen, adult, senior
var ages = new int[] { 8, 15, 30, 70, 19 };
// the bucket of each age: the first limit >= it (left side)
Console.WriteLine(string.Join(" ", Sorter.SearchSorted(ageLimits, ages)));

Output

0 1 2 3 1

How many in each bucket? bucket_counts

bucket_counts(values, boundaries) counts the values in each bucket. It is a histogram with the edges you choose, and it never builds the per-value bucket array.

import numpy as np
import kwker

age_limits = np.array([12, 19, 64])
ages = np.array([8, 15, 30, 70, 19, 45, 3])
print(kwker.bucket_counts(ages, age_limits))

[2 2 2 1]

RustAdd kwker to Cargo.toml, then cargo run.

use kwker::Order;

fn main() {
    let age_limits = [12, 19, 64];
    let ages = [8, 15, 30, 70, 19, 45, 3];
    println!("{:?}", kwker::bucket_counts(&ages, &age_limits, false, Order::ASCENDING));
}

Output

[2, 2, 2, 1]

CInclude kwker.h; link with -lkwker_c.

#include <inttypes.h>
#include <stdio.h>
#include <kwker.h>

int main(void) {
    const int32_t age_limits[] = {12, 19, 64};
    const int32_t ages[] = {8, 15, 30, 70, 19, 45, 3};
    uint64_t counts[4];
    kwker_i32_bucket_counts(ages, 7, age_limits, 3, KWKER_ASCENDING, 0, counts);
    printf("%" PRIu64 " %" PRIu64 " %" PRIu64 " %" PRIu64 "\n", counts[0], counts[1], counts[2], counts[3]);
    return 0;
}

Output

2 2 2 1

C++Include kwker.hpp; link with -lkwker_c.

#include <iostream>
#include <vector>
#include <kwker.hpp>

int main() {
    std::vector<int> age_limits{12, 19, 64};
    std::vector<int> ages{8, 15, 30, 70, 19, 45, 3};
    for (auto c : kwker::bucket_counts(ages, age_limits)) std::cout << c << ' ';
    std::cout << '\n';
}

Output

2 2 2 1

const kwk = require("kwker");

const ageLimits = new Int32Array([12, 19, 64]);
const ages = new Int32Array([8, 15, 30, 70, 19, 45, 3]);
console.log(kwk.bucketCounts(ages, ageLimits));

Float64Array(4) [ 2, 2, 2, 1 ]

Gogo get kwker.io/go, then go run .

package main

import (
	"fmt"

	"kwker.io/go/kwker"
)

func main() {
	ageLimits := []int32{12, 19, 64}
	ages := []int32{8, 15, 30, 70, 19, 45, 3}
	fmt.Println(kwker.BucketCounts(ages, ageLimits, false, kwker.Ascending))
}

Output

[2 2 2 1]

JavaPut kwker.jar on the class path.

import io.kwker.Kwker;
import java.util.Arrays;

public class Example {
    public static void main(String[] args) {
        int[] ageLimits = {12, 19, 64};
        int[] ages = {8, 15, 30, 70, 19, 45, 3};
        System.out.println(Arrays.toString(Kwker.bucketCounts(ages, ageLimits, false, Kwker.ASCENDING)));
    }
}

Output

[2, 2, 2, 1]

C#Add the Kwker NuGet package, then dotnet run.

using Kwker;

var ageLimits = new[] { 12, 19, 64 };
var ages = new[] { 8, 15, 30, 70, 19, 45, 3 };
Console.WriteLine(string.Join(" ", Sorter.BucketCounts(ages, ageLimits)));

Output

2 2 2 1

Things to know

Important

The sorted array must be sorted in the same order you pass (descending, nans_first). Kwker does not check it, because checking would take as long as the search. An unsorted array gives positions that mean nothing.

The values are converted to the sorted array's type, and the conversion must be exact.
Large batches of values are sorted and merged with the array in one pass, which is faster than searching for them one by one.

Searching sorted data

Where does a value go? searchsorted

Which bucket? bucketize

How many in each bucket? bucket_counts

Things to know

Related