7
\$\begingroup\$

Gematria is an ancient Jewish method to determine a numeric value of a letter sequence, using a fixed value for each letter. Gematria is originally applied to Hebrew letters, but for the context of this challenge, we'll use Latin script instead. There are many ways to implement Gematria in Latin script, but let's define it as a close as it can be to the original standard encoding. The numbering goes as such:

A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, I = 9, J = 10, K = 20, L = 30, M = 40, N = 50, O = 60, P = 70, Q = 80, R = 90, S = 100, T = 200, U = 300, V = 400, W = 500, X = 600, Y = 700, Z = 800.

Your job is to calculate the Gematria value for each character of a string, sum the result and print it or return it.

Rules

  • Lowercase and uppercase letters yield the same value. Anything else equals 0. You can assume the input encoding will always be ASCII.
  • You can input the file in whatever method you see fit, be it loading it from a file, piping it in the terminal or baking it into the source code.
  • You can use any method you see fit in order to make this go fast, except const evaluation of the input's value and baking that into the binary or a similar method. That would be way too easy. The calculation must happen locally on runtime.

And here's a naïve implementation in Rust to provide an example implementation:

#![feature(exclusive_range_pattern)]
fn char_to_number(mut letter: char) -> u32 {
    // map to lowercase as casing doesn't matter in Gematria
    letter = letter.to_ascii_lowercase();
    // get numerical value relative to 'a', mod 9 and plus 1 because a = 1, not 0.
    // overflow doesn't matter here because all valid ranges ahead have valid values 
    let num_value = ((letter as u32).overflowing_sub('a' as u32).0) % 9 + 1;
    // map according to the Gematria skip rule
    match letter.to_ascii_lowercase() {
        'a'..'j' => num_value, // simply its value: 1, 2, 3...
        'j'..'s' => num_value * 10, // in jumps of 10: 10, 20, 30...
        's'..='z' => num_value * 100, // in jumps of 100: 100, 200, 300...
        _ => 0 // anything else has no value
    }
}

fn gematria(word: &str) -> u64 {
    word
        .chars()
        .map(char_to_number)
        .map(|it| it as u64) // convert to a bigger type before summing
        .sum()
}

In order to measure speed, each implementation will be fed the exact same file: a random 100MB text file from Github: https://github.com/awhipp/100mb-daily-random-text/releases/tag/v20221005

The speed of my implementation, measured with Measure-Command, completes in ~573ms and yields the number 9140634224. I compiled using -O 3 and baked the input text into the source code, and then ran the code on an Intel i5-10400 CPU.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ This would be clearer if you specified what submissions are supposed to do with the numbers. From the sample script it looks like they're summed, but that isn't super clear. Also, I'm not sure how interesting this will be as fastest-code since it's O(n) and basically just involves taking the sum of some bytes mapped to certain integers. \$\endgroup\$ Commented Oct 5, 2022 at 20:59
  • \$\begingroup\$ @RadvylfPrograms fixed. It being so simple is what allows for some crazy optimizations. You can use vector instructions, multithreading, all sorts of interesting tricks to make this execute faster. \$\endgroup\$ Commented Oct 5, 2022 at 21:10
  • 1
    \$\begingroup\$ @TheShwarma the problem is, it's going to be so fast as to be almost immeasurable. Also, such a simple fastest-code task means you're effectively limiting the challenge to assembly language? I honestly think shortest code would make more sense. Also, a worked example would make it far more obvious what this challenge is about. \$\endgroup\$ Commented Oct 5, 2022 at 21:17
  • 3
    \$\begingroup\$ @TheShwarma I think Adám's just saying/joking that "convert" is an odd way of phrasing it when the files are exactly identical binary-wise \$\endgroup\$ Commented Oct 5, 2022 at 21:39
  • 1
    \$\begingroup\$ 100 MB isn’t nearly big enough—my program runs at about 13.5 GB/s on larger files, so the program startup and measurement variance contribute about as much to measured time as the computation itself. \$\endgroup\$ Commented Oct 7, 2022 at 21:49

