4 ms·

I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anythi

by samwho 1y ago

I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible.

eru 1y ago
I have a few more topics we could cooperate on, if you are interested. https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d3a47e3a9c8d https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d... has a 'very static' visualisation of sorting algorithms. Basically, we have a 2d plane, and we colour a pixel (x, y) black iff the sorting algorithm compares x with y when it runs. It's a resurrection (with AI) of an older project I was coding up manually at https://github.com/matthiasgoergens/static-sorting-visualisation/blob/master/images/quick_random_xy_1500.png https://github.com/matthiasgoergens/static-sorting-visualisa... I'm also working on making https://cs.stackexchange.com/q/56643/50292 https://cs.stackexchange.com/q/56643/50292 with its answer https://cs.stackexchange.com/a/171695/50292 https://cs.stackexchange.com/a/171695/50292 more accessible. It's a little algorithmic problem I've been working on: 'simulate' a heap in O(n) time. I'm also developing a new, really simple implementation of soft heaps. And on my write-up for the solution to https://github.com/matthiasgoergens/TwoTimePad/blob/master/description.txt https://github.com/matthiasgoergens/TwoTimePad/blob/master/d... > I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible. If memory serves right, they don't do much about how you can efficiently support changes to your discrete probability distribution.
- samwho 1y ago
  I appreciate the offer (and your contributions in the comments here!) but collaborations are very difficult for me atm. Most of the work I do on these posts I do when I can steal time away from other aspects of my life, which can sometimes take weeks. I wouldn’t be a dependable collaboration partner.
  - eru 1y ago
    No worries. I'd mostly just appreciate a beta tester / beta reader.
    - samwho 1y ago
      Totally happy to do that! You’ll find where to contact me on my homepage. :)
- smusamashah 1y ago
  I made a tool to visualize sorting algos https://xosh.org/VisualizingSorts/sorting.html https://xosh.org/VisualizingSorts/sorting.html where you can put your own algo too if you like.
  - ncruces 1y ago
    I love the idea behind that sorting visualization, and found it extremely useful to validate the properties of my Quicksort implementation. https://github.com/ncruces/sort https://github.com/ncruces/sort
  - eru 1y ago
    That's interesting. Alas, it only works for in-place sorting algorithms (and it's also an animation).
tmoertel 1y ago
A while ago I tried to create a more self-explanatory implementation: https://github.com/tmoertel/practice/blob/master/libraries%2Fdiscrete_random_variables.py https://github.com/tmoertel/practice/blob/master/libraries%2... It is limited to integer weights only to make it easy to verify that the algorithm implements the requested distribution exactly. (See the test file in the same directory.)
- eru 1y ago
  You could probably restrict to rational numbers, and still verify? Languages like Python, Haskell, Rust etc have good support for arbitrary length rational numbers. Each floating point number is also a rational number, and thus you could then restrict again to floating point afterwards.

by samwho 1y ago

eru 1y ago

I have a few more topics we could cooperate on, if you are interested. https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d3a47e3a9c8d https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d... has a 'very static' visualisation of sorting algorithms. Basically, we have a 2d plane, and we colour a pixel (x, y) black iff the sorting algorithm compares x with y when it runs. It's a resurrection (with AI) of an older project I was coding up manually at https://github.com/matthiasgoergens/static-sorting-visualisation/blob/master/images/quick_random_xy_1500.png https://github.com/matthiasgoergens/static-sorting-visualisa... I'm also working on making https://cs.stackexchange.com/q/56643/50292 https://cs.stackexchange.com/q/56643/50292 with its answer https://cs.stackexchange.com/a/171695/50292 https://cs.stackexchange.com/a/171695/50292 more accessible. It's a little algorithmic problem I've been working on: 'simulate' a heap in O(n) time. I'm also developing a new, really simple implementation of soft heaps. And on my write-up for the solution to https://github.com/matthiasgoergens/TwoTimePad/blob/master/description.txt https://github.com/matthiasgoergens/TwoTimePad/blob/master/d... > I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible. If memory serves right, they don't do much about how you can efficiently support changes to your discrete probability distribution.

samwho 1y ago
I appreciate the offer (and your contributions in the comments here!) but collaborations are very difficult for me atm. Most of the work I do on these posts I do when I can steal time away from other aspects of my life, which can sometimes take weeks. I wouldn’t be a dependable collaboration partner.
- eru 1y ago
  No worries. I'd mostly just appreciate a beta tester / beta reader.
  - samwho 1y ago
    Totally happy to do that! You’ll find where to contact me on my homepage. :)
smusamashah 1y ago
I made a tool to visualize sorting algos https://xosh.org/VisualizingSorts/sorting.html https://xosh.org/VisualizingSorts/sorting.html where you can put your own algo too if you like.
- ncruces 1y ago
  I love the idea behind that sorting visualization, and found it extremely useful to validate the properties of my Quicksort implementation. https://github.com/ncruces/sort https://github.com/ncruces/sort
- eru 1y ago
  That's interesting. Alas, it only works for in-place sorting algorithms (and it's also an animation).

tmoertel 1y ago

A while ago I tried to create a more self-explanatory implementation: https://github.com/tmoertel/practice/blob/master/libraries%2Fdiscrete_random_variables.py https://github.com/tmoertel/practice/blob/master/libraries%2... It is limited to integer weights only to make it easy to verify that the algorithm implements the requested distribution exactly. (See the test file in the same directory.)

eru 1y ago
You could probably restrict to rational numbers, and still verify? Languages like Python, Haskell, Rust etc have good support for arbitrary length rational numbers. Each floating point number is also a rational number, and thus you could then restrict again to floating point afterwards.