Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Denormalise net user debts to optimise algorithm to minimise transactions #60

Closed
IsaacCheng9 opened this issue Aug 26, 2022 · 0 comments · Fixed by #61
Closed

Denormalise net user debts to optimise algorithm to minimise transactions #60

IsaacCheng9 opened this issue Aug 26, 2022 · 0 comments · Fixed by #61
Assignees
Labels
backend Requires attention on the backend enhancement New feature or request

Comments

@IsaacCheng9
Copy link
Owner

Specification

  • As mentioned in PR #58, the algorithm for minimising transactions is currently O(k * n log n), where k is the number of debts, and n is the number of users.
  • We can optimise the algorithm to O(n log n) by denormalising the user debts.
    • The algorithm currently spends O(k) time going through all debts and calculating the net debt for each user.
    • If we store this in a separate collection and update it every time a debt pair is updated, we'll save repeated work.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
backend Requires attention on the backend enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant