JAXB and Commons pool

Lately I made a mistake, which went unnoticed for quite a long time. In an effort to improve performance of JAXB (Java Architecture for XML Binding) operations, I cached instances of javax.xml.bind.Marshaller and javax.xml.bind.Unmarshaller. This article explains why this was not a good idea and describes how pooling with Apache Commons Pool can be used instead, to improve overall JAXB performance.

JAXB

JAXB API is fairly verbose, however when working with XML we generally do not want to create SchemaFactory or JAXBContext... What we really need is just one method to marshal object into XML string and second to unmarshal string to object. This goal is described by JaxbHelper interface. When parameter schemaLocation is present XML is validated against XSD schema, in case it is null validation is not performed.

/**
 * Custom interface, which simplifies JAXB API.
 */
public interface JaxbHelper {

    public <T> String marshal(T instance, @Nullable String schemaLocation) throws Exception;

    public <T> T unmarshal(String xml, Class<T> clazz, @Nullable String schemaLocation) throws Exception;
}

SimpleJaxbHelper

Let's start with the simplest possible implementation. It will serve later as a unit of measurement for comparing performance. This and all following JaxbHelper implementations are thread-safe and re-entrant. Parameter schemaLocation is relative to the class, so in case XSD schema is in the same package as class, then name of schema is sufficient and path can be omitted.

/**
 * Simplest possible implementation, does not use cache nor pooling. It is thread-safe and re-entrant.
 */
public class SimpleJaxbHelper implements JaxbHelper {

    @Override
    public <T> String marshal(T instance, @Nullable String schemaLocation) throws JAXBException, SAXException {
        StringWriter result = new StringWriter();

        JAXBContext jaxbContext = JAXBContext.newInstance(instance.getClass());

        Marshaller marshaller = jaxbContext.createMarshaller();

        if (schemaLocation != null) {
            SchemaFactory schemaFactory = SchemaFactory.newInstance(XMLConstants.W3C_XML_SCHEMA_NS_URI);
            Schema schema = schemaFactory.newSchema(instance.getClass().getResource(schemaLocation));
            marshaller.setSchema(schema);
        }

        marshaller.marshal(instance, result);

        return result.toString();
    }

    @Override
    public <T> T unmarshal(String xml, Class<T> clazz, @Nullable String schemaLocation) throws JAXBException, SAXException {
        JAXBContext jaxbContext = JAXBContext.newInstance(clazz);

        Unmarshaller unmarshaller = jaxbContext.createUnmarshaller();

        if (schemaLocation != null) {
            SchemaFactory schemaFactory = SchemaFactory.newInstance(XMLConstants.W3C_XML_SCHEMA_NS_URI);
            Schema schema = schemaFactory.newSchema(clazz.getResource(schemaLocation));
            unmarshaller.setSchema(schema);
        }

        //noinspection unchecked
        return (T) unmarshaller.unmarshal(new StringReader(xml));
    }

CachedJaxbHelper

Second implementation uses cache for javax.xml.bind.JAXBContext instances which are thread-safe, at least in JAXB RI implementation. It caches instances of javax.xml.validation.Schema as well, because these are immutable and there is really no reason why not to do so. Notice that java.util.concurrent.ConcurrentHashMap is used here because it's get method generally does not block, and may overlap with put method

/**
 * Implementation which holds it's JAXBContext and Schema instances in a map. It is thread-safe and re-entrant.
 */
public class CachedJaxbHelper implements JaxbHelper {

    private static Map<Class, JAXBContext> jaxbContextMap = new ConcurrentHashMap<Class, JAXBContext>();
    private static Map<String, Schema> schemaMap = new ConcurrentHashMap<String, Schema>();

    private static JAXBContext getJaxbContext(Class clazz) throws JAXBException {
        JAXBContext jaxbContext = jaxbContextMap.get(clazz);

        if (jaxbContext == null) {
            jaxbContext = JAXBContext.newInstance(clazz);
            jaxbContextMap.put(clazz, jaxbContext);
        }
        return jaxbContext;
    }

    private static Schema getSchema(Class clazz, String schemaLocation) throws JAXBException, SAXException {
        Schema schema = schemaMap.get(schemaLocation);

        if (schema == null) {
            SchemaFactory schemaFactory = SchemaFactory.newInstance(XMLConstants.W3C_XML_SCHEMA_NS_URI);
            schema = schemaFactory.newSchema(clazz.getResource(schemaLocation));
            schemaMap.put(schemaLocation, schema);
        }
        return schema;
    }

    @Override
    public <T> String marshal(T instance, @Nullable String schemaLocation) throws JAXBException, SAXException {
        StringWriter result = new StringWriter();

        JAXBContext jaxbContext = getJaxbContext(instance.getClass());

        Marshaller marshaller = jaxbContext.createMarshaller();

        if (schemaLocation != null) {
            Schema schema = getSchema(instance.getClass(), schemaLocation);
            marshaller.setSchema(schema);
        }

        marshaller.marshal(instance, result);

        return result.toString();
    }

    @Override
    public <T> T unmarshal(String xml, Class<T> clazz, @Nullable String schemaLocation) throws JAXBException, SAXException {
        JAXBContext jaxbContext = getJaxbContext(clazz);

        Unmarshaller unmarshaller = jaxbContext.createUnmarshaller();

        if (schemaLocation != null) {
            Schema schema = getSchema(clazz, schemaLocation);
            unmarshaller.setSchema(schema);
        }

        //noinspection unchecked
        return (T) unmarshaller.unmarshal(new StringReader(xml));
    }
}

PooledJaxbHelper

Third implementation leaves Schema instances cached as before, but uses pooling for javax.xml.bind.JAXBContext, javax.xml.bind.Marshaller and javax.xml.bind.Unmarshaller. First to notice in PooledJaxbHelper is PoolKey, this inner class serves as key for marshaller, unmarshaller pools. It encapsulates class and schema location, schema location may be null so equals and hashCode methods must be generated accordingly.

Commons pool is very easy to work with, it contains org.apache.commons.pool.impl.GenericKeyedObjectPool which can hold instances relative to a key. It must be provided with factories which can create pooled objects. JaxbContextFactory is responsible for creating new JAXBContext instances where MarshallerFactory and UnmarshallerFactory are responsible for creating Marshaller and Unmarshaller instances. MarshallerFactory and UnmarshallerFactory already use jaxbContextPool for borrowing JAXBContext instance. Every object borrowed from pool with borrowObject method must be returned with returnObject method. Pool may be provided with optional GenericKeyedObjectPool.Config to change default configuration. I decided to invalidate Marshaller and Unmarshaller instances when exception happens with invalidateObject method, so that this instance is not to be used again.

/**
 * Implementation which holds it's Schema instances in a map, and uses pooling for JAXBContext, Marshaller and Unmarshaller instances.
 * It is thread-safe and re-entrant.
 */
public class PooledJaxbHelper implements JaxbHelper {

    private static class PoolKey {
        private Class clazz;
        private String schemaLocation;

        private PoolKey(Class clazz, @Nullable String schemaLocation) {
            this.clazz = clazz;
            this.schemaLocation = schemaLocation;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            PoolKey poolKey = (PoolKey) o;

            return clazz.equals(poolKey.clazz) && !(schemaLocation != null ? !schemaLocation.equals(poolKey.schemaLocation) : poolKey.schemaLocation != null);

        }

        @Override
        public int hashCode() {
            int result = clazz.hashCode();
            result = 31 * result + (schemaLocation != null ? schemaLocation.hashCode() : 0);
            return result;
        }

        public Class getClazz() {
            return clazz;
        }

        @Nullable
        public String getSchemaLocation() {
            return schemaLocation;
        }
    }

    private static class MarshallerFactory extends BaseKeyedPoolableObjectFactory<PoolKey, Marshaller> {
        @Override
        public Marshaller makeObject(PoolKey key) throws Exception {
            JAXBContext jaxbContext = jaxbContextPool.borrowObject(key.getClazz());

            Marshaller marshaller = jaxbContext.createMarshaller();

            if (key.getSchemaLocation() != null) {
                Schema schema = getSchema(key);
                marshaller.setSchema(schema);
            }

            jaxbContextPool.returnObject(key.getClazz(), jaxbContext);

            return marshaller;
        }
    }

    private static class UnmarshallerFactory extends BaseKeyedPoolableObjectFactory<PoolKey, Unmarshaller> {
        @Override
        public Unmarshaller makeObject(PoolKey key) throws Exception {
            JAXBContext jaxbContext = jaxbContextPool.borrowObject(key.getClazz());

            Unmarshaller unmarshaller = jaxbContext.createUnmarshaller();

            if (key.getSchemaLocation() != null) {
                Schema schema = getSchema(key);
                unmarshaller.setSchema(schema);
            }

            jaxbContextPool.returnObject(key.getClazz(), jaxbContext);

            return unmarshaller;
        }
    }

    private static class JaxbContextFactory extends BaseKeyedPoolableObjectFactory<Class, JAXBContext> {
        @Override
        public JAXBContext makeObject(Class clazz) throws Exception {
            return JAXBContext.newInstance(clazz);
        }
    }

    private static class CustomPoolConfig extends GenericKeyedObjectPool.Config {
        {
            maxIdle = 3;
            maxActive = 10;
            maxTotal = 100;
            minIdle = 1;
            whenExhaustedAction = GenericKeyedObjectPool.WHEN_EXHAUSTED_GROW;
            timeBetweenEvictionRunsMillis = 1000L * 60L * 10L;
            numTestsPerEvictionRun = 50;
            minEvictableIdleTimeMillis = 1000L * 60L * 5L; // 30 min.
        }
    }

    private static Schema getSchema(PoolKey poolKey) throws JAXBException, SAXException {
        Schema schema = schemaMap.get(poolKey.getSchemaLocation());

        if (schema == null) {
            SchemaFactory schemaFactory = SchemaFactory.newInstance(XMLConstants.W3C_XML_SCHEMA_NS_URI);
            schema = schemaFactory.newSchema(poolKey.getClazz().getResource(poolKey.getSchemaLocation()));
            schemaMap.put(poolKey.getSchemaLocation(), schema);
        }
        return schema;
    }

    private static Map<String, Schema> schemaMap = new ConcurrentHashMap<String, Schema>();
    private static GenericKeyedObjectPool<Class, JAXBContext> jaxbContextPool = new GenericKeyedObjectPool<Class, JAXBContext>(new JaxbContextFactory(), new CustomPoolConfig());
    private static GenericKeyedObjectPool<PoolKey, Marshaller> marshallerPool = new GenericKeyedObjectPool<PoolKey, Marshaller>(new MarshallerFactory(), new CustomPoolConfig());
    private static GenericKeyedObjectPool<PoolKey, Unmarshaller> unmarshallerPool = new GenericKeyedObjectPool<PoolKey, Unmarshaller>(new UnmarshallerFactory(), new CustomPoolConfig());

    @Override
    public <T> String marshal(T instance, @Nullable String schemaLocation) throws Exception {
        StringWriter result = new StringWriter();

        PoolKey poolKey = new PoolKey(instance.getClass(), schemaLocation);
        Marshaller marshaller = marshallerPool.borrowObject(poolKey);

        try {
            marshaller.marshal(instance, result);

            marshallerPool.returnObject(poolKey, marshaller);

            return result.toString();
        } catch (Exception e) {
            marshallerPool.invalidateObject(poolKey, marshaller);
            throw new RuntimeException(e);
        }
    }

    @Override
    public <T> T unmarshal(String xml, Class<T> clazz, @Nullable String schemaLocation) throws Exception {
        T result;

        PoolKey poolKey = new PoolKey(clazz, schemaLocation);
        Unmarshaller unmarshaller = unmarshallerPool.borrowObject(poolKey);

        try {
            //noinspection unchecked
            result = (T) unmarshaller.unmarshal(new StringReader(xml));

            unmarshallerPool.returnObject(poolKey, unmarshaller);

            return result;
        } catch (Exception e) {
            unmarshallerPool.invalidateObject(poolKey, unmarshaller);
            throw new RuntimeException(e);
        }
    }
}

Conclusion

As for performance there are many factors which must be taken into consideration, like for example complexity of XML documents, pool configuration, number of processors, size of memory and so on... Therefore absolute numbers do not have any meaning here, but here are some relative results which seem to be consistent enough.

INFO  JaxbHelperTest - testCompareAllToSimple
INFO  JaxbHelperTest - SimpleJaxbHelper / CachedJaxbHelper ratio: 5.813814804912555
INFO  JaxbHelperTest - SimpleJaxbHelper / PooledJaxbHelper ratio: 14.213429365043625

INFO  JaxbHelperTest - testCompareAllToSimpleMultipleThreads
INFO  JaxbHelperTest - SimpleJaxbHelper / CachedJaxbHelper ratio: 7.6223063332965735
INFO  JaxbHelperTest - SimpleJaxbHelper / PooledJaxbHelper ratio: 9.20335326080807

Which basically says that CachedJaxbHelper is 6 to 8 times faster than SimpleJaxbHelper and PooledJaxbHelper is 9 to 14 times faster then SimpleJaxbHelper.

Appendix

Project structure

JaxbPool/
|-- pom.xml
|-- src
    |-- main
    |   |-- java
    |   |   `-- eu
    |   |       `-- zont
    |   |           `-- jaxbpool
    |   |               |-- core
    |   |               |   |-- CachedJaxbHelper.java
    |   |               |   |-- JaxbHelper.java
    |   |               |   |-- PooledJaxbHelper.java
    |   |               |   `-- SimpleJaxbHelper.java
    |   |               `-- xml
    |   |                   |-- ObjectFactory.java
    |   |                   |-- PersonType.java
    |   |                   `-- SampleType.java
    |   `-- resources
    |       |-- eu
    |       |   `-- zont
    |       |       `-- jaxbpool
    |       |           `-- xml
    |       |               `-- sample.xsd
    |       |-- log4j.dtd
    |       `-- log4j.xml
    `-- test
        |-- java
        |   `-- eu
        |       `-- zont
        |           `-- jaxbpool
        |               `-- core
        |                   `-- JaxbHelperTest.java
        `-- resources
            `-- eu
                `-- zont
                    `-- jaxbpool
                        `-- xml
                            `-- sample.xml

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>eu.zont.jaxbpool</groupId>
    <artifactId>jaxb-pool</artifactId>
    <version>1.0-SNAPSHOT</version>

    <dependencies>
        <dependency>
            <groupId>commons-pool</groupId>
            <artifactId>commons-pool</artifactId>
            <version>1.6</version>
        </dependency>
        <dependency>
            <groupId>org.kohsuke.jetbrains</groupId>
            <artifactId>annotations</artifactId>
            <version>9.0</version>
        </dependency>
        <dependency>
            <groupId>log4j</groupId>
            <artifactId>log4j</artifactId>
            <version>1.2.16</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.10</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

Tests

public class JaxbHelperTest {

    private static final Logger log = Logger.getLogger(JaxbHelperTest.class);

    private static final String SAMPLE_SCHEMA_LOCATION = "sample.xsd";
    private static final int TO_MILLISECONDS = 1000000;
    private static final int HEAVY_LOAD = 1000;
    private static final int NUM_THREADS = 10;


    private SampleType createSample() {
        ObjectFactory objectFactory = new ObjectFactory();

        SampleType sample = objectFactory.createSampleType();

        PersonType person = objectFactory.createPersonType();
        person.setFirstname("firstname");
        person.setSurname("surname");

        sample.getPerson().add(person);

        return sample;
    }

    private void testJaxbHelper(JaxbHelper jaxbHelper) throws Exception {
        SampleType sample = createSample();

        String sampleXml = jaxbHelper.marshal(sample, SAMPLE_SCHEMA_LOCATION);
        SampleType sampleCopy = jaxbHelper.unmarshal(sampleXml, SampleType.class, SAMPLE_SCHEMA_LOCATION);

        assertNotNull(sampleXml);
        assertNotNull(sampleCopy);
        assertEquals(sample.getPerson().size(), sampleCopy.getPerson().size());
        assertEquals(sample.getPerson().get(0).getFirstname(), sampleCopy.getPerson().get(0).getFirstname());
        assertEquals(sample.getPerson().get(0).getSurname(), sampleCopy.getPerson().get(0).getSurname());
    }

    @Test
    public void testSimpleJaxbHelper() throws Exception {
        testJaxbHelper(new SimpleJaxbHelper());
    }

    @Test
    public void testCachedJaxbHelper() throws Exception {
        testJaxbHelper(new CachedJaxbHelper());
    }

    @Test
    public void testPooledJaxbHelper() throws Exception {
        testJaxbHelper(new PooledJaxbHelper());
    }

    private long testJaxbHelperLoad(JaxbHelper jaxbHelper, int load) throws Exception {
        SampleType sample = createSample();

        long startTime = System.nanoTime();

        for (int i = 0; i < load; i++) {
            String sampleXml = jaxbHelper.marshal(sample, SAMPLE_SCHEMA_LOCATION);
            jaxbHelper.unmarshal(sampleXml, SampleType.class, SAMPLE_SCHEMA_LOCATION);
        }

        return System.nanoTime() - startTime;
    }

    @Test
    public void testSimpleJaxbHelperHeavyLoad() throws Exception {
        long estimatedTime = testJaxbHelperLoad(new SimpleJaxbHelper(), HEAVY_LOAD);
        log.info("SimpleJaxbHelper estimated time: " + estimatedTime / TO_MILLISECONDS);
    }

    @Test
    public void testCachedJaxbHelperHeavyLoad() throws Exception {
        long estimatedTime = testJaxbHelperLoad(new CachedJaxbHelper(), HEAVY_LOAD);
        log.info("CachedJaxbHelper estimated time: " + estimatedTime / TO_MILLISECONDS);
    }

    @Test
    public void testPooledJaxbHelperHeavyLoad() throws Exception {
        long estimatedTime = testJaxbHelperLoad(new PooledJaxbHelper(), HEAVY_LOAD);
        log.info("PooledJaxbHelper estimated time: " + estimatedTime / TO_MILLISECONDS);
    }

