java将字符串与大型arrayList进行比较的最快方法

Question

我有一个文件处理程序

在它中，我有一个方法，可以根据ArrayList个文件名检查文件名（字符串）。其想法是，该程序不必处理ArrayList中已经存在的文件

我遇到的问题是ArrayList可能非常大（16000个元素），并且我正在迭代大约相同数量的文件，因此根据ArrayList检查每个文件需要花费太多时间。我想这是因为我在使用.contains

是否有一种更有效（即更快）的方法来执行这些与非常大的ArrayList的字符串到ArrayList比较，或者我应该存储在不同的数据结构中

我的代码：

public class Iterator {
    static ArrayList<String> myFiles = new ArrayList<String>();
    static String filename= "/Files/FilesLogged.txt";

    public static void main(String[] args) throws IOException, SAXException, TikaException, SQLException, ParseException, URISyntaxException, BackingStoreException {       
    BufferedReader reader = new BufferedReader(new InputStreamReader(ClassLoader.class.getResourceAsStream(filename)),2048);
        String line = null;

        while((line = reader.readLine()) != null) {
            myFiles.add(line);
        }
            reader.close();
        }  

    public static void loopthrough(String folderName) throws IOException, SAXException, TikaException, SQLException, ParseException, URISyntaxException{
        System.out.println("This is the loopthrough folderName"+folderName);
        File dir = new File(folderName);
        File[] directoryListing = dir.listFiles();        

            if (directoryListing != null) {                   
                for (File child : directoryListing) {
                    if(!myFiles.contains(child.getName())){

             System.out.println("THE FILE NAMES ARE"+child.getName().toString());

                                           }
                                                     }
                                                          }

Answer 1

首先，你应该使用搜索算法。一个简单的开始就是二进制搜索。这将使您的处理时间从n减少到lg（n）（例如10步而不是1024步）

如果ArrayList没有经常更改，您可以随时使用另一个线程进行搜索（如果您之前有信息或时间这样做的话）。找到结果后，可以缓存它，如果ArrayList发生了更改，则将删除缓存

Answer 2

你应该使用Set（HashSet或TreeSet）

此数据结构允许您分别检查其中元素在时间O（1）或O（logn）中的存在性

ArrayList将值与每个元素进行比较，因此它是O（n）

我建议您使用HashSet。使用它的开销是每个条目大约70字节