Java初学者问题: Method for finding next available ID in an ArrayList

Question

我已经完成了这个练习:创建一个在成员对象的 ArrayList 中查找下一个可用成员 ID 的方法。我在创建新成员时手动创建成员 ID，并且我始终可以假设成员已按 ID 按顺序排列。例如:如果我有 4 个 ID 为 0-3 的成员，并且我删除了第二个成员，则该方法应返回 1。

这是我现在的困惑部分:

public int getNextID (){
    int i;
    for(i = 0; i < members.size(); i++){
        if(i == members.get(i).getID()){
            i++;



        }
        else if(i != members.get(i).getID()){
            System.out.println("Next available ID:  " + i);

        } else {
            System.out.println("Next available ID: " + members.size());
            break;
        }
    }
    return i;
} 

Answer 1

此解决方案从列表中提供新的成员(member) ID，其中所有 MemberItem 均按 ID 排序。列表中的项目 0，必须具有 ID 0。项目 1 -> ID 1。新 ID 将始终是当前未分配的最低可用 ID。

<小时/>

解决方案1

public int getNextID (){
    for(int i = 0; i < members.size(); i++){
        if(i < members.get(i).getID()){
            System.out.println("Next available ID:  " + i);
            // at this point we know this is the next id.
            // we can leave the method and return the next ID.
            return i;
        }
    }
    // we did not leave the loop (and method), because all id's are assigned.
    System.out.println("Next available ID:  " + members.size());
    return members.size();
}

<小时/>

解决方案 2(Java 1.8+ Stream)

如果您更喜欢 2 行 java 8 流解决方案，您也可以使用这个:

public int getNextID() {
   Member m = members.stream().filter(member -> member.getID() != members.indexOf(member)).findFirst().orElse(null);
   return (m != null ? members.indexOf(m) : members.size());
}

解决方案 3(Java 1.8+ Stream)

或 1 线流解决方案:

public int getNextID() {
   return members.stream().filter(member -> member.getID() != members.indexOf(member)).findFirst().map(m2 -> members.indexOf(m2)).orElse(members.size());
}

<小时/>

说说你的代码:您将 i 增加两次。一旦在 for 语句末尾使用 i++ ，下面两行再次使用 i++ 。这样，如果第一个成员具有与索引相同的 id，则您将跳过索引 1。

<小时/>

时间和测试

对于任何对这 3 个解决方案之间的时间比较感兴趣的人。这是我的 java1.8 机器的计时:

|----------------------------------------------------------------------|
| 10000 Items, Free Position 9998    | 10000 Items, Free Position 1    |
|----------------------------------------------------------------------|
| Solution1: ~2ms                    |  Solution1: ~0.005ms            |  
| Solution2: ~65ms                   |  Solution2: ~0.05ms             |
| Solution3: ~60ms                   |  Solution3: ~0.06ms             |
|----------------------------------------------------------------------|

在您的机器上执行它的代码。肯定会导致不同的计时结果，但比例应该保持大致相同。

import java.util.ArrayList;
import java.util.List;

public class Test {
    private static List<Member> members = new ArrayList<>();

    public static void main(String[] args) {
        members = getTestList(10000);

        warmUp();

        members.remove(9998);
        testSolutions();
        members.remove(1);
        testSolutions();

    }

    private static void warmUp() {
        for (int i = 0; i < 5; i++) {
            for (Member m : members) {
                // warm up cpu for iteration
            }
            members.forEach(Member::getID);
        }
    }

    private static void testSolutions() {
        long start = System.nanoTime();
        int result1 = getNextID();
        System.out.println("#1 Iterative result: " + result1 + " | in " + (System.nanoTime() - start) / 1000000.0 + "ms");
        start = System.nanoTime();
        Member m = members.stream().filter(member -> member.getID() != members.indexOf(member)).findFirst().orElse(null);
        int result2 = m != null ? members.indexOf(m) : members.size();
        System.out.println("#2 Stream Result: " + result2 + " | in " + ((System.nanoTime() - start) / 1000000.0) + "ms");
        start = System.nanoTime();
        int result3 = members.stream().filter(member -> member.getID() != members.indexOf(member)).findFirst().map(m2 -> members.indexOf(m2)).orElse(members.size());
        System.out.println("#3 Stream Result: " + result3 + " | in " + ((System.nanoTime() - start) / 1000000.0) + "ms");
    }

    private static int getNextID() {
        for (int i = 0; i < members.size(); i++) {
            if (i < members.get(i).getID()) {
                return i;
            }
        }
        return members.size();
    }

    private static List<Member> getTestList(int count) {
        List<Member> members = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            members.add(new Member(i));
        }
        return members;
    }

    private static class Member {
        private int id;

        public Member(int id) {
            this.id = id;
        }

        private int getID() {
            return id;
        }
    }
}