首頁(yè) 猿問(wèn) 如何在...

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

Java

開(kāi)心每一天1111 2023-03-09 17:21:33

我需要在特定位置獲取一個(gè)元素，Iterable<MyType>以免遍歷所有元素，Iterable<MyType>因?yàn)槲抑浪柙匚挥谀膫€(gè)位置（就我而言，遍歷所有元素將花費(fèi) O(n) 時(shí)間，另一方面訪(fǎng)問(wèn)特定的將花費(fèi) O(1) 時(shí)間）。這必須是最后一個(gè)之前的元素。但我找不到辦法做到這一點(diǎn)。public interface Iterable<T>，顯然，沒(méi)有方法來(lái)訪(fǎng)問(wèn)任意位置的元素。我嘗試投射Iterable<MyType>到，List<MyType>但投射在運(yùn)行時(shí)失敗了ClassCastException。所以我不能使用ListIterator<E>, simpleList.get(E e)或一些自定義Function<T, U>來(lái)向后遍歷元素或獲取這個(gè)元素（我打算做的這些事情）。我當(dāng)前的代碼// 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))); } }}正如您目前看到的，我只是循環(huán)遍歷所有元素，Iterable<T>直到到達(dá)目標(biāo)元素，盡管我知道我正在尋找的目標(biāo)元素位于哪個(gè)位置。我想在Iterable<MyType>.我想找出最有效的方法來(lái)做到這一點(diǎn)（或者至少是比我當(dāng)前的解決方案更好的方法）。UPD：list是來(lái)自第三方庫(kù)的類(lèi)的實(shí)例，我沒(méi)有寫(xiě)，我也可以在類(lèi)getItems()中添加新的東西。list

查看完整描述

4 回答

牧羊人nacy

TA貢獻(xiàn)1862條經(jīng)驗(yàn) 獲得超7個(gè)贊

Iterable沒(méi)有為您提供在給定位置提取元素的方法，這是設(shè)計(jì)使然。集合框架包含更多專(zhuān)門(mén)的類(lèi)來(lái)處理具有O(1)元素訪(fǎng)問(wèn)的順序集合。這些是各種眾所周知的列表實(shí)現(xiàn)，尤其是那些實(shí)現(xiàn)RandomAccess接口的。

如您所見(jiàn)，選擇集合接口會(huì)產(chǎn)生很大的不同，尤其是在涉及O(xxx)符號(hào)方面。這是多功能性和性能之間的一種權(quán)衡。通用接口為Iterable您提供了最廣泛的適用輸入集，但您只能獲得RandomAccess集合的性能。

如果您要使用的所有輸入都是RandomAccess集合（ArrayList實(shí)現(xiàn)它），則沒(méi)有理由將它們作為Iterable. 如果不是這種情況，您可以在運(yùn)行時(shí)檢查此條件并選擇最有效的算法。

反對(duì) 回復(fù) 2023-03-09

慕絲7291255

TA貢獻(xiàn)1859條經(jīng)驗(yàn) 獲得超6個(gè)贊

使用 Iterable 接口，您無(wú)法獲取特定索引處的元素。所有界面允許您遍歷 Iterable 中的所有項(xiàng)目并觀察其中的內(nèi)容，僅此而已。您將不得不手動(dòng)管理當(dāng)前位置（索引/光標(biāo)）。一個(gè)簡(jiǎn)單的解決方案如下：

public static <T> T retrieveItemByIndex(Iterable<T> iterable, int index) {

if (iterable == null || index < 0) {

return null;

}

int cursor = 0;

Iterator<T> iterator = iterable.iterator();

while (cursor < index && iterator.hasNext()) {

iterator.next();

cursor++;

}

return cursor == index && iterator.hasNext() ? iterator.next() : null;

}

如果您不希望此輔助方法使用泛型，只需將其更改為僅適用于您的自定義類(lèi)型，如：

public MyType retrieveItemByIndex(Iterable<MyType> iterable, int index) {

if (iterable == null || index < 0) {

return null;

}

int cursor = 0;

Iterator<MyType> iterator = iterable.iterator();

while (cursor < index && iterator.hasNext()) {

iterator.next();

cursor++;

}

return cursor == index && iterator.hasNext() ? iterator.next() : null;

}

另一種方法是使用 Stream API（Java 8 及更高版本）。

首先，您必須從 Iterable 中獲取一個(gè)流，然后跳過(guò)第一個(gè)index元素并找到第一個(gè)。如果索引超出范圍，將返回默認(rèn)值。

int index = N - 2;

MyType defaultValue = null;

StreamSupport.stream(iterable.spliterator(), false)

.skip(index)

.findFirst()

.orElse(defaultValue);

反對(duì) 回復(fù) 2023-03-09

狐的傳說(shuō)

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超3個(gè)贊

正如 dbl 所提到的，您無(wú)法在 Iterable 對(duì)象的特定索引處獲取元素。如果您打算將 Iterable 對(duì)象轉(zhuǎn)換為列表，則只需花費(fèi)相同的時(shí)間 (O(n))，再加上獲取目標(biāo)元素的 O(1)。如果您真的很關(guān)心您的 O(n) 時(shí)間，我建議您按原樣迭代它直到您的目標(biāo)元素 (O(n-1))。

反對(duì) 回復(fù) 2023-03-09