nedeľa 4. septembra 2011

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.

8 komentárov:

  1. Kdy bude mit tenhle clanek druhy dil trosku zajimavych a netrivialnich vecech ktere se toho tykaji ?

    OdpovedaťOdstrániť
  2. po spárování by se ta faktura mohla vždycky vyhodit z té mapy, což by mělo postupně zrychlovat to hledání Faktura faktura = mapaFaktury.get(new Kluc(platba));

    OdpovedaťOdstrániť
  3. Druhy diel zatial neplanujem, nikdy som netvrdil, ze je to nieco netrivialne, alebo zlozite, ale dufam, ze aspon niekomu to pomoze. Skor som sa snazil aby to bolo prakticke a nie prilis dlhe.

    Co sa tyka vyhadzovania sparovanych faktur z mapy, tak priznam sa, ze to ma vobec nenapadlo. Ako by to bolo efektivne zalezi asi od toho do akej miery by dochadzalo ku koliziam pri pristupe do mapy. (tj. ci by vobec niekedy bol pre dve rozne faktury vypocitany rovnaky hashcode)

    OdpovedaťOdstrániť
  4. pekny clanok, urcite zaciatocnikom pomoze

    OdpovedaťOdstrániť
  5. Odkud ty faktury a platby načítáte? Z databáze? A neumí ta databáze to párování udělat sama, jedním správně napsaným dotazem?

    OdpovedaťOdstrániť
  6. Za predpokladu, ze by boli data v databaze a parovacie kriteria by sa dali vyjadrit vo WHERE klauzule, tak by bolo samozrejme mozne riesit to databazovym dotazom.

    OdpovedaťOdstrániť
  7. Děkuji za zajímavý článek. Postupů jak zrychlit algoritmy není nikdy dost.
    Dovolím si však poznámku. Podobnou úlohu jsem kdysi řešil. Praxe totiž vypadá rapidně jinak.
    S fakturami není problém. Stačí zajistit unikátnost čísel faktur. Předpokládám, že jsou generovány námi tvořeným IS. Pak mohou být rovnou uloženy v Mapě.
    PROBLÉM je ale s platbami. Správně přepsat variabilní symbol je pro mnoho lidí nepřekonatelný problém. V lednu tak pravidelně chodí faktury s variabilním symbolem 1, v únoru 2, atd. Případně plátce nemá dostatečnou hotovost, ale aby projevil snahu platit, zaplatí např. pouze polovinu. Další část pak zaplatí třeba příští mesíc.
    Často pomáhá identifikovat platbu i podle čísla účtu odkud daná platba přišla (pokud není zaplacená složenkou). Proto se některé instituce ptají na číslo účtu, odkud bude placeno.
    Automatizované párování je dobrá pomůcka, ale IS by měl nabízet i další služby. Půjde vždy o manuální procesy realizované účetní/m. Např. spárování více plateb k jedné faktuře, roztržení vytvořeného páru protože k sobě napatří, spárování i bez shodného čísla faktury a variabilního symbolu platby, atd.

    OdpovedaťOdstrániť
  8. Já většinou řeším párování tak, že si obě množiny podle klíče setřídím a pak je jednoduše v cyklu procházím najednou oba setříděné seznamy a spárují záznamy s odpovídajícími kliči. Výhoda tohoto způsobu je v tom, že má menší nároky na paměť - nepotřebujete vytvářet hashovací tabulku. Např. pokud jsou platby a faktury uloženy v relační databázi, stačí do databáze poslat 2 dotazy, které budou vracet správně setřídené seznamy faktur a plateb určených ke spárování. Párovací program potom bude mít v paměti najednou pouze 1 platbu a 1 fakturu :-) .

    OdpovedaťOdstrániť