Hacker News with Generative AI: Data Structures

Relaxed Radix Balanced Trees (2024) (horne-khan.com)
I’m adding immutable vectors to my language, Ivan, and needed to pick a suitable data structure to implement them.
Data Structures, Programming Languages, Computer Science
173 points by jasonjmcghee 1 day ago | 15 comments
TOML [Tom's Obvious Minimal Language] (toml.io)
TOML aims to be a minimal configuration file format that's easy to read due to obvious semantics. TOML is designed to map unambiguously to a hash table. TOML should be easy to parse into data structures in a wide variety of languages.
Configuration Files, Programming Languages, Data Structures
10 points by wanderer2323 2 days ago | 11 comments
This New Algorithm for Sorting Books or Files Is Close to Perfection (wired.com)
Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf.
Algorithms, Computer Science, Organization, Data Structures
10 points by f_allwein 2 days ago | 6 comments
What's in a ring buffer? And using them in Rust (ntietz.com)
Working on my cursed MIDI project, I needed a way to store the most recent messages without risking an unbounded amount of memory usage.
Programming, Rust, Data Structures
18 points by todsacerdoti 3 days ago | 12 comments
JesseSort: A novel sorting algorithm that is faster than Python's default sort. (github.com/lewj85)
JesseSort is a novel sorting algorithm that introduces a new data structure called a Rainbow to efficiently organize and merge elements. It achieves a runtime of O(n log n).
Algorithms, Software, Programming, Data Structures
97 points by amichail 7 days ago | 60 comments
Tiny Pointers (arxiv.org)
This paper introduces a new data-structural object that we call the tiny pointer.
Computer Science, Data Structures, Research Papers
163 points by levzettelin 8 days ago | 35 comments
Go's new map implementation in 1.24 is powered by Swiss Tables (twitter.com)
Go, Programming Languages, Data Structures, Performance
60 points by tosh 9 days ago | 4 comments
Solving the ABA Problem in Rust with Tagged Pointers (minikin.me)
Concurrent programming is challenging, especially when designing lock-free data structures. One subtle issue that can arise is the ABA problem, leading to unexpected behavior in compare-and-swap (CAS) operations. In this post, we’ll explore the ABA problem and how to solve it in Rust using idiomatic and efficient techniques.
Rust, Concurrent Programming, Data Structures, Programming
41 points by todsacerdoti 9 days ago | 49 comments
Generating Voronoi diagrams using Fortune's algorithm (redpenguin101.github.io)
Generating Voronoi Diagrams using Fortune’s Algorithm
Algorithms, Computer Graphics, Geometry, Data Structures
204 points by redpenguin101 12 days ago | 19 comments
Implementation of a RingBuffer in Java with optional FIFO like semantics (github.com/evolvedbinary)
Some extra Collection classes targetting Java 8.
Java, Data Structures, Programming, Software, GitHub
23 points by todsacerdoti 15 days ago | 14 comments
Elastic Binary Trees (2011) (blogspot.com)
In computer science, an elastic binary tree (or EB tree or EBtree) is a binary search tree specially optimized to very frequently store, retrieve and delete discrete integer or binary data without having to deal with memory allocation.
Data Structures, Algorithms, Computer Science
30 points by tosh 15 days ago | 10 comments
Go Data Structures (2009) (swtch.com)
When explaining Go to new programmers, I've found that it often helps to explain what Go values look like in memory, to build the right intuition about which operations are expensive and which are not. This post is about basic types, structs, arrays, and slices.
Go, Programming Languages, Data Structures, Memory Management
146 points by rednafi 15 days ago | 77 comments
Search logs faster than Sonic – Log search engine internals (vegasecurity.com)
Have you ever wondered how Elasticsearch works? How is it so fast? What makes it different from other databases like PostgreSQL? What cool data structures are at play?
Search Engines, Databases, Performance, Data Structures
17 points by tontinton 16 days ago | 5 comments
Show HN: Multi-/BiKeyMap (Go Module) (github.com/aeimer)
A go lib which handles maps with multiple keys.
Go, Programming, Data Structures, Libraries
14 points by baquero 17 days ago | 0 comments
Hierarchical CSV (github.com/Ericson2314)
Suppose I have a simple database of IDs and names. I can do this in JSON5 with:
Data Structures, Programming, Databases, Software
8 points by Ericson2314 20 days ago | 0 comments
Show HN: Ldump – serialize any Lua data (github.com/girvel)
ldump is a flexible serializer, able to serialize any data, starting with circular references, tables as keys, functions with upvalues, metatables and ending with coroutines, threads and userdata (by defining how they should be serialized). It outputs valid Lua code that recreates the original object, doing the deserialization through load(data)(). It aims for functionality and flexibility instead of speed and size, allowing full serialization of complex data, such as video game saves.
Lua, Programming, Serialization, Data Structures, Game Development
96 points by girvel 20 days ago | 41 comments
[x<<1 + 2, x<<1 + 3] is a Binary Tree (ivanbelenky.com)
From the post $$x + 1 \ \text{is a list}$$ I bring to you the binary tree.
Binary Trees, Programming, Data Structures
11 points by ivanbelenky 23 days ago | 0 comments
You could have invented Fenwick trees (cambridge.org)
Fenwick trees, also known as binary indexed trees are a clever solution to the problem of maintaining a sequence of values while allowing both updates and range queries in sublinear time.
Data Structures, Algorithms, Computer Science
131 points by matt_d 27 days ago | 29 comments
Examples of quick hash tables and dynamic arrays in C (nullprogram.com)
This article durably captures my reddit comment showing techniques for std::unordered_map and std::vector equivalents in C programs. The core, important features of these data structures require only a dozen or so lines of code apiece. They compile quickly, and tend to run faster in debug builds than release builds of their C++ equivalents. What they lack in genericity they compensate in simplicity. Nothing here will be new. Everything has been covered in greater detail previously, which I will reference when appropriate.
Data Structures, C Programming, Performance, Optimization
26 points by signa11 30 days ago | 10 comments
Examples of quick hash tables and dynamic arrays in C (nullprogram.com)
This article durably captures my reddit comment showing techniques for std::unordered_map and std::vector equivalents in C programs. The core, important features of these data structures require only a dozen or so lines of code apiece. They compile quickly, and tend to run faster in debug builds than release builds of their C++ equivalents. What they lack in genericity they compensate in simplicity. Nothing here will be new. Everything has been covered in greater detail previously, which I will reference when appropriate.
C Programming, Data Structures, Performance, Optimization
29 points by grep_it 32 days ago | 9 comments
Ropey – A UTF8 text rope for manipulating and editing large text (github.com/cessen)
Ropey is a utf8 text rope for Rust, designed to be the backing text-buffer for applications such as text editors. Ropey is fast, robust, and can handle huge texts and memory-incoherent edits with ease.
Programming, Rust, Text Editing, Data Structures, Libraries
249 points by keepamovin 36 days ago | 108 comments
Data evolution with set-theoretic types (dashbit.co)
Recently I have been working on projects that integrate Elixir with native code in C and Rust. One of the Rust libraries defines the following struct (with fields removed for simplicity):
Programming Languages, Data Structures, Elixir, Rust
127 points by josevalim 37 days ago | 32 comments
Using black magic to make a fast circular buffer (2017) (calho.st)
Yesterday, I took a glance at the Wikipedia page for the circular buffer and was intrigued by an alleged optimization technique that I was not familiar with:
Data Structures, Programming, Optimization, Performance
77 points by fanf2 40 days ago | 29 comments
Flattening ASTs and other compiler data structures (2023) (cs.cornell.edu)
Arenas, a.k.a. regions, are everywhere in modern language implementations. One form of arenas is both super simple and surprisingly effective for compilers and compiler-like things. Maybe because of its simplicity, I haven’t seen the basic technique in many compiler courses—or anywhere else in a CS curriculum for that matter. This post is an introduction to the idea and its many virtues.
Compiler Optimization, Data Structures, Computer Science, Programming Languages
157 points by aw1621107 41 days ago | 49 comments
Today I learned that bash has hashmaps (2024) (xeiaso.net)
Hashmaps (associative arrays) are a great way to store a bag of key-value data. At work I was writing something that needed me to spawn a bunch of GPU instances, GPU availability is spread out by region and GPU type. I wanted to store a mapping of GPU kind to region name and for some reason I thought it would be a good idea to do it in bash.
Bash, Programming, Shell Scripting, Data Structures
177 points by stefankuehnel 43 days ago | 133 comments
Why is hash(-1) == hash(-2) in Python? (omairmajid.com)
While browsing Reddit the other day waiting for my code to compile, I ran across this question on r/Python:
Python, Programming, Hashing, Data Structures
103 points by alexmolas 44 days ago | 91 comments
Show HN: SPath is a Rust lib for query JSONPath over any semi-structured data (github.com/cratesland)
SPath: Query expressions for semi-structured data
Rust, JSON, Data Structures, Libraries, Query Languages
35 points by tison 45 days ago | 10 comments
Parallel-hashmap: drop-in replacement for unordered_map, unordered_set (github.com/greg7mdp)
This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map and std::set, with the following characteristics:
C++, Data Structures, Programming, Open Source, Libraries
62 points by klaussilveira 46 days ago | 19 comments
B-Trees: More Than I Thought I'd Want to Know (benjamincongdon.me)
Recently, I’ve been reading through the excellent Database Internals (Alex Petrov, 2019). The first half of the book is dedicated to the implementation of database storage engines – the subsystem(s) of a DBMS that handles long-term persistence of data. A surprising amount of this section discusses the implementation and optimization of various B-Tree data structures.
Databases, Data Structures, B-Trees
319 points by hochmartinez 48 days ago | 16 comments
Static search trees: faster than binary search (curiouscoding.nl)
In this post, we will implement a static search tree (S+ tree) for high-throughput searching of sorted data, as introduced on Algorithmica.
Data Structures, Algorithms, Performance Optimization
656 points by atombender 51 days ago | 232 comments