5

Как ускорить код? При изменении ввода/вывода система отказывается принимать, поэтому нужно оставить неприкосновенный 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");
        }
    }
}
5
  • А вывод "NO" в цикле обязателен? Commented 28 сент. 2017 в 14:00
  • 2
    А смысл кода в общем-то в чём? Какая задача решается? Commented 28 сент. 2017 в 14:18
  • заменить весь поиск на for (final int i : arr) { if (i == key) { return true; } } return false; Commented 28 сент. 2017 в 14:19
  • Есть у нас вопрос про олимпиадные задачи на яве, а в ответе к нему ссылка на рекомендации с acm.timus.ru. Сам сайт чот прилег, но есть вебархив. Идея с заворачиванием System.out в новый PrintWriter сэкономит вам до полсекунды, использование StreamTokenizer для чтения - еще столько же.
    – zRrr
    Commented 28 сент. 2017 в 17:38
  • 1
    Попробуйте вариант с многопоточностью и стримом. ` public static boolean find(int []arr,int search) { return Arrays.stream(arr).parallel().anyMatch(a->a==search); }` Commented 28 сент. 2017 в 19:48

3 ответа 3

5

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

//убран лишний параметр 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
  • 4
    Или даже return (search==arr[fst]) вместо if в конце.
    – Lyth
    Commented 28 сент. 2017 в 16:12
  • Точно - спасибо за наводку. В алгоритмах поиска часто улучшение асимптотики является решающим
    – Barmaley
    Commented 28 сент. 2017 в 16:15
1

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

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

1
  • Оно конечно так, но в задача предполагает именно поиск в сортированном массиве, а не позиционирование по индексу :)
    – Barmaley
    Commented 28 сент. 2017 в 15:33
1

Считывание из файла за 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();
    }
}
1
  • Возможно, из-за буферизации ввода-вывода.
    – Qwertiy
    Commented 20 нояб. 2017 в 10:07

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.