2

我有一个包含几个项目的数组列表。假设它们是：“深棕色”，“蓝色”，“绿色”，....

有什么方法可以查找我的某些物品中是否有字符串“DARK”？我知道 contains 会这样做，但只有在字符串完全正确的情况下才会这样做。我的想法是寻找一个以我的项目之一开头但没有所有最后一个字符的文本。

我有想法做一个循环，如：

for(int i=0;i<arraylist.size;i++){
  String s = arraylist.get(i);
  if (s.startsWith(mytext)){
   do something
  }
}

但这似乎是一个非常慢的方法，因为 arraylist 可以包含很多元素。有更好的想法吗？

编辑

只是为了确保你理解我的观点。我想知道我的数组列表中的一个项目是否包含一个以某些文本开头的元素并获取该元素的完整文本。ArrayList.contains 是一个布尔值。如果我需要检索信息，我将不得不使用 IndexOf 左右，但是如果我输入“棕色”，这个函数会给我 null

编辑 2

这是给你的 auselen：

Arraylist（大约 5000 个元素）：

  • “大卫的猫在他的卧室里”
  • “我喜欢月亮”
  • “我想去火星”
  • “我的球是红色的”
  • “他们总是忘记南极洲”
  • ...

我想知道是否有一个以“我想”开头的元素，然后检索该元素的其余部分。

4

5 回答 5

2

这似乎是一个非常慢的方法，因为 arraylist 可以包含很多元素。

比如，一百万？

Nov 30, 2012 10:05:20 AM test.t100.t001.ArrayListSpeed main
INFO: Creating entries.
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching..
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'dark' 333716
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'light' 333333
Nov 30, 2012 10:05:22 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'plain' 332951

代码

package test.t100.t001;

import java.util.ArrayList;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

public class ArrayListSpeed {

    public static String[] PREFIX = {"Dark ", "Light ", "Plain "};
    public static String[] COLOR = {"Red", "Green", "Blue"};

    public static String getColor(Random r) {
        int val = r.nextInt(COLOR.length);
        return COLOR[val];
    }

    public static String getPrefix(Random r) {
        int val = r.nextInt(PREFIX.length);
        return PREFIX[val];
    }

    public static int countPrefixes(ArrayList<String> list, String prefix) {
        int count = 0;
        for (String val : list) {
            if (val.toLowerCase().startsWith(prefix.toLowerCase())) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Logger logger = Logger.getAnonymousLogger();
        ArrayList<String> list = new ArrayList<String>();
        Random r = new Random();
        logger.log(Level.INFO, "Creating entries.");
        for (int ii=0; ii<1000000; ii++) {
            list.add( getPrefix(r) + getColor(r) );
        }
        logger.log(Level.INFO, "Searching..");
        logger.log(Level.INFO, 
                "Searching 'dark' " + countPrefixes(list,"dark"));
        logger.log(Level.INFO, 
                "Searching 'light' " + countPrefixes(list,"light"));
        logger.log(Level.INFO, 
                "Searching 'plain' " + countPrefixes(list,"plain"));
    } 
}
于 2012-11-29T23:07:08.603 回答
2

将字符串保存在 sorted(!) 数组中，并用于binarysearch查找前缀的插入点。比赛将在那个时候进行，如果有的话。

如果这是O(log n)而不是O(n)的性能，您应该会发现它要快得多，尤其是对于大型数据集。

import static org.junit.Assert.assertEquals;
import java.util.Arrays;
import org.junit.Test;

public class ContainsPrefix {

    public static String findWithPrefix(String[] data, String prefix) {
        int n = Arrays.binarySearch(data, prefix);
        if (n < 0) n = -1 - n;
        // Loop here if you want to find all matches ...
        if (!data[n].startsWith(prefix)) return null;
        return data[n];
    }


    @Test
    public void shouldFindStringWithPrefix() {
        String[] data = { //
                "David's cat is in his bedroom", //
                "I like the moon", //
                "I want to travel to Mars", //
                "My ball is red", //
                "They always forget about Antarctida", //
                "..." //
            };
        Arrays.sort(data);
        String found = findWithPrefix(data, "I want to");
        assertEquals("I want to travel to Mars", found);

    }

}
于 2012-11-30T02:32:40.733 回答
1

要么像以前那样做，要么变得更复杂。有一个名为“trie”的搜索结构，但这很复杂。

你可以通过让一个 a-z 数组指向你排序的 ArrayList 中第一个字母的起始位置来获得一点好处。然后，您只需在以相同字母开头的单词中进行搜索。

于 2012-11-29T22:47:06.980 回答
-1

或者您可以使用完全不同的方法。并包装 ArrayList 并检查 list.add() 是否匹配。并将其存储在某个 var 中以便快速访问。但是，如果您要搜索多个值，那么这种方法根本不好:)。

于 2012-11-29T22:47:54.873 回答
-3

下面是一个可用于获取每个项目的函数示例。这个速度并不是真正的增加。由于这是一个数组列表，因此没有真正的好方法来做到这一点。有更好的数据结构来搜索字符串的一部分。

    public class RegionMatchesDemo {
public static void main(String[] args) {
    String searchMe = "Green Eggs and Ham";
    String findMe = "Eggs";
    int searchMeLength = searchMe.length();
    int findMeLength = findMe.length();
    boolean foundIt = false;
    for (int i = 0; 
         i <= (searchMeLength - findMeLength);
         i++) {
       if (searchMe.regionMatches(i, findMe, 0, findMeLength)) {
          foundIt = true;
          System.out.println(searchMe.substring(i, i + findMeLength));
          break;
       }
    }
    if (!foundIt)
        System.out.println("No match found.");
  }
}
于 2012-11-29T22:45:33.123 回答