    @Test
    public void testCompareAllToSimple() throws Exception {
        long simpleEstimatedTime = testJaxbHelperLoad(new SimpleJaxbHelper(), HEAVY_LOAD);
        long cachedEstimatedTime = testJaxbHelperLoad(new CachedJaxbHelper(), HEAVY_LOAD);
        long pooledEstimatedTime = testJaxbHelperLoad(new PooledJaxbHelper(), HEAVY_LOAD);

        log.info("testCompareAllToSimple");
        log.info("SimpleJaxbHelper / CachedJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) cachedEstimatedTime);
        log.info("SimpleJaxbHelper / PooledJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) pooledEstimatedTime);
    }


    private class JaxbTask implements Callable<Long> {
        private JaxbHelper jaxbHelper;
        private int load;

        public JaxbTask(JaxbHelper jaxbHelper, int load) {
            this.jaxbHelper = jaxbHelper;
            this.load = load;
        }

        public Long call() throws Exception {
            return testJaxbHelperLoad(jaxbHelper, load);
        }
    }


    private long testJaxbHelperHeavyLoadMultipleThreads(JaxbHelper jaxbHelper, int numThreads, int load) throws Exception {
        long estimatedTime = 0;

        ExecutorService threadExecutor = Executors.newFixedThreadPool(numThreads);

        List<JaxbTask> taskList = new ArrayList<JaxbTask>(numThreads);

        for (int i = 0; i < numThreads; i++) {
            taskList.add(new JaxbTask(jaxbHelper, load / numThreads));
        }

        List<Future<Long>> results = threadExecutor.invokeAll(taskList);

        threadExecutor.shutdown();

        boolean finished = threadExecutor.awaitTermination(1, TimeUnit.MINUTES);

        if (finished) {
            for (Future<Long> result : results) {
                estimatedTime += result.get();
            }
        } else {
            fail("Some of the test threads failed to finish correctly.");
        }

        return estimatedTime;
    }

    @Test
    public void testCompareSimpleAndPooledMultipleThreads() throws Exception {
        long simpleEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new SimpleJaxbHelper(), NUM_THREADS, HEAVY_LOAD);
        long pooledEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new PooledJaxbHelper(), NUM_THREADS, HEAVY_LOAD);

        log.info("SimpleJaxbHelper / PooledJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) pooledEstimatedTime);
    }

    @Test
    public void testCompareSimpleAndCachedMultipleThreads() throws Exception {
        long simpleEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new SimpleJaxbHelper(), NUM_THREADS, HEAVY_LOAD);
        long cachedEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new CachedJaxbHelper(), NUM_THREADS, HEAVY_LOAD);

        log.info("SimpleJaxbHelper / CachedJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) cachedEstimatedTime);
    }

    @Test
    public void testCompareAllToSimpleMultipleThreads() throws Exception {
        long simpleEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new SimpleJaxbHelper(), NUM_THREADS, HEAVY_LOAD);
        long cachedEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new CachedJaxbHelper(), NUM_THREADS, HEAVY_LOAD);
        long pooledEstimatedTime = testJaxbHelperHeavyLoadMultipleThreads(new PooledJaxbHelper(), NUM_THREADS, HEAVY_LOAD);

        log.info("testCompareAllToSimpleMultipleThreads");
        log.info("SimpleJaxbHelper / CachedJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) cachedEstimatedTime);
        log.info("SimpleJaxbHelper / PooledJaxbHelper ratio: " + (double) simpleEstimatedTime / (double) pooledEstimatedTime);
    }
}

Párovacie algoritmy

K napísaniu tohoto príspevku ma priviedla potreba prepísať kus kódu tak aby bol rýchlejší. Keďže som sa už s podobným problémom stretol viackrát, tak ho považujem za celkom všedný, ale nechcem ho popisovať všeobecne, preto som si vymyslel príklad s faktúrami a platbami.

Všeobecný popis problému by znel asi takto: Máme dve množiny objektov a potrebujeme priradiť k objektu z prvej množiny objekt z druhej množiny na základe určitých kritérií a vlastností týchto objektov.

Inými slovami: Máme množinu faktúr a množinu platieb, pričom predpokladáme, že dáta prišli z externých systémov a nemáme možnosť ovplyvniť ich štruktúru ani poradie.

Faktúra obsahuje číslo faktúry a peňažnú sumu, prípadne iné vlastnosti, ktoré nás nezaujímajú.

public class Faktura {

private String cisloFaktury;
private BigDecimal suma;

// ...konstruktor, gettery...pripadne dalsie vlastnosti, s ktorymi nepracujeme...
}

Platba obsahuje variabilný symbol a sumu, prípadne iné vlastnosti, ktoré nás nezaujímajú.

public class Platba {

 private String variabilnySymbol;
 private BigDecimal suma;

 // ...konstruktor, gettery...pripadne dalsie vlastnosti, s ktorymi nepracujeme...
}

V prípade, že číslo faktúry sa rovná variabilnému symbolu platby a zároveň sa rovnajú aj peňažné sumy, tak faktúra a platba tvoria pár. Predpokladáme, že jedna faktúra bude zaplatená iba jednou platbou a naopak. Predpokladáme, že môžu existovať faktúry po splatnosti, ktoré neboli zaplatené a neexistujú pre ne platby. A zároveň môžu existovať platby, ktoré sa netýkajú faktúr.

Skutočnosť, že faktúra a platba tvoria pár vyjadríme triedou Par.

public class Par {

  private Faktura faktura;
  private Platba platba;

  // ...konstruktor, gettery...
}

Riešenie, ktoré hľadáme bude mať na vstupe množinu faktúr a platieb a výstupom bude množina párov.

public interface ParovanieRiesenie {

  /**
   * Metoda sparuje faktury s platbami podla urcitych kriterii.
   *
   * @param faktury mnozina faktur, nie vsetky faktury musia byt zaplatene, tj. mozu existovat aj take, ktore nieje mozne sparovat
   * @param platby mnozina platieb, nie pre vsetky platby musi existovat faktura, tj. mozu existovat aj take, ktore nieje mozne sparovat
   * @return mnozina parov, par tvori faktura a platba, pricom predpokladame, ze jedna faktura moze mat iba jednu platbu a naopak
   */
  public Set<Par> parovanie(Set<Faktura> faktury, Set<Platba> platby);
}

Riešenie 1.

Najjednoduchšie riešenie, ktoré asi napadne každého ako prvé, je cyklus v cykle. Funguje tak, že vo vonkajšom cykle prechádzame všetky faktúry a vo vnútornom platby. Keď narazíme na zhodu, tak vytvoríme pár a vyskočíme z vnútorného cyklu. (predpoklad jedna faktúra môže mať iba jednu platbu a naopak)

public class RiesenieCyklus implements ParovanieRiesenie {

  public Set<Par> parovanie(Set<Faktura> faktury, Set<Platba> platby) {

      Set<Par> vysledok = new HashSet<Par>();

      for (Faktura faktura : faktury) {
          for (Platba platba : platby) {
              if (porovnanie(faktura, platba)) {
                  vysledok.add(new Par(faktura, platba));
                  break; // predpokladame, ze jedna faktura moze mat len jednu platbu
              }
          }
      }

      return vysledok;
  }

  /**
   * Porovna fakturu a platbu opdla urcitych kriterii.
   *
   * @param faktura na porovnanie
   * @param platba  na porovnanie
   * @return vrati true ak sa cislo faktury rovna variabilnemu symbolu platby a zaroven sa zhoduju sumy, inak false.
   */
  private boolean porovnanie(Faktura faktura, Platba platba) {
      return faktura.getCisloFaktury().equals(platba.getVariabilnySymbol())
              && faktura.getSuma().equals(platba.getSuma());
  }
}

