Day: November 13, 2008

Categories
discuss

Why does this regular expression kill the Java regex engine?

I have this naive regex “<([s]|[^<])+?>” (excluding the quotation marks). It seems so straightforward but it is indeed evil when it works against the below HTML text. It sends the Java regular expression engine to an infinite loop.

I have another regex (“<.+?>”), which does somewhat the same thing, but it doesn’t kill anything. Do you know why this happens?

<script language="JavaScript" type="text/javascript">
        var numDivs, layerName;
        layerName = "lnavLayer";
        catLinkName = "category";
        numDivs = 2;
        function toggleLayer(layerID){
            if (!(navigator.appName == "Netscape" && navigator.appVersion.substr(0, 1) < 5)){
                thisLayer = document.getElementById(layerName + layerID);
                categoryLink = document.getElementById(catLinkName + layerID);
                closeThem();
                if (thisLayer.className == 'subnavDefault'){
                    thisLayer.className = 'subnavToggled';
                    categoryLink.className = 'leftnavLinkSelectedSection';
                }
            }
        }
        function closeThem(){
            for(x = 0; x < numDivs; x++){
                theLayer = document.getElementById(layerName + (x
+ 1));
                thecategoryLink = document.getElementById(catLinkName + (x + 1));
                theLayer.className = 'subnavDefault';
                thecategoryLink.className = 'leftnavLink';
            }
        } var flag = 0; var lastClicked = 0
    //-->
    </script>

it even keeps looping with an online Java regex tool (such as www.fileformat.info/tool/regex.htm) or a utility like RegexBuddy.

Answer

The reason the Java regex engine crashes is that this part of your regex causes a stack overflow (indeed!):

[s]|[^<]

What happens here is that every character matched by s can also be matched by [^<]. That means there are two ways to match each whitespace character. If we represent the two character classes with A and B:

A|B

Then a string of three spaces could be matched as AAA, AAB, ABA, ABB, BAA, BAB, BBA, or BBB. In other words the complexity of this part of the regex is 2^N. This will kill any regex engine that doesn’t have any safeguards against what I call catastrophic backtracking.

When using alternation (vertical bar) in a regex, always make sure the alternatives are mutually exclusive. That is, at most one of the alternatives may be allowed to match any given bit of text.

Categories
discuss

JavaScript Non-regex Replace

Do any of the existing JavaScript frameworks have a non-regex replace() function, or has this already been posted on the web somewhere as a one-off function?

For example I want to replace "@!#$123=%" and I don’t want to worry about which characters to escape. Most languages seem to have both methods of doing replacements. I would like to see this simple thing added.

Answer

i may be misunderstanding your question, but javascript does have a replace()

var string = '@!#$123=%';
var newstring = string.replace('@!#$123=%', 'hi');

edit: (see comments) the 5th edition does seem to have this info in it, although it doesn’t show up when i link directly to it. here’s the relevant part:

The replace( ) method performs a search-and-replace operation. It takes a regular expression as its first argument and a replacement string as its second argument. It searches the string on which it is called for matches with the specified pattern. If the regular expression has the g flag set, the replace( ) method replaces all matches in the string with the replacement string; otherwise, it replaces only the first match it finds. If the first argument to replace( ) is a string rather than a regular expression, the method searches for that string literally rather than converting it to a regular expression with the RegExp( ) constructor, as search( ) does.

Categories
discuss

Prime number calculation fun

We’re having a bit of fun here at work. It all started with one of the guys setting up a Hackintosh and we were wondering whether it was faster than a Windows Box of (nearly) same specs that we have. So we decided to write a little test for it. Just a simple Prime number calculator. It’s written in Java and tells us the time it takes to calculate the first n Prime numbers.

Optimised version below – now takes ~6.6secs

public class Primes {

    public static void main(String[] args) {
        int topPrime = 150000;
        int current = 2;
        int count = 0;
        int lastPrime = 2;

        long start = System.currentTimeMillis();

        while (count < topPrime) {

            boolean prime = true;

            int top = (int)Math.sqrt(current) + 1;

            for (int i = 2; i < top; i++) {
                if (current % i == 0) {
                    prime = false;
                    break;
                }
            }

            if (prime) {
                count++;
                lastPrime = current;
            }
            if (current == 2) {
             current++;
            } else {
                current = current + 2;
            }
        }

        System.out.println("Last prime = " + lastPrime);
        System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
    } 
}

We’ve pretty much lost the plot of the whole Hackintosh vs PC thing and are just having some fun with optimising it. First attempt with no optimisations (the above code has a couple) ran around 52.6min to find the first 150000 prime numbers. This optimisation is running around 47.2mins.

If you want to have a go and post your results, then stick em up.

Specs for the PC I’m running it on are Pentium D 2.8GHz, 2GB RAM, running Ubuntu 8.04.

Best Optimisation so far has been the square root of current, first mentioned by Jason Z.

Answer

Well I see a couple of quick optimizations that can be done. First you don’t have to try each number up to half of the current number.

Instead you only have try up to the square root of the current number.

And the other optimization was what BP said with a twist: Instead of

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

use

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

This should speed things up quite a lot.

Edit:
More optimization courtesy of Joe Pineda:
Remove the variable “top”. 

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

If this optimization indeed increases speed is up to java.
Calculating the square root takes a lot of time compared to multiplying two numbers. However since we move the multiplication into the for loop this is done every single loop. So this COULD slow things down depending on how fast the square root algorithm in java is.

Categories
discuss

How to persist a property of type List in JPA?

What is the smartest way to get an entity with a field of type List persisted?

Command.java

package persistlistofstring;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import javax.persistence.Basic;
import javax.persistence.Entity;
import javax.persistence.EntityManager;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.Persistence;

@Entity
public class Command implements Serializable {

    @Id
    @GeneratedValue(strategy = GenerationType.AUTO)
    Long id;
    @Basic
    List<String> arguments = new ArrayList<String>();

    public static void main(String[] args) {
        Command command = new Command();

        EntityManager em = Persistence
                .createEntityManagerFactory("pu")
                .createEntityManager();
        em.getTransaction().begin();
        em.persist(command);
        em.getTransaction().commit();
        em.close();

        System.out.println("Persisted with id=" + command.id);
    }
}

This code produces:

> Exception in thread "main" javax.persistence.PersistenceException: No Persistence provider for EntityManager named pu: Provider named oracle.toplink.essentials.PersistenceProvider threw unexpected exception at create EntityManagerFactory: 
> oracle.toplink.essentials.exceptions.PersistenceUnitLoadingException
> Local Exception Stack: 
> Exception [TOPLINK-30005] (Oracle TopLink Essentials - 2.0.1 (Build b09d-fcs (12/06/2007))): oracle.toplink.essentials.exceptions.PersistenceUnitLoadingException
> Exception Description: An exception was thrown while searching for persistence archives with ClassLoader: sun.misc.Launcher$AppClassLoader@11b86e7
> Internal Exception: javax.persistence.PersistenceException: Exception [TOPLINK-28018] (Oracle TopLink Essentials - 2.0.1 (Build b09d-fcs (12/06/2007))): oracle.toplink.essentials.exceptions.EntityManagerSetupException
> Exception Description: predeploy for PersistenceUnit [pu] failed.
> Internal Exception: Exception [TOPLINK-7155] (Oracle TopLink Essentials - 2.0.1 (Build b09d-fcs (12/06/2007))): oracle.toplink.essentials.exceptions.ValidationException
> Exception Description: The type [interface java.util.List] for the attribute [arguments] on the entity class [class persistlistofstring.Command] is not a valid type for a serialized mapping. The attribute type must implement the Serializable interface.
>         at oracle.toplink.essentials.exceptions.PersistenceUnitLoadingException.exceptionSearchingForPersistenceResources(PersistenceUnitLoadingException.java:143)
>         at oracle.toplink.essentials.ejb.cmp3.EntityManagerFactoryProvider.createEntityManagerFactory(EntityManagerFactoryProvider.java:169)
>         at javax.persistence.Persistence.createEntityManagerFactory(Persistence.java:110)
>         at javax.persistence.Persistence.createEntityManagerFactory(Persistence.java:83)
>         at persistlistofstring.Command.main(Command.java:30)
> Caused by: 
> ...

Answer

Use some JPA 2 implementation: it adds a @ElementCollection annotation, similar to the Hibernate one, that does exactly what you need. There’s one example here.

Edit

As mentioned in the comments below, the correct JPA 2 implementation is

javax.persistence.ElementCollection

@ElementCollection
Map<Key, Value> collection;

See: http://docs.oracle.com/javaee/6/api/javax/persistence/ElementCollection.html

Categories
discuss

Unresponsive KeyListener for JFrame

I’m trying to implement a KeyListener for my JFrame. On the constructor, I’m using this code:

System.out.println("test");
addKeyListener(new KeyListener() {
    public void keyPressed(KeyEvent e) { System.out.println( "tester"); }

    public void keyReleased(KeyEvent e) { System.out.println("2test2"); }

    public void keyTyped(KeyEvent e) { System.out.println("3test3"); }
});

When I run it, the test message comes up in my console. However, when I press a key, I don’t get any of the other messages, as if the KeyListener was not even there.

I was thinking that it could be because the focus is not on the JFrame
and so they KeyListener doesn’t receive any events. But, I’m pretty sure it is.

Is there something that I am missing?

Answer

You must add your keyListener to every component that you need. Only the component with the focus will send these events. For instance, if you have only one TextBox in your JFrame, that TextBox has the focus. So you must add a KeyListener to this component as well.

The process is the same:

myComponent.addKeyListener(new KeyListener ...);

Note: Some components aren’t focusable like JLabel.

For setting them to focusable you need to:

myComponent.setFocusable(true);
Source: stackoverflow
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Privacy Policy, and Copyright Policy. Content is available under CC BY-SA 3.0 unless otherwise noted. The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 © No Copyrights, All Questions are retrived from public domain..