Câu hỏi Làm thế nào tôi có thể kiểm tra nếu một mảng có chứa một giá trị nhất định?


tôi có một String[] với các giá trị như vậy:

public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

Được String s, có cách kiểm tra tốt hay không VALUES chứa đựng s?


1855
2017-07-15 00:03


gốc


Đường dài xung quanh nó, nhưng bạn có thể sử dụng vòng lặp for: "for (String s: VALUES) nếu (s.equals (" MYVALUE ")) trả về true; - Zack
Tại sao mọi người vẫn upvoting câu trả lời này (bây giờ 75)? Của nó 2 tuổi và một câu trả lời rất đơn giản. Tất cả những gì tôi đã làm là chỉ cho ai đó một phương pháp API. Tôi không nghĩ rằng bất kỳ câu trả lời là như vậy amiăng rằng nó xứng đáng này tháng mười một của upvotes. - camickr
@camickr. Đối với câu hỏi của bạn, tôi đã bỏ phiếu cho câu hỏi này và câu trả lời của bạn - vì nó đã lưu lại cho tôi 30 phút và 20 dòng mã viết xấu cho các vòng lặp, -now-. Đã không đọc nó ba năm trước. (BTW, cảm ơn :)) - Pursuit
@ camickr - Tôi có một tình huống gần như giống hệt nhau với điều này: stackoverflow.com/a/223929/12943  Nó chỉ tiếp tục nhận được phiếu bầu chỉ là một bản sao / dán từ tài liệu của mặt trời. Tôi đoán điểm số dựa trên mức độ giúp đỡ bạn cung cấp và không phải nỗ lực bạn đã bỏ ra bao nhiêu - và chủ yếu là bạn đăng nó nhanh như thế nào! Có lẽ chúng tôi đã vấp phải bí mật của John Skeet! Câu trả lời hay, +1 cho bạn. - Bill K
@camickr bởi vì mọi người, như tôi, google một câu hỏi, bấm vào kết quả SO, xem câu trả lời của bạn, kiểm tra nó, nó hoạt động, upvote câu trả lời và sau đó để lại. - Aequitas


Các câu trả lời:


Arrays.asList(yourArray).contains(yourValue)

Cảnh báo: điều này không làm việc cho các mảng nguyên thủy (xem các bình luận).


Bây giờ bạn có thể sử dụng Stream để kiểm tra xem một mảng int, double hoặc là long chứa một giá trị (tương ứng bằng cách sử dụng một IntStream, DoubleStream hoặc là LongStream)

Thí dụ

int[] a = {1,2,3,4};
boolean contains = IntStream.of(a).anyMatch(x -> x == 4);

2428
2017-07-15 00:04



Tôi hơi tò mò về hiệu suất của điều này so với các chức năng tìm kiếm trong lớp Mảng so với lặp qua một mảng và sử dụng hàm equals () hoặc == cho các nguyên thủy. - Thomas Owens
Bạn không bị mất nhiều, vì asList () trả về một ArrayList có một mảng ở trung tâm của nó. Các nhà xây dựng sẽ chỉ thay đổi một tham chiếu vì vậy đó không phải là nhiều việc phải làm ở đó. Và chứa () / indexOf () sẽ lặp lại và sử dụng equals (). Đối với nguyên thủy bạn nên tốt hơn off mã hóa nó cho mình, mặc dù. Đối với các chuỗi hoặc các lớp khác, sự khác biệt sẽ không đáng chú ý. - Joey
Odd, NetBeans tuyên bố rằng 'Arrays.asList (ngày nghỉ)' cho một ngày 'int []' trả về một 'danh sách <int []>', và không phải là 'danh sách <int>'. Nó chỉ chứa một phần tử duy nhất. Có nghĩa là các Contains không hoạt động vì nó chỉ có một phần tử; mảng int. - Nyerguds
Nyerguds: thực sự, điều này không làm việc cho các nguyên thủy. Trong các kiểu nguyên thủy java không thể là chung chung. asList được khai báo là <T> List <T> asList (T ...). Khi bạn truyền một int [] vào trong nó, trình biên dịch đưa vào T = int [] bởi vì nó không thể suy ra T = int, vì các nguyên thủy không thể là generic. - CromTheDestroyer
@ Chỉ là một lưu ý phụ, đó là một ArrayList, nhưng không java.util.ArrayList như bạn mong đợi, lớp thực sự trở lại là: java.util.Arrays.ArrayList<E> định nghĩa là: public class java.util.Arrays {private static class ArrayList<E> ... {}}. - TWiStErRob


Chỉ cần xóa mã để bắt đầu. Chúng tôi có (đã sửa):

public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

Đây là một tĩnh có thể thay đổi mà FindBugs sẽ cho bạn biết là rất nghịch ngợm. Nó phải là riêng tư:

private static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

(Lưu ý, bạn thực sự có thể thả new String[]; bit.)

Vì vậy, mảng tham chiếu là xấu, và đặc biệt ở đây chúng tôi muốn có một bộ:

private static final Set<String> VALUES = new HashSet<String>(Arrays.asList(
     new String[] {"AB","BC","CD","AE"}
));

(Những người hoang tưởng, như bản thân tôi, có thể cảm thấy thoải mái hơn nếu điều này được bao bọc trong Collections.unmodifiableSet - nó thậm chí có thể được công khai.)

"Cho String s, có cách nào tốt để kiểm tra xem VALUES có chứa s không?"

VALUES.contains(s)

O (1).


309
2017-07-15 01:13



Ngoại trừ O (N) để tạo bộ sưu tập ngay từ đầu :) - Drew Noakes
Nếu nó tĩnh, nó có thể sẽ được sử dụng khá nhiều lần. Vì vậy, thời gian tiêu thụ để khởi tạo các thiết lập có cơ hội tốt là khá nhỏ so với chi phí của rất nhiều tìm kiếm tuyến tính. - Xr.
Tạo ra sau đó bộ sưu tập sẽ bị chi phối bởi thời gian tải mã (đó là về mặt kỹ thuật O (n) nhưng thực tế không đổi). - Tom Hawtin - tackline
@ TomHawtin-tackline Tại sao bạn nói "đặc biệt ở đây chúng tôi muốn có một bộ"? Lợi thế của một Set (HashSet) trong trường hợp này là gì? Tại sao một "mảng tham chiếu" xấu (bởi "mảng tham chiếu", bạn có nghĩa là một ArrayList được hỗ trợ bởi một mảng được tạo ra bởi một cuộc gọi đến Arrays.asList)? - Basil Bourque
@nmr A TreeSet sẽ là O(log n). HashSets được chia tỷ lệ sao cho số lượng trung bình của các phần tử trong một xô gần như không đổi. Ít nhất là cho mảng lên đến 2 ^ 30. Có thể có những ảnh hưởng từ bộ nhớ cache phần cứng mà phân tích lớn-O bỏ qua. Cũng giả sử hàm băm hoạt động hiệu quả. - Tom Hawtin - tackline


Bạn có thể dùng ArrayUtils.contains từ Apache Commons Lang

public static boolean contains(Object[] array, Object objectToFind)

Lưu ý rằng phương thức này trả về false nếu mảng đã qua là null.

Ngoài ra còn có các phương pháp có sẵn cho các mảng nguyên thủy của tất cả các loại.

Thí dụ:

String[] fieldsToInclude = { "id", "name", "location" };

if ( ArrayUtils.contains( fieldsToInclude, "id" ) ) {
    // Do some stuff.
}

171
2018-05-31 13:17



Thư viện 300kb cho ứng dụng Android 78kb, không phải lúc nào cũng tốt - max4ever
@ max4ever Tôi đồng ý, nhưng điều này vẫn còn tốt hơn sau đó "lăn của riêng bạn" và dễ dàng hơn để đọc sau đó cách java nguyên. - Jason
gói: org.apache.commons.lang.ArrayUtils - slamborne
@ max4ever Đôi khi bạn đã có sẵn thư viện này (vì các lý do khác) và đó là câu trả lời hoàn toàn hợp lệ. Tôi đã tìm kiếm điều này và tôi đã phụ thuộc vào Apache Commons Lang. Cảm ơn câu trả lời này. - GuiSim
@ max4ever Hầu hết các ứng dụng Android được tối thiểu hóa bởi Proguard, chỉ đặt các lớp và chức năng bạn cần vào ứng dụng của mình. Điều đó làm cho nó tương đương với cuộn của riêng bạn, hoặc sao chép nguồn gốc của điều apache. Và bất cứ ai không sử dụng tối thiểu hóa đó không cần phải phàn nàn về 700kb hoặc 78kb :) - Kenyakorn Ketsombut


Tôi ngạc nhiên không ai đề nghị chỉ đơn giản là thực hiện nó bằng tay:

public static <T> boolean contains(final T[] array, final T v) {
    for (final T e : array)
        if (e == v || v != null && v.equals(e))
            return true;

    return false;
}

Cải tiến:

Các v != null điều kiện là hằng số bên trong phương thức, nó luôn luôn đánh giá cùng giá trị boolean trong suốt cuộc gọi phương thức. Vì vậy, nếu đầu vào array là lớn, hiệu quả hơn để đánh giá tình trạng này chỉ một lần và chúng tôi có thể sử dụng điều kiện đơn giản / nhanh hơn bên trong for vòng lặp dựa trên kết quả. Cải tiến contains() phương pháp:

public static <T> boolean contains2(final T[] array, final T v) {
    if (v == null) {
        for (final T e : array)
            if (e == null)
                return true;
    } else {
        for (final T e : array)
            if (e == v || v.equals(e))
                return true;
    }

    return false;
}

142
2017-09-28 07:45



@ Phoexo Giải pháp này rõ ràng là nhanh hơn bởi vì câu trả lời được chấp nhận kết thúc tốt đẹp mảng vào danh sách, và gọi phương thức contains () trong danh sách đó trong khi giải pháp của tôi về cơ bản làm những gì chứa () chỉ có thể làm. - icza
@AlastorMoody e == v thực hiện kiểm tra bình đẳng tham chiếu rất nhanh. Nếu cùng một đối tượng (cùng tham chiếu) nằm trong mảng, nó sẽ được tìm thấy nhanh hơn. Nếu nó không phải là cùng một thể hiện, nó vẫn có thể giống như được xác nhận bởi phương thức equals (), đây là những gì được kiểm tra nếu các tham chiếu không giống nhau. - icza
Tại sao không phải là một phần chức năng của Java? Không có gì ngạc nhiên khi mọi người nói Java đang cồng kềnh ... hãy nhìn vào tất cả các câu trả lời ở trên điều này sử dụng một loạt các thư viện khi tất cả những gì bạn cần là một vòng lặp for. Bọn nhóc thời nay! - phreakhead
@phreakhead Đây là một phần của Java, xem Collection.contains(Object) - Steve Kuo
@icza Nếu bạn nhìn vào nguồn gốc của Arrays và ArrayList nó chỉ ra rằng điều này không nhất thiết phải nhanh hơn phiên bản sử dụng Arrays.asList(...).contains(...). Phần trên của việc tạo ra một ArrayList cực kỳ nhỏ, và ArrayList.contains() sử dụng vòng lặp thông minh hơn (thực tế nó sử dụng hai vòng lặp khác nhau) so với vòng lặp được hiển thị ở trên (JDK 7). - Axel


Nếu mảng không được sắp xếp, bạn sẽ phải lặp qua tất cả mọi thứ và thực hiện cuộc gọi bằng nhau.

Nếu mảng được sắp xếp, bạn có thể thực hiện tìm kiếm nhị phân, có một trong Mảng lớp học.

Nói chung, nếu bạn định thực hiện rất nhiều kiểm tra thành viên, bạn có thể muốn lưu trữ mọi thứ trong một Set, không phải trong một mảng.


65
2017-07-15 00:05



Ngoài ra, như tôi đã nói trong câu trả lời của tôi, nếu bạn sử dụng lớp Arrays, bạn có thể sắp xếp mảng sau đó thực hiện tìm kiếm nhị phân trên mảng mới được sắp xếp. - Thomas Owens
@ Thomas: Tôi đồng ý. Hoặc bạn chỉ có thể thêm mọi thứ vào một TreeSet; cùng một sự phức tạp. Tôi sẽ sử dụng các mảng nếu nó không thay đổi (có thể tiết kiệm một chút địa phương bộ nhớ vì các tài liệu tham khảo được đặt liền kề mặc dù các chuỗi không). Tôi sẽ sử dụng thiết lập nếu điều này sẽ thay đổi theo thời gian. - Uri


Bốn cách khác nhau để kiểm tra nếu một mảng chứa một giá trị

1) Sử dụng Danh sách:

public static boolean useList(String[] arr, String targetValue) {
    return Arrays.asList(arr).contains(targetValue);
}

2) Sử dụng Set:

public static boolean useSet(String[] arr, String targetValue) {
    Set<String> set = new HashSet<String>(Arrays.asList(arr));
    return set.contains(targetValue);
}

3) Sử dụng một vòng lặp đơn giản:

public static boolean useLoop(String[] arr, String targetValue) {
    for (String s: arr) {
        if (s.equals(targetValue))
            return true;
    }
    return false;
}

4) Sử dụng Arrays.binarySearch ():

Mã dưới đây là sai, nó được liệt kê ở đây để hoàn thành. binarySearch () CHỈ có thể được sử dụng trên các mảng được sắp xếp. Bạn sẽ thấy kết quả là lạ bên dưới. Đây là tùy chọn tốt nhất khi sắp xếp mảng.

public static boolean binarySearch(String[] arr, String targetValue) {  
            int a = Arrays.binarySearch(arr, targetValue);
            return a > 0;
        }

Ví dụ nhanh:

String testValue="test";
String newValueNotInList="newValue";
String[] valueArray = { "this", "is", "java" , "test" };
Arrays.asList(valueArray).contains(testValue); // returns true
Arrays.asList(valueArray).contains(newValueNotInList); // returns false

59
2018-05-07 19:14



ví dụ tìm kiếm nhị phân của bạn phải trả về a> 0; - Will Sherwood
Tại sao? Tôi nghĩ rằng nó sẽ trả về một -1 -1, vì 0 sẽ chỉ ra rằng nó được chứa ở phần đầu của mảng. - mbelow
Biến thể đầu tiên với (a >= 0) đã đúng, chỉ cần kiểm tra tài liệu, họ nói "Lưu ý rằng điều này đảm bảo rằng giá trị trả về sẽ là> = 0 nếu và chỉ khi tìm thấy khóa". - Yoory N.


Đối với những gì giá trị của nó tôi chạy một thử nghiệm so sánh 3 đề xuất cho tốc độ. Tôi tạo ra các số nguyên ngẫu nhiên, chuyển đổi chúng thành một String và thêm chúng vào một mảng. Sau đó tôi đã tìm kiếm số / chuỗi có thể cao nhất, đó sẽ là trường hợp xấu nhất cho asList (). Contains ().

Khi sử dụng kích thước mảng 10K, kết quả trong đó:

Sắp xếp & Tìm kiếm: 15
Tìm kiếm nhị phân: 0
asList.contains: 0

Khi sử dụng một mảng 100K kết quả trong đó:

Sắp xếp & Tìm kiếm: 156
Tìm kiếm nhị phân: 0
asList.contains: 32

Vì vậy, nếu mảng được tạo theo thứ tự sắp xếp thì tìm kiếm nhị phân là nhanh nhất, nếu không thì hàm asList () chứa sẽ là cách để đi. Nếu bạn có nhiều tìm kiếm, thì có thể đáng giá để sắp xếp mảng để bạn có thể sử dụng tìm kiếm nhị phân. Tất cả phụ thuộc vào ứng dụng của bạn.

Tôi nghĩ đó là những kết quả mà hầu hết mọi người mong đợi. Đây là mã thử nghiệm:

import java.util.*;

public class Test
{
    public static void main(String args[])
    {
        long start = 0;
        int size = 100000;
        String[] strings = new String[size];
        Random random = new Random();


        for (int i = 0; i < size; i++)
            strings[i] = "" + random.nextInt( size );

        start = System.currentTimeMillis();
        Arrays.sort(strings);
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Sort & Search : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Search        : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.asList(strings).contains( "" + (size - 1) ));
        System.out.println("Contains      : " + (System.currentTimeMillis() - start));
    }
}

46
2017-07-15 01:28



Tôi không hiểu mã này. Bạn sắp xếp mảng 'chuỗi' và sử dụng cùng một mảng (được sắp xếp) trong cả hai lệnh gọi đến binarySearch. Làm thế nào nó có thể hiển thị bất cứ điều gì ngoại trừ tối ưu hóa thời gian chạy của HotSpot? Cùng với cuộc gọi asList.contains. Bạn tạo một danh sách từ mảng được sắp xếp và sau đó có chứa nó với giá trị cao nhất. Tất nhiên nó sẽ mất thời gian. Ý nghĩa của thử nghiệm này là gì? Chưa kể đến việc viết một microbenchmark không đúng cách - Erik
Ngoài ra, vì tìm kiếm nhị phân chỉ có thể được áp dụng cho một tập hợp được sắp xếp, sắp xếp và tìm kiếm là cách duy nhất có thể sử dụng tìm kiếm nhị phân. - Erik
Sắp xếp có thể đã được thực hiện vì một số lý do khác, ví dụ: có thể sắp xếp nó trên init và không bao giờ thay đổi. Có sử dụng trong thời gian thử nghiệm tìm kiếm của riêng mình. Tuy nhiên, khi điều này rơi xuống là một ví dụ ít xuất sắc hơn về việc đánh dấu vi sinh vật. Microbenchmarks nổi tiếng là khó có được quyền trong Java và ví dụ như thực thi mã kiểm tra đủ để có được tối ưu hóa điểm phát sóng trước khi chạy thử nghiệm thực tế, hãy để một mình chạy mã thử nghiệm thực tế nhiều hơn ONCE với bộ hẹn giờ. Cạm bẫy ví dụ - Thor84no
Bài kiểm tra này là thiếu sót khi chạy tất cả 3 bài kiểm tra trong tương tự Ví dụ JVM. Các bài kiểm tra sau này có thể được hưởng lợi từ những bài trước đó làm ấm bộ nhớ cache, JIT, v.v. - Steve Kuo
Thử nghiệm này thực sự hoàn toàn không liên quan. Sắp xếp & Tìm kiếm là sự phức tạp tuyến tính (n * log (n)), tìm kiếm nhị phân là logarit và ArrayUtils.contains rõ ràng là tuyến tính. Nó không sử dụng để so sánh các giải pháp này vì chúng nằm trong các lớp phức tạp hoàn toàn khác nhau. - dragn


Thay vì sử dụng cú pháp khởi tạo mảng nhanh để bạn có thể chỉ khởi tạo nó như một Danh sách ngay lập tức theo cách tương tự bằng cách sử dụng phương thức Arrays.asList, ví dụ:

public static final List<String> STRINGS = Arrays.asList("firstString", "secondString" ...., "lastString");

Sau đó, bạn có thể làm (như trên): STRINGS.contains("the string you want to find");


29
2018-01-20 13:58