2

複数のアイテムを含む配列リストがあります。それらが「ダークブラウン」、「ブルー」、「グリーン」、....であるとしましょう。

一部のアイテムに「DARK」という文字列があるかどうかを調べる方法はありますか? contains がこれを行うことは知っていますが、文字列が正確である場合にのみ行います。私の考えは、アイテムの 1 つで始まるが、最後の文字がすべて含まれていないテキストを探すことです。

私は次のようなループを行うことを考えています:

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

ただし、arraylist には多くの要素を含めることができるため、非常に遅い方法のようです。より良いアイデアはありますか？

編集

あなたが私の言いたいことを理解していることを確認するためです。arraylist の項目にテキストで始まる要素が含まれているかどうかを知り、その要素の完全なテキストを取得したいと考えています。ArrayList.contains はブール値です。情報を取得する必要がある場合は、IndexOf などを使用する必要がありますが、「茶色」を入力すると、この関数は null を返します

編集2

これはあなたのためです auselen:

Arraylist (5000 要素程度):

  • 「デビッドの猫は彼の寝室にいます」
  • 「月が好き」
  • 「火星に行きたい」
  • 「私のボールは赤い」
  • 「彼らはいつも南極大陸のことを忘れている」
  • ...

「したい」で始まる要素があるかどうかを知り、残りの要素を取得したい。

4

5 に答える 5

2

文字列をsorted（！）配列に保持しbinarysearch、プレフィックスの挿入ポイントを見つけるために使用します。試合は、仮にあったとしても、その時点で行われます。

これがO（n）ではなくO （log 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 に答える
2

配列リストには多くの要素を含めることができるため、非常に遅い方法のようです。

100万くらい？

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 に答える
1

今までと同じようにするか、もっと複雑にするかのどちらかです。「トライ」という検索構造がありますが、これは複雑です。

最初の文字の並べ替えられた ArrayList の開始位置を指す a-z の配列を持つことで、少し得ることができます。次に、同じ文字で始まる単語内を検索するだけです。

于 2012-11-29T22:47:06.980 に答える
-1

または、完全に異なるアプローチを使用できます。ArrayList をラップし、list.add() で一致をチェックします。そして、すぐにアクセスできるように、それをいくつかの変数に保存します。ただし、検索する値が複数ある場合、このアプローチはまったく適していません:)。

于 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 に答える