felipernb / algorithms.js Goto Github PK

I'm looking for a good way to find elements on a LinkedList (academic purpose), using a functional aproach.

The forEach iterate over all list applying a function, it's useful for some cases, discussed at #88.
When the scenario is only to search and return an element, the forEach can be used with a workaround:

var a;
list.forEach(function (e) {
        if (key === e) {
          a = e;
          return;
        };
    });

and it will perform over all elements. I want to stop at first match, something like

var a = list.find(function(e /*[, key [,comparator_func]]*/){...})  // return an element or null

The iterator pattern can be used, maybe just refactor some code...
What do you think about this?

• Levenshtein

var graph = graphFromEdges(false, [
[1, 2],
[1, 5]
]);

graph.edge("1","2")
1

graph.edge("1","constructor")
function Object() { [native code] }

hasOwnProperty can help here.

I've created a jsperf test to compare the performance of this library's implementation of quicksort agains the native Array.prototype.sort();

http://jsperf.com/algorithms-js-quicksort-vs-native-sort/4

Surprisingly, the quicksort in JS seems to be faster and I wonder if I'm doing something wrong, and maybe someone could help me verifying it.

Ping @eush77 @quietshu @joshuacurl 😁

For 1.0 it would be nice to have all algos and data structures documented properly on the wiki

We can do better, namely in O(log n).

I remember this one for my data structures class!
http://en.wikipedia.org/wiki/2–3–4_tree

Here's a simpler implementation of a Binary Heap; feel free to introduce a comparator into the constructor...

function PriorityQ(elems) {
// Implements a binary heap priority queue
    var q = [null];
    this.push = function (h) {
        var i, j;
        for (i = q.length; (j = (i / 2) | 0) && q[j] > h; q[i] = q[j], i = j);
        q[i] = h;
        return this;
    };
    this.pop = function () {
        var i, j, r, t;
        for (r = q[1]; q.length > 1 && r == q[1]; q[i] = t) {
            for (i = 1, t = q.pop(); (j = i * 2) < q.length;) {
                if (j < q.length && q[j] > q[j + 1]) j++;
                if (t <= q[j]) break;
                q[i] = q[i = j];
            }
        }
        return r;
    };
    if (Object.prototype.toString.call(elems) === '[object Array]')
        elems.forEach(this.push);
}

I got notifications for these, which are both 404 (page not found) when clicked.

https://github.com/felipernb/algorithms.js/releases/tag/0.1.0
https://github.com/felipernb/algorithms.js/releases/tag/0.2.0

I see
https://github.com/felipernb/algorithms.js/tree/v0.3.0
now but did not get a notification for it.

https://github.com/felipernb/algorithms.js/releases/tag/0.3.0
would also be 404.

• Quicksort
• Merge sort
• Bubble sort
• BST
• Heap

This will allow doing custom sorting like in descending order and also perform it with different types of objects.

I noticed that a lot of the data structures(BST, HashTable, Set, etc) don't have iterators defined. Were they intentionally left out? If not then I wouldn't mind going through and adding them.

see https://gist.github.com/Fil/8903368

A user should be able to load just some "module" of the library, like just the data_structures or just the sorting algorithms

See the hacker news discussion:
https://news.ycombinator.com/item?id=7821552

Also, why not do a least common multiple while you're doing these things?

Adding the library to Bower would make it easier to use on front end projects than npm.

Bower is a package manager for the web. It offers a generic, unopinionated solution to the problem of front-end package management, while exposing the package dependency model via an API that can be consumed by a more opinionated build stack.

http://bower.io/#defining-a-package

From this http://www.algorithmist.com/index.php/Bubble_sort

var bubbleSort = function(a) {
  var n = a.length,
    bound = n - 1;
  for (var i = 0; i < n - 2; i++) {
    var newbound = 0;
    for (var j = 0; j < bound; j++) {
      if (a[j] > a[j + 1]) {
        var tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
        newbound = j - 1;
      }
    }
    bound = newbound;
  }
  return a;
};

Everything passes and it fails on sonar-scanner, resulting in a negative overall result for PR.

Even for basic variable change PR #127 , sonar-scanner failed. There must be some issue with it.

This is the log from Travis-CI build.
The command "make" exited with 0.
0.11s$ sonar-scanner
sonar-scanner: command not found
The command "sonar-scanner" exited with 127.

Hello guys!
Would be that interesting for you ?
The idea is: from usual parent -> children relations we build an hierarchied topology and calculate the x, y coords for the nodes to be shown on layout with specific width, height and make a general connections between nodes: connections to the same node from different nodes could be replaced with one common bus, etc.
I am going to implement it for the project in samsung.

In order to have a 1.0 release we need:

1. Add self-balancing BSTs (red and black, avl, ...)
2. Add iterators (forEach) for all the data structures
3. Have a modular structure to allow someone to load just the sorting algorithms, for example, in a simple way

In its current form the binary search algorithm is not really useful, because in most cases it is not only the presence of a value that matters but also the position in the array.

I suggest that the binary search interface should mimic the standard Array#indexOf, in which case the algorithm could be considered as a more efficient alternative to indexOf for sorted arrays.

The name "algorithms" doesn't seem to be taken yet on npm. You should consider publishing this module with that name. http://registry.npmjs.org/algorithms

Can't modern javascript compilers optimize this kind of instructions? I know this is kind of bikeshedding, but I think using shifts instead of multiplications only sacrifices readability of the code.

Thanks for providing this module.

I've used the PriorityQueue a bit and noticed something that looks like a bug to me. It seems like if the same element is inserted again after have being extracted once alrady, is not possible.

See this minimal example:

const PriorityQueue = require("algorithms/data_structures").PriorityQueue;

const q = new PriorityQueue();

// Inserting and extracting one time works as expected:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());
console.log(q.isEmpty());

// Inserting 'a' again does not work, queue will be empty and nothing to extract:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());

The outoupt of this is:

false
a
true
true
undefined

while the expected output is:

false
a
true
false
a

My system:

• node v19.2.0.
• macOS 13.0.1

graph = new Graph(false)
graph.addEdge(1,2,-1)
graph.addEdge(2,3,-2)
graph.addEdge(3,4,0)
graph.addEdge(4,1,1)

SPFA(graph, "2")

The algorithm is going to infinite loop, because on every iteration we can improve shortest path.

Looks like algorithm should remember visited edges and break if it trying to visit some edge in the second time.

Nice to see another person doing CS101 to keep themselves sharp. There are a couple of cute O(ln(n)) Fibonacci calculators to try:

• There's a very clever iterative solution in Abelson and Sussman's SICP (Ex. 1.19)
  https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf
• There's another crazy solution using Matrix exponentiation:
  https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
  You'll want an iterative O(ln(n)) matrix exponentiation algorithm, however, so you should check out SICP (Ex. 1.16)
• There's also the old trick of rounding powers of the golden ratio:
  https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
  Again, you can do this one iteratively in O(ln(n)), although a hand crafted exponentiation function will never outperform Math.pow on Chrome.
• Another approach is to use Binet's formula: fib(n) = (phi^n - phi^(-n)) / sqrt(5) ; you can use this iteratively without rounding by defining a custom class for Z[sqrt(5)]; see Integral Extensions for a discussion of this idea. Here's an implementation (in Haskell): https://github.com/jaycoskey/RealWorldBenchmarking/blob/master/Fibonacci/extension.hs
• Another neat way to solve this problem is to derive the closed form of the recurrence using the z transform. Here's a MathOverflow about it: https://math.stackexchange.com/questions/279868/causal-inverse-z-transform-of-fibonacci
  Again, an efficient, exact solution would require expressing the zeros of x^2 -x - 1 in Z[sqrt(5)] and defining iterative O(ln(n)) integer exponentiation for that ring. All of the ring extension solutions are less efficient than Abelson and Sussman's solution.

I am finding some libraries about computational geometry, especially Bezier-curve related.

Including these algorithms will be helpful.

may I add this topic