Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
  • adaptive adaptive
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 36
    • Issues 36
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 5
    • Merge requests 5
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Packages and registries
    • Packages and registries
    • Container Registry
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Quantum TinkererQuantum Tinkerer
  • adaptiveadaptive
  • Merge requests
  • !139

Resolve "(Learner1D) improve time complexity"

  • Review changes

  • Download
  • Email patches
  • Plain diff
Merged Jorn Hoofwijk requested to merge 126--speed-up-learner1D into master Dec 03, 2018
  • Overview 29
  • Commits 2
  • Pipelines 13
  • Changes 3

Closes #126 (closed) #104 (closed)

improves time complexity from O(N^2) to O(N log N) (for learning a function from 0 to N points).

Speed is now ~1000 points per second on my computer (given the default loss) and remains more or less constant untill 5000 points

obviously for small N (say 10 points) the old method was faster, for larger N (say >20, the new method is faster).

It does need to be said that according to my profiler, most of the time is spend on this line: be74ad62 (line 572)

please do verify that the results are noticeable for you as well.

Also do note that the complexity now is as follows:

Operation Comblexity @ master Complexity @ branch
tell(x,y) O(N) O(log N)
ask(1) O(N) O(log N)
loss() O(N) O(1)
ask(k) O(N*k) O(k * log N)
run 1..N O(N^2) O(N log N)
Edited Dec 07, 2018 by Jorn Hoofwijk
Assignee
Assign to
Reviewers
Request review from
Time tracking
Source branch: 126--speed-up-learner1D