Summary: | Automatically clear transactions at the beginning of reconciliation | ||
---|---|---|---|
Product: | [Applications] kmymoney | Reporter: | Thomas Baumgart <tbaumgart> |
Component: | general | Assignee: | KMyMoney Devel Mailing List <kmymoney-devel> |
Status: | RESOLVED FIXED | ||
Severity: | wishlist | ||
Priority: | NOR | ||
Version: | unspecified | ||
Target Milestone: | --- | ||
Platform: | openSUSE | ||
OS: | Linux | ||
Latest Commit: | Version Fixed In: |
Description
Thomas Baumgart
2010-02-25 18:00:04 UTC
The first algorithm that I thought of when reading the requirements has a really big performance issue - it's execution time is O(2^N) where N is the number of possible transactions in the reconciliation period. This means that execution time doubles at each extra transaction in the reconciliation period. At let's say 20 transactions this could already take a while. The algorithm sounds something like this: "Generate the sum of all combination of numbers (the amount of transactions) until the target sum is obtained; if the target sum is not obtained than the automatic matching algorithm failed." We could gain some improvement from the fact that we already know the target sum so we could come up with an heuristic algorithm. I think that the http://en.wikipedia.org/wiki/Subset_sum_problem is the same problem that we have. I've tested an implementation of this algorithm http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm it seems to very good performance (I've tested it with 22 numbers so far). I'll implement this feature using this algorithm. SVN commit 1127345 by conet: BUG: 228492 This is an initial implementation of the 'Automatic reconciliation' feature. It could still need optimizations but it's usable in it's current state and I think we'll manage to polish the rough edges until the next release. I've added a setting to enable the feature in the 'Register settings' page under the 'Data entry' tab since in the 'General settings' page the wasn't any room for another check-mark. M +13 -0 dialogs/settings/ksettingsregisterdecl.ui M +155 -0 kmymoney.cpp M +4 -0 kmymoney.kcfg WebSVN link: http://websvn.kde.org/?view=rev&revision=1127345 |