1

假设我有一个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，因为它们对应于Xwithin的位置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方法非常长。

4

3 回答 3

1

如果列表已排序，请在遇到更大的内容后停止。如果列表实现允许随机访问（即 an ArrayList），则使用二进制搜索。由于列表包含重复项，您需要从找到的元素向前和向后扫描，以确保获得所有索引。

如果搜索与更新的比率很大（搜索比更新多），那么您可以在 aMap<Long,List<Integer>>中维护一个索引，将每个值映射到该值出现在列表中的索引列表。随着原始列表的更新，您将不得不编写代码来维护索引。

在评估性能时，构建和维护索引的成本可以在搜索中分摊。如果列表在创建后从未更新，并且搜索量很大，那么这将是一个明显的赢家。

但是，除非列表很大（> 10000）并且查询数量很大（> 1,000,000），否则可能不值得麻烦。

于 2013-10-06T08:14:13.193 回答
1

如果您使用GS Collections，您可以将原始列表用于源列表和索引列表，因此您不会产生装箱原始值的成本。以下代码将在 Java 8 中使用 lambdas 与您的示例一起工作：

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 的开发人员。

于 2013-10-09T19:23:04.093 回答
0

试试这个解决方案：

int firstIndex = foo.indexOf(X);

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

如果你List是sorted，那么你有 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);
}
于 2013-10-06T08:17:25.093 回答