在列表中查找对象而不迭代它

Question

我有一个 class 具有 3 个属性：

private static class OrderListItem {
    public int price;
    public int size;
    public Type type;
}

此 class 的项目已添加到列表中。 List<OrderListItem> orders_book = new ArrayList<>();

我想在列表中找到指定价格的对象。但大小和类型并不重要。我可以这样做吗：

int index = orders_book.indexOf(new OrderListItem(price, **any size**, **any type**)); ?

或者我必须进行“循环”搜索？

Answer 1

如果您需要检索具有所需价格的实例，则可以将集合流与 filter 和 findAny 操作一起使用。

int myPrice = /* any value you want */

//This will retrieve an instance with the disired price or null if none is found
OrderListItem item = orders_book.stream()
        .filter(i -> i.getPrice() == myPrice)
        .findFirst()
        .orElse(null);

或者，如果您想检索具有所需价格的对象的索引，那么您有两种选择：

重新定义 OrderListItem class 的 equals 方法，使两个 OrderListItems 的价格相等，因为 indexOf 方法的文档通过其价格检索元素equals 方法。但是，我不会倾向于这种解决方案，因为在我看来，单一价格不足以等于两个订单商品，但您肯定比我更了解您正在建模的问题类型。所以，我会把选择权留给你。此外，如果您重新定义 equals 方法，您还应该将 hashCode 方法重新定义为一般 hashcode contract 状态。

https://docs.oracle.com/javase/8/docs/api/java/util/List.html#indexOf-java.lang.Object-

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

class OrderListItem {
    public int price;
    public int size;
    public Type type;

    /* ... your implementation ...*/

    @Override
    public int hashCode() {
        return Objects.hash(price);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (this == obj) return true;
        if (getClass() != obj.getClass()) return false;
        OrderListItem other = (OrderListItem) obj;
        return Objects.equals(price, other.price);
    }
}

不是重新定义 equals 方法，而是使用流检索确切的实例（就像在第一个片段中一样），然后使用相同的实例作为 indexOf 调用的参数。

int myPrice = /* any value you want */

//This will retrieve an instance with the disired price or null if none is found
OrderListItem item = orders_book.stream()
        .filter(i -> i.getPrice() == myPrice)
        .findFirst()
        .orElse(null);

//Retrieving the index
int index = orders_book.indexOf(item);

Answer 2

我提供这个答案作为一种可能性，尽管它可能超出您的实际要求。使用一些 pre-defined 谓词，它允许在列表中 return 编辑任意数量的匹配、连续的项目。如果找不到匹配项，将return编辑一个空列表。

但首先，如果您想要索引（可能还有对象的值），您可以这样做而不需要修改您的 class。

这使用 IntStream 流式传输所有可能的索引。
它将索引和该索引处的对象映射到 Map.entry
然后它使用 entry 的 value 过滤所需的属性。
和 return 是遇到的第一个或带有 -1 和 null 的条目。（此处使用AbstractMap.SimpleEntry允许空值）

int desiredPrice = 3;
Entry<Integer, OrderListItem> result = IntStream
        .range(0, orderList.size())
        .mapToObj(i -> Map.entry(i, orderList.get(i)))
        .filter(e -> e.getValue().getPrice() == desiredPrice)
        .findFirst().orElse(new AbstractMap.SimpleEntry<>(-1,null));

为了便于演示，使用以下 record 代替 class 定义。一个class可以直接代替这个。还提供了类型枚举。

enum Type {
    FICTION, TECHNICAL, BIOGRAPHY
}

private record OrderListItem(int getPrice, int getSize,
        Type getType) {
    
    @Override
    public String toString() {
        return String.format("[%s, %s, %s]", getPrice, getSize,
                getType);
    }
}

现在定义一些谓词。每个都有一个 orderListItem 对象和一个 Type。比较方法（等于或 == ）取决于属性类型。该谓词和所需的属性值将提供给稍后所示的方法。即使您只对 price 感兴趣，其他的也很容易添加。

static BiPredicate<OrderListItem, Integer> CHECK_PRICE =
        (order, val) -> order.getPrice() == val;

static BiPredicate<OrderListItem, Type> CHECK_TYPE =
        (order, val) -> order.getType().equals(val);

static BiPredicate<OrderListItem, Integer> CHECK_SIZE =
            (order, val) -> order.getSize() == val;

一些数据

List<OrderListItem> orderList =
        ArrayList<>(List.of(new OrderListItem(3, 20, Type.FICTION),
                new OrderListItem(4, 20, Type.TECHNICAL),
                new OrderListItem(5, 20, Type.TECHNICAL),
                new OrderListItem(3, 30, Type.FICTION),
                new OrderListItem(4, 30, Type.FICTION),
                new OrderListItem(5, 30, Type.TECHNICAL),
                new OrderListItem(3, 40, Type.FICTION),
                new OrderListItem(4, 40, Type.BIOGRAPHY),
                new OrderListItem(5, 40, Type.FICTION),
                new OrderListItem(3, 50, Type.FICTION),
                new OrderListItem(4, 50, Type.BIOGRAPHY),
                new OrderListItem(5, 50, Type.BIOGRAPHY)));

演示

List<OrderListItem> matches =
        retrieve(orderList, CHECK_SIZE, 20, 2);
    
matches.forEach(System.out::println);

打印

[3, 20, FICTION]
[4, 20, TECHNICAL]

该方法采用以下参数。

订单列表
比较谓词
要比较的属性值
所需的 return 成功匹配数（负值将导致所有匹配被 returned）。

该方法通过对订单进行简单迭代，将谓词应用于订单和属性来工作。如果找到匹配项，则将其添加到 return 列表并减少计数。当计数达到 0 或检查整个列表时，列表将被 returned.

public static <T> List<OrderListItem> retrieve(
        List<OrderListItem> orders,
        BiPredicate<OrderListItem, T> pred, T attribute,
        int count) {
    List<OrderListItem> matches = new ArrayList<>();
    for (OrderListItem order : orders) {
        if (pred.test(order, attribute)) {
            matches.add(order);
            if (--count == 0) {
                break;
            }
        }
    }
    return matches;
}

性能

与 JMH 相比，这不是最好的测试，而是一个粗略的想法。

首先，我将数据列表自身添加了 20 次以创建一个大列表。
我在没有打印输出的情况下对所有记录重复了上述查找。

for (int i = 0; i < 20; i++) {
    orderList.addAll(orderList);
}
System.out.printf("%,d total objects%n",orderList.size());
    
long time = System.nanoTime();
List<OrderListItem> matches =
        retrieve(orderList, CHECK_SIZE, 20, -1);
System.out.println("Execution time ~ "+(System.nanoTime()-time)/1e9 + " sec");

打印

12,582,912 total objects
Execution time ~ 0.632698253 sec

没有找到整个列表的匹配项，结果是 Execution time ~ 0.033943752 sec.

匹配整个列表的结果是 Execution time ~ 0.939900075 sec.

时间上的差异主要是由于（imo）随着容量的增加必须更新支持阵列。这需要对数组进行多次重新复制。通过将 returned 列表的初始容量设置为 orders.size()，改进了匹配和 returning 所有元素的结果。

将整个列表与调整后的容量匹配，结果为 Execution time ~ 0.19100866 sec

我运行 Windows 使用 Intel 4 核 I7 处理器。

我不知道以上任何一项与您的要求有什么关系，但它可以启发您。

在列表中查找对象而不迭代它

Find an object in a list without iterating it

java

performance