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.
