New Posts  All Forums:Forum Nav:

Java optimization

post #1 of 3
Thread Starter 
Hey, I'm not sure if you guys are familiar with USACO, but there's a problem I've been having trouble with on their training pages.

Here's the problem:
Quote:
It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.

Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines which, when taken together, represent one long string. No line is longer than 80 characters (not counting the newline at the end).
SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.
OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam

So here's my code:
Code:
import java.io.*;
import java.util.*;

public class calfflac
{
        public static void main (String [] args) throws IOException
        {
                new calfflac();
        }
        
        public calfflac() throws IOException 
        {

                BufferedReader in = new BufferedReader(new FileReader("calfflac.in"));
                PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("calfflac.out")));
                
                String input = "";
                String temp = in.readLine();
                
                while(temp != null)
                {
                        input += temp + "\n";
                        temp = in.readLine();
                }
                        
                int maxlength = 0, index, beginning = 0, end = 0;
                
                for(int x = 0; x < input.length(); x++)
                {
                        if(isChar(input.toUpperCase().charAt(x)))
                        {
                                int[] result = palLength(input, x, maxlength);
                                int length = result[0];
                                if(length > maxlength)
                                {
                                        maxlength = length;
                                        index = x;
                                        beginning = result[1];
                                        end = result[2];
                                }
                        }
                }
                
                
                System.out.println(maxlength);
                for(int x = beginning; x <= end; x++)
                        System.out.print(input.charAt(x));
                
                
                out.println(maxlength);
                for(int x = beginning; x <= end; x++)
                        out.print(input.charAt(x));
                
                out.println();
                out.close();
                System.exit(0);
        }
        
        public int[] palLength(String line, int index, int maxlength)
        {
                String compare = line.toUpperCase();
                int[] temp1 = {1, 0, 0};
                int[] temp2 = {1, line.length() - 1, line.length() - 1};
                int[] result = new int[3];
                
                int length = 1;
                
                if(index == 0)
                        return temp1;
                if(index == line.length() - 1)
                        return temp2;
                
                int beginning = index - 1, end = index + 1;
                
                if(!isChar(compare.charAt(beginning)))
                                beginning = nextLetter(compare, beginning, true);
                
                if(!isChar(compare.charAt(end)))
                        end = nextLetter(compare, end, false);
                
                if(compare.charAt(beginning) != compare.charAt(end) && compare.charAt(index) == compare.charAt(end))
                {
                        beginning = index;
                        length = 0;
                }
                
                int temp3 = beginning, temp4 = end;
                for(int x = 0; x < maxlength / 2; x++)
                {
                        temp3 = nextLetter(compare, temp3, true);
                        temp4 = nextLetter(compare, temp4, false);
                }
                
                if(compare.charAt(temp3) != compare.charAt(temp4))
                        return temp1;
                
                int temp5 = beginning, temp6 = end;
                
                while(compare.charAt(beginning) == compare.charAt(end))
                {
                        temp5 = beginning;
                        temp6 = end;
                        beginning = nextLetter(compare, beginning, true);
                        end = nextLetter(compare, end, false);
                        length += 2;
                        //System.out.println("a" + length + " " + line.charAt(beginning) + " " + line.charAt(end));
                }
                
                beginning = temp5;
                end = temp6;
        
                result[0] = length;
                result[1] = beginning;
                result[2] = end;
                return result;
        }
        
        public int nextLetter(String line, int index, boolean beginning)
        {
                
                if(beginning)
                {
                        index--;
                        if(index > 0)
                                while(index > 0 && !isChar(line.charAt(index)))
                                        index--;
                        index = Math.max(0, index);
                }
                else
                {
                        index++;
                        if(index < line.length() - 1)
                                while(index < line.length() - 1 && !isChar(line.charAt(index)))
                                        index++;
                        index = Math.min(line.length() -1, index);
                }
                return index;
        }
        
        public boolean isChar(char a)
        {
                int temp = (int) a;
                if(a < 65 || a > 90)
                        return false;
                return true;
        }
}

Basically this code works, but it runs quite slowly, I think it's like O(n^3) or something along those lines. The problem needs this to complete in under 1 second, I'm currently getting 1.5 seconds on 5000 input line and 5 seconds on 20000 input.

Any idea how I could optimize my code?

Thanks.
    
CPUMotherboardGraphicsRAM
E8400 GIGABYTE GA-P35-DS3L eVGA 9800GT Stock Speeds GSkill 4GB (2x2GB) PC6400 
Hard DriveOptical DriveOSMonitor
Samsung F3 500GB Samsung 22X DVD Drive Windows 7 64-bit 22" Acer x223w 
KeyboardPowerCaseMouse
IBM Model M Model 1391401 Antec EarthWatts 500W Troglodytic Tech Terminal Razer Deathadder 
Mouse Pad
Steelseries Qck+ 
  hide details  
Reply
    
CPUMotherboardGraphicsRAM
E8400 GIGABYTE GA-P35-DS3L eVGA 9800GT Stock Speeds GSkill 4GB (2x2GB) PC6400 
Hard DriveOptical DriveOSMonitor
Samsung F3 500GB Samsung 22X DVD Drive Windows 7 64-bit 22" Acer x223w 
KeyboardPowerCaseMouse
IBM Model M Model 1391401 Antec EarthWatts 500W Troglodytic Tech Terminal Razer Deathadder 
Mouse Pad
Steelseries Qck+ 
  hide details  
Reply
post #2 of 3
I have no idea if this is a fully viable but you could try threading separate reading tasks, like say thread a reader to go from 0 to 150, and another go through 100 to 200. Of course dynamically figuring that out according to the length of the file input, using threads somewhat like below. I'm not sure if that will help out a large amount though and I'm a bit too busy to give your code a thorough look. I myself haven't worked with Java a large amount so I don't know to what extent threads will help with.
Code:
public int reader = 0;

public void start() {
    while (reader < 5) {
        new Thread(new Runnable() {
            public void run() {
                 read();
                }
        }).start();
    }
}

public read() {
    reader += 1;
    int lengthToRead = fileString.length() / 4;
    int placeToStart = (reader == 1) ? 0 : (((reader - 1) * lengthToRead) - lengthToRead / 10)  ;
    //Reading stuff?
}
    
CPUMotherboardGraphicsRAM
i5 2500k Asus P8P67 XFX HD 6950 G.Skill 2x4GB 
CoolingOSPowerCase
CM Hyper 212+ Windows 7 / Linux Mint Seasonic S12ii 620 HAF 912 
  hide details  
Reply
    
CPUMotherboardGraphicsRAM
i5 2500k Asus P8P67 XFX HD 6950 G.Skill 2x4GB 
CoolingOSPowerCase
CM Hyper 212+ Windows 7 / Linux Mint Seasonic S12ii 620 HAF 912 
  hide details  
Reply
post #3 of 3
Looks like you have an algorithm problem. It should be easy enough to convert the basic concepts in this article to Java.
The New Guy
(16 items)
 
  
CPUMotherboardGraphicsRAM
Q6600 G0@3.0GHz GA-P35-DS3L EVGA 8800GT Superclocked 4GB Corsair XMS2 DDR2 800 
Hard DriveHard DriveOptical DriveOS
Seagate 320GB 7200RPM Western Digital Caviar Black Lite-on DVD burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Samsung 225BW Filco Majestouch Ninja (full keyboard w/browns) Cooler Master Xtreme 650 Antec 900 
MouseAudioAudio
Logitech MX518 Denon AHD-2000 Sennheiser HD595 
  hide details  
Reply
The New Guy
(16 items)
 
  
CPUMotherboardGraphicsRAM
Q6600 G0@3.0GHz GA-P35-DS3L EVGA 8800GT Superclocked 4GB Corsair XMS2 DDR2 800 
Hard DriveHard DriveOptical DriveOS
Seagate 320GB 7200RPM Western Digital Caviar Black Lite-on DVD burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Samsung 225BW Filco Majestouch Ninja (full keyboard w/browns) Cooler Master Xtreme 650 Antec 900 
MouseAudioAudio
Logitech MX518 Denon AHD-2000 Sennheiser HD595 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming