Блог

Главная - Вопросы по программированию - Самый быстрый способ сравнить строку с большим списком массивов

Самый быстрый способ сравнить строку с большим списком массивов

#java #string #arraylist

#java #строка #список массивов

Вопрос:

У меня есть программа обработки файлов.

В нем у меня есть метод, который проверяет имя файла (строку) на ArrayList соответствие имен файлов. Идея в том, что программе не нужно обрабатывать файлы, которые ArrayList уже находятся в.

Проблема, с которой я сталкиваюсь, заключается в том, что ArrayList может быть очень большим (16 000 элементов), и я перебираю примерно одинаковое количество файлов, так что проверка каждого файла на ArrayList соответствие занимает слишком много времени. Я думаю, это потому, что я использую .contains .

Существует ли более эффективный (т. Е. Более Быстрый) способ выполнения этих строк для 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());

                                           }
                                                     }
                                                          }

Комментарии:

1. Пожалуйста, правильно отформатируйте свой код. Прямо сейчас это нечитаемо.

2. Почему бы вместо этого не использовать HashSet?

3. Быстрее ли хэш-набор?

Ответ №1:

Вы должны использовать Set (HashSet или TreeSet).

Эти структуры данных позволяют вам проверять существование элемента в нем за время O (1) или O (log n) соответственно.

ArrayList сравнивает значение с каждым элементом, поэтому оно равно O(n).

Я бы рекомендовал вам использовать HashSet. Накладные расходы на его использование составляют около ~ 70 байт для каждой записи.

Комментарии:

1. HashSet поддерживает метод contains . Значит, я все еще могу использовать этот метод и получать более быстрые сравнения?

2. @SebastianZeki, да. Хотя метод имеет то же имя и проверяет, сохранен ли элемент, он работает совершенно по-другому под капотом и работает намного быстрее.

3. Хорошо, спасибо. Это здорово.

Ответ №2:

Прежде всего, вы должны использовать алгоритм поиска. Простым началом будет бинарный поиск. Это даст вам время обработки на lg (n) меньше n. (Например, 10 шагов вместо 1024);

Если список массивов меняется не так часто, вы можете выполнить этот поиск в любое время, используя другой поток (если у вас есть информация или время, чтобы сделать это раньше). И после того, как вы нашли результат, вы можете его кэшировать, вы будете удалять кеш, если список массивов изменился

Метки: