Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Found another input that triggers non-polynomial time with the code in this
PR. I'm again borrowing from scikit-learn. I think this is the case they found
that led them to re-write their implementation.
```
val y = ((0 until length) ++ (-(length - 1) until length) ++ (-(length
- 1) to 0)).toArray.map(_.toDouble)
val x = (1 to y.length).toArray.map(_.toDouble)
```
| Input Length | Time (ns) |
| --: | --: |
| 40 | 2059 |
| 80 | 4604 |
| 160 | 1974269 |
| 320 | 3246603433 |
I'm now working on implementing what's described in the Best papers. This
should give O(n), even in the worst case.
Should I close this and open a new PR with the new algorithm, or just add
it here and you can squash when you merge?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
