4 ms·

This stuff is fun to play with. I implemented a Rust version of fractional indexing based on another of Evan’s blog posts. https://docs.rs/fractional_index/lat

• dang 4y ago
  Ok, let's try changing the URL from https://madebyevan.com/algos/ https://madebyevan.com/algos/ (a generic list) to https://docs.rs/fractional_index/latest/fractional_index/ https://docs.rs/fractional_index/latest/fractional_index/ (the item you're taking about). Explanation here: https://news.ycombinator.com/item?id=33764956 https://news.ycombinator.com/item?id=33764956. Thanks!
• chrisoverzero 4y ago
  Does a Vec<u8> with that calculation listed end up smaller than two integers of (presumably) arbitrary length? When I read about the problem, I imagined using the mediant to calculate “between”. I think that mediant of $value and 1/1 would work for “after” and mediant of $value and 0/1 would work for “before”. There must be a requirement I’m missing, though! mediant: https://en.wikipedia.org/wiki/Mediant_(mathematics) https://en.wikipedia.org/wiki/Mediant_(mathematics)
  • paulgb 4y ago
    That would be an interesting thing to test! My first instinct is that the comparison operation (when denominators differ) would be more expensive. In general some approaches should be better than others depending on how inserts are distributed — I think my approach is optimal when inserts are made at random (I haven’t proved this), but in practice it may be common for a bunch of things to be inserted in sequence for some applications. In those cases, there are more space-optimal approaches.