Вовремя ли манипуляции с битами были недостаточно быстрыми? - PullRequest
Новая
       129

Вовремя ли манипуляции с битами были недостаточно быстрыми?

0 голосов
/ 06 ноября 2019

Это вопрос:

https://practice.geeksforgeeks.org/problems/find-the-odd-occurence/0

Задан массив натуральных чисел, где все числа встречаются четное число раз, кроме одного числа, которое встречается нечетное количество раз. Найти число.

Вход может варьироваться от

1 ≤ T ≤ 100: тестовые случаи
1 ≤ N ≤ 107: количество входов
1 ≤ A [i] ≤ 106: входы

Пример: 

Input:

1
5
8 4 4 8 23

Output:

23

Это код: 

class GFG
 {
    public static void main (String[] args)
     {
     //code
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
              int N = sc.nextInt();
              int count = 0;
              for(int j = 0; j<N; j++){
                  int in = sc.nextInt();
                 count =count^in;
              }
              System.out.println(count);
        }

    }
}

Мой вопрос: OJ потребовалось 2,5 с , чтобы выполнить его, и другие люди сделали это значительно быстрее, чем я. Некоторые сделали это за 0.3s . И это также включает в себя ввод чисел в массиве и последующую итерацию по ним.

Почему, это из-за OJ или из-за того, что я не понял? Также я несколько раз делал подачу, чтобы убедиться, что произошла ошибка, но все время это занимало более 2,5 с.

1 Ответ

2 голосов
/ 08 ноября 2019

Современная Java считается довольно быстрой, если вы пишете оптимизированный код, но она все еще медленнее, чем языки, которые взаимодействуют на еще более низком уровне и имеют опережающий компилятор. В любом случае, у этой темы есть очень хороший подробный ответ: Действительно ли Java медленна? .

Однако ваш код Java все еще можно оптимизировать, используя BufferedReader вместо прямого использования Scanner. Scanner фактически принимает входной поток и затем анализирует в соответствии с типом данных, который мы пытаемся получить, но BufferedReader просто дает необработанный ввод и не выполняет никаких операций. Следовательно, если вы используете его и анализируете необработанную строку ввода отдельно, это будет намного лучше для вашего времени выполнения кода. Мне удалось получить 0,61 с немного измененной версией вашего кода, используя BufferedReader: 

import java.util.*;
import java.io.*;
class gfg
{
    public static void main(String args []) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out, true);
        int t=Integer.parseInt(br.readLine());
        while(t-->0)
        {
            int N = Integer.parseInt(br.readLine());
            String str[]=br.readLine().split(" ");
            int count = 0;
            for(int j = 0; j<N; j++){
                int in = Integer.parseInt(str[j]);
                count =count^in;
              }
              System.out.println(count);
        }

    }
}

Я думаю, что с помощью еще нескольких оптимизаций вы можете приблизить время, почти сравнимое с 0,3 с.

...