Как ускорить код поиска на java?

#java #поиск #производительность

Как ускорить код? При изменении ввода/вывода система отказывается принимать, поэтому
нужно оставить неприкосновенный Scan. На данный момент проходит за 1070 мс, нужно ускорить
до 1000 мс. Приветствуются любые идеи!

import java.util.Scanner;

class Main {
    public static boolean find(int search, int[] arr, int len) {
        boolean ret = false;
        int fst = 0;
        int lst = len - 1;
        if ( arr != null){
            while (fst <= lst) {
                int mid = (fst + lst) >>> 1;
                if (search == arr[mid]) {
                    ret = true;
                    break;
                } else if (search < arr[mid]) {
                    lst = mid - 1;
                } else {
                    fst = mid + 1;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int len = scan.nextInt();
        int[] arr = new int[len];
        int i;
        for (i = 0; i < len; i++) {
            arr[i] = scan.nextInt();
        }
        int num = scan.nextInt();
        int search;
        for (i = 0; i < num; i++) {
            search = scan.nextInt();
            System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
        }
    }
}

    

Ответы

Ответ 1

Не трогая собственно дихотомический поиск, предложу модификации:

//убран лишний параметр len + упрощаем вызов private дешевле public
private static boolean find(int search, int[] arr) {
    //boolean ret = false; //лишняя декларация - фтопку
    int mid;
    if ( arr == null)
       return false; 
    int fst = 0;
    int lst = arr.length - 1;
    while (fst < lst) {
        mid = (fst + lst) >>> 1;  //убираем декларацию mid - зачем нам лишнее движение
в стеке?
        if (search == arr[mid]) 
            return true; //убираем break
        else if (search < arr[mid]) 
            lst = --mid;
        else 
            fst = ++mid;
    }
    if(search==arr[fst])  //улучшаем асимптотику - то есть последний проход, когда
fst==lst выносим за цикл
       return true;
    return false;
}


Ответ 2

Записывай числа не в массив, а в HashSet. Бинарный поиск по массиву работает за O(ln(n)),
а проверка наличия элемента в HashSet-е может выполниться за O(1).

Если проблема с производительностью была НЕ из-за долгого поиска, или если есть специальные
проверки, учитывающие особенности реализации хэш-функции, то не сработает. Но в общем
случае должно помочь.


Ответ 3

Считывание из файла за 940мс прошло. Не понимаю правда почему из файла быстрее, но
это сработало. Сама задача https://www.e-olymp.com/ru/problems/3966

import java.io.*;
import java.util.*;
import java.lang.*;

public class test1 {
    public static boolean find(int search, int[] arr, int len) {
        boolean ret = false;
        int fst = 0;
        int lst = len - 1;
        while (fst <= lst) {
            int mid = (fst + lst) / 2;
            if (search == arr[mid]) {
                ret = true;
                break;
            } else if (search < arr[mid]) {
                lst = mid - 1;
            } else {
                fst = mid + 1;
            }
        }
        return ret;
    }

    public static void main(String[] args) throws FileNotFoundException {
        final Scanner scan = new Scanner(new BufferedInputStream(new FileInputStream(new
File("input.txt"))));
        final PrintStream out = new PrintStream(new BufferedOutputStream(new FileOutputStream(new
File("output.txt"))));
        int len = scan.nextInt();
        int[] arr = new int[len];
        int i;
        for (i = 0; i < len; i++) {
            arr[i] = scan.nextInt();
        }
        int num = scan.nextInt();
        int search;
        for (i = 0; i < num; i++) {
            search = scan.nextInt();
            out.print((find(search, arr, len))? "YES\n" : "NO\n");
        }
        scan.close();
        out.flush();
        out.close();
    }
}