Zrejmou výhodou takéhoto riešenia je jednoduchosť implementácie, ktokoľvek sa na to pozrie, hneď vie o čo ide. Horšie je to už s výkonom. Za predpokladu, že máme N faktúr a M platieb a nieje možné spárovať ani jednu platbu s faktúrou, tak sa telo vnútorného cyklu vykoná M*N krát. Pričom je predpoklad, že metóda porovnaj bude v skutočnosti komplexnejšia.

Riešenie 2.

Alternatívne riešenie, ktoré by som chcel opísať, spočíva v tom, že sa vyrobí spoločný kľúč pre faktúry aj platby. Pomocou tohoto kľúča sa v jednom cykle vložia do HashMap-y faktúry. A v druhom cykle, ktorý nieje vnorený, sa prehľadáva mapa pomocou kľúča vytvoreného z platieb. Ja som zvolil implementáciu kľúča tak, že obsahuje String, v ktorom je zakódovaná informácia z platby, alebo faktúry, pričom metódy equals a hashcode sú vygenerované nad týmto String-om.

public class RiesenieMapa implements ParovanieRiesenie {


  public Set<Par> parovanie(Set<Faktura> faktury, Set<Platba> platby) {

      Set<Par> vysledok = new HashSet<Par>();

      Map<Kluc, Faktura> mapaFaktury = new HashMap<Kluc, Faktura>();

      for (Faktura faktura : faktury) {
          mapaFaktury.put(new Kluc(faktura), faktura);
      }

      for (Platba platba : platby) {
          Faktura faktura = mapaFaktury.get(new Kluc(platba));

          if (faktura != null) {
              vysledok.add(new Par(faktura, platba));
          }
      }

      return vysledok;
  }

  private class Kluc {
      private static final String SEPARATOR = "_";

      private String kluc;

      /**
       * Vytvori kluc reprezentovany stringom v tvare "cislo faktury" + "separator" + "suma faktury".
       * <p/>
       * napr.: "000001_1000"
       *
       * @param faktura z ktorej sa vytvara kluc
       */
      private Kluc(Faktura faktura) {
          StringBuilder sb = new StringBuilder();

          sb.append(faktura.getCisloFaktury());
          sb.append(SEPARATOR);
          sb.append(faktura.getSuma().toPlainString());

          this.kluc = sb.toString();
      }

      /**
       * Vytvori kluc reprezentovany stringom v tvare "variabilny symbol" + "separator" + "suma platby".
       * <p/>
       * napr.: "000001_1000"
       *
       * @param platba z ktorej sa vytvara kluc
       */
      private Kluc(Platba platba) {
          StringBuilder sb = new StringBuilder();

          sb.append(platba.getVariabilnySymbol());
          sb.append(SEPARATOR);
          sb.append(platba.getSuma().toPlainString());

          this.kluc = sb.toString();
      }

      /**
       * Generovana metoda equals, ktora berie do uvahy vlastnost kluc.
       */
      @Override
      public boolean equals(Object o) {
          if (this == o) return true;
          if (o == null || getClass() != o.getClass()) return false;

          Kluc that = (Kluc) o;

          return kluc.equals(that.kluc);
      }

      /**
       * Generovana metoda hashCode, ktora berie do uvahy vlastnost kluc.
       */
      @Override
      public int hashCode() {
          return kluc.hashCode();
      }
  }
}

Výhodou tohoto riešenia je, že kód pre vytvorenie kľúča sa opakuje iba M+N krát. Samozrejme nie vždy je možné všetky podmienky zakódovať priamo do String-u. Tiež považujem za výhodu, že výkon algoritmu nieje až do takej veľkej miery ovplyvnený vstupnými dátami a teda je oveľa jednoduchšie ho predpovedať.

Možno by ešte stálo za zamyslenie ako by sa dala táto úloha efektívne rozdeliť aby sa mohla vykonávať paralelne, ale to už nechám na čitateľovi.

Ako na to HTTPS, JBoss a Seam

Toto je krátky návod, ktorý by mal pomôcť pri konfigurácii HTTPS komunikácie vo vývojom prostredí, ktoré obsahuje aplikačný server JBoss 5.1.0.GA a aplikáciu vygenerovanú nástrojom seam-gen vo verzii 2.1.2.

1. Vygenerovanie "selfsigned" certifikátu ak nemáme žiadny k dispozícii.
2. Nastavenie JBoss HTTPS konektora.
3. Konfigurácia stránok v Seame.

Vygenerovanie "selfsigned" certifikátu ak nemáme žiadny k dispozícii.

Na generovanie použijeme nástroj keytool, ktorý sa štandardne nachádza v Sun JDK.

cd %JAVA_HOME%\bin

C:\Program Files\Java\jdk1.6.0_10\bin\keytool -genkeypair -alias devServerCert -keyalg RSA -validity 1500 -keystore devServer.keystore

Enter keystore password: devserver
Re-enter new password: devserver
What is your first and last name?
[Unknown]:  Meno Priezvisko
What is the name of your organizational unit?
[Unknown]:  oddelenie
What is the name of your organization?
[Unknown]:  spolocnost
What is the name of your City or Locality?
[Unknown]:  mesto
What is the name of your State or Province?
[Unknown]:  stat
What is the two-letter country code for this unit?
[Unknown]:  sk
Is CN=Meno Priezvisko, OU=oddelenie, O=spolocnost, L=mesto, ST=stat, C=sk correct?
[no]:  yes

Enter key password for devservercert enter
 (RETURN if same as keystore password):

Je potrebné si uvedomiť, že heslo pre kľúč je také isté ako heslo pre keystore, preto je ako vstup na konci iba enter. Vygenerovaný súbor devServer.keystore okopírujeme do ...jboss-5.1.0.GA\server\default\conf\ za predpokladu, že používame profil default.

Nastavenie JBoss HTTPS konektora.

Za predpokladu, že používame profil default je potrebné zmeniť súbor ...\jboss-5.1.0.GA\server\default\deploy\jbossweb.sar\server.xml takto:

...
   <Connector protocol="HTTP/1.1" SSLEnabled="true"
        port="8443" address="${jboss.bind.address}"
        scheme="https" secure="true" clientAuth="false"
        keystoreFile="${jboss.server.home.dir}/conf/devServer.keystore"
        keystorePass="devserver" sslProtocol = "TLS" />
...

kde:
keystoreFile - je cesta kde je uloženýdevServer.keystore súbor
keystorePass - je heslo pre keystore a zároveň aj pre klúč v ňom uložený

