sort - java数组




我如何测试数组是否包含某个值? (16)

  1. 对于有限长度的数组,请使用以下内容(由camickr给出)。 这对重复检查来说很慢,特别是对于较长的阵列(线性搜索)。

     Arrays.asList(...).contains(...)
    
  2. 如果您反复检查更大的一组元素,可以获得更快的性能

    • 数组是错误的结构。 使用TreeSet并添加每个元素。 它对元素进行排序并具有快速的exist()方法(二进制搜索)。

    • 如果这些元素实现了Comparable您希望TreeSet进行排序:

      ElementClass.compareTo()方法必须与ElementClass.equals()兼容:请参阅三元组没有显示战斗? (Java集遗漏了一个项目)

      TreeSet myElements = new TreeSet();
      
      // Do this for each element (implementing *Comparable*)
      myElements.add(nextElement);
      
      // *Alternatively*, if an array is forceably provided from other code:
      myElements.addAll(Arrays.asList(myArray));
      
    • 否则,请使用您自己的Comparator

      class MyComparator implements Comparator<ElementClass> {
           int compareTo(ElementClass element1; ElementClass element2) {
                // Your comparison of elements
                // Should be consistent with object equality
           }
      
           boolean equals(Object otherComparator) {
                // Your equality of comparators
           }
      }
      
      
      // construct TreeSet with the comparator
      TreeSet myElements = new TreeSet(new MyComparator());
      
      // Do this for each element (implementing *Comparable*)
      myElements.add(nextElement);
      
    • 收益:检查一些元素的存在:

      // Fast binary search through sorted elements (performance ~ log(size)):
      boolean containsElement = myElements.exists(someElement);
      

我有一个String[] ,其值如下所示:

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

给定String s ,是否有一种测试VALUES是否包含s的好方法?


Arrays.asList =>然后应用contains()方法将始终有效,但搜索算法要好得多,因为首先,必须将Array转换为列表,然后调用contains方法,使开销加倍,查看我的意思? 这是因为它是O(n)创建列表和O(n)以包含通过顺序检查来查找元素。 当简单的线性搜索只做一次工作时,为什么会遭受O(n)两次。

public boolean findString(String[] strings, String desired){
   for(String s : strings){
       if (desired.equals(s)){
           return true;
       }
   }
   return false; //if we get here… there is no desired String, return false.
}

检查数组是否包含值的四种不同方法

1)使用列表:

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

2)使用Set:

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

3)使用一个简单的循环:

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

4)使用Arrays.binarySearch():

下面的代码是错误的,它在这里列出的完整性。 binarySearch()只能用于有序数组。 你会发现下面的结果很奇怪。 数组排序后,这是最好的选择。

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

快速示例:

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

一种可能的解决方

import java.util.Arrays;
import java.util.List;

public class ArrayContainsElement {
  public static final List<String> VALUES = Arrays.asList("AB", "BC", "CD", "AE");

  public static void main(String args[]) {

      if (VALUES.contains("AB")) {
          System.out.println("Contains");
      } else {
          System.out.println("Not contains");
      }
  }
}

使用Array.BinarySearch(array,obj)来查找数组中给定的对象。 例如:

if (Array.BinarySearch(str, i) > -1) - > true - 存在

假 - 不存在


使用Java 8,您可以创建一个流并检查流中的任何条目是否匹配"s"

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

或者作为一个通用的方法:

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

只需清除代码即可开始使用。 我们已经(更正):

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

这是一个可变的静态FindBugs会告诉你很淘气。 它应该是私人的:

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

(请注意,您实际上可以删除new String[];位)。

所以,引用数组是不好的,特别是在这里我们需要一个集合:

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

(如我自己那样的偏执狂的人,如果这个包裹在Collections.unmodifiableSet ,它可能会更放心 - 它甚至可以公开。)

“给定String,是否有一种测试VALUES是否包含s的好方法?”

VALUES.contains(s)

O(1)。


Java 8中使用Streams。

List<String> myList =
Arrays.asList("a1", "a2", "b1", "c2", "c1");

myList
.stream()
.filter(s -> s.startsWith("c"))
.map(String::toUpperCase)
.sorted()
.forEach(System.out::println);

如果数组未被排序,则必须遍历所有内容并在每个数组上调用equals。

如果数组已排序,则可以执行二分搜索, Arrays类中有一个。

一般来说,如果您要进行大量的会员检查,您可能希望将所有内容存储在Set中,而不是数组中。


它可以像下面这样简单:

String[] VALUE = new String[] {"AB","BC","CD","AE"};
Arrays.asList(VALUE).contains(s);

对于它的价值,我进行了一次测试,比较了3条速度建议。 我生成随机整数,将它们转换为一个字符串并将它们添加到数组中。 然后我搜索了最高可能的数字/字符串,这对asList()。contains()来说是最糟糕的情况。

当使用10K阵列尺寸时,结果如下:

Sort & Search   : 15
Binary Search   : 0
asList.contains : 0

当使用100K阵列时,结果如下:

Sort & Search   : 156
Binary Search   : 0
asList.contains : 32

因此,如果数组按照排序顺序创建,则二进制搜索是最快的,否则asList()。contains将是要走的路。 如果您有很多搜索,那么可能需要对数组进行排序,以便可以使用二进制搜索。 这一切都取决于你的应用程序。

我想这些都是大多数人期望的结果。 这里是测试代码:

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

尝试这个:

ArrayList<Integer> arrlist = new ArrayList<Integer>(8);

// use add() method to add elements in the list
arrlist.add(20);
arrlist.add(25);
arrlist.add(10);
arrlist.add(15);

boolean retval = arrlist.contains(10);
if (retval == true) {
    System.out.println("10 is contained in the list");
}
else {
    System.out.println("10 is not contained in the list");
}

您可以使用Arrays类对该值执行二进制搜索。 如果你的数组没有排序,你将不得不使用同一个类中的排序函数对数组进行排序,然后搜索它。


我很惊讶没有人建议只是简单地实施它:

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

改进:

v != null条件在方法内部是常量,它在方法调用期间总是计算为相同的布尔值。 因此,如果输入array很大,则只需评估一次该条件就会更有效,并且可以根据结果在for循环中使用简化/更快的条件。 改进的contains()方法:

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

检查这个

String[] VALUES = new String[] {"AB","BC","CD","AE"};
String s;

for(int i=0; i< VALUES.length ; i++)
{
    if ( VALUES[i].equals(s) )
    { 
        // do your stuff
    } 
    else{    
        //do your stuff
    }
}

而不是使用快速数组初始化语法,您可以使用Arrays.asList方法以类似方式直接将它初始化为List,例如:

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

然后你可以做(​​像上面): STRINGS.contains("the string you want to find");





arrays