RSS

Przetwarzanie sekwencyjne kolekcji danych

Liczba odsłon: 186

Kolekcje da­nych w ję­zy­ku Java ewo­lu­owa­ły od amor­ficz­nych, przez ge­ne­rycz­ne, aż po prze­twa­rza­ne sek­wen­cyj­ne. Najnowsza wer­sja ję­zy­ka ob­słu­gu­je wy­ra­że­nia lamb­da, jed­nak im­ple­men­tac­ja pro­ce­du­ral­na w po­sta­ci bi­blio­te­ki Google Guava, zgod­nej ze spe­cy­fi­kac­ja­mi 1.6 i 1.7 ję­zy­ka, po­ja­wi­ła się wcześ­niej i zdo­by­ła spo­rą po­pu­lar­ność wśród pro­gra­mis­tów.

Idea zreali­zo­wa­na w bi­blio­te­ce Guava po­le­ga na prze­twa­rza­niu nie go­to­wych za­sob­ni­ków da­nych, lecz sek­wen­cyj­nych wi­do­ków re­pre­zen­to­wa­nych przez ite­ra­to­ry. Gdy po­ja­wi­ła się tab­li­co­wa po­stać pęt­li for, inter­fejs Iterator po­padł w nie­łas­kę, jed­nak ca­ły czas je­go sto­so­wa­nie wią­że się z ko­rzyś­cia­mi. Bibliote­ka Guava wpro­wa­dza no­wą kla­sę po­moc­ni­czą Iterables, któ­rej me­to­dy po­zwa­la­ją na two­rze­nie tym­cza­so­wych, nie­mu­to­wal­nych, ite­ro­wal­nych wi­do­ków ko­lek­cji da­nych pod­le­ga­ją­cych prze­kształ­ce­niom.

Rozpozna­wa­ne są dwa pod­sta­wo­we ro­dza­je prze­kształ­ceń. Predyka­ty umoż­li­wia­ją filt­ro­wa­nie ko­lek­cji i od­rzu­ca­nie z nich ele­men­tów nie speł­nia­ją­cych okreś­lo­ne­go kry­terium:

new Predicate<ElementType>() {
   @Override
   public boolean apply(ElementType element) {
      .....
   }
}

Z kolei funk­cje po­zwa­la­ją za­mie­nić war­tość lub typ ele­men­tu, prze­kształ­ca­jąc ko­lek­cję zgod­nie z pew­nym algo­ryt­mem:

new Function<SourceType, TargetType>() {
   @Override
   public TargetType apply(SourceType element) {
      .....
   }
}

Dodatkowo, je­że­li pro­gra­mis­tę in­te­re­su­ją je­dy­nie naj­prost­sze ope­rac­je, do dys­po­zyc­ji sto­ją kla­sy po­moc­ni­cze Predica­tes oraz Functions. Ta pierw­sza za­wie­ra zbiór me­tod bu­dow­ni­czych, umoż­li­wia­ją­cych uzys­ka­nie do­stę­pu do pre­de­fi­nio­wa­nych obiek­tów pre­dy­ka­tów wy­ko­nu­ją­cych pros­te ana­li­zy re­fe­ren­cji i tek­stu oraz łą­cze­nie pre­dy­ka­tów w więk­sze two­ry. Functions z kolei za­wie­ra funk­cje wy­szu­ku­ją­ce in­for­mac­je oraz zwra­ca­ją­ce in­for­mac­je diag­no­stycz­ne.

Zalety

Najważniej­szą za­le­tą prze­twa­rza­nia za­war­toś­ci ko­lek­cji za po­mo­cą pre­dy­ka­tów i funk­cji jest brak po­śred­nich za­sob­ni­ków da­nych. Przy zwyk­łym wie­lo­eta­po­wym prze­twa­rza­niu za­sob­ni­ków, na każ­dym eta­pie two­rzo­na jest no­wa po­stać ko­lek­cji, re­pre­zen­to­wa­na przez no­wy (po­ten­cjal­nie nie­mu­to­wal­ny) za­sob­nik. Język Java za­pew­nia współ­dzie­le­nie ele­men­tów ko­lek­cji mię­dzy za­sob­ni­ka­mi, jed­nak przy ich roz­mia­rach rzę­du milio­na ele­men­tów każ­dy etap prze­twa­rza­nia ozna­cza ko­niecz­ność zuży­cia od czte­rech do oś­miu me­ga­baj­tów pa­mię­ci (i to przy za­ło­że­niu opty­mal­ne­go two­rze­nia do­ce­lo­we­go za­sob­ni­ka w jed­nym kro­ku).

Element kla­sy Iterator za­zwy­czaj bę­dzie zaj­mo­wał od 16 do 32 B pa­mię­ci i koszt je­go utwo­rze­nia jest prak­tycz­nie po­mi­jal­ny. Jeżeli prze­twa­rza­nie ko­lek­cji ma być wy­ko­ny­wa­ne w kil­ku kro­kach, za­miast kil­ku po­sta­ci po­śred­nich otrzy­ma­my od ra­zu po­stać wy­ni­ko­wą.

Dodatkowo, je­że­li ko­lek­cję da­nych sta­no­wi sek­wen­cyj­ne źród­ło da­nych, ta­kie jak zbiór dys­ko­wy lub wy­nik za­py­ta­nia rea­li­zo­wa­ne­go przez ba­zę da­nych, sek­wen­cyj­ne prze­twa­rza­nie po jed­nym ele­men­cie i od­rzu­ca­nie już prze­two­rzo­nych wpi­sów skut­ku­je ogra­ni­cze­niem wy­ko­rzys­ta­nia pa­mię­ci i szyb­szym dzia­ła­niem pro­gra­mu. Wzrost wy­daj­noś­ci bę­dzie jesz­cze bar­dziej za­uwa­żal­ny, je­że­li wy­ni­ki prze­twa­rza­nia bę­dą stru­mie­nio­wa­ne: od­bior­ca otrzy­ma pierw­szy ele­ment nie po za­koń­cze­niu prze­twa­rza­nia ko­lek­cji, lecz po prze­two­rze­niu te­go do­kład­nie ele­men­tu, a czas prze­twa­rza­nia ko­lek­cji na­ło­ży się na czas ope­rac­ji wejś­cia-wyj­ścia.

Stosowa­nie prze­twa­rza­nia sek­wen­cyj­ne­go za­zwy­czaj zwięk­sza czy­tel­ność tek­stu źród­ło­we­go pro­gra­mu. Poszczegól­ne pre­dy­ka­ty i funk­cje moż­na za­wrzeć w kla­sach prze­twa­rza­nych ele­men­tów (po­dob­nie jak na przy­kład kom­pa­ra­to­ry), a na­stęp­nie bu­do­wać na ich pod­sta­wie łań­cu­chy ope­rac­ji. Na przy­kład, z po­niż­sze­go frag­men­tu:

final Iterable<String> names = Iterables.transform(
          attributes, Attribute.TO_HUMAN_READABLE_NAME);

dość ja­sno wy­ni­ka, że do­ko­nu­je­my trans­for­ma­cji ko­lek­cji at­tri­bu­tes na po­stać ko­lek­cji na­pi­sów czy­tel­nych dla czło­wie­ka (TO_HUMAN_READABLE_NAME jest funk­cją do­ko­nu­ją­cą trans­for­ma­cji). Alterna­ty­wą wy­ko­rzy­stu­ją­cą stan­dar­do­we ele­men­ty ję­zy­ka Java jest:

final List<String> names = new ArrayList<>(attributes.size());
for (final Attribute attribute : attributes) {
   names.add(attribute.getHumanReadableName());
}

I choć su­ma­rycz­nie obję­tość tek­stu źród­ło­we­go w wer­sji sek­wen­cyj­nej bę­dzie za­zwy­czaj jed­nak więk­sza, tekst ten bę­dzie roz­miesz­czo­ny w kil­ku miej­scach i lo­gicz­nie po­wią­za­ny z miej­scem wy­stę­po­wa­nia, a tak­że łat­wiej­szy do po­wtór­ne­go wy­ko­rzys­ta­nia.

Wady

Nieodłącz­ną ce­chą sek­wen­cyj­nych ite­ra­cji jest brak in­for­mac­ji o tym, ja­ka jest licz­ba ite­ro­wa­nych ele­men­tów. Iterowa­na sek­wen­cja mo­że być teore­tycz­nie nie­skoń­czo­na. W nie­któ­rych przy­pad­kach waż­ne jest jed­nak, by znać licz­bę ele­men­tów. Możemy chcieć umieś­cić prze­two­rzo­ne ele­men­ty w pre­alo­ko­wa­nym za­sob­ni­ku; po­da­nia licz­by ele­men­tów mo­że też wy­ma­gać sto­so­wa­ny pro­to­kół trans­mi­syj­ny lub skła­do­wa­nia da­nych.

Jedynym spo­so­bem, by uzys­kać ta­ką in­for­mac­ję, jest za­pi­sa­nie wszyst­kich ele­men­tów do za­sob­ni­ka o zmien­nej po­jem­noś­ci. Jest to nie­ste­ty źród­łem spo­rej nie­efek­tyw­noś­ci, gdyż ko­lej­ne re­alo­ka­cje za­sob­ni­ka mo­gą zu­żyć po­kaź­ne iloś­ci pa­mię­ci ze ster­ty.

Należy też bar­dzo uwa­żać, by w chę­ci do prze­kształ­ce­nia ko­du z po­sta­ci pro­ce­du­ral­nej do funk­cyj­nej nie zmniej­szyć je­go czy­tel­no­ści i nie zwięk­szyć dia­met­ral­nie obję­toś­ci. Jak zo­sta­ło wspom­nia­ne wręcz w do­ku­men­ta­cji bi­blio­te­ki Guava:

Excessive use of Guava's func­tio­nal pro­gram­ming idioms can lead to ver­bo­se, con­fus­ing, un­rea­dab­le, and in­ef­fi­cient code. These are by far the most easily (and most com­mon­ly) ab­used parts of Guava, and when you go to pre­pos­te­rous lengths to make your code «a one-liner», the Guava team weeps.

W szcze­gól­noś­ci, dłu­gie cią­gi ele­men­tar­nych prze­kształ­ceń mo­gą być zna­czą­co mniej efek­tyw­ne, niż po­je­dyn­cze prze­kształ­ce­nie wy­ko­nu­ją­ce wszyst­kie ope­rac­je. Dobrą prak­ty­ką jest za­tem przy­go­to­wy­wa­nie włas­nych pre­dy­ka­tów i funk­cji, któ­re w ra­mach jed­nej me­to­dy rea­li­zu­ją ca­łość ana­li­zy obiek­tu lub je­go prze­kształ­ce­nia na po­stać do­ce­lo­wą.

Składa­nie prze­kształ­ceń ele­men­tar­nych jest wska­za­ne w przy­pad­kach, gdy filt­ro­wa­nie lub prze­kształ­ca­nie ko­lek­cji da­nych jest kon­fi­gu­ro­wa­ne przez użyt­kow­ni­ka i za­leż­ne od zew­nętrz­nych kry­teriów. Jedno­krot­ne przy­go­to­wa­nie właś­ci­we­go łań­cu­cha ite­ra­to­rów bę­dzie za­zwy­czaj oszczęd­niej­sze niż skom­pli­ko­wa­na me­to­da filt­ru­ją­co-prze­twa­rza­ją­ca za­wie­ra­ją­ca roz­pat­ry­wa­ne w każ­dej ite­ra­cji wy­ra­że­nia wa­run­ko­we.

Pod­su­mo­wa­nie

Przetwarza­nie sek­wen­cyj­ne za po­mo­cą ite­ra­to­rów i uzys­ki­wa­ne w ten spo­sób moż­li­woś­ci dyna­micz­ne­go filt­ro­wa­nia i prze­kształ­ca­nia ko­lek­cji da­nych zbli­ża­ją ję­zy­ki obiek­to­wo-pro­ce­du­ral­ne, ta­kie jak C++ czy Java, do ję­zy­ków obiek­to­wo-funk­cyj­nych, ta­kich jak Scala. Pozwala­ją też zwięk­szyć przej­rzy­stość tek­stu źród­ło­we­go i zmniej­szyć ob­cią­że­nie pa­mię­ci przez ope­ro­wa­nie na wir­tu­al­nych, ite­ro­wa­nych ko­lek­cjach da­nych a nie ich zma­te­ria­li­zo­wa­nych wi­do­kach w po­sta­ci rze­czy­wis­tych za­sob­ni­ków. Zawsze na­le­ży jed­nak pa­mię­tać o kosz­cie wy­daj­no­ścio­wym. Im licz­ba na­kła­da­nych na sie­bie prze­kształ­ceń jest mniej­sza, tym wyż­sza bę­dzie wy­daj­ność. Opłaca się za­tem two­rzyć spe­cja­li­zo­wa­ne pre­dy­ka­ty i funk­cje, reali­zu­ją­ce w jed­nym kro­ku wszyst­kie po­trzeb­ne (i nie uza­leż­nio­ne od zew­nętrz­nych kry­teriów) ana­li­zy i prze­kształ­ca­nia. W nie­któ­rych przy­pad­kach zaś stan­dar­do­we po­dejś­cie po­le­ga­ją­ce na ite­ro­wa­niu ko­lek­cji i wy­ko­ny­wa­niu ope­rac­ji dla każ­de­go jej ele­men­tu mo­że dać bar­dziej zwięz­ły i czy­tel­ny tekst źród­ło­wy pro­gra­mu.