[REEF-1073] Improve ConstructorDefImpl.equalsIgnoreOrder algorithm

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.14
• Component/s: Tang
• Assignee: Dongjoon Hyun
• Reporter: Dongjoon Hyun
• Created: 12/Dec/15 07:33
• Updated: 17/Dec/15 23:13
• Resolved: 17/Dec/15 23:13

Description

This issue aims to improve the algorithm in `equalsIgnoreOrder` function of `ConstructorDefImpl` class.

  /**
   * Check to see if two boundConstructors take indistinguishable arguments. If
   * so (and they are in the same class), then this would lead to ambiguous
   * injection targets, and we want to fail fast.
   * <p>
   * TODO could be faster. Currently O(n^2) in number of parameters.
   *
   * @param def
   * @return
   */
  private boolean equalsIgnoreOrder(final ConstructorDef<?> def) {

For the first attempt, the following is the reduced time using HashMap. Please refer the linked PR.

[n=00] 63% ( 785 -> 501)
[n=01] 57% ( 2444 -> 1403)
[n=02] 75% ( 6276 -> 4710)
[n=03] 63% ( 10552 -> 6697)
[n=04] 32% ( 18599 -> 5966)
[n=05] 41% ( 19830 -> 8201)
[n=06] 33% ( 42960 -> 14273)
[n=07] 28% ( 34635 -> 9838)
[n=08] 21% ( 40503 -> 8683)
[n=09] 19% ( 60205 -> 11751)
[n=10] 14% ( 74540 -> 10703)
[n=11] 13% ( 79839 -> 10657)
[n=12] 22% ( 59905 -> 13759)
[n=13] 27% ( 60297 -> 16346)
[n=14] 24% ( 63540 -> 15653)
[n=15] 31% ( 62749 -> 20063)
[n=16] 22% ( 80392 -> 17727)
[n=17] 21% ( 92287 -> 20229)
[n=18] 19% (110056 -> 21405)
[n=19] 15% (110352 -> 17264)
[n=20] 13% (126597 -> 17536)

Please note that, new algorithm will consume more memory.

Issue Links

• links to: Link to PR