Przyspieszenie działania algorytmu

Próbuję rozwiązać to zadanie: http://www.spoj.pl/problems/ETI07F3/

Wprawdzie nie na SPOJu ale na platformie, która jest jego bliźniakiem. Problem w tym, że mój kod działa za wolno. W jaki sposób mogę to przyspieszyć?

A oto moje rozwiązanie:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
	static int level=0;
	
	static class Cyfra {
		int wartosc;
		int level;
		
		public Cyfra(String wartosc, int level) {
			this.wartosc=Integer.parseInt(wartosc);
			this.level=level;
		}
		
		public boolean equals(Object o) {
			Cyfra c2=(Cyfra) o;
			return c2.wartosc==wartosc && c2.level==level;
		}
		
		public String toString() {
			return "Wartosc: "+wartosc+" | Level: "+level;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int testow=Integer.parseInt(br.readLine());
		for(int t=0; t<testow; t++) {
			ArrayList<Cyfra> lista=new ArrayList<Cyfra>();
			level=0;
			int cyfr=Integer.parseInt(br.readLine());
			String slowo=br.readLine();
			int i=0;
			while(lista.size()<cyfr) {
				if(slowo.charAt(i)=='(') level++;
				else if(slowo.charAt(i)!=' ') {
					int poc=i;
					while(slowo.charAt(i)!=' ' && slowo.charAt(i)!=')') i++;
					lista.add(new Cyfra(slowo.substring(poc,i),level));
				}
				if(slowo.charAt(i)==')') level--;
				i++;
			}
			slowo=br.readLine();
			level=0;
			i=0;
			boolean czy=true;
			while(i<slowo.length()-1 && czy) {
				if(slowo.charAt(i)=='(') level++;
				else if(slowo.charAt(i)!=' ') {
					int poc=i;
					while(slowo.charAt(i)!=' ' && slowo.charAt(i)!=')') i++;
					Cyfra c=new Cyfra(slowo.substring(poc,i),level);
					if(!lista.contains(c)) czy=false;
				}
				if(slowo.charAt(i)==')') level--;
				i++;
			}
			if(czy) System.out.println("TAK");
			else System.out.println("NIE");
		}
	}
	
}

Po pierwsze - zero komentarzy to całkowity brak zrozumienia kodu. W zasadzie nie wiadomo na czym opiera się Twój algorytm. Jaką ma złożoność czasową?

Ze swojego doświadczenia radzę Ci ograniczać korzystanie w Javy na spoju do minimum. Przeciętny program napisany w Javie działa jakieś 6-10 razy wolniej niż taki sam program napisany w C++. Więc po pierwsze - skup się na złożoności, a po drugie - jeżeli nie musisz to nie pisz tego w Javie.

Przeciętny program napisany w Javie działa jakieś 6-10 razy wolniej niż taki sam program napisany w C++.

Czyżby? http://shootout.alioth.debian.org/u64q/which-programming-languages-are-fastest.php

1. Zamiast:

ArrayList<Cyfra> lista=new ArrayList<Cyfra>();

używaj ogólnych interfejsów, np:List<Cyfra> lista=new ArrayList<Cyfra>();

lub tutaj nawet wystarczyłoby<code class="java">Collection<Cyfra> lista=new ArrayList<Cyfra>();

bo nie używasz żadnych metod specyficznych nawet dla List, a co dopiero ArrayList.
2. ArrayList.contains ma złożoność oczekiwaną O(n). Operację tą wykonujesz n razy, a więc złożoność wynosi O(n^2) od wielkości listy.
3. Możliwe rozwiązania:
a) wykorzystanie HashSeta zamiast ArrayListy, lub
b) utworzenie dwóch list dla obydwu opisów, następnie posortowanie obu za pomocą Arrays.sort i porównanie za pomocą Arrays.equals, lub
c) itp

Najszybszym rozwiązaniem byłoby chyba:

Oczywiście zakładając, że podany algorytm jest dobry.

To mnie teraz zadziwiłeś ;)

Wygląda na to, że stworzenie własnej mocno uproszczonej implementacji wektora pomaga. Taki kod przechodzi na dużych testach:

import java.util.Arrays

class MyVector {
  var t = Array[Int](10)
  var n = 0
  def add(v: Int) {
    if (n == t.length)
      t = Arrays.copyOf(t, n * 2)
    t(n) = v
    n += 1
  }
  
  override def equals(that: Any) = that match {
    case that: MyVector => Arrays.equals(this.t, that.t)
    case _ => false
  }
  
  def sort() = Arrays.sort(t)
}

object Main {

  def parseTree(n: Int) = {
    val levels = (0 until n) map (_ => new MyVector())
    var num = 0
    var wasNum = false
    var level = -1
    readLine foreach { c =>
      val isNum = Character.isDigit(c)
      if (isNum) {
        if (wasNum)
          num *= 10
        else
          num = 0
        num += c - '0'
      } else {
        if (wasNum)
          levels(level).add(num)
        if (c == '(')
          level += 1
        else if (c == ')')
          level -= 1
      }
      wasNum = isNum
    }
    levels foreach (_.sort)
    levels
  }

  def main(args: Array[String]) = {
    val t = Integer.parseInt(readLine)
    (0 until t) foreach { i =>
      val n = Integer.parseInt(readLine)
      println(if (parseTree(n) == parseTree(n)) "TAK" else "NIE")
    }
  }
}

Na małych testach nie przechodzi, bo Scalowy kod za długo się na ich sprawdzarce odpala i nawet Hello worldy dostają u nich timeouty jeśli limit jest ustawiony na 1s.

Albo z małą modyfikacją, szybszy, ale i tak małych testów nie przechodzi z powodu przedstawionego tuż powyżej:

import java.util.Arrays

class MyVector {
  var t = Array[Int](10)
  var n = 0
  def add(v: Int) {
    if (n == t.length)
      t = Arrays.copyOf(t, n * 2)
    t(n) = v
    n += 1
  }
  
  override def equals(that: Any) = that match {
    case that: MyVector => Arrays.equals(this.t, that.t)
    case _ => false
  }
  
  def sort() = Arrays.sort(t)
}

object Main {

  def parseTree(n: Int) = {
    val levels = new MyVector()
    var num = 0
    var wasNum = false
    var level = -1
    readLine foreach { c =>
      val isNum = Character.isDigit(c)
      if (isNum) {
        if (wasNum)
          num *= 10
        else
          num = 0
        num += c - '0'
      } else {
        if (wasNum)
          levels.add(num * 10000 + level)
        if (c == '(')
          level += 1
        else if (c == ')')
          level -= 1
      }
      wasNum = isNum
    }
    levels.sort
    levels
  }

  def main(args: Array[String]) = {
    val t = Integer.parseInt(readLine)
    (0 until t) foreach { i =>
      val n = Integer.parseInt(readLine)
      println(if (parseTree(n) == parseTree(n)) "TAK" else "NIE")
    }
  }
}

Zrobiłem wersję w Javie, ale z jakichś powodów wolniejsza od Scalowej tuż powyżej no i nie przechodzi małych testów. Późno jest i nie chce mi się już dociekać dlaczego:

import java.util.Arrays;
import java.util.Scanner;

class MyVector {
  int[] t = new int[10];
  int n = 0;
  void add(int v) {
    if (n == t.length)
      t = Arrays.copyOf(t, n * 2);
    t[n] = v;
    n += 1;
  }
  
  void sort() {
    Arrays.sort(t);
  }
}

public class Main {

  static MyVector parseTree(Scanner s, int n) {
    MyVector levels = new MyVector();
    int num = 0;
    boolean wasNum = false;
    int level = -1;
    for (char c : s.nextLine().toCharArray()) {
      final boolean isNum = Character.isDigit(c);
      if (isNum) {
        if (wasNum)
          num *= 10;
        else
          num = 0;
        num += c - '0';
      } else {
        if (wasNum)
          levels.add(num * 10000 + level);
        if (c == '(')
          level += 1;
        else if (c == ')')
          level -= 1;
      }
      wasNum = isNum;      
    }
    levels.sort();
    return levels;
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int t = Integer.parseInt(s.nextLine());
    for (int i = 0; i < t; i++) {
      int n = Integer.parseInt(s.nextLine());
      if (Arrays.equals(parseTree(s, n).t, parseTree(s, n).t)) {
        System.out.println("TAK");
      } else {
        System.out.println("NIE");
      }
    }
  }
}

Dzieki Wibowit!

Skorzystalem z Twoich porad, ktore podales i algorytm przyspieszyl znaczaco. Zmiescilem sie juz w czasie :)

Bede przynajmniej wiedzial na co w przyszlosci zwracac uwage, bo nie wiedzialem o kilku rzeczach, o ktorych napisales. Takze tym wieksze dzieki!

PS. Wiem, ze Java czesto bywa wolniejsza niz C++ chocby, ale musze to w Javie pisac, no a poza tym wlasnie nie zawsze Java jest wolniejsza ;)