[jira] [Reopened] (GROOVY-10964) List.minus() slow for Numbers

["Ingo Wilms (Jira)" <ji...@apache.org>]

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

Ingo Wilms reopened GROOVY-10964:
---------------------------------

Recently I've been thinking about this again and wondering why it shouldn't be possible to keep the desired behavior while improving the time complexity for Numbers. Instead of finding all elements in self1 that are in the answer-TreeSet, we could find those that are not in the removeMe-TreeSet:

{code:java}
if (nlgnSort && (head instanceof Comparable)) {
    //n*LOG(n) version
    Set<T> removeMe2;
    removeMe2 = new TreeSet<>(comparator);
    for(Object o: removeMe1) {
        removeMe2.add((T) o);
    }
    for (T o : self1) {
        if (!removeMe2.contains(o))
            ansCollection.add(o);
    }
} else {
    //n*n version {code}
There is most likely another catch, but I was just wondering if that is possible.

> List.minus() slow for Numbers
> -----------------------------
>
>                 Key: GROOVY-10964
>                 URL: https://issues.apache.org/jira/browse/GROOVY-10964
>             Project: Groovy
>          Issue Type: Question
>          Components: groovy-jdk
>    Affects Versions: 2.4.0, 3.0.9, 4.0.9
>            Reporter: Ingo Wilms
>            Priority: Minor
>              Labels: Collections, Groovy, List, Number
>   Original Estimate: 1h
>  Remaining Estimate: 1h
>
> In List.minus() is a n*LOG\(n) version for comparable objects. Only for numbers, there is a dedicated slower n^2*LOG\(n) version. Is there a reason for this? It exists since 2.4.0 and hasn't changed much since then. Here is part of the code from version 4.0.9:
>  
> {code:java}
> // if (nlgnSort && (head instanceof Comparable)) {
>     //n*LOG(n) version
>     Set<T> answer;
>     if (head instanceof Number) {
>         answer = new TreeSet<>(comparator);
>         answer.addAll(self1);
>         for (T t : self1) {
>             if (t instanceof Number) {
>                 for (Object t2 : removeMe1) {
>                     if (t2 instanceof Number) {
>                         if (comparator.compare(t, (T) t2) == 0)
>                             answer.remove(t);
>                     }
>                 }
>             } else {
>                 if (removeMe1.contains(t))
>                     answer.remove(t);
>             }
>         }
>     } else {
>         answer = new TreeSet<>(comparator);
>         answer.addAll(self1);
>         answer.removeAll(removeMe1);
>     }
>     for (T o : self1) {
>         if (answer.contains(o))
>             ansCollection.add(o);
>     }
> } else {
>     //n*n version {code}
> I fail to see why the whole extra block for numbers beginning with
> {code:java}
> if (head instanceof Number) { {code}
> is necessary.
>  



--
This message was sent by Atlassian Jira
(v8.20.10#820010)