问题

你好，以下是您要求的翻译部分：

"Hello to the wonderful community, i came up with a small problem that struggling me to figure out a solution. I have a simple dummy class with a name and surname and an ArrayList of that class.In reality my real class is very heavy and multiple add operations happened all time thus i want an efficient approach to perform searching operations and hence i use the binary search base. The problem is that the performed operations sometimes are for name and others for the surname. i want to avoid all time to sort based on the given field and then perform binary search, so is there any efficient solution on that?"

"Here is my dummy solutions:

Dummy solution 1: keep the code as it with the overhead of sort method before i called the binary search.

Dummy solution 2: waste my memory and keep two sorted ArrayList one with name and the other surname and keep also the insertion order so as to avoid sort func every time i do a binary search.

I am sure there is exist another efficient approach can you suggest me please a solution to this problem"

"package Memory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MemTest2 {
static ArrayList al = new ArrayList();
public static void main(String[] args) {

    add("John","colins");
    add("Andrew","tate");
    add("Zoe","prelevits");
    add("jonh","adam");


    BinarySearchName();
    BinarySearchSurname();
}

public static void add(String name,String surname){
    al.add(new Foo(name,surname));
}

public static void BinarySearchName(){
    Comparator<Foo> c = new Comparator<Foo>() {
        public int compare(Foo u1, Foo u2)
        {
            return u1.getName().compareTo(u2.getName());
        }
    };
    Collections.sort(al, Comparator.comparing(Foo::getName));
    int index = Collections.binarySearch(al, new Foo("Zoe","prelevits"), c);
}

public static void BinarySearchSurname(){
    Comparator<Foo> c = new Comparator<Foo>() {
        public int compare(Foo u1, Foo u2)
        {
            return u1.getSurname().compareTo(u2.getSurname());
        }
    };
    Collections.sort(al, Comparator.comparing(Foo::getSurname));
    int index = Collections.binarySearch(al, new Foo("john","adam"), c);
}

private static class Foo{
    private String name;
    private String surname;

    public Foo(String name, String surname) {
        this.name = name;
        this.surname = surname;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getSurname() {
        return surname;
    }

    public void setSurname(String surname) {
        this.surname = surname;
    }
}

}"

请让我知道如果您需要更多的帮助。

package Memory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MemTest2 {
    static ArrayList<Foo> al = new ArrayList<Foo>();
    public static void main(String[] args) {

        add("John","colins");
        add("Andrew","tate");
        add("Zoe","prelevits");
        add("jonh","adam");


        BinarySearchName();
        BinarySearchSurname();
    }

    public static void add(String name,String surname){
        al.add(new Foo(name,surname));
    }

    public static void BinarySearchName(){
        Comparator<Foo> c = new Comparator<Foo>() {
            public int compare(Foo u1, Foo u2)
            {
                return u1.getName().compareTo(u2.getName());
            }
        };
        Collections.sort(al, Comparator.comparing(Foo::getName));
        int index = Collections.binarySearch(al, new Foo("Zoe","prelevits"), c);
    }

    public static void BinarySearchSurname(){
        Comparator<Foo> c = new Comparator<Foo>() {
            public int compare(Foo u1, Foo u2)
            {
                return u1.getSurname().compareTo(u2.getSurname());
            }
        };
        Collections.sort(al, Comparator.comparing(Foo::getSurname));
        int index = Collections.binarySearch(al, new Foo("john","adam"), c);
    }

    private static class Foo{
        private String name;
        private String surname;

        public Foo(String name, String surname) {
            this.name = name;
            this.surname = surname;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getSurname() {
            return surname;
        }

        public void setSurname(String surname) {
            this.surname = surname;
        }
    }
}

答案1

得分: 2

There is no point at all in sorting before searching every time. Sorting will cost you more than a linear scan through the data, so you get a benefit only if you can perform multiple searches per sort. Ideally, you sort once for all, then perform all the searches.

In your case, however,

> multiple add operations happened all time

You think that ...

> The problem is that the performed operations sometimes are for name and others for the surname.

... but in fact, even if the searches were always for one field, it would be very costly to keep the list in sorted order as you add elements (unless the additions were in order already). For unordered additions, the average cost per addition would be proportional to the number of elements already in the list.

> i want to avoid all time to sort based on the given field and then perform binary search, so is there any efficient solution on that?

Yes. Use a HashMap<String, Foo> for each search criterion you want to support, instead of a list of any flavor. That will give you O(1) (ammortized) cost for additions and lookups, at the cost of more storage use. (The Foos are not duplicated, but the framework of one ArrayList will be smaller than that of two HashMaps for the same number of elements / entries).

    static HashMap<String, Foo> byGivenName = new HashMap<>();
    static HashMap<String, Foo> bySurname = new HashMap<>();

    public static void main(String[] args) {

        add("John","colins");
        add("Andrew","tate");
        add("Zoe","prelevits");
        add("jonh","adam");
    }

    public static void add(String name,String surname){
        Foo foo = new Foo(name, surname);

        byGivenName.put(name, foo);
        bySurname.put(surname, foo);
        retrieveByGivenName("Zoe");
        retrieveBySurname("adam");
    }

    public static foo retrieveByGivenName(String name) {
        return byGivenName.get(name);
    }

    public static foo retrieveBySurname(String surname) {
        return bySurname.get(surname);
    }

    // ...
} ``` I presume there that the element indexes are not actually significant, but I think that must be true because otherwise, the continual re-sorting you propose to do would be an issue too.

<details>
<summary>英文:</summary>

There is no point at all in sorting before searching *every time*.  Sorting will cost you more than a linear scan through the data, so you get a benefit only if you can perform multiple searches per sort.  Ideally, you sort once for all, then perform all the searches.

In your case, however,

&gt; multiple add operations happened all time

You think that ...

&gt; The problem is that the performed operations sometimes are for name and others for the surname.

... but in fact, even if the searches were always for one field, it would be very costly to keep the list in sorted order as you add elements (unless the additions were in order already).  For unordered additions, the average cost per addition would be proportional to the number of elements already in the list.

&gt; i want to avoid all time to sort based on the given field and then perform binary search, so is there any efficient solution on that?

Yes.  Use a `HashMap&lt;String, Foo&gt;` for each search criterion you want to support, instead of a list of any flavor.  That will give you O(1) (ammortized) cost for additions and lookups, at the cost of more storage use.  (The `Foo`s are not duplicated, but the framework of one `ArrayList` will be smaller than that of two `HashMap`s for the same number of elements / entries).

public class MemTest3 {
static HashMap<String, Foo> byGivenName = new HashMap<>();
static HashMap<String, Foo> bySurname = new HashMap<>();

public static void main(String[] args) {

    add("John","colins");
    add("Andrew","tate");
    add("Zoe","prelevits");
    add("jonh","adam");
}

public static void add(String name,String surname){
    Foo foo = new Foo(name, surname);

    byGivenName.put(name, foo);
    bySurname.put(surname, foo);
    retrieveByGivenName("Zoe");
    retrieveBySurname("adam");
}

public static foo retrieveByGivenName(String name) {
    return byGivenName.get(name);
}

public static foo retrieveBySurname(String surname) {
    return bySurname.get(surname);
}

// ...

}

I presume there that the element indexes are not actually significant, but I think that must be true because otherwise, the continual re-sorting you propose to do would be an issue too.

</details>



# 答案2
**得分**: 0

&gt; _"…我想要一个高效的方法来执行搜索操作…"_  
&gt; _"…是否有高效的解决方案…"_  

这完全取决于数据和搜索条件。

统计上，单次迭代将是最有效的方法。
而不是先排序，然后再搜索。

```java
Foo BinarySearchName(String string) {
    for (Foo foo : al) {
        if (foo.getName().equals(string))
            return foo;
    }
    return null;
}

Foo BinarySearchSurname(String string) {
    for (Foo foo : al) {
        if (foo.getSurname().equals(string))
            return foo;
    }
    return null;
}

Foo BinarySearchName(String string) {
    for (Foo foo : al) {
        if (foo.getName().equals(string))
            return foo;
    }
    return null;
}

Foo BinarySearchSurname(String string) {
    for (Foo foo : al) {
        if (foo.getSurname().equals(string))
            return foo;
    }
    return null;
}