Почему одинаковые программы на Python и Java работают по разному (или почти одинаковые)?

#java #python #алгоритм

Вы, наверное, посчитаете этот вопрос глупым, но все же...

Есть два алгоритма на Python и Java, делающие одинаковые вещи и написание почти один
в один, но при проверке (если интересно что код делает, то почитайте в Statement) алгоритм
на Java проходит все отлично, а на Python видает ошибку Time Limit

Код на Java

//package allukrainianOlimpiad;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();
        scanner.close();

        ArrayList res = new ArrayList<>();
        ArrayList str = new ArrayList<>();
        for (char i : str1.toCharArray()) {
            str.add(i);
        }

        for (int i = 1; i < str.size(); i++) {
            if (str.get(i) == ')') {
                for (int j = i; j >= 0; j--) {
                    if (str.get(j) == '(') {
                        res.add(j + 1);
                        res.add(i + 1);

                        str.set(i, '@');
                        str.set(j, '@');
                        break;
                    }
                }
            }
        }

        System.out.println(res.size() / 2);     
        for (int i = 0; i < res.size(); i += 2) {
            System.out.println(res.get(i) + " " + res.get(i + 1));
        }
    }
}


Код на Python

expression = list(input())
result = []

for i in range(len(expression)):
  if expression[i] == ')':

    for j in reversed(range(i)):
      if expression[j] == '(':
        result.append([j + 1, i + 1])
        expression[i] = expression[j] = '1'
        break

print(len(result))
for i in result:
  print(str(i[0]) + ' ' + str(i[1]))


Проверка





Вопрос

Почему алгоритм на Java справился намного быстрее чем на Python? И как можно это
пофиксить?
    

Ответы

Ответ 1

Ошибок в коде Python не вижу. Вижу медленный алгоритм, который при определённых условиях
будет сильно отставать от оптимального. Java быстрее Python, поэтому решение на Java
уложилось в установленное время, на Python же неоптимальность алгоритма проявилась.

Посмотрите сравнительные тесты Java vs Python.

Я решил эту задачу на Python, используя быстрый алгоритм, который находит решение
за один проход:

expression = input()
stack = []
result = ''
cnt = 0 
for idx, char in enumerate(expression, 1): 
    if char == '(':
        stack.append((idx,char))
    elif char == ')':
        if stack and stack[-1][1] == '(':
            result += f"{stack.pop()[0]} {idx}\n"
            cnt += 1

print(cnt)
print(result, end='')


Результат:



Я сравнил эти два алгоритма (мой и ваш) программой time на Linux, используя такое
входное выражение:

expression = '(' * 100 + "4" + "+((7-4)+(4+4))*(7-4)" * 10000 + ')' * 100


Результат:

Мой = 0.08 с
Ваш = 1.727 с


Думаю, у них есть похожие тесты, поэтому ваше решение и не прошло.

Для интереса сравните время работы ваших решений на Java и Python с этим же выражением.