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] [Updated] (REEF-1073) Improve ConstructorDefImpl.equalsIgnoreOrder algorithm
Date Sat, 12 Dec 2015 07:34:46 GMT

     [ https://issues.apache.org/jira/browse/REEF-1073?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Dongjoon Hyun updated REEF-1073:
--------------------------------
    Description: 
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, 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.

  was:
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.


> 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, 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.



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

Mime
View raw message