Konfigurácia stránok v Seame.

• konfigurácia portov pre HTTP (8080) a HTTPS (8443) v štandartnom konfiguračnom súbore pages.xml

<?xml version="1.0" encoding="UTF-8"?>
<pages xmlns="http://jboss.com/products/seam/pages"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://jboss.com/products/seam/pages http://jboss.com/products/seam/pages-2.1.xsd"

    no-conversation-view-id="/home.xhtml"
    login-view-id="/login.xhtml"
    http-port="8080"
    https-port="8443">
...

• nastavenie pre konkrétnu stránku aby sa zobrazovala cez HTTPS protokol (v prípade, že request bude požadovať HTTP presmeruje sa na HTTPS), napríklad pre stránku login.xhtml stačí pridať scheme="https" do súboru login.page.xml

<?xml version="1.0" encoding="UTF-8"?>
<page xmlns="http://jboss.com/products/seam/pages"
   xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
   xsi:schemaLocation="http://jboss.com/products/seam/pages http://jboss.com/products/seam/pages-2.1.xsd"
   scheme="https">
...

Workaround for GWT Menubar issue 374

Issue link: Command based top level MenuItems (no sub-menu) stay highlighted when mouse leaves MenuBar.

Short description:

MenuItems on main MenuBar that have no sub-menus stay highlighted even after the mouse leaves the MenuBar. For example the fragment below produces just such a menu...

Workaround:

All workarounds provided on issue page required users to maintain their own GWT builds, which is pretty annoying for such a small nuisance. I have slightly modified one of those solutions, so that now you can package it into your application. It breaks some good practices concerning encapsulation, but it seems to work quite well with GWT 1.6.4. However use only at your own risk.

package com.yourcompany.gwtfix;

import com.google.gwt.user.client.DOM;
import com.google.gwt.user.client.Element;
import com.google.gwt.user.client.Event;
import com.google.gwt.user.client.ui.MenuBar;
import com.google.gwt.user.client.ui.MenuItem;

public class FixedMenuBar extends MenuBar {
    private static final String DEPENDENT_STYLENAME_SELECTED_ITEM = "selected";

    public void onBrowserEvent(Event event) {
        super.onBrowserEvent(event);
        MenuItem item = myFindItem(DOM.eventGetTarget(event));
        if (item == null) {
            return;
        }

        if (DOM.eventGetType(event) == Event.ONMOUSEOUT) {
            this.setSelectionStyle(item, false);
        } else if (DOM.eventGetType(event) == Event.ONMOUSEOVER) {
            this.setSelectionStyle(item, true);
        }
    }

    private void setSelectionStyle(MenuItem item, boolean selected) {
        if (selected) {
            item.addStyleDependentName(DEPENDENT_STYLENAME_SELECTED_ITEM);
        } else {
            item.removeStyleDependentName(DEPENDENT_STYLENAME_SELECTED_ITEM);
        }
    }

    private MenuItem myFindItem(Element hItem) {
        for (MenuItem item : getItems()) {
            if (DOM.isOrHasChild(item.getElement(), hItem))
                return item;
        }
        return null;
    }

    public FixedMenuBar() {
        super();
    }

    public FixedMenuBar(boolean autoClose) {
        super(autoClose);
    }
}

Ako na geolokáciu s WorldIP API

Pojem geolokácia (Geolocation) v tomto kontexte znamená určenie reálnej geografickej polohy počítača podľa jeho IP adresy.

Požiadavka:

Web stránka podporuje viac jazykových mutácií, medzi ktorými si užívateľ môže vybrať jazyk, ktorému rozumie. Pri otvorení stránky sa implicitne vyberie jazyk, ktorým sa hovorí v krajine, z ktorej je užívateľ pripojený na internet. Konkrétne, ak máme web stránku, ktorá podporuje anglický a slovenský jazyk, výsledok bude, že užívateľovi zo Slovenska, alebo Čiech sa načíta slovenská verzia a pri vstupe na stránku z iných krajín sa zobrazí anglická verzia.

Riešenie:

Riešenie by malo byť jednoduché, zadarmo, rýchlo realizovateľné a dostatočne univerzálne.
Malo by bežať na Google App Engine (GAE) s klientom v Google Web Toolkit (GWT).

Na prvý pohľad sa mi zapáčilo WorldIP API, pretože formát HTTP dotazu je veľmi jednoduchý a výsledkom je iba dvojmiestny kód krajiny. Teda nieje potrebné parsovať žiadne XML a neprenášajú sa iné zbytočné údaje.

Formát dotazu je:

http://api.wipmania.com/[IPADDR]?[URL]

kde:

IPADDR - je IP adresa, ktorej geografickú lokáciu chceme zistit URL - je doména našej aplikácie, slúži na kontrolu denných limitov

príklad: Aplikácia myappid.appspot.com sa dotazuje na pôvod IP adresy 123.45.67.89

http://api.wipmania.com/123.45.67.89?myappid.appspot.com

výsledok:

dvojznakový kód krajiny, napr. "SK" pre Slovensko.

Jednoduchá pomocná trieda, ktorá funguje aj na GAE:

public class WorldIPHelper {
...
 private static final String WIP_API_URL = "http://api.wipmania.com/";
 private static final String DOMAIN_NAME_PARAMETER = "?myappid.appspot.com";
...
 public static String getLocaleFromWorldIP(String remoteIPAddress) {
  String countryCode = "";
  try {
   URL url = new URL(WIP_API_URL + remoteIPAddress + DOMAIN_NAME_PARAMETER);
   BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
   char[] cbuf = new char[2];
   reader.read(cbuf);
   countryCode = new String(cbuf);
   reader.close();
  } catch (MalformedURLException e) {
   log.severe(e.toString());
  } catch (IOException e) {
   log.severe(e.toString());
  }
  return countryCodeToLocale(countryCode).getLocaleString();
 }
}

JSP stránka, ktorá nastavuje lokalizačnú vlastnosť GWT podľa IP adresy klienta.

...
<%
...
 localeString = WorldIPHelper.getLocaleFromWorldIP(request.getRemoteAddr());
...
%>
...
<meta name="gwt:property" content="locale=<%=localeString%>">
...

Limity:

- pre GAE platí hlavne skupina kvót UrlFetch - pre WorldIP API je to 10 000 dotazov denne na jednu aplikáciu

Ak by dané limity WorldIP API neboli dostačujúce, prípadne by nebolo vhodné sa z nejakého dôvodu spoliehať na externú službu, je tu tiež možnosť stiahnuť si priamo databázu IP adries, naimportovať si ju do vlastnej databázy a naimplementovať si vyhľadávanie vo vlastnej réžii.

Ak ste niekedy riešili niečo podobné, tak odporučte akú službu ste použili, prípadne či ste s ňou boli spokojní.

PR0GR4M470R5K4 UL0H4

V poslednom čase sa v reálnom živote, ale aj na internete rozpútala zúrivá reklamná kampaň, ktorá má okrem iného osloviť aj programátorov. Nemohol som si ju nevšimnúť, pretože každý deň chodím okolo veľkého reklamného nápisu:

BUĎTE LEPŠÍ AKO VŠETCI HACKERI SVETA.

Všimol som si, že táto reklama obsahuje aj malú programátorskú úlohu. A keďže každý programátor bez výnimky si myslí, že je najlepší na svete, tak ani ja som nemohol odolať a musel som ju kvôli spokojnému spánku vyriešiť.

Znenie úlohy je možné nájsť tu http://www.3537.sk/programator.html, citujem:

Máte zoznam súborov, v ktorom je každý súbor identifikovaný menom a podpisom. Meno je ľubovoľný reťazec v úvodzovkách a podpis je postupnosť nezáporných 32-bitových čísiel v šestnástkovej sústave ako môžete vidieť na obr. 01.

"test_name" 3a 45ffa2 236da0 34cc 21
"/usr/stdio.h" 456fa 34dd 28ab9 457e
".other.txt" 5623d ff3a21 783d 22456

Obr. 01: formát zoznamu súborov

Vašou úlohou je nájsť počet jedinečných súborov v zozname. Súbor je považovaný za jedinečný, ak jeho podpis nie je riadnym prefixom podpisu akéhokoľvek iného súboru v zozname. Podpis s1 je považovaný za riadny prefix podpisu s2 vtedy (a len vtedy), keď s2 začína s s1 a podpisy majú rôzne dĺžky. V prípade, že viaceré súbory majú rovnaký podpis, započítajte ich všetky.

Úlohu som rozdelil na dve časti:

1. načítanie celého súboru do pamäte a rozparsovanie obsahu do vhodnej dátovej štruktúry
2. algoritmus, ktorý počíta požadované hodnoty nad touto dátovou štruktúrou

Ďalej sa bodom 1 nebudem zaoberať, pretože ho nepovažujem za dôležitý. Predpokladajme, že máme už celý obsah súboru uložený v List<FileDescription>, kde FileDescription vyzerá takto:

public class FileDescription {
    private String name;
    private List<Long> signature = new ArrayList<Long>();

    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public int getSignatureSize() { return signature.size(); }
    public Long getSignature(int index) { return signature.get(index); }
    public void addSignature(long signature) { this.signature.add(signature); }
}

Je to obyčajný value object, ktorý obsahuje meno súboru, a podpis, ktorý je List Long-ov, pretože do Java int-u sa 32-bitové číslo nezmestí. (kvôli znamienku)

Riešenie 1 (Java):

Najjednoduchšie riešenie spočíva v tom, že najprv zoradíme FileDescription prvky v Liste podľa veľkosti podpisu od najväčšieho po najmenší a potom prejdeme každý prvok v Liste od začiatku a skontrolujeme, či má nejaké duplikáty. Ak na nejaký duplikát narazíme, proste ho z Listu vymažeme. Na konci metódy nám v Liste ostanú iba unikátne (jedinečné) súbory.

    private static class FileDescriptionComparatorLargestFirst implements Comparator<FileDescription>, Serializable {
        public int compare(FileDescription fileDescription1, FileDescription fileDescription2) {
            if (fileDescription1.getSignatureSize() < fileDescription2.getSignatureSize()) return 1;
            if (fileDescription1.getSignatureSize() > fileDescription2.getSignatureSize()) return -1;
            return 0;
        }
    }

    public int calculateNumberOfUnique1P(List<FileDescription> fileDescriptions) {
        Collections.sort(fileDescriptions, new FileDescriptionComparatorLargestFirst());
        for (int i = 0; i < fileDescriptions.size(); i++) {
            FileDescription outerFileDescription = fileDescriptions.get(i);
            for (int j = i + 1; j < fileDescriptions.size(); j++) {
                FileDescription innerFileDescription = fileDescriptions.get(j);
                if (outerFileDescription.getSignatureSize() > innerFileDescription.getSignatureSize()) {
                    boolean equal = true;
                    for (int k = 0; k < innerFileDescription.getSignatureSize(); k++) {
                        if (!innerFileDescription.getSignature(k).equals(outerFileDescription.getSignature(k))) {
                            equal = false;
                            break;
                        }
                    }
                    if (equal) {
                        fileDescriptions.remove(innerFileDescription);
                        j--;
                    }
                }
            }
        }
        return fileDescriptions.size();
    }

• algoritmus využíva 3 vnorené for cykly, čo na prvý pohľad naznačuje, že nebude príliš výkonný, ale malý test súbor set_small.dat spracuje bez problémov v zlomku sekundy
• taktiež výsledok zahŕňa List s unikátnymi súbormi a nielen ich počet (aj keď metóda vracia iba číslo)
• vyskúšal som metódu aj na veľkom súbore set_large.dat, ale aby sa súbor vôbec načítal do pamäte je potrebné pridať pamäť pre JVM oproti štandardnému nastaveniu, napríklad takto -Xms128m -Xmx1024m
• kým sa algoritmus dopracoval k výsledku prešlo viac než 20 minút, takže "Tudy cesta nevede." :)

Riešenie 2 (Java):

Druhý algoritmus rozdelí súbory z Listu do Mapy Listov podľa ich podpisu, najprv podľa prvého čísla v podpise a potom odstráni na tej úrovni všetky duplikáty a unikátne súbory z Listu a opakuje tú istú procedúru pre všetky Listy v Mape rekurzívne. Týmto spôsobom sa dá dosiahnuť minimalizácia porovnávania podpisov jednotlivých súborov.

    public int calculateNumberOfUnique2P(List<FileDescription> fileDescriptions) {
        List<FileDescription> uniques = new ArrayList<FileDescription>();
        List<FileDescription> duplicates = new ArrayList<FileDescription>();

        recurseFileDescriptionListP(fileDescriptions, 0, uniques, duplicates);

        return uniques.size();
    }

    private void recurseFileDescriptionListP(List<FileDescription> fileDescriptions, Integer level, List<FileDescription> uniques, List<FileDescription> duplicates) {
        if (level > 0) {
            if (fileDescriptions.size() == 1) {
                uniques.add(fileDescriptions.get(0));
                return;
            }
            if (fileDescriptions.size() > 0) {
                List<FileDescription> cleanCandidates = new ArrayList<FileDescription>();
                Integer largestSizeInList = 0;
                for (FileDescription fileDescription : fileDescriptions) {
                    if (fileDescription.getSignatureSize() == level) {
                        cleanCandidates.add(fileDescription);
                    }
                    if (fileDescription.getSignatureSize() > largestSizeInList) {
                        largestSizeInList = fileDescription.getSignatureSize();
                    }
                }
                if (cleanCandidates.size() > 0) {
                    if (largestSizeInList.equals(level)) {
                        uniques.addAll(cleanCandidates);
                        return;
                    }
                     if (largestSizeInList > level) {
                        duplicates.addAll(cleanCandidates);
                        fileDescriptions.removeAll(cleanCandidates);
                    }
                }
            }
        }

        Map<Long, List<FileDescription>> longFileDescriptionMap = new HashMap<Long, List<FileDescription>>();

        for (FileDescription fileDescription : fileDescriptions) {
            Long key = fileDescription.getSignature(level);
            List<FileDescription> fileDescriptionList = longFileDescriptionMap.get(key);
            if (fileDescriptionList == null) {
                fileDescriptionList = new ArrayList<FileDescription>();
                longFileDescriptionMap.put(key, fileDescriptionList);
            }
            fileDescriptionList.add(fileDescription);
        }

        for (List<FileDescription> fileDescriptionList : longFileDescriptionMap.values()) {
            recurseFileDescriptionList(fileDescriptionList, level + 1, uniques, duplicates);
        }
    }

• aby sme zabránili pretečeniu zásobníka pri tejto metóde je potrebné upraviť parametre JVM, napríklad takto -Xms128m -Xmx1024m -Xss64m
• výsledkom algoritmu sú 2 nové Listy, jeden obsahuje unikátne súbory a druhý duplicitné
• beh programu pre veľký testovací súbor set_large.dat trvá menej ako jednu sekundu
• pomerne ľahko by sa dal prepísať aby bežal vo viacerých threadoch

Riešenie 3 (C++):

Toto riešenie je prepisom riešenia 2 do iteratívnej podoby, teda ten istý algoritmus, ale bez rekurzie a pretože je napísaný v C++, tak opakujem aj triedu FileDescription.

class FileDescription {
private:
    string name;
    vector<unsigned int> signature;
public:
    string getName() const { return name; }
    void setName(string name) { this->name = name; }
    unsigned int getSignature(unsigned int level) const { return signature[level]; }
    void addSignature(unsigned int signature) { this->signature.push_back(signature); }
    unsigned int getSignatureSize() const { return this->signature.size(); }
};

unsigned int cleanFileDescriptions3P(list<FileDescription*>& fileDescriptions, unsigned int level, unsigned int& uniques, unsigned int& duplicates) {
    if (fileDescriptions.size() == 1) {
        uniques++;
        return 0;
    }
    if (fileDescriptions.size() > 1) {
        list<FileDescription*> toRemove;
        unsigned int largestSizeInList = 0;

        for (list<FileDescription*>::iterator iter = fileDescriptions.begin(); iter != fileDescriptions.end(); ++iter) {
            unsigned int signatureSize = (*iter)->getSignatureSize();
            if (signatureSize == level+1) {
                toRemove.push_back((*iter));
            }
            if (signatureSize > largestSizeInList) {
                largestSizeInList = signatureSize;
            }
        }
        if (toRemove.size() > 0) {
            if (largestSizeInList == level+1) {
                uniques += toRemove.size();
                return 0;
            }
            if (largestSizeInList > level+1) {
                duplicates += toRemove.size();

                for (list<FileDescription*>::const_iterator iter = toRemove.begin(); iter != toRemove.end(); ++iter) {
                    fileDescriptions.remove(*iter);
                }
            }
        }
    }
    return fileDescriptions.size();
}

void calculateNumberOfUnique3P(list<FileDescription*>& fileDescriptions, unsigned int& uniques, unsigned int& duplicates) {
    unsigned int level = 0;
    map<unsigned int, list<FileDescription*> > fileDescriptionMap;
    list<list<FileDescription*> > fileDescriptionsListOfLists;

    fileDescriptionsListOfLists.push_back(fileDescriptions);

    while (!fileDescriptionsListOfLists.empty()) {
        for (list<list<FileDescription*> >::const_iterator outerListIter = fileDescriptionsListOfLists.begin(); outerListIter != fileDescriptionsListOfLists.end(); ++outerListIter) {

            for (list<FileDescription*>::const_iterator innerListIter = (*outerListIter).begin(); innerListIter != (*outerListIter).end(); ++innerListIter) {
                unsigned int key = (*innerListIter)->getSignature(level);
                fileDescriptionMap[key].push_back((*innerListIter));
            }
        }
        fileDescriptionsListOfLists.clear();

        for (map<unsigned int, list<FileDescription*> >::const_iterator mapIter = fileDescriptionMap.begin(); mapIter != fileDescriptionMap.end(); ++mapIter) {
            list<FileDescription*> fileDescriptionsPart = mapIter->second;

            unsigned int unresolvedListFlag = cleanFileDescriptions3P(fileDescriptionsPart, level, uniques, duplicates);
            if (unresolvedListFlag>0) {
                fileDescriptionsListOfLists.push_back(fileDescriptionsPart);
            }
        }
        fileDescriptionMap.clear();
        level++;
    }
}

• výsledkom sú dve čísla a to počet duplicitných a počet unikátnych súborov
• výkon je porovnateľný s riešením číslo 2

Záver:

Moje výsledky:

• set_small.dat: spolu súborov 942, z toho unikátnych 851
• set_large.dat: spolu súborov 106020, z toho unikátnych 96312

Zadávatelia úlohy výsledky nezverejnili, takže nemám možnosť si skontrolovať či som zadanie pochopil správne. Každopádne pokiaľ problém niekto riešil, určite napíšte komentár ako Vám vyšiel, prípadne aj linku na Vaše riešenie.

Čo dodať ku koncu? Netrúfam si síce povedať, že som lepší ako najlepší hackeri sveta. Ale za predpokladu, že najlepší hackeri sveta sú z Číny, som lepší ako najlepší hackeri sveta v jedení lyžičkou. :)

A čo Vy? Ste lepší ako najlepší hackeri sveta?