5 Answers 5

7
\$\begingroup\$

Rust, ≈ 10 ms

Compile with cargo build --release, run with target/release/gematria random-20221005.txt.

Cargo.toml

[package]
name = "gematria"
version = "0.1.0"
edition = "2021"

[dependencies]
memmap = "0.7.0"
rayon = "1.5.3"

src/main.rs

use core::arch::x86_64::*;
use memmap::MmapOptions;
use rayon::prelude::*;
use std::env::args;
use std::fs::File;
use std::io;

fn gematria(bytes: &[u8]) -> u64 {
    let (prefix, vecs, suffix) = unsafe { bytes.align_to::<__m256i>() };

    let (mut sum0, mut sum10, mut sum19) = vecs
        .par_chunks(2048)
        .map(|chunk| unsafe {
            let splat32 = _mm256_set1_epi8(32);
            let splat123 = _mm256_set1_epi8(123);
            let splat229 = _mm256_set1_epi8(-27);
            let splat0 = _mm256_set1_epi8(0);
            let splat10 = _mm256_set1_epi8(10);
            let splat19 = _mm256_set1_epi8(19);

            let mut sum0 = splat0;
            let mut sum10 = splat0;
            let mut sum19 = splat0;

            for &vec in chunk {
                let x = _mm256_subs_epu8(
                    _mm256_sub_epi8(_mm256_or_si256(vec, splat32), splat123),
                    splat229,
                );
                sum0 = _mm256_add_epi64(sum0, _mm256_sad_epu8(x, splat0));
                sum10 = _mm256_add_epi64(sum10, _mm256_sad_epu8(x, splat10));
                sum19 = _mm256_add_epi64(sum19, _mm256_sad_epu8(x, splat19));
            }

            (
                (_mm256_extract_epi64(sum0, 0)
                    + _mm256_extract_epi64(sum0, 1)
                    + _mm256_extract_epi64(sum0, 2)
                    + _mm256_extract_epi64(sum0, 3)) as u64,
                (_mm256_extract_epi64(sum10, 0)
                    + _mm256_extract_epi64(sum10, 1)
                    + _mm256_extract_epi64(sum10, 2)
                    + _mm256_extract_epi64(sum10, 3)) as u64,
                (_mm256_extract_epi64(sum19, 0)
                    + _mm256_extract_epi64(sum19, 1)
                    + _mm256_extract_epi64(sum19, 2)
                    + _mm256_extract_epi64(sum19, 3)) as u64,
            )
        })
        .reduce(
            || (0, 0, 0),
            |(a0, a10, a19), (b0, b10, b19)| (a0 + b0, a10 + b10, a19 + b19),
        );

    for affix in [prefix, suffix] {
        for &byte in affix {
            let x = (byte | 32).wrapping_sub(123).saturating_sub(229);
            sum0 += x as u64;
            sum10 += x.abs_diff(10) as u64;
            sum19 += x.abs_diff(19) as u64;
        }
    }

    (101 * sum0 + 9 * sum10) / 2 + 45 * sum19 - 900 * bytes.len() as u64
}

fn main() -> io::Result<()> {
    let [_, filename]: [String; 2] = Vec::from_iter(args()).try_into().expect("missing filename");
    let file = File::open(filename)?;
    let mmap = unsafe { MmapOptions::new().map(&file)? };
    println!("{}", gematria(&mmap[..]));
    Ok(())
}
\$\endgroup\$
1
  • \$\begingroup\$ That's assembly not Rust :) \$\endgroup\$
    – user108721
    Commented Oct 9, 2022 at 15:06
4
\$\begingroup\$

C++ (clang), ~21 ms on my Linux machine

#include <array>
#include <chrono>
#include <fcntl.h>
#include <iostream>
#include <numeric>
#include <thread>
#include <vector>
#include <unistd.h>

