Pracuję nad algorytmem, który musi obliczyć rozmiar zestawu wygenerowanego przez przecięcie co najmniej 2 zestawów. Dokładniej:
Przecinane zestawy są generowane przez zapytania SQL i starając się utrzymać szybkość, otrzymuję z wyprzedzeniem liczbę każdego zapytania, a następnie biorę zestaw o najniższej liczbie () i używaj tych identyfikatorów jako granic w pozostałych dużych zapytaniach, aby skrzyżowanie skutecznie stało się:
Od tej pory nawet ta strategia pozostawia mi dość duże zapytania czasami może być duży. Moim pomysłem na poradzenie sobie z tym jest pobranie losowej próbki i przecinając go z resztą zbiorów przed ekstrapolacją z powrotem do właściwego oszacowania . Moje pytanie brzmi: jaki jest najlepszy sposób na próbkowanie, a następnie ekstrapolację, aby wrócić do wartości to znaczy, jeśli nie do końca dokładny, ma przewidywalny zakres błędów?
Oto, co próbowałem do tej pory (w pseudokodzie, w pewnym sensie):
sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
factor = sample_threshold / len(A0)
}
// Take a random sample of size 10000 from A0
// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
a = intersect(A0, a)
working_set = intersect(working_set, a)
}
z := len(working_set) * (1 / factor)
Ten kod działa, ale wydaje się, że konsekwentnie przecenia z
, przy czym mniejsza próbka daje wyższe oszacowania. Ponadto nie jestem pewien, jak to się skaluje przy więcej niż dwóch zestawach do przecięcia.
Mam nadzieję, że to pytanie ma sens, daj mi znać, czy mogę coś wyjaśnić. Ponadto, jeśli to pytanie jest nie na temat lub należy do kogoś innego, proszę dać mi znać i chętnie je przeniesie.
Zgodnie z komentarzem Billa przeprowadziłem kilka szybkich prób, aby pokazać wielkość próby w porównaniu do błędu. Każde wiadro wielkości próby było uruchamiane 20 razy i jak widać, istnieje dość wyraźny trend:
ORDER BY RAND()
nie jest idealna, ale powinna być odpowiednia do tego zadania.Odpowiedzi:
Jeśli twój zestawA0 ma powtarzające się elementy (tzn. faktycznie jest to zbiór wielosetowy), rozmiar przecięcia zostanie przeceniony przez twoją procedurę, ponieważ twój współczynnik skalowania wykorzystuje liczbę próbkowanych elementów, a nie liczbę unikalnych „typów” próbkowanych. Możesz skorygować oszacowanie, obliczając współczynnik jako stosunek liczby unikalnych elementów w losowej próbce do liczby unikalnych elementów w pełnym zestawieA0 .
źródło
Jak zauważa Innuo , mój problem był spowodowany duplikatami w moim próbkowanym zestawieA0 , co spowodowało, że
factor
mój pseudokodz
był zbyt niski, co z kolei spowodowało, że końcowa ekstrapolacja była zbyt wysoka, ponieważ została wygenerowana przez odwrotnośćfactor
. Usunięcie duplikatów rozwiązało ten problem, a teraz algorytm generuje wykres delta względem wielkości próby bardziej zgodny z tym, czego się spodziewałem (linie wskazują margines błędu przy 95% poziomie ufności dla tej wielkości próby w stosunku do całej populacji ):źródło