13
Czy istnieje algorytm wykonywania próbkowania w zbiorniku, gdy punkty w strumieniu danych mają powiązane wagi?Czy istnieje algorytm ważonego pobierania próbek w zbiorniku
A
Odpowiedz
13
Algorytm Pavlos Efraimidis i Pawła Spirakis dokładnie rozwiązuje ten problem. Oryginalny papier z pełnymi dowodami jest publikowany pod tytułem "Ważone losowe pobieranie próbek ze zbiornikiem" w Information Processing Letters 2006, ale można znaleźć proste podsumowanie here.
Algorytm działa w następujący sposób. Po pierwsze, należy zauważyć, że innym sposobem rozwiązania nieważonego próbkowania zbiorników jest przypisanie każdemu elementowi losowego identyfikatora R od 0 do 1 i przyrostowe (powiedzmy za pomocą sterty) śledzenie najwyższych wartości k. Teraz spójrzmy na wersję ważoną, powiedzmy, że i-ten element ma wagę w_i. Następnie modyfikujemy algorytm, wybierając ID i-tego elementu na R^(1/w_i), gdzie R jest równomiernie rozłożone w (0,1).
Kolejny artykuł mówiący o tym algorytmie to this one autorstwa Cloudera.
+4
I jedna liniowa implementacja python: 'heapq.nlargest (k, items, key = element lambdy: math.pow (random.random(), 1/weight (item)))' –
+0
Czy można to zrobić z wymianą ? – eleanora
+0
@eleanora Nie ma sensu robić tego z zamiennikiem, ponieważ istnieje metoda aliasu, musisz najpierw utworzyć tabelę, która zajmuje O (n) czas, a następnie każdy wybór to O (1). Alias nie zachowuje jednak złożoności środowiska wykonawczego przy wyborze, chyba że użyje się go z zamiennikiem. – snb
5
Możesz wypróbować algorytm A-ES od this paper of S. Efraimidis. Kod jest bardzo prosty i bardzo wydajny.
Nadzieja to pomaga,
Benoit
Powiązane problemy
- 1. Algorytm do pobierania próbek bez wymiany?
- 2. Czy istnieje algorytm wielomianowy do znalezienia maksymalnego ważonego idealnego dopasowania na ogólnym wykresie?
- 3. Czy istnieje algorytm pobierania odcisków palców algorytmu sterowania przeciążeniem TCP używanego w przechwyconej sesji?
- 4. Czy istnieje algorytm elipsy punktu środkowego?
- 5. Czy istnieje algorytm "upraszczający" wykres zależności?
- 6. Czy istnieje dobra implementacja częściowego pobierania plików w PHP?
- 7. Czy istnieje algorytm ładowania zbiorczego w drzewie B?
- 8. Redis: Implementacja ważonego wykresu ukierunkowanego
- 9. Tworzenie niestandardowego rozkładu prawdopodobieństwa w celu losowego pobierania próbek z SciPy
- 10. Czy istnieje preferowany sposób pobierania strumienia list do listy płaskiej?
- 11. Czy istnieje przykład użycia narzędzia pobierania przy użyciu metody flowjs?
- 12. Czy istnieje sposób na zmuszenie przeglądarek do odświeżania/pobierania obrazów?
- 13. Czy istnieje sposób pobierania identyfikatora autoinkrementacji z przygotowanego oświadczenia
- 14. Czy istnieje publiczny serwer FTP do testowania przesyłania i pobierania?
- 15. Czy istnieje jakiś kod lub algorytm rozpoznawania podpisu?
- 16. Czy istnieje odpowiedni algorytm do wykrywania koloru tła figury?
- 17. Analiza liczby zmiennoprzecinkowej: Czy istnieje algorytm Catch All?
- 18. Czy istnieje algorytm rozwiązywania takiego problemu z rekonstrukcją geometryczną projekcji?
- 19. Czy istnieje algorytm, który tworzy rozkład uniwersytecki na cały semestr?
- 20. Czy istnieje algorytm Objective-C, jak "transformacja" C++ STL?
- 21. Wprowadzanie próbek dla różnych algorytmów
- 22. objętość Kubernetes configMap nie tworzy plik w zbiorniku
- 23. Tworzenie ważonego nieukierunkowanego wykresu w "igraph" w C/C++
- 24. Dźwięk: Zmień głośność próbek w tablicy bajtów
- 25. Jak zwiększyć rozmiar próbek kodu?
- 26. Losowe pobieranie próbek z Mongo
- 27. Czy poprawnie wprowadzam algorytm "Heapify"?
- 28. Węgierski algorytm w Pythonie
- 29. Czy istnieje metoda czarnej skrzynki do wykrywania, czy algorytm sortowania jest stabilny?
- 30. Jak znaleźć minimalną krawędź krawędziową ważonego wykresu dwudzielnego za pomocą programu Mathematica 8?
Zbyt szeroki? Myślę, że pytanie wymaga bardzo specyficznego algorytmu. –
Całkowicie zgadzam się z @ JuanA.Navarro - pytanie jest bardzo przydatne do przetwarzania strumieniowego lub równoległego i powinno zostać ponownie otwarte (jego odpowiedź jest również bardzo dobra, BTW). –