📌 Marque-pages Pinboard

A visual introduction to big O notation.

There are a whole bunch of popular interview questions that can be solved in one of two ways: Either using common data structures and algorithms in a sensible manner, or by using some properties of...

Explore and understand consistent hashing with our interactive visualizer. Perfect for developers, students, and distributed systems enthusiasts. Simulate node addition, removal, and key distribution in real-time.

Loro - Reimagine state management with CRDTs | Built for local-first software.

The fastest pure-Python PEG parser I can muster. Contribute to erikrose/parsimonious development by creating an account on GitHub.

Table of Contents 1 Introduction 1.1 Problem statement 1.2 Recommended reading 1.3 Binary search and Eytzinger layout 1.4 Hugepages 1.5 A note on benchmarking 1.6 Cache lines 1.7 S-trees and B-trees 2 Optimizing find 2.1 Linear 2.2 Auto-vectorization 2.3 Trailing zeros 2.4 Popcount 2.5 Manual SIMD 3 Optimizing the search 3.1 Batching 3.2 Prefetching 3.3 Pointer arithmetic 3.3.1 Up-front splat 3.3.2 Byte-based pointers 3.3.3 The final version 3.4 Skip prefetch 3.5 Interleave 4 Optimizing the tree layout 4.1 Left-tree 4.2 Memory layouts 4.3 Node size \(B=15\) 4.3.1 Data structure size 4.4 Summary 5 Prefix partitioning 5.1 Full layout 5.2 Compact subtrees 5.3 The best of both: compact first level 5.4 Overlapping trees 5.5 Human data 5.6 Prefix map 5.7 Summary 6 Multi-threaded comparison 7 Conclusion 7.1 Future work 7.1.1 Branchy search 7.1.2 Interpolation search 7.1.3 Packing data smaller 7.1.4 Returning indices in original data 7.1.5 Range queries 7.1.6 Sorting queries 7.1.7 Suffix array searching In this post, we will implement a static search tree (S+ tree) for high-throughput searching of sorted data, as introduced on Algorithmica. We’ll mostly take the code presented there as a starting point, and optimize it to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post and implementing them. And then there will be a bunch of looking at assembly code to shave off all the instructions we can. Lastly, there will be one big addition to optimize throughput: batching.

A small, portable, linear probing hash map. Contribute to e-dant/salmagundi development by creating an account on GitHub.

B-trees are used by many modern DBMSs. Learn how they work, how databases use them, and how your choice of primary key can affect index performance.

Vector Search is hot! Everyone is pouring resources into a seemingly new and AI-related topic. But are there any non-AI-related use cases? Are there features you want from your vector search engine, but are too afraid to ask? Last week was 🔥 for vector search. Weaviate raised $50M, and Pinecone raised $100M... That's a lot and makes you believe that vector search is hard. But it's not. I have spent the last few days implementing a single-file vector search engine.

TL;DR The code from the tutorial is available at matmul.c. This blog post is the result of my attempt to implement high-performance matrix multiplication on CPU while keeping the code simple, portable and scalable. The implementation follows the BLIS design, works for arbitrary matrix sizes, and, when fine-tuned for an AMD Ryzen 7700 (8 cores), outperforms NumPy (=OpenBLAS), achieving over 1 TFLOPS of peak performance across a wide range of matrix sizes.

Parsing gigabytes of JSON per second : used by Facebook/Meta Velox, the Node.js runtime, ClickHouse, WatermelonDB, Apache Doris, Milvus, StarRocks - simdjson/simdjson

I'm sick of complex blogging solutions, so markdown files in a git repo it is - githublog/2024/5/29/fast-inverse-sqrt.md at main · francisrstokes/githublog

Aggregated Highest Random Weight Hashing / Aggregated Rendezvous Hashing - SenseUnit/ahrw

