ovidiuch / illustrated-algorithms Goto Github PK

Can provide the code for karatsuba multiplication (<=20 lines).

What's up?

Current quicksort implementation will not sort list with duplicate values:

quicksort([3,3,2,1,4]) // returns [1,2,3,4]

this along with the hidden random function may result in some confusion if someone were to try and implement the code with reference to the site.

Mkay, tell me more...

This can be alleviated with the following implementation:

function randomIndex(list) {
  return Math.round(Math.random() * (list.length - 1)); // changes here
}

export default function quicksort(list) {
  if (list.length < 2) {
    return list;
  }
  const pivot = list.splice(randomIndex(list), 1); // here
  const less = list.filter(i => i <= pivot); // here (<= rather than <)
  const greater = list.filter(i => i > pivot);

  return [
    ...quicksort(less),
    ...pivot, // and here
    ...quicksort(greater)
  ];
}

Which would result in:
quicksort([3,3,2,1,4]) // returns [1,2,3,3,4]

Although I could see the current implementation being favored for a slight increase in brevity, I thought this was worth bringing up :)

(As an aside I initially wanted to make a PR... I attempted to (naively) drop the above code into algorithms/quicksort.js but this resulted in the pivot not displaying correctly :( )

What's up?

Transitions in the Quicksort visualization (not released yet) are skipping frames and none of my experiments brought any significant perf improvement.

The Binary Search viz is also barely staying smooth on slow devices, but only when entries are added & removed from the call stack in the new viz does performance visibly drop (at least on my devices).

This is when I get worse perf (large elements get translated, while opacity is also applied)

Mkay, tell me more...

Full disclosure: I'm a newbie when it comes to performance so feel free to point out any obvious flaw in my analysis.

There are two main reasons why animation in this project is so expensive:

1. Transitions are custom built (no CSS transition) and CSS attributes like transform and opacity are set manually on every frame*
2. The frame index is stored in React state, which also means 60 React tree updates per second.

* The UI is currently rendering 60fps, but this number doesn't say much as setting it to, say 30, doesn't have any real impact (frame skipping still occurs, and it didn't really have a 60fps feel before anyway).

At first I suspected React reconciliation is behind the hiccups, and the Chrome DevTools Timeline seemed to back it up.

(I've had cases where Scripting took a much larger share in comparison to Rendering and Painting)

This led me to create an experiment where I would render via React once, store refs for all interesting nodes and then imperatively change the styles on those nodes on frame (rAF). My timeline looked much better, but after a short burst of enthusiasm I noticed the same frame skipping occur. I returned to rendering each frame thru React because that code was a mess.

I think comparing these times on a large time interval isn't representative, so here's a zoom in on a single frame (a nasty one):

OK, React is taking 4.55ms, but I'm really abusing it here so it's more than decent imo. But after you add 5.15ms to Recalculate Styles, 6.22ms to Update Layer Tree, 2.93ms to Paint and a few other small bits, you get a long ass 20ms frame which in fact feels much longer.

Btw, can anyone tell me why the firing of Animation Frame doesn't coincide with the dotted line between frames?

Some other thoughts:

• Could it be that updating DOM styles so aggressively is simply not feasible and the level of smooth I'm aiming for can only be achieved using CSS transitions or rendering something on a canvas?
• Maybe I'm getting penalized for setting (or combining) styles in a certain way? Or something related to how I'm scheduling frames?

Feel free to suggest any alternatives, I'll take any help I can get with this!

What's up?

From HN thread:

I realize the featured example is not the most optimal Quicksort implementation. I doesn't even handle duplicates. Indeed this variant was chosen primarely because of its aesthetics.

While I'd like to keep the mission of this project to "illustrating the basic mechanics of algorithms as elegantly as possible", I realize this can be a) annoying for people who understand the specifics in depth, and b) not enough (or confusing) for people just picking this up. Which is why I'm thinking of creating an info page for each algorithm to:

• Outline the limitations of the featured version
• List a number of possible improvements (e.g. pivot strategies)
• Link to external resources for complete examples & docs

Mkay, tell me more...

A few actions to take

• Improve docs on project mission, constraints and biases (e.g. brevity vs optimal solution) to avoid creating wrong expectations
• Create layout for info page

You can use now alias illustrated-algorithms-xxxxzzz.now.sh illustrated-algorithms.now.sh in order to provide a simpler and canonical URL. Note that would need to do that for each time you now deploy, or you can add it to your now configuration (not really sure though).

What's up?

Reported by @scshepard

Mkay, tell me more...

I managed to do a quick IE debugging session on BrowserStack (Edge was not available on trial, but the error was reproduced) and found that adding position: relative to some divs fixed the problem.

On top of this, the entire build was broken in IE due to the fact that the version I tested in had no support for Promises. I'll include babel-polyfill in the build to fix this.

Firstly, awesome project.

I remember reading that it's common in many implementations of binary search to calculate the midpoint as such

mid = (low + high) / 2

which is how it's calculated here.

The has a subtle issue (as discussed here) in that it can lead to overflow if low and high are sufficiently large enough. One way to avoid this is to calculate the midpoint as such

mid = low + ((high - low) / 2)

This is obviously not an issue in the illustration which is searching through a list of 6 animals, however it might be worth updating the implementation for general correctness. Thoughts?

In page.js get the viewport size via document.body.clientWidth instead of window.width to account for scrollbars taking up visual space.