如何在 Iterable<T> 中以最有效的方式获取特定位置的元素？

Question

我需要在特定位置获取一个元素，Iterable<MyType>以免遍历所有元素，Iterable<MyType>因为我知道所需元素位于哪个位置（就我而言，遍历所有元素将花费 O(n) 时间，另一方面访问特定的将花费 O(1) 时间）。这必须是最后一个之前的元素。但我找不到办法做到这一点。

public interface Iterable<T>，显然，没有方法来访问任意位置的元素。

我尝试投射Iterable<MyType>到，List<MyType>但投射在运行时失败了ClassCastException。所以我不能使用ListIterator<E>, simpleList.get(E e)或一些自定义Function<T, U>来向后遍历元素或获取这个元素（我打算做的这些事情）。

我当前的代码

// list.getItems() returns Iterable<MyType>

// I know that element I am looking for is at (iterable.size - 2) position

        for(MyType item : list.getItems()) {

            if (item.convertToText().matches(targetElementRegex)) {

                Pattern pattern = Pattern.compile(targetElementRegex);

                Matcher matcher = pattern.matcher(item.convertToText());

                if (matcher.find()) {

                    return Optional.of(Integer.parseInt(matcher.group(1)));

                }

            }

}

正如您目前看到的，我只是循环遍历所有元素，Iterable<T>直到到达目标元素，尽管我知道我正在寻找的目标元素位于哪个位置。我想在Iterable<MyType>.

我想找出最有效的方法来做到这一点（或者至少是比我当前的解决方案更好的方法）。

UPD：list是来自第三方库的类的实例，我没有写，我也可以在类getItems()中添加新的东西。list

Answer 1

Iterable没有为您提供在给定位置提取元素的方法，这是设计使然。集合框架包含更多专门的类来处理具有O(1)元素访问的顺序集合。这些是各种众所周知的列表实现，尤其是那些实现RandomAccess接口的。如您所见，选择集合接口会产生很大的不同，尤其是在涉及O(xxx)符号方面。这是多功能性和性能之间的一种权衡。通用接口为Iterable您提供了最广泛的适用输入集，但您只能获得RandomAccess集合的性能。如果您要使用的所有输入都是RandomAccess集合（ArrayList实现它），则没有理由将它们作为Iterable.&nbsp;如果不是这种情况，您可以在运行时检查此条件并选择最有效的算法。

Answer 2

使用 Iterable 接口，您无法获取特定索引处的元素。所有界面允许您遍历 Iterable 中的所有项目并观察其中的内容，仅此而已。您将不得不手动管理当前位置（索引/光标）。一个简单的解决方案如下：public static <T> T retrieveItemByIndex(Iterable<T> iterable, int index) {&nbsp; &nbsp; if (iterable == null || index < 0) {&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }&nbsp; &nbsp; int cursor = 0;&nbsp; &nbsp; Iterator<T> iterator = iterable.iterator();&nbsp; &nbsp; while (cursor < index && iterator.hasNext()) {&nbsp; &nbsp; &nbsp; &nbsp; iterator.next();&nbsp; &nbsp; &nbsp; &nbsp; cursor++;&nbsp; &nbsp; }&nbsp; &nbsp; return cursor == index && iterator.hasNext() ? iterator.next() : null;}如果您不希望此辅助方法使用泛型，只需将其更改为仅适用于您的自定义类型，如：public MyType retrieveItemByIndex(Iterable<MyType> iterable, int index) {&nbsp; &nbsp; if (iterable == null || index < 0) {&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }&nbsp; &nbsp; int cursor = 0;&nbsp; &nbsp; Iterator<MyType> iterator = iterable.iterator();&nbsp; &nbsp; while (cursor < index && iterator.hasNext()) {&nbsp; &nbsp; &nbsp; &nbsp; iterator.next();&nbsp; &nbsp; &nbsp; &nbsp; cursor++;&nbsp; &nbsp; }&nbsp; &nbsp; return cursor == index && iterator.hasNext() ? iterator.next() : null;}另一种方法是使用 Stream API（Java 8 及更高版本）。首先，您必须从 Iterable 中获取一个流，然后跳过第一个index元素并找到第一个。如果索引超出范围，将返回默认值。int index = N - 2;MyType defaultValue = null;StreamSupport.stream(iterable.spliterator(), false)&nbsp; &nbsp; .skip(index)&nbsp; &nbsp; .findFirst()&nbsp; &nbsp; .orElse(defaultValue);

Answer 3

正如 dbl 所提到的，您无法在 Iterable 对象的特定索引处获取元素。如果您打算将 Iterable 对象转换为列表，则只需花费相同的时间 (O(n))，再加上获取目标元素的 O(1)。如果您真的很关心您的 O(n) 时间，我建议您按原样迭代它直到您的目标元素 (O(n-1))。

Answer 4

如果您只想要倒数第二个位置，为什么不在进入循环之前用列表索引那个位置呢？而不是 list.getItems()，尝试 list.getItem(list.getItemCount()-2)