Ryan Marcus, assistant professor at the University of Pennsylvania (Fall '23). Using machine learning to build the next generation of data systems.

Bitcoin Improvement Proposals. Contribute to bitcoin/bips development by creating an account on GitHub.

Problem: Getting insights from sensitive data while keeping individual privacy is tricky. Solution: Differential privacy is a mathematical concept that allows for the analysis of sensitive datasets while protecting the privacy of individuals.

Write fast, flexible pipelines that use modern techniques to aggregate user data in a privacy-preserving manner.

We are engaging a community of collaborators in academia, industry, and government to build trustworthy, open-source software tools for statistical analysis of sensitive private data

A DOM-merging algorithm. Contribute to bigskysoftware/idiomorph development by creating an account on GitHub.

CRDTs don't have to be all academic papers and math jargon. Learn what CRDTs are and how they work through interactive visualizations and code samples.

BLAS-like Library Instantiation Software Framework - flame/blis: BLAS-like Library Instantiation Software Framework

In this document, I describe what is, in my humble but correct opinion, the best known algorithm for threading messages (that is, grouping messages together in parent/child relationships based on which messages are replies to which others.) This is the threading algorithm that was used in Netscape Mail and News 2.0 and 3.0, and in Grendel.

A DOM-merging algorithm. Contribute to bigskysoftware/idiomorph development by creating an account on GitHub.

A comprehensive collection of hash functions, a hash visualiser and some test results [see Mckenzie et al. Selecting a Hashing Algorithm, SP&E 20(2):209-224, Feb 1990] will be available someday. If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes. you are not likely to do better with one of the "well known" functions such as PJW, K&R[1], etc. Also see tpop pp. 126 for graphing hash functions.

Les guides d'Etalab : vous accompagner dans la réalisation de vos projets relatifs aux données, algorithmes et codes sources.

An online AST explorer.

miguelgrinberg.com

How do you convert a UTC timestamp to UnixTime (seconds since theepoch)?

La plate-forme qui gère l’affectation des futurs étudiants reste en partie insaisissable pour lycéens, parents et professeurs. Avant la publication des résultats, le 1er juin, « Le Monde » a suivi les travaux d’examinateurs pour tenter de faire la lumière sur les modes de sélection.

There are a whole bunch of popular interview questions that can be solved in one of two ways: Either using common data structures and algorithms in a sensible manner, or by using some properties of...

The goals for the course are to gain a facility with using the Fourier transform, both specific techniques and general principles, and learning to recognize when, why, and how it is used. Together with a great variety, the subject also has a great coherence, and the hope is students come to appreciate both. <br><br> Topics include: The Fourier transform as a tool for solving physical problems. Fourier series, the Fourier transform of continuous and discrete signals and its properties. The Dirac delta, distributions, and generalized transforms. Convolutions and correlations and applications; probability distributions, sampling theory, filters, and analysis of linear systems. The discrete Fourier transform and the FFT algorithm. Multidimensional Fourier transform and use in imaging. Further applications to optics, crystallography. Emphasis is on relating the theoretical principles to solving practical engineering and science problems.

The drawing app to express, grasp, and organize your thoughts and ideas

Open Source resource for learning Data Structures & Algorithms and their implementation in any Programming Language

Let's open a hex editor and see what this thing is made of

Benchmarks of approximate nearest neighbor libraries in Python - erikbern/ann-benchmarks: Benchmarks of approximate nearest neighbor libraries in Python

Minisketch: an optimized library for BCH-based set reconciliation - sipa/minisketch: Minisketch: an optimized library for BCH-based set reconciliation

Roaring Bitmap

Bumped Ribbon Retrieval and Approximate Membership Query - lorenzhs/BuRR: Bumped Ribbon Retrieval and Approximate Membership Query

A better compressed bitset in Java. Contribute to RoaringBitmap/RoaringBitmap development by creating an account on GitHub.

Sorting algorithms visualized using the Blender Python API. - ForeignGods/Sorting-Algorithms-Blender: Sorting algorithms visualized using the Blender Python API.

Parcoursup est la plateforme nationale de préinscription en première année de l’enseignement supérieur en France. Ce document présente une partie des travaux de sûreté logicielle autour d’un des algorithmes de cette plateforme, appelé calcul des ordres d’appel: spécification de l’algorithme, vérification à l’exécution de la spécification, et preuve formelle de correction de l’algorithme. Ces travaux été réalisés à l’aide des outils de preuve Why3 et COQ et de techniques de vérification à l’exécution du code Java et permettent d’atteindre un très haut niveau de confiance dans l’algorithme de calcul des ordre d’appel de Parcoursup.