Pytanie Jak mogę sprawdzić, czy tablica zawiera określoną wartość?


mam String[] z wartościami takimi jak:

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

Dany String s, czy istnieje dobry sposób na sprawdzenie, czy VALUES zawiera s?


1855
2017-07-15 00:03


pochodzenie


Długa droga wokół niego, ale możesz użyć pętli for: "for (String s: VALUES) if (s.equals (" MYVALUE ")) zwraca true; - Zack
Dlaczego ludzie wciąż przegłosowują tę odpowiedź (obecnie 75)? Jego 2 lata i bardzo prosta odpowiedź. Wszystko, co zrobiłem, to skierować kogoś do metody API. Nie sądzę, aby jakakolwiek odpowiedź była tak ammazująca, że ​​zasługuje na ten listopadowy przegrany. - camickr
@camickr. Na twoje pytanie przegłosowałem to pytanie i twoją odpowiedź -now- ponieważ dzięki temu zaoszczędziłem 30 minut i 20 linii kodu piszących brzydko dla pętli, -now-. Nie czytałem tego trzy lata temu. (BTW, dzięki :)) - Pursuit
@ camickr - Mam prawie identyczną sytuację z tym: stackoverflow.com/a/223929/12943  Po prostu zdobywa się głosy, ale była tylko kopią / wklejaniem z dokumentacji Sun'a. Sądzę, że wynik opiera się na tym, ile pomocy ci dostarczyłeś, a nie ile wysiłku w to włożyłeś - a przede wszystkim, jak szybko to publikujesz! Może natknęliśmy się na sekret Johna Skeeta! Dobra odpowiedź, +1 dla ciebie. - Bill K
@camickr, ponieważ ludzie, tacy jak ja, google pytanie, kliknij na wynik SO, zobacz swoją odpowiedź, przetestuj go, działa, przegłosuj odpowiedź, a następnie odejdź. - Aequitas


Odpowiedzi:


Arrays.asList(yourArray).contains(yourValue)

Ostrzeżenie: to nie działa dla tablic prymitywów (zobacz komentarze).


Od

Możesz teraz użyć a Stream aby sprawdzić, czy tablica int, double lub long zawiera wartość (odpowiednio za pomocą IntStream, DoubleStream lub LongStream)

Przykład

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

2428
2017-07-15 00:04



Jestem nieco ciekawy co do wydajności tego w porównaniu do funkcji wyszukiwania w klasie Arrays w porównaniu do iteracji po tablicy i użycia funkcji equals () lub == dla prymitywów. - Thomas Owens
Nie tracisz wiele, ponieważ asList () zwraca tablicę ArrayList, która ma tablicę w swoim sercu. Konstruktor po prostu zmieni odniesienie, więc nie będzie tam wiele pracy. I zawiera () / indexOf () będzie iterować i używać equals (). Dla prymitywów powinieneś jednak lepiej kodować to samemu. W przypadku ciągów lub innych klas różnica nie będzie zauważalna. - Joey
Nieparzyste, NetBeans twierdzi, że "Arrays.asList (wakacje)" dla "int [] wakacji" zwraca "listę <int []>", a nie "listę <int>". Zawiera tylko jeden element. Znaczenie Contains nie działa, ponieważ ma tylko jeden element; tablica int. - Nyerguds
Nyerguds: w rzeczy samej, to nie działa dla prymitywów. W typach pierwotnych java nie można generic. asList jest zadeklarowany jako <T> Lista <T> asList (T ...). Kiedy przekazujesz do niego int [], kompilator podaje T = int [], ponieważ nie może wywnioskować T = int, ponieważ prymitywy nie mogą być generyczne. - CromTheDestroyer
@Jeyey tylko notatkę, to jest ArrayList, ale nie java.util.ArrayList zgodnie z oczekiwaniami, prawdziwą klasą zwróconą jest: java.util.Arrays.ArrayList<E> zdefiniowana jako: public class java.util.Arrays {private static class ArrayList<E> ... {}}. - TWiStErRob


Wystarczy wyczyścić kod, aby rozpocząć. Mamy (poprawione):

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

Jest to zmienna statyczna, która FindBugs powie ci, że jest bardzo niegrzeczna. Powinno być prywatne:

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

(Uwaga, możesz faktycznie upuścić new String[]; kawałek.)

A więc tablice referencyjne są złe, a w szczególności tutaj chcemy ustawić:

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

