метода, чтобы найти все индексы в списке <Long>, соответствующие некоторый элемент

Question

Предположит, что у меня есть long под названием X и List<Long> под названием foo, который содержит X как один не уникальный элемент среди многих элементов. Какой метод я должен применить, чтобы найти все индексы в foo, которые соответствуют X. Этот foo не обязательно сортируется (но хороший ответ может принять это, если есть конкретный метод, который требует сортировки - меня интересуют как отсортированные, так и несортированные случаи).

Например, это может быть установка проблема:

long X = 5L 
List<Long> foo = new ArrayList<Long>(); 
foo.add(4L); 
foo.add(5L); 
foo.add(5L); 
foo.add(6L); 
foo.add(7L); 

Я хочу способ принять X в качестве аргумента и возвращает список (или другой объект), который содержит индексы 1 и 2, так как они соответствуют к местоположению X в пределах foo.

Тривиально,

public static List<Long> locator(long target, List<Long> fooList) { 
    List<Long> output = new ArrayList<Long>(); 

    for(int i = 0 ; i < foo.size() ; i++) { 
     if(foo.get(i) == target) { 
     output.add(i); 
     } 
    } 

    return output; 
} 

Но я хочу более быстрый способ упаковывают мой foo является гигантски долго.

Answer 1

Если список отсортирован, остановите его после того, как вы нажмете что-то большее. Если реализация списка допускает произвольный доступ (то есть ArrayList), то используйте двоичный поиск. Поскольку список содержит дубликаты, вам нужно будет сканировать вперед и назад от найденного элемента, чтобы убедиться, что вы получаете все индексы.

Если отношение поиска к обновлениям велико (выполняется намного больше запросов, чем обновлений), вы можете сохранить индекс в Map<Long,List<Integer>>, который отображает каждое значение в список индексов, где значение отображается в списке. Вам нужно будет написать код для поддержания индекса по мере обновления исходного списка.

При оценке производительности стоимость строительства и обслуживания индекса может быть амортизирована по результатам поиска. Если список не обновляется после создания, а количество запросов велико, то это будет явным победителем.

Однако, если список не большой (> 10000) И количество запросов велико (> 1,000,000), это может не стоить проблем.

Answer 2

Попробуйте это решение:

int firstIndex = foo.indexOf(X); 

int count = Collections.frequency(foo, X); 

Если ваш List является отсортирован, поэтому у вас есть 2 позиции: firstIndex и firstIndex + 1

Из вашего примера:

long X = 5L 
List<Long> foo = new ArrayList<Long>(); 
foo.add(4L); 
foo.add(5L); 
foo.add(5L); 
foo.add(6L); 
foo.add(7L); 

int firstIndex = foo.indexOf(X); // 1 
int count = Collections.frequency(foo, X); // 2 

List<Long> output = new ArrayList<Long>(); 

for(int i=firstIndex; i<count; i++){ 
    output.add(i); 
} 

Answer 3

Если вы используете GS Collections вы можете использовать примитивные списки как для исходного списка и список индексов, поэтому вы не понесете стоимость боксирования примитивных значений.Следующий код будет работать в Java 8, используя лямбды с вашего примера:

long X = 5L; 
LongArrayList list = LongArrayList.newListWith(4L, 5L, 5L, 6L, 7L); 
IntArrayList indices = new IntArrayList(); 
list.forEachWithIndex((each, index) -> { if (each == X) indices.add(index);}); 
Assert.assertEquals(IntArrayList.newListWith(1, 2), indices); 

В Java 7 это будет выглядеть следующим образом:

long X = 5L; 
LongArrayList list = LongArrayList.newListWith(4L, 5L, 5L, 6L, 7L); 
IntArrayList indices = new IntArrayList(); 
list.forEachWithIndex(new LongIntProcedure() 
{ 
    public void value(long each, int index) 
    { 
     if (each == X) indices.add(index); 
    } 
}); 
Assert.assertEquals(IntArrayList.newListWith(1, 2), indices); 

Примечание: Я являюсь разработчиком на GS Collections.