3
91%

Ran 05 Mar 2020 07:59AM UTC

Jobs 3

Files 11

Run time 722888min

Badge

Embed ▾

pending completion

Build # 3

Build Type

push

jenkins

Committed by

Commit Message

Improve fiter commit algorithm (#4)

## Description

Implements #3 

The commit filter algorithm in the `DefaultChangeDetector` had an exponential complexity (it was searching multiple times the same paths from nodes to same nodes). This was sufficient for most normal wdk repos or other repos that heavily used only PR's.  But unfortunately it was taking too long on a busy repo like for example a game repo like @wooga/switchcraft .

This  PR changes the algorithm a bit in order to memoize the already computed paths.  It also adds a performance test on a worst-case scenario with 30 merges. (2^30 -> 1 billion OPS)

This reduced the complexity from O( E(branching factor)^V(nodes) ) to O( V^2+E) ). Also to be able to re-use multiple paths to the same head with various iterating base's, I reversed the traversal order. (from base->head), reducing the complexity even more to O(V+E)

## Changes
* ![IMPROVE] Adds memoization to commit filter algorithm to reduce complexity to O(V+E)

Run Details

210 of 226 relevant lines covered (92.92%)

1.86 hits per line

Jobs

ID	Job ID	Ran	Files	Coverage
1	3.1	05 Mar 2020 07:59AM UTC	11	92.92
2	3.2	05 Mar 2020 07:59AM UTC	11	92.92
3	3.3	20 Jul 2021 08:07AM UTC	22	91.42

wooga / github-changelog-lib / 3
91%

README BADGES
x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 3

wooga / github-changelog-lib / 3 91%

README BADGES x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 3

wooga / github-changelog-lib / 3
91%

README BADGES
x