reef-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dongjoon Hyun (JIRA)" <j...@apache.org>
Subject [jira] [Created] (REEF-1073) Improve ConstructorDefImpl.equalsIgnoreOrder algorithm
Date Sat, 12 Dec 2015 07:33:46 GMT
Dongjoon Hyun created REEF-1073:
-----------------------------------

             Summary: Improve ConstructorDefImpl.equalsIgnoreOrder algorithm
                 Key: REEF-1073
                 URL: https://issues.apache.org/jira/browse/REEF-1073
             Project: REEF
          Issue Type: Improvement
          Components: Tang
            Reporter: Dongjoon Hyun
            Assignee: Dongjoon Hyun


This issue aims to improve the algorithm in `equalsIgnoreOrder` function of `ConstructorDefImpl`
class.
{code}
  /**
   * 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) {
{code}

For the first attempt using HashMap, the following is the reduction in terms of time. 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.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message