constexpr std::array<unsigned long, 128> numbering {
    // ASCII NUL to @
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    // A to Z
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
    70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
    // [ \ ] ^ _ `
    0, 0, 0, 0, 0, 0,
    // a to z
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
    70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
    // all the rest up to 127
    0, 0, 0, 0, 0
};

struct accumulate_block
{
    void operator()(const char* first, const char* last, std::vector<unsigned long>::reference result) {
        result = 0;
        for (const char* str = first; str < last; ++str)
            result += numbering[*str];
    }
};

int main() {
    const auto start = std::chrono::high_resolution_clock::now();
    
    auto fd = open("random-20221005.txt", O_RDONLY);
    posix_fadvise(fd, 0, 0, 1);

    constexpr std::size_t buffer_size = 4 * 1024 * 1024;
    constexpr unsigned long num_threads = 8;
    constexpr unsigned long min_per_thread = buffer_size / num_threads;
    std::vector<unsigned long> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1);
    char buffer[buffer_size];

    unsigned long count = 0;
    while (const std::size_t bytes_read = read(fd, buffer, buffer_size)) {
        const char* block_start = buffer;
        unsigned long const block_size = bytes_read / num_threads;
        for(unsigned long i = 0; i < num_threads - 1; ++i) {
            const char* block_end = block_start + block_size;
            threads[i] = std::thread(accumulate_block(), block_start, block_end, std::ref(results[i]));
            block_start = block_end;
        }
        accumulate_block()(block_start, buffer + bytes_read, results[num_threads - 1]);
        for(auto& entry: threads) {
            entry.join();
        }
        count = std::accumulate(results.begin() , results.end(), count);
    }

    const auto finish = std::chrono::high_resolution_clock::now();

    constexpr unsigned long expected = 9140634224L;
    const char* checker[] = {"\xE2\x9C\x95", "\xE2\x9C\x93"};
    std::cout << "count = " << count << " " << checker[count == expected] << "\n";

    const auto ms_interval = std::chrono::duration_cast<std::chrono::milliseconds>(finish - start);
    const std::chrono::duration<double, std::milli> ms_double = finish - start;
    std::cout << ms_interval.count() << " ms\n";
    std::cout << ms_double.count() << " ms\n";

    return 0;
}

Outputs:

count = 9140634224 ✓
21 ms
21.8556 ms   

Compiled with clang++ \$14.0.0\$ using -O3 -march=native -std=gnu++20

\$\endgroup\$
9
  • \$\begingroup\$ On Windows it runs for about 120ms of which reading the file takes about 80ms. You can still save a couple of ms by parallelizing the for loop. Something like this TIO \$\endgroup\$
    – jdt
    Commented Oct 6, 2022 at 20:21
  • \$\begingroup\$ @jdt I was running this on WSL! Move it to my Linux machine and the time drops dramatically! \$\endgroup\$
    – Noodle9
    Commented Oct 6, 2022 at 22:03
  • \$\begingroup\$ The original submission bakes the input file into the source code, you could maybe save performance by doing the same? \$\endgroup\$
    – mousetail
    Commented Oct 7, 2022 at 8:28
  • 1
    \$\begingroup\$ @mousetail Yes I tried that and it performed badly, then I tried several ways of reading the file optimally and end up here. Basically reading the data is the main bottle-neck. \$\endgroup\$
    – Noodle9
    Commented Oct 7, 2022 at 8:57
  • 1
    \$\begingroup\$ I'm getting much faster results with openmp. Can you see what happens if you compile this with the following options: clang++ -O3 -march=native -std=gnu++20 -fopenmp -pthreads \$\endgroup\$
    – jdt
    Commented Oct 9, 2022 at 19:19
0
\$\begingroup\$

C# (.NET Core 6), ~60 ms on my Windows machine

var sw = new System.Diagnostics.Stopwatch();
sw.Start();
var data = File.ReadAllBytes("random-20221005.txt");
sw.Stop();
var readTime = sw.ElapsedMilliseconds;

sw.Restart();
var list = new List<long>();
long taskCount = 16;
long taskSize = data.Length / taskCount;
for (long i = 0; i < taskCount; i++)
    list.Add(i * taskSize);

long grandTotal = 0;
Parallel.ForEach(list, start =>
{
    var lookup = new long[] {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
        0, 0, 0, 0, 0, 0,
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
        0, 0, 0, 0, 0
    };
    long total = 0;
    long end = start + taskSize;
    for (long i = start; i < end; i++)
        total += lookup[data[i]];
    grandTotal += total;
});

sw.Stop();
var calcTime = sw.ElapsedMilliseconds;

Console.WriteLine($"read time: {readTime} ms");
Console.WriteLine($"calc time: {calcTime} ms");
Console.WriteLine($"total time: {readTime + calcTime} ms");
Console.WriteLine($"result: {grandTotal}");

Output:

read time: 48 ms
calc time: 12 ms
total time: 60 ms
result: 9140634224

Ouput without parallelization:

read time: 48 ms
calc time: 64 ms
total time: 112 ms
result: 9140634224
\$\endgroup\$
0
\$\begingroup\$

Julia 1.0, 140 bytes

!x=sum(getindex.((Dict(Char.([1:255...]).=>[zeros(Int,64)...,1:9...,10:10:90...,100:100:800...,zeros(Int,165)...]),),collect(uppercase(x))))

Try it online!

\$\endgroup\$
2
  • 7
    \$\begingroup\$ Please keep in mind that this is a fastest-code challenge, and should be scored accordingly; time, not bytes. \$\endgroup\$
    – Baby_Boy
    Commented Oct 6, 2022 at 17:48
  • 2
    \$\begingroup\$ For the record, this takes 2609 ms on my machine. \$\endgroup\$
    – naffetS
    Commented Oct 7, 2022 at 21:22
0
\$\begingroup\$

Python (multithreaded + numpy + numba) <30ms total

windows i7-8750H windows laptop, imdisk ramdisk

import numpy as np
from numba import jit
import os
from concurrent.futures import ThreadPoolExecutor

@jit(nogil=True, fastmath=True)
def counter(full_dict, bytearr):
    total = 0
    for i in bytearr:
        total += full_dict[i]
    return total
_ = counter(np.zeros((128,), dtype=np.int32), b'abc') #to compile

def final_fast_gematria(filename, chunksize=600000, max_threads=4):
    maindict = {65: 1, 66: 2, 67: 3, 68: 4, 69: 5, 70: 6, 71: 7, 72: 8, 73: 9, 74: 10, \
                75: 20, 76: 30, 77: 40, 78: 50, 79: 60, 80: 70, 81: 80, 82: 90, 83: 100, \
                84: 200, 85: 300, 86: 400, 87: 500, 88: 600, 89: 700, 90: 800}
    full_dict = {**{i:0 for i in range(128)}, **maindict, **{key+32:val for key,val in maindict.items()}}
    full_dict = np.array(tuple(full_dict.values()), dtype=np.int32)    
    threads = []
    with ThreadPoolExecutor(max_workers=max_threads) as executor:
        with open(filename, 'rb', 0) as f:
            filesize = os.fstat(f.fileno()).st_size
            for _ in range(filesize//chunksize - 1):
                threads.append(executor.submit(counter, full_dict, f.read(chunksize)))
            return counter(full_dict, f.read()) + sum(thread.result() for thread in threads)

print(final_fast_gematria("E:/random-20221005.txt"))

9140634224

%%timeit -n 2 -r 10
final_fast_gematria("E:/random-20221005.txt")

27.9 ms ± 1.11 ms per loop (mean ± std. dev. of 10 runs, 2 loops each)

Read time

def only_read(filename, chunksize=600000):
with open(filename, 'rb', chunksize) as f:
    filesize = os.fstat(f.fileno()).st_size
    for _ in range(1 + filesize//chunksize):
        f.read(600000)

%%timeit -n 1 -r 10
only_read("E:/random-20221005.txt")

22.6 ms ± 985 µs per loop (mean ± std. dev. of 10 runs, 1 loop each)

notebook with other variants link

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.