Blog do projektu Open Source JavaHotel

piątek, 29 lipca 2011

Find all subsets recursively

Problem
Having a set of positive numbers from 0 to 9 find recursively all subsets which sums up to 10.

Algorithm 1
Take a subset. If sums up to 10 then print it. Is sums less than 10 then break. Then apply the same algorithm for any subset received by removing from the first subset one element.
Start with the initial set.
C++ code :
#include <iostream>
#include <vector>

const int SET_SIZE = 10;
typedef std::vector<bool> settype;
const int SUM=10;

void print(const settype &set) {
  for (int i=0; i<SET_SIZE; i++) {
    if (set[i]) std::cout<<i+1<<' ';
  }
  std::cout<<std::endl;
}

void run_set(settype set,int sum, int remove) {
  if (remove != -1) {
    set[remove] = false;
    sum -= (remove + 1);
  }
  if (sum < SUM) return;
  if (sum == SUM) print(set);

  for (int i = remove+1; i<SET_SIZE; i++) {
    if (set[i]) {
      run_set(set,sum,i);
    }
  }
}

int main(int argc, char **argv) {
    bool init_set[SET_SIZE] = { true,false,true,true,false,true,true,true,false,true};
    settype setOfNum(init_set,init_set + sizeof(init_set) / sizeof(bool));
    int sum = 39;
    run_set(setOfNum,sum,-1);   
    return 0;
}


Algorithm 2
Apply a variant of 0-1 snapsack problem.
Take a subset.
  1. If subset sums to less than 10 then break.
  2. Remove last element and find all subsets which sums to 10.
  3. Remove last element and find all subsets which sums to 10 minus the last element.
  4. Sums set of sets received in point 1) and set of sets received in point 2) plus the last (removed) element.
C++ code:
#include <iostream>

#include <vector>
#include <algorithm>
using namespace std;

const int SUM=10;

typedef std::vector<int> settype;
typedef std::vector<settype> listofset;

void print(const settype &set) {
    for (int k=0; k<set.size(); k++) {
      cout << set[k] << ' ';
    }
    cout << endl;
}  

void D(int i,int w,const settype &set,listofset &outlist) {
  listofset list1,list2;
  i--;
  if ((w == 0) || (i == -1)) {
    outlist = list1;
    return;
  }
  D(i,w,set,list1);
  D(i,w-set[i],set,list2);
  outlist = list1;
  for (int k=0; k<list2.size(); k++) {
    list2[k].push_back(set[i]);
    outlist.push_back(list2[k]);
  }
  if (set[i] == w) {
    settype t;
    t.push_back(set[i]);
    outlist.push_back(t);
    return;
  }
}
  

int main(int argc, char **argv) {
    int init_set[] = { 1,9,10,2,7 };
    settype set(init_set,init_set + sizeof(init_set) / sizeof(int));
    listofset outset;
    D(set.size(),SUM,set,outset);
    for (int i=0; i<outset.size(); i++) {      
     cout << i << ":";
      print(outset[i]);
    }  
    return 0;
}

Remarks
Of course - it is an artificial problem, the best way is to apply simple iteration without recursion.
Another problem is the complexity. The number of all subsets of n-element set is exponential (2 to power n). So the algorithm is no worse than that. But is it possible to do it faster - in polynomial complexity.

niedziela, 24 lipca 2011

BenchmarkSQL

I started playing with the opensource tool "BenchmarkSQL". It allows to run TPC-C like test allowing measuring OLTP performance on different databases. Unfortunately, I had to fix several minor bugs - it seemed that loading data does not work correctly - the order of columns in several tables does not match INSERT and LOAD command. I also added additional run-time parameters for setting some settings related to test.
-DNoW={number of warehouses}
-DNoT=10 {number of terminales}
-DNoM=5 {number of minutes for test to run}
The fixed version can be downloaded from : BenchmarkSQL
I run the test again DB2, Oracle and Postgress databases running on the same box : Ubuntu, ThinkPad T-42, 1.7 GH IntelPentium, 2 GB RAM.
The databases have been installed out of the box, using default settings. The current score is as follows (10 warehouses, 10 terminals, 5 minute test)
Oracle: tpmC = 410
DB2: tpmC = 260
Postgres : tpmC = 240
I will try to improve DB2 performance by providing some tunning.

wtorek, 19 lipca 2011

Byliśmy na przedstawieniu

Dnia 18 lipca 2011 roku byliśmy na przedstawieniu opery Mozarta "Idomeneo, król Krety" wystawianego w ramach XXI Festiwalu Mozartowskiego, ale wyszliśmy mocno rozczarowani.
"Idomeneo" to mniej znana opera Mozarta, pozostająca trochę w cieniu sławniejszych oper tego kompozytora. A zupełnie niesłusznie, to także piękna muzyka i efektowne arie. Tego samego zdania był przecież sam Mozart, który kilka zapożyczeń z "Idomeneo" przeniósł do późniejszych dzieł. Na przykład, marsz z towarzyszeniem recytatywu Elektry z pierwszego aktu jako żywo przypomina słynny "Ecco la marcia" z trzeciego aktu "Wesela Figara". Tylko, że w tym przedstawieniu zupełnie nie było tego słychać, jakby realizatorzy chcieli nas przekonać, że mniejsza popularność tej opery jest w pełni zasłużona.
Zupełnie zawiódł odtwórca głównej roli, wyraźnie czuł się bardzo niepewnie, kilkakrotnie niezbędna była pomoc suflera. W konsekwencji, w miarę upływu czasu każde pojawienie się tej postaci powodowało rosnący niepokój, czy coś znowu nie pójdzie źle. Zły nastrój udzielił się chyba także orkiestrze, która wyraźnie nie była w formie, czasami bardziej przeszkadzała wykonawcom niż pomagała. 
Także inscenizacja nie trafiła mi do przekonania, nie potrafiłem zrozumieć zamiłowania inscenizatora do pogrążania sceny w mroku, cały czas odnosiłem wrażenie, że wykonawcy śpiewają z piwnicy. W operze istotną rolę pełni morski potwór pustoszący Kretę jako karę za złamaną obietnicę Idomenea. Na scenie widzimy dwie istoty z zaświatów - raz to prawdziwe monstrum, zaś potem na scenie nam towarzyszy ubrane w złoto bóstwo, sądząc z trojzębu trzymanego w ręku miał to być bóg Posejdon. Ale to bóstwo pada pod ciosem Idamanta, zaś potem głos z zaświatów oznajmia ostateczną wolę Posejdona i sztuka znajduje szczęśliwe zakończenie. Więc jeśli był tutaj jakiś zamysł inscenizatorski, to sens całkowicie mi umknął.
Na szczęście pozostali wykonawcy stanęli na wysokości zadania. Nie zawiódł ani Sylweser Smulczyński jako Idamante, ani Marta Boberska jako Ilia. Zaś każde pojawienie się Gabrieli Kamińskiej w roli Elektry podnosiło temperaturę o kilka stopni. Końcowe wykonanie brawurowej arii ""D'Oreste, d'Ajace" zapadało w pamięć.
Także chór wypadł znakomicie. W "Idomeneo", inaczej niż w innym operach Mozarta, chór ma dużą rolę do odegrania, w tym partie solowe.
Ale złe wrażenie jednak pozostało. Trzeba mieć tylko nadzieję, że jeśli Warszawska Opera Kameralna utrzyma w programie to przedstawienie w następnym roku, to poprzedzi występ bardziej starannymi przygotowaniami i z lepszym przemyśleniem, co zaprezentować widzom.

poniedziałek, 18 lipca 2011

Byliśmy na koncercie

16 lipca 2011 roku byliśmy na przedstawieniu (a właściwie projekcji) inscenizacji "Króla Rogera" w ramach tegorocznego Festiwalu "Ogrody Muzyczne", podobało nam się bardzo, chociaż z pewnymi zastrzeżeniami. Była to rejestracja przedstawienia, które miało swoją premierę w 2009 roku w paryskiej "Opéra Bastille". Przedstawienie odbyło się w atmosferze skandalu spowodowanego kontrowersyjną inscenizacją Krzysztofa Warlikowskiego. Przykłady druzgocących recenzji można znaleźć w Gazecie Wyborczej lub w polskiej edycji Newsweeka
Zacytuję fragment z tej drugiej recenzji:
Widzowie znający utwór słabo – Francuzi, którzy go dotąd nie widzieli, albo Polacy z rzadka bywający w operze – skłonni byli tej inscenizacji bronić.
 Jestem skłonny bronić tej inscenizacji, aczkolwiek z przyczyn innych niż to zakłada autor recenzji.
Gdyż o czym opowiada nam libretto opery (autorstwa Iwaszkiewicza) ? Na dwór mądrego króla Rogera, spędzającego wieczór w towarzystwie uroczej żony Roksany (równolegle odprawiana jest liturgia religijna) przybywa tajemniczy Pasterz, szukający zbłąkanych stad w imieniu nieznanego boga. W zetknięciu z Pasterzem, cały ten uporządkowany i zorganizowany świat świecki i religijny rozpada się w gruzy porywając także Rogerowi ukochaną Roksanę.
Pod to libretto można podkładać czy doszukiwać się dowolnych znaczeń, można także tego nie robić. I wyraźnie tą drugą drogą poszedł Warlikowski. Nie próbuje nam opowiadać jakiejś historii czy sugerować, że kryją się pod tym głębokie i ponadczasowe treści. Na scenie widzimy absurdalny i nierzeczywisty świat, przypominający atmosferą dawne filmy science-fiction. Chociaż końcowa scena, gdzie Pasterz ma założoną głowę Myszki Miki, zaś tłum oddaje cześć słońcu wyobrażonemu w postaci neonu przypominającego wejście do baru sugeruje, że owym nowym bogiem, do którego prowadzi Pasterz są nasze współczesne bożki kultury masowej.
Można próbować to zrozumieć, ale wtedy ryzykujemy porażkę niczym tytułowy król Roger usiłujący zrozumieć, co się wokół niego dzieje.Oczywiście, tego typu inscenizacja odniesiona do np. opery Mozarta pewnie by raziła tanim efekciarstwem.
Głównym zarzutem jaki można postawić tej inscenizacji, jak zauważył we wprowadzeniu Zygmunt Krauze, jest to, że tutaj gubi się niestety piękna i oryginalna muzyka Szymanowskiego. Zamiast słuchać muzyki śledzimy na scenie kolejne pomysły inscenizatorskie.
Ogromnym atutem przedstawienie jest także doskonałe wykonawstwo: Mariusz Kwiecień, Olga Pasiecznik oraz Eric Cutler (jako Pasterz). Chociaż też można odnieść wrażenie, że czasami ekspresja o charakterze aktorskim przytłacza stronę muzyczną.
Część osób zgromadzonych w namiocie, gdzie odbyła się projekcja, była zniecierpliwiona długim wprowadzeniem w muzykę Szymanowskiego Zygmunta Krauze i Krzysztofa Baculewskiego. My jednak słuchaliśmy z zainteresowaniem, obaj rozmówcy doskonale znali temat, zaś Szymanowski - chociaż "pierwszy po Chopinie" - to ciągle człowiek i kompozytor mało znany, także w Polsce.
Uderzała także wysoka frekwencja, namiot na kilkaset osób był prawie pełny, i to pomimo tego, że muzyka Szymanowskiego nie jest łatwa w odbiorze, wymaga pewnego przygotowania od słuchacza. Dzieło Szymanowskiego zostawia dużo swobody wykonawcom,  na pewno jest dużo pola do popisu dla innych inscenizatorów i na pewno znajdą się widzowie i słuchacze.

czwartek, 7 lipca 2011

GWT+DB2+Spring

Next version of the simple database/GWT application. The whole source code is available and can be downloaded.
Introduction
The application displays the content of EMPLOYEE table from DB2 sample database. But what is worth personal data without keeping some  additional data like: documents, images, scans etc ? So I decided to extend the application by this feature.
Database
Data like that can be kept in database as blob column. Because more than one document related to a single employee can be stored I decided to create additional table to implement this one-to-many relationship.
create table empattach (id INTEGER GENERATED ALWAYS AS IDENTITY, empno char(6) NOT NULL, filename varchar2(100) NOT NULL, comment varchar2(100), adddate DATE DEFAULT CURRENT DATE, attach BLOB)
alter table empattach FOREIGN KEY FOREIGN_EMPNO (EMPNO) REFERENCES EMPLOYEE ON DELETE NO ACTION

Defining foreign key (the second statement) is not necessary from the application point of view. But by introducing this constraint we are sure that we would not have "dangling" attachment in our database, it is enforced by the database engine.
Because it is one-to-many relationship the "empno" column is not a primary key for empattach table, additional identity column (generated automatically) is defined.
Client application
Additional column "Att" was added. This column displays number of attachments related to the employee and also - after clicking at this cell - additional window pop-ups enabling some actions on attachments.


In order to activate this additional window GWT ActionCell extended as Button was used. The code is something like:
 
private class AttachClass implements ActionCell.Delegate {

  @Override
  public void execute(OneRecord object) {
   AttachmentDialog a = new AttachmentDialog(object, rInfo);
   PopupDraw p = new PopupDraw(a, false);
   p.draw(100, 100);
  }

 }

 private class ActionNumberCell extends ActionCell {

  private final RowFieldInfo f;

  ActionNumberCell(RowFieldInfo f) {
   super("", new AttachClass());
   this.f = f;
  }

  @Override
  public void render(Cell.Context context, OneRecord value,
    SafeHtmlBuilder sb) {
   FieldValue numb = GetField.getValue(f, value);
   sb.appendHtmlConstant("");
   sb.append(numb.getiField());
   sb.appendHtmlConstant("");
  }

 }

       private Column constructAction(RowFieldInfo f) {
  ActionNumberCell ce = new ActionNumberCell(f);
  return new ButtonColumn(ce);
 }


This column cell behaves like a normal button and activates an action after clicking at it.
Sending attachments to and fro
Uploading and downloading attachments is done by a traditional servlet, it does not make any sense to do it via RPC call.
So web.xml file keeps additional definitions for servlets implementing GET and POST method.
In GWT code uploading (sending attachment from client to the server) is done via FormPanel and triggering "SUBMIT" action.
Downloading (sending attachment from server to the client) is implemented via enabling Anchor (link) to click on.
Because together with attachment also content-type is sent (based on file name extension) the web browser will try to apply the proper action for the file sent - for instance: to display an image. It is very nice part of it, not trivial action  affordable for a song.
Server side
There is a standard definition of two servlets on the server side, one for uploading and the second for downloading. Storing and extracting blob column to and from the database is done via Spring LobHandler class. In order to send a valid content-type very nice feature of Java EE is used  :
MimetypesFileTypeMap (starting from Java 1.6 it comes also with JRE).
Refactoring
Unfortunately, by adding this feature the code size doubled. On the other by refactoring the code responsible for displaying a table on the screen (RecordPresentation.java) I was able to reuse this code twicely: to display the rows from the employee table and also for displaying the list of attachments (empattach table).

poniedziałek, 4 lipca 2011

BoaTester - new version

I added a simple enhancement do Selenium extension to BoaTest framework. I found very annoying using long XPath selectors for GWT Presentation CellTable. It looks like:
xpath=/html/body/table/tbody/tr[2]/td[2]/table/tbody/tr[3]/td/table/tbody/tr[2]/td/table/tbody/tr/td/table/tbody/tr[2]/td[2]/div
or
xpath=/html/body/table/tbody/tr[2]/td[2]/table/tbody/tr/td/table/tbody/tr[2]/td/table/tbody/tr/td/table/tbody/tr[2]/td/div[text() = '6'] 
But - if test case is related to the same table - all that selectors share the same starting xpath. So the solution is to introduce a "macro"or interpolation just avoiding entering repeating sequences. There is very useful option in Python ConfigParser class. But action sequence (selenium.file)  for Selenium based test case is read by basic File object so this option is not available immediately. So it was necessary to implement it manually through the following procedure:
"""Replace variables using format (like ConfigParser) %(..)s
    
    Args:
      line : line to be changed
      param : TestParam 
      teparam : OneTestParam
      
    Returns:
      Fixed line
      
    Raises: 
      Exception if variable for replacement not found
      
    """


def replaceLine(line,  param,  teparam):
    while 1 :
        low = line.rfind("%(")
        if low == -1 : break
        up = line.rfind(")s")
        if up == -1 : break
        before = line[0: low]
        after = line[up+2: len(line)]
        key = line[low+2: up]
        value = teparam.getPar(key)
        if value == None : value = param.getPar(key)
        if value == None : 
            raise TestException(key + " variable for replacement not found !")
        line = before + value + after
        
    return line     

I decided to use the same syntax (%(...)s) like in ConfigParser to avoid reinventing the wheel. "Variables" for macro substitution are taken for test.properties file.

So now it is possible to put long XPath selected sharing the same theme in much simpler and less error prone manner.

test.properties
tabletestbase=xpath=/html/body/table/tbody/tr[2]/td[2]/table/tbody/tr[3]/td/table/tbody/tr[2]/td/table/tbody/tr/td/table/tbody/tr[2]/td
and Selenium action file :
isPresent : %(tabletestbase)[2]/div
waitFor :  %(tabletestbase)s/td/div[text() = '6']