(Paranoiczni ludzie, tacy jak ja, mogą czuć się bardziej swobodnie, jeśli się to zapakuje Collections.unmodifiableSet - może nawet zostać upublicznione.)

"Given String s, czy istnieje dobry sposób na sprawdzenie, czy VALUES zawiera s?"

VALUES.contains(s)

O (1).


309
2017-07-15 01:13



Poza tym, że to O (N), aby stworzyć kolekcję na pierwszym miejscu :) - Drew Noakes
Jeśli jest statyczny, prawdopodobnie zostanie użyty kilka razy. Czas potrzebny na zainicjowanie zestawu ma duże szanse na to, że będzie on niewielki w porównaniu z kosztami wielu liniowych wyszukiwań. - Xr.
Wówczas tworzenie kolekcji będzie zdominowane przez czas ładowania kodu (który jest technicznie O (n), ale praktycznie stały). - Tom Hawtin - tackline
@ TomHawtin-tackline Dlaczego mówisz "w szczególności tutaj chcemy zestawu"? Jaka jest zaleta zestawu (HashSet) w tym przypadku? Dlaczego "tablica referencyjna" jest zła (przez "tablicę referencyjną" oznacza tablicę ArrayList wspieraną przez tablicę generowaną przez wywołanie Arrays.asList)? - Basil Bourque
@ nmr TreeSet byłoby O(log n). HashSets są skalowane w taki sposób, że średnia liczba elementów w wiadrze jest w przybliżeniu stała. Przynajmniej dla tablic do 2 ^ 30. Mogą wystąpić wpływy z, powiedzmy, pamięci podręcznych sprzętowych, które ignoruje analiza big-o. Zakłada również, że funkcja hash działa skutecznie. - Tom Hawtin - tackline


Możesz użyć ArrayUtils.contains od Apache Commons Lang

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

Zwróć uwagę, że ta metoda zwraca false jeśli przekazana tablica jest null.

Istnieją również metody dostępne dla prymitywnych tablic wszelkiego rodzaju.

Przykład:

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

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

171
2018-05-31 13:17



Biblioteka 300 kb dla aplikacji Android 78kb, nie zawsze jest dobra - max4ever
@ max4ever Zgadzam się, ale to jest jeszcze lepsze niż "toczenie własne" i łatwiejsze do odczytania niż surowy sposób Java. - Jason
pakiet: org.apache.commons.lang.ArrayUtils - slamborne
@ max4ever Czasami masz już tę bibliotekę (z innych powodów) i jest to całkowicie poprawna odpowiedź. Szukałem tego i już polegam na Apache Commons Lang. Dziękuję za tę odpowiedź. - GuiSim
@ max4ever Większość aplikacji na Androida jest minimalizowana przez Proguard, umieszczając tylko klasy i funkcje, które potrzebujesz w swojej aplikacji. To sprawia, że ​​jest to równe rzucaniu własnymi, lub kopiowaniu źródła apache. A ktokolwiek nie używa tej minimalizacji, nie musi narzekać na 700kb lub 78kb :) - Kenyakorn Ketsombut


Jestem zaskoczony, nikt nie zaproponował po prostu wdrożyć go ręcznie:

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;
}

Poprawa:

The v != null warunek jest stały wewnątrz metody, zawsze zwraca wartość tej samej wartości logicznej podczas wywołania metody. Więc jeśli wejście array jest duży, bardziej efektywny jest ocenianie tego stanu tylko raz i możemy użyć uproszczonego / szybszego warunku wewnątrz for pętla oparta na wyniku. Ulepszone contains() metoda:

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 To rozwiązanie jest oczywiście szybsze, ponieważ zaakceptowana odpowiedź opakowuje tablicę na listę i wywołuje metodę contains () na tej liście, podczas gdy moje rozwiązanie w zasadzie robi to, co zawiera tylko (). - icza
@AlastorMoody e == v wykonuje referencyjną kontrolę równości, która jest bardzo szybka. Jeśli ten sam obiekt (ten sam przez odniesienie) znajduje się w tablicy, zostanie znaleziony szybciej. Jeśli nie jest to ta sama instancja, nadal może być taka sama jak deklarowana przez metodę equals (), jest to sprawdzane, jeśli odwołania nie są takie same. - icza
Dlaczego ta funkcja nie jest częścią Java? Nic dziwnego, że ludzie mówią, że Java jest nadęta ... spójrz na wszystkie odpowiedzi powyżej, które używają garstki bibliotek, kiedy wszystko czego potrzebujesz to pętla for. Dzieci w tych czasach! - phreakhead
@phreakhead Jest częścią Java, zobacz Collection.contains(Object) - Steve Kuo
@icza Jeśli spojrzysz na źródło Arrays i ArrayList okazuje się, że nie jest to koniecznie szybsze od używanej wersji Arrays.asList(...).contains(...). Obciążenie tworzenia ArrayList jest bardzo mały, i ArrayList.contains() używa inteligentniejszej pętli (w rzeczywistości używa dwóch różnych pętli) niż pokazana powyżej (JDK 7). - Axel


Jeśli tablica nie jest posortowana, będziesz musiał powtórzyć wszystko i nawiązywać połączenia z równymi.

Jeśli tablica jest posortowana, możesz wykonać wyszukiwanie binarne, które znajduje się w Tablice klasa.

Ogólnie mówiąc, jeśli zamierzasz przeprowadzić wiele testów członkostwa, możesz chcieć przechowywać wszystko w zestawie, a nie w tablicy.


65
2017-07-15 00:05



Podobnie jak powiedziałem w mojej odpowiedzi, jeśli używasz klasy Arrays, możesz posortować tablicę, a następnie przeprowadzić wyszukiwanie binarne w nowo posortowanej tablicy. - Thomas Owens
@Thomas: Zgadzam się. Lub możesz po prostu dodać wszystko do TreeSet; taka sama złożoność. Użyłbym tablic, jeśli się nie zmieni (może zapisać trochę miejsca w pamięci, ponieważ odwołania sąsiadują ze sobą, chociaż ciągi nie są). Używałbym tego zestawu, gdyby to się zmieniało z czasem. - Uri


Cztery różne sposoby sprawdzania, czy tablica zawiera wartość

1) Korzystanie z listy:

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

2) Korzystanie z zestawu:

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

3) Za pomocą prostej pętli:

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

4) Korzystanie z Arrays.binarySearch ():

Poniższy kod jest niepoprawny, jest tutaj wymieniony dla kompletności. Funkcja binarySearch () może być używana TYLKO na posortowanych tablicach. Przekonasz się, że wynik jest dziwny poniżej. Jest to najlepsza opcja, gdy tablica jest posortowana.

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

Szybki przykład:

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



Twój przykład wyszukiwania binarnego powinien zwrócić wartość> 0; - Will Sherwood
Czemu? Myślę, że powinien on zwrócić wartość> -1, ponieważ 0 oznacza, że ​​jest zawarte na początku tablicy. - mbelow
Pierwszy wariant z (a >= 0) było poprawne, po prostu sprawdź doktorzy, mówią: "Zauważ, że to gwarantuje, że zwracana wartość będzie> = 0 wtedy i tylko wtedy, gdy klucz zostanie znaleziony". - Yoory N.


Na ile to było możliwe, przeprowadziłem test porównując 3 sugestie dotyczące prędkości. Wygenerowałem losowe liczby całkowite, przekonwertowałem je na ciąg i dodałem do tablicy. Następnie szukałem możliwie największej liczby / ciągu znaków, co byłoby najgorszym scenariuszem dla asList (). Contains ().

Podczas korzystania z rozmiaru tablicy 10K wyniki:

Sortowanie i wyszukiwanie: 15
Wyszukiwanie binarne: 0
asList.contains: 0

Podczas korzystania z tablicy 100K wyniki:

Sortuj i wyszukaj: 156
Wyszukiwanie binarne: 0
asList.contains: 32

Zatem jeśli tablica jest tworzona w porządku posortowanym, wyszukiwanie binarne jest najszybsze, w przeciwnym razie sposób, w jaki będzie można przejść do asList (). Jeśli masz wiele wyszukiwań, może warto sortować tablicę, aby móc korzystać z wyszukiwania binarnego. Wszystko zależy od twojej aplikacji.

Sądzę, że są to wyniki, których większość ludzi by się spodziewała. Oto kod testowy:

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



Nie rozumiem tego kodu. Sortujesz ciągi tablicowe i używasz tej samej (posortowanej) tablicy w obu wywołaniach do binarySearch. Jak może to pokazać cokolwiek oprócz optymalizacji środowiska wykonawczego HotSpot? To samo z wywołaniem asList.contains. Tworzysz listę z posortowanej tablicy, a następnie zawiera ona na niej najwyższą wartość. Oczywiście to zajmie trochę czasu. Jakie jest znaczenie tego testu? Nie wspominając już o byciu niewłaściwie napisanym mikrobenkiem - Erik
Ponadto, ponieważ wyszukiwanie binarne można zastosować tylko do posortowanego zestawu, sortowanie i wyszukiwanie jest jedynym możliwym sposobem użycia wyszukiwania binarnego. - Erik
Sortowanie może już być wykonane z wielu innych powodów, np. Może być posortowane na init i nigdy nie zmienione. Ma zastosowanie w samodzielnym testowaniu czasu wyszukiwania. Tam, gdzie to spada, jest to mniej niż gwiezdny przykład mikrobezpieczenia. Microbenchmarks są bardzo trudne do uzyskania w Javie i powinny na przykład obejmować wykonanie kodu testowego na tyle, aby uzyskać optymalizację hotspotu przed uruchomieniem rzeczywistego testu, nie mówiąc już o uruchomieniu aktualnego kodu testowego więcej niż RAZ z timerem. Przykładowe pułapki - Thor84no
Ten test jest wadliwy, ponieważ wykonuje wszystkie 3 testy w podobnie Instancja JVM. Późniejsze testy mogą przynieść korzyści wcześniejszym nagrzewaniu pamięci podręcznej, JIT itp - Steve Kuo
Ten test jest w rzeczywistości całkowicie niepowiązany. Sort & Search jest złożonością linearithmic (n * log (n)), wyszukiwanie binarne jest logarytmiczne, a ArrayUtils.contains jest oczywiście liniowe. Porównywanie tych rozwiązań nie ma sensu, ponieważ są one w zupełnie różnych klasach złożoności. - dragn


Zamiast używać składni inicjałów szybkiej tablicy, możesz od razu ją zainicjować jako List w podobny sposób, używając metody Arrays.asList np .:

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

Następnie możesz zrobić (jak wyżej): STRINGS.contains("the string you want to find");


29
2018-01-20 13:58





W języku Java 8 można utworzyć strumień i sprawdzić, czy pasują do niego jakiekolwiek wpisy w strumieniu "s":

String[] values = {"AB","BC","CD","AE"};
boolean sInArray = Arrays.stream(values).anyMatch("s"::equals);

Lub jako metoda generyczna:

public static <T> boolean arrayContains(T[] array, T value) {
    return Arrays.stream(array).anyMatch(value::equals);
}

29
2018-03-13 14:53



Warto również zwrócić uwagę na prymitywne specjalizacje. - skiwi
Aby dodać, anyMatch JavaDoc stwierdza, że ​​to "...May not evaluate the predicate on all elements if not necessary for determining the result.", więc może nie być konieczne kontynuowanie przetwarzania po znalezieniu dopasowania. - mkobit


Możesz użyć Arrays class wykonać binarne wyszukiwanie wartości. Jeśli twoja tablica nie jest posortowana, będziesz musiał użyć funkcji sortowania w tej samej klasie, aby posortować tablicę, a następnie przeszukać ją.


22
2017-07-15 00:05



Możesz użyć funkcji sortowania w tej samej klasie, aby to osiągnąć ... Powinienem dodać to do mojej odpowiedzi. - Thomas Owens
Prawdopodobnie będzie to kosztować więcej niż podejście asList (). Contains (). O ile nie musisz tego robić bardzo często (ale jeśli jest to po prostu statyczna lista wartości, które można sortować na początek, aby być uczciwym). - Joey
Prawdziwe. Istnieje wiele zmiennych, które byłyby najbardziej skuteczne. Jednak dobrze mieć opcje. - Thomas Owens
Czy mógłbyś nam pokazać, jak można to zrobić? - AHH
Jakiś kod, który robi to tutaj: stackoverflow.com/a/48242328/9131078 - O.O.Balance


ObStupidAnswer (ale myślę, że gdzieś tu jest lekcja):

enum Values {
    AB, BC, CD, AE
}

try {
    Values.valueOf(s);
    return true;
} catch (IllegalArgumentException exc) {
    return false;
}

15
2017-07-15 01:18



Rzucanie wyjątkami jest najwyraźniej ciężkie, ale byłby to nowatorski sposób testowania wartości, gdyby działał. Minusem jest to, że enum musi zostać zdefiniowane wcześniej. - James P.