Algorytm kroczącej mediany w C

Obecnie pracuję nad algorytmem do implementacji kroczącego filtru mediany (analogicznego do kroczącego filtru średniej) w C. Z moich poszukiwań w literaturze wynika, że ​​istnieją dwa racjonalnie efektywne sposoby na zrobienie tego. Pierwszym jest posortowanie początkowego okna wartości, a następnie wykonanie wyszukiwania binarnego w celu wstawienia nowej wartości i usunięcia istniejącej przy każdej iteracji.

Drugi (z Hardle i Steiger, 1995, JRSS-C, Algorithm 296) buduje dwustronną strukturę sterty, z maxheap na jednym końcu, minheap na drugim i medianą w środku. Daje to algorytm czasu liniowego zamiast algorytmu O (n log n).

Oto mój problem: wdrożenie tego pierwszego jest wykonalne, ale muszę to uruchomić na milionach szeregów czasowych, więc wydajność ma duże znaczenie. To ostatnie okazuje się bardzo trudne do wdrożenia. Znalazłem kod w pliku Trunmed.c kodu pakietu statystycznego R, ale jest on raczej nieczytelny.

Czy ktoś wie o dobrze napisanej implementacji C dla liniowego algorytmu mediany kroczącej w czasie?

Edytuj: Link do kodu Trunmed.c http://google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c

Patrzyłem na R src/library/stats/src/Trunmed.ckilka razy, ponieważ chciałem też czegoś podobnego w samodzielnej podprocedurze klasy C ++ / C. Zauważ, że są to właściwie dwie implementacje w jednej, zobacz src/library/stats/man/runmed.Rd(źródło pliku pomocy), który mówi

\details{
  Apart from the end values, the result \code{y = runmed(x, k)} simply has
  \code{y[j] = median(x[(j-k2):(j+k2)])} (k = 2*k2+1), computed very
  efficiently.

  The two algorithms are internally entirely different:
  \describe{
    \item{"Turlach"}{is the Härdle-Steiger
      algorithm (see Ref.) as implemented by Berwin Turlach.
      A tree algorithm is used, ensuring performance \eqn{O(n \log
        k)}{O(n * log(k))} where \code{n <- length(x)} which is
      asymptotically optimal.}
    \item{"Stuetzle"}{is the (older) Stuetzle-Friedman implementation
      which makes use of median \emph{updating} when one observation
      enters and one leaves the smoothing window.  While this performs as
      \eqn{O(n \times k)}{O(n * k)} which is slower asymptotically, it is
      considerably faster for small \eqn{k} or \eqn{n}.}
  }
}

Byłoby miło zobaczyć to ponownie użyte w bardziej samodzielny sposób. Czy jesteś wolontariuszem? Mogę pomóc z niektórymi bitami R.

Edycja 1 : Oprócz linku do starszej wersji Trunmed.c powyżej, tutaj są aktualne kopie SVN

• Srunmed.c (dla wersji Stuetzle)
• Trunmed.c (dla wersji Turlach)
• runmed.R dla funkcji R wywołującej te

Edycja 2 : Ryan Tibshirani ma trochę kodu C i Fortran na temat szybkiego binowania mediany, co może być odpowiednim punktem wyjścia dla podejścia okienkowego.

Nie mogłem znaleźć nowoczesnej implementacji struktury danych c ++ ze statystyką zamówień, więc ostatecznie zaimplementowałem oba pomysły w linku do najlepszych programistów sugerowanym przez MAK ( Match Editorial : przewiń w dół do FloatingMedian).

Dwa zestawy multisetowe

Pierwsza idea dzieli dane na dwie struktury danych (sterty, zestawy wielozbiorowe itp.) Z O (ln N) na wstawianie / usuwanie nie pozwala na dynamiczną zmianę kwantyla bez dużych kosztów. Oznacza to, że możemy mieć kroczącą medianę lub kroczące 75%, ale nie obie jednocześnie.

Drzewo segmentów

Drugi pomysł wykorzystuje drzewo segmentów, które jest O (ln N) do wstawiania / usuwania / zapytań, ale jest bardziej elastyczne. Najlepsze ze wszystkich „N” to rozmiar zakresu danych. Więc jeśli twoja krocząca mediana ma okno miliona elementów, ale twoje dane wahają się od 1..65536, wtedy tylko 16 operacji jest wymaganych na ruch przesuwanego okna 1 miliona !!

Kod C ++ jest podobny do tego, co Denis opublikował powyżej („Oto prosty algorytm dla skwantyzowanych danych”)

Drzewa statystyk porządkowych GNU

Tuż przed poddaniem się stwierdziłem, że stdlibc ++ zawiera drzewa statystyk zamówień !!!

Mają dwie krytyczne operacje:

iter = tree.find_by_order(value)
order = tree.order_of_key(value)

Zobacz podręcznik libstdc ++ policy_based_data_structures_test (wyszukaj „podziel i dołącz”).

Zapakowałem drzewo do użycia w wygodnym nagłówku dla kompilatorów obsługujących częściowe typy plików typu c ++ 0x / c ++ 11:

#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
                                  T,
                                  __gnu_pbds::null_type,
                                  std::less<T>,
                                  __gnu_pbds::rb_tree_tag,
                                  // This policy updates nodes'  metadata for order statistics.
                                  __gnu_pbds::tree_order_statistics_node_update>;

#endif //GNU_ORDER_STATISTIC_SET_H

Zrobiłem realizację C tutaj . W tym pytaniu jest jeszcze kilka szczegółów: Mediana krocząca w implementacji C - Turlach .

Przykładowe użycie:

int main(int argc, char* argv[])
{
   int i,v;
   Mediator* m = MediatorNew(15);

   for (i=0;i<30;i++)
   {
      v = rand()&127;
      printf("Inserting %3d \n",v);
      MediatorInsert(m,v);
      v=MediatorMedian(m);
      printf("Median = %3d.\n\n",v);
      ShowTree(m);
   }
}

Używam tego przyrostowego estymatora mediany:

median += eta * sgn(sample - median)

który ma taką samą postać jak bardziej powszechny estymator średniej:

mean += eta * (sample - mean)

Tutaj eta jest małym parametrem szybkości uczenia się (np. 0.001) I sgn()jest funkcją signum, która zwraca jedną z {-1, 0, 1}. (Użyj stałej etatakiej jak ta, jeśli dane są niestacjonarne i chcesz śledzić zmiany w czasie; w przeciwnym razie w przypadku źródeł stacjonarnych użyj czegoś podobnego eta = 1 / ndo zbieżności, gdzie njest liczba próbek widzianych do tej pory).

Zmodyfikowałem również estymator mediany, aby działał dla dowolnych kwantyli. Ogólnie rzecz biorąc, funkcja kwantylowa podaje wartość, która dzieli dane na dwa ułamki: pi 1 - p. Następujący szacuje tę wartość w sposób przyrostowy:

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

Wartość ppowinna mieścić się w granicach [0, 1]. To zasadniczo przesuwa sgn()symetryczne wyjście funkcji, {-1, 0, 1}aby pochyliło się w jedną stronę, dzieląc próbki danych na dwa pojemniki o nierównej wielkości (odpowiednio ułamki pi 1 - pdane są mniejsze / większe niż oszacowanie kwantylowe). Zauważ, że dla p = 0.5, to sprowadza się do estymatora mediany.

Oto prosty algorytm dla skwantowanych danych (miesiące później):

""" median1.py: moving median 1d for quantized, e.g. 8-bit data

Method: cache the median, so that wider windows are faster.
    The code is simple -- no heaps, no trees.

Keywords: median filter, moving median, running median, numpy, scipy

See Perreault + Hebert, Median Filtering in Constant Time, 2007,
    http://nomis80.org/ctmf.html: nice 6-page paper and C code,
    mainly for 2d images

Example:
    y = medians( x, window=window, nlevel=nlevel )
    uses:
    med = Median1( nlevel, window, counts=np.bincount( x[0:window] ))
    med.addsub( +, - )  -- see the picture in Perreault
    m = med.median()  -- using cached m, summ

How it works:
    picture nlevel=8, window=3 -- 3 1s in an array of 8 counters:
        counts: . 1 . . 1 . 1 .
        sums:   0 1 1 1 2 2 3 3
                        ^ sums[3] < 2 <= sums[4] <=> median 4
        addsub( 0, 1 )  m, summ stay the same
        addsub( 5, 1 )  slide right
        addsub( 5, 6 )  slide left

Updating `counts` in an `addsub` is trivial, updating `sums` is not.
But we can cache the previous median `m` and the sum to m `summ`.
The less often the median changes, the faster;
so fewer levels or *wider* windows are faster.
(Like any cache, run time varies a lot, depending on the input.)

See also:
    scipy.signal.medfilt -- runtime roughly ~ window size
    http://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c

"""

from __future__ import division
import numpy as np  # bincount, pad0

__date__ = "2009-10-27 oct"
__author_email__ = "denis-bz-py at t-online dot de"


#...............................................................................
class Median1:
    """ moving median 1d for quantized, e.g. 8-bit data """

    def __init__( s, nlevel, window, counts ):
        s.nlevel = nlevel  # >= len(counts)
        s.window = window  # == sum(counts)
        s.half = (window // 2) + 1  # odd or even
        s.setcounts( counts )

    def median( s ):
        """ step up or down until sum cnt to m-1 < half <= sum to m """
        if s.summ - s.cnt[s.m] < s.half <= s.summ:
            return s.m
        j, sumj = s.m, s.summ
        if sumj <= s.half:
            while j < s.nlevel - 1:
                j += 1
                sumj += s.cnt[j]
                # print "j sumj:", j, sumj
                if sumj - s.cnt[j] < s.half <= sumj:  break
        else:
            while j > 0:
                sumj -= s.cnt[j]
                j -= 1
                # print "j sumj:", j, sumj
                if sumj - s.cnt[j] < s.half <= sumj:  break
        s.m, s.summ = j, sumj
        return s.m

    def addsub( s, add, sub ):
        s.cnt[add] += 1
        s.cnt[sub] -= 1
        assert s.cnt[sub] >= 0, (add, sub)
        if add <= s.m:
            s.summ += 1
        if sub <= s.m:
            s.summ -= 1

    def setcounts( s, counts ):
        assert len(counts) <= s.nlevel, (len(counts), s.nlevel)
        if len(counts) < s.nlevel:
            counts = pad0__( counts, s.nlevel )  # numpy array / list
        sumcounts = sum(counts)
        assert sumcounts == s.window, (sumcounts, s.window)
        s.cnt = counts
        s.slowmedian()

    def slowmedian( s ):
        j, sumj = -1, 0
        while sumj < s.half:
            j += 1
            sumj += s.cnt[j]
        s.m, s.summ = j, sumj

    def __str__( s ):
        return ("median %d: " % s.m) + \
            "".join([ (" ." if c == 0 else "%2d" % c) for c in s.cnt ])

#...............................................................................
def medianfilter( x, window, nlevel=256 ):
    """ moving medians, y[j] = median( x[j:j+window] )
        -> a shorter list, len(y) = len(x) - window + 1
    """
    assert len(x) >= window, (len(x), window)
    # np.clip( x, 0, nlevel-1, out=x )
        # cf http://scipy.org/Cookbook/Rebinning
    cnt = np.bincount( x[0:window] )
    med = Median1( nlevel=nlevel, window=window, counts=cnt )
    y = (len(x) - window + 1) * [0]
    y[0] = med.median()
    for j in xrange( len(x) - window ):
        med.addsub( x[j+window], x[j] )
        y[j+1] = med.median()
    return y  # list
    # return np.array( y )

def pad0__( x, tolen ):
    """ pad x with 0 s, numpy array or list """
    n = tolen - len(x)
    if n > 0:
        try:
            x = np.r_[ x, np.zeros( n, dtype=x[0].dtype )]
        except NameError:
            x += n * [0]
    return x

#...............................................................................
if __name__ == "__main__":
    Len = 10000
    window = 3
    nlevel = 256
    period = 100

    np.set_printoptions( 2, threshold=100, edgeitems=10 )
    # print medians( np.arange(3), 3 )

    sinwave = (np.sin( 2 * np.pi * np.arange(Len) / period )
        + 1) * (nlevel-1) / 2
    x = np.asarray( sinwave, int )
    print "x:", x
    for window in ( 3, 31, 63, 127, 255 ):
        if window > Len:  continue
        print "medianfilter: Len=%d window=%d nlevel=%d:" % (Len, window, nlevel)
            y = medianfilter( x, window=window, nlevel=nlevel )
        print np.array( y )

# end median1.py

Medianę kroczącą można znaleźć, zachowując dwie partycje liczb.

Do obsługi partycji użyj Min Heap i Max Heap.

Max Heap będzie zawierał liczby mniejsze niż równe medianie.

Sterta minimalna będzie zawierała liczby większe niż równe medianie.

Wiązanie równoważące: jeśli całkowita liczba elementów jest parzysta, obie sterty powinny mieć równe elementy.

jeśli całkowita liczba elementów jest nieparzysta, wówczas Max Heap będzie miał o jeden element więcej niż Min Heap.

Element mediany: jeśli obie partycje mają równą liczbę elementów, mediana będzie równa połowie sumy elementu maksymalnego z pierwszej partycji i elementu minimalnego z drugiej partycji.

W przeciwnym razie mediana będzie maksymalnym elementem z pierwszej partycji.

Algorytm-
1- Weź dwa stosy (1 min i 1 maks.)
   Max Heap będzie zawierał pierwszą połowę liczby elementów
   Min Heap będzie zawierał drugą połowę liczby elementów

2- Porównaj nowy numer ze strumienia z wierzchołkiem Max Heap, 
   jeśli jest mniejsza lub równa, dodaj tę liczbę do maksymalnego stosu. 
   W przeciwnym razie dodaj liczbę w Min Heap.

3- jeśli min Heap ma więcej elementów niż Max Heap 
   następnie usuń górny element z Min Heap i dodaj Max Heap.
   jeśli max Heap ma więcej niż jeden element niż w Min Heap 
   następnie usuń górny element Max Heap i dodaj Min Heap.

4- Jeśli obie sterty mają równą liczbę elementów, to
   mediana będzie połową sumy maksymalnego elementu z Max Heap i minimalnego elementu z Min Heap.
   W przeciwnym razie mediana będzie maksymalnym elementem z pierwszej partycji.

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        RunningMedianHeaps s = new RunningMedianHeaps();
        int n = in.nextInt();
        for(int a_i=0; a_i < n; a_i++){
            printMedian(s,in.nextInt());
        }
        in.close();       
    }

    public static void printMedian(RunningMedianHeaps s, int nextNum){
            s.addNumberInHeap(nextNum);
            System.out.printf("%.1f\n",s.getMedian());
    }
}

class RunningMedianHeaps{
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Comparator.reverseOrder());

    public double getMedian() {

        int size = minHeap.size() + maxHeap.size();     
        if(size % 2 == 0)
            return (maxHeap.peek()+minHeap.peek())/2.0;
        return maxHeap.peek()*1.0;
    }

    private void balanceHeaps() {
        if(maxHeap.size() < minHeap.size())
        {
            maxHeap.add(minHeap.poll());
        }   
        else if(maxHeap.size() > 1+minHeap.size())
        {
            minHeap.add(maxHeap.poll());
        }
    }

    public void addNumberInHeap(int num) {
        if(maxHeap.size()==0 || num <= maxHeap.peek())
        {
            maxHeap.add(num);
        }
        else
        {
            minHeap.add(num);
        }
        balanceHeaps();
    }
}

Może warto zauważyć, że istnieje szczególny przypadek, który ma proste, dokładne rozwiązanie: kiedy wszystkie wartości w strumieniu są liczbami całkowitymi w (stosunkowo) małym zdefiniowanym zakresie. Na przykład załóżmy, że wszystkie muszą mieścić się w przedziale od 0 do 1023. W tym przypadku po prostu zdefiniuj tablicę 1024 elementów i liczbę i wyczyść wszystkie te wartości. Dla każdej wartości w strumieniu zwiększ odpowiedni pojemnik i liczbę. Po zakończeniu strumienia znajdź przedział, który zawiera największą liczbę zliczeń / 2 - łatwo to zrobić dodając kolejne przedziały, zaczynając od 0. W ten sam sposób można znaleźć wartość dowolnego rzędu. (Występuje niewielka komplikacja, jeśli wykrycie nasycenia zasobnika i „uaktualnienie” rozmiaru pojemników pamięci do większego typu będzie potrzebne podczas przebiegu).

Ten szczególny przypadek może wydawać się sztuczny, ale w praktyce jest bardzo powszechny. Można go również zastosować jako przybliżenie liczb rzeczywistych, jeśli mieszczą się one w zakresie i znany jest „dostatecznie dobry” poziom dokładności. Potwierdziłoby to prawie każdy zestaw pomiarów na grupie obiektów „świata rzeczywistego”. Na przykład wzrost lub waga grupy osób. Nie jest wystarczająco duży zestaw? Działałoby to równie dobrze w przypadku długości lub wagi wszystkich (pojedynczych) bakterii na planecie - zakładając, że ktoś mógłby dostarczyć dane!

Wygląda na to, że źle odczytałem oryginał - który wydaje się, że chce mieć przesuwaną środkową część okna zamiast tylko mediany bardzo długiego strumienia. To podejście nadal się sprawdza. Załaduj wartości pierwszego strumienia N dla okna początkowego, a następnie dla wartości strumienia N + 1 zwiększaj odpowiedni pojemnik, zmniejszając jednocześnie pojemnik odpowiadający zerowej wartości strumienia. W tym przypadku konieczne jest zachowanie ostatnich wartości N, aby umożliwić dekrementację, co można zrobić efektywnie poprzez cykliczne adresowanie tablicy o rozmiarze N. Ponieważ pozycja mediany może się zmieniać tylko o -2, -1,0,1 , 2 na każdym kroku przesuwanego okna nie jest konieczne sumowanie wszystkich koszy do mediany na każdym kroku, wystarczy dostosować „wskaźnik mediany” w zależności od tego, która strona (e) została zmodyfikowana. Na przykład, jeśli zarówno nowa wartość, jak i usuwana wartość spadną poniżej bieżącej mediany, to się nie zmienia (przesunięcie = 0). Metoda nie działa, gdy N staje się zbyt duże, aby wygodnie przechowywać je w pamięci.

Jeśli masz możliwość odniesienia się do wartości jako funkcji punktów w czasie, możesz próbkować wartości z zamianą, stosując metodę ładowania początkowego, aby wygenerować początkową wartość mediany w przedziałach ufności. Może to umożliwić obliczenie przybliżonej mediany z większą wydajnością niż ciągłe sortowanie przychodzących wartości w strukturę danych.

Dla tych, którzy potrzebują bieżącej mediany w Javie ... PriorityQueue jest Twoim przyjacielem. O (log N) wstaw, O (1) bieżąca mediana i O (N) usuń. Jeśli znasz dystrybucję swoich danych, możesz zrobić o wiele lepiej.

public class RunningMedian {
  // Two priority queues, one of reversed order.
  PriorityQueue<Integer> lower = new PriorityQueue<Integer>(10,
          new Comparator<Integer>() {
              public int compare(Integer arg0, Integer arg1) {
                  return (arg0 < arg1) ? 1 : arg0 == arg1 ? 0 : -1;
              }
          }), higher = new PriorityQueue<Integer>();

  public void insert(Integer n) {
      if (lower.isEmpty() && higher.isEmpty())
          lower.add(n);
      else {
          if (n <= lower.peek())
              lower.add(n);
          else
              higher.add(n);
          rebalance();
      }
  }

  void rebalance() {
      if (lower.size() < higher.size() - 1)
          lower.add(higher.remove());
      else if (higher.size() < lower.size() - 1)
          higher.add(lower.remove());
  }

  public Integer getMedian() {
      if (lower.isEmpty() && higher.isEmpty())
          return null;
      else if (lower.size() == higher.size())
          return (lower.peek() + higher.peek()) / 2;
      else
          return (lower.size() < higher.size()) ? higher.peek() : lower
                  .peek();
  }

  public void remove(Integer n) {
      if (lower.remove(n) || higher.remove(n))
          rebalance();
  }
}

Oto jeden, którego można użyć, gdy dokładny wynik nie jest ważny (do celów wyświetlania itp.) Potrzebujesz totalcount i lastmedian plus newvalue.

{
totalcount++;
newmedian=lastmedian+(newvalue>lastmedian?1:-1)*(lastmedian==0?newvalue: lastmedian/totalcount*2);
}

Daje dość dokładne wyniki dla rzeczy takich jak page_display_time.

Reguły: strumień wejściowy musi być płynny w kolejności czasu wyświetlania strony, mieć dużą liczbę (> 30 itd.) I mieć niezerową medianę.

Przykład: czas ładowania strony, 800 elementów, 10 ms ... 3000 ms, średnio 90 ms, rzeczywista mediana: 11 ms

Po 30 danych wejściowych błąd mediany wynosi zwykle <= 20% (9 ms..12 ms) i jest coraz mniejszy. Po 800 wejściach błąd wynosi + -2%.

Inny myśliciel z podobnym rozwiązaniem jest tutaj: Median Filter Super wydajna implementacja

Oto implementacja Java

package MedianOfIntegerStream;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;


public class MedianOfIntegerStream {

    public Set<Integer> rightMinSet;
    public Set<Integer> leftMaxSet;
    public int numOfElements;

    public MedianOfIntegerStream() {
        rightMinSet = new TreeSet<Integer>();
        leftMaxSet = new TreeSet<Integer>(new DescendingComparator());
        numOfElements = 0;
    }

    public void addNumberToStream(Integer num) {
        leftMaxSet.add(num);

        Iterator<Integer> iterMax = leftMaxSet.iterator();
        Iterator<Integer> iterMin = rightMinSet.iterator();
        int maxEl = iterMax.next();
        int minEl = 0;
        if (iterMin.hasNext()) {
            minEl = iterMin.next();
        }

        if (numOfElements % 2 == 0) {
            if (numOfElements == 0) {
                numOfElements++;
                return;
            } else if (maxEl > minEl) {
                iterMax.remove();

                if (minEl != 0) {
                    iterMin.remove();
                }
                leftMaxSet.add(minEl);
                rightMinSet.add(maxEl);
            }
        } else {

            if (maxEl != 0) {
                iterMax.remove();
            }

            rightMinSet.add(maxEl);
        }
        numOfElements++;
    }

    public Double getMedian() {
        if (numOfElements % 2 != 0)
            return new Double(leftMaxSet.iterator().next());
        else
            return (leftMaxSet.iterator().next() + rightMinSet.iterator().next()) / 2.0;
    }

    private class DescendingComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public static void main(String[] args) {
        MedianOfIntegerStream streamMedian = new MedianOfIntegerStream();

        streamMedian.addNumberToStream(1);
        System.out.println(streamMedian.getMedian()); // should be 1

        streamMedian.addNumberToStream(5);
        streamMedian.addNumberToStream(10);
        streamMedian.addNumberToStream(12);
        streamMedian.addNumberToStream(2);
        System.out.println(streamMedian.getMedian()); // should be 5

        streamMedian.addNumberToStream(3);
        streamMedian.addNumberToStream(8);
        streamMedian.addNumberToStream(9);
        System.out.println(streamMedian.getMedian()); // should be 6.5
    }
}

Jeśli potrzebujesz tylko wygładzonej średniej, szybkim / łatwym sposobem jest pomnożenie ostatniej wartości przez x, a wartość średnią przez (1-x), a następnie dodanie ich. To staje się nową średnią.

edycja: nie to, o co prosił użytkownik i nie jest tak statystycznie ważne, ale wystarczająco dobre do wielu zastosowań.
Zostawię to tutaj (pomimo głosów przeciw) do wyszukiwania!