←back to thread

A Raycaster in Bash

(github.com)
235 points izabera | 2 comments | 20 Dec 24 22:25 UTC | HN request time: 0.001s | source
Show context
anfractuosity ◴[21 Dec 24 12:39 UTC] No.42479336[source]▶
Very cool! I'm curious when it says "did you know that accessing a random element in an array takes linear time", why that's the case, with bash?
replies(1): >>42479861 #
1. izabera ◴[21 Dec 24 14:24 UTC] No.42479861[source]▶
normal arrays in bash are implemented as linked lists. bash stores a pointer to the last accessed element, which turns the most common case of iteration into O(1), but the performance is terrible if you need to jump around

see some basic benchmarks here https://gist.github.com/izabera/16a46ed79c2248349a1fb8384468...

there are also associative arrays which are bucketed hash tables, which are fine for string keys but imho they are hardly ever worth it as a replacement for indexed arrays

replies(1): >>42481036 #
2. anfractuosity ◴[21 Dec 24 17:47 UTC] No.42481036[source]▶
Thanks a lot, that's very interesting re. it using linked lists, and nice benchmark!