Znajdź median w wielu zakresach podrzędnych nieuporządkowanej listy

Question

E.g. biorąc pod uwagę nieuporządkowaną listę N elementów, znajdź mediany dla pod zakresów 0..100, 25..200, 400..1000, 10..500, ... Nie widzę lepszego sposobu niż przechodzenie przez każdą z nich. pod zakres i uruchomić standardowe algorytmy ustalania mediany.

Prosty przykład: [5 3 6 2 4] Mediana dla punktu 0..3 wynosi 5. (Nie 4, ponieważ pytamy o medianę pierwszych trzech elementów z oryginalnej listy)

Answer 1

Myślę, że wraz ze wzrostem liczby pod-zakresów bardzo szybko okaże się, że szybciej jest posortować, a następnie odzyskać element liczby, które chcesz.

W praktyce, ponieważ istnieją wysoce zoptymalizowane procedury sortowania, które można wywoływać.

Teoretycznie i być może również w praktyce, ponieważ ponieważ mamy do czynienia z liczbami całkowitymi, nie trzeba płacić nnn n za sortowanie - patrz: http://en.wikipedia.org/wiki/Integer_sorting.

Jeśli twoje dane są w rzeczywistości zmiennoprzecinkowe, a nie NaN, to odrobina twiddlinga pozwoli ci używać sortowania liczb całkowitych - od - http://en.wikipedia.org/wiki/IEEE_754-1985#Comparing_floating-point_numbers - Reprezentacja binarna ma specjalną właściwość, która, z wyłączeniem NaN, dowolnych dwóch liczby można porównywać jak liczby całkowite ze znakiem i wielkością (chociaż w przypadku współczesnych procesorów komputerowych nie ma to już bezpośredniego zastosowania): jeśli bit znaku jest inny, liczba ujemna poprzedza liczbę dodatnią (z wyjątkiem tego, że ujemne zero i dodatnie zero powinny być uważane za równe) w przeciwnym razie porządek względny jest taki sam jak porządek leksykograficzny, ale odwrócony dla dwóch liczb ujemnych; Obowiązują problemy z endiancją.

Możesz sprawdzić NaN i inne funny, udawać, że liczby zmiennoprzecinkowe są znakiem + liczby całkowite z zakresu bezwartościowości, odjąć je, gdy są ujemne, aby poprawić kolejność liczb ujemnych, a następnie traktować jako zwykłe liczby całkowite z dopełnieniem ze znakiem, sortować, a następnie odwrócić proces.

Answer 2

INTEGER ELEMENTS:

Jeśli typ swoimi elementami są liczbami całkowitymi, to najlepszym sposobem jest mieć wiadro na każdy numer leży w żadnej z podzakresów, gdzie każdy czerpak jest stosowany do liczenia numer jego powiązanej liczby całkowitej znaleziony w elementach wejściowych (na przykład bucket[100] przechowuje liczbę 100 s w sekwencji wejściowej). Zasadniczo można to osiągnąć w następujących krokach:

1. tworzenie wiader dla każdej liczby leży w dowolnym z zakresów.
2. iteracyjne przechodzenie przez wszystkie elementy, dla każdego numeru n, jeśli mamy bucket[n], następnie bucket[n]++.
3. Oblicz mediany na podstawie zagregowanych wartości przechowywanych w twoich zasobnikach.

Podejmij to w inny sposób, załóżmy, że masz podzakres [0, 10], a chcesz obliczyć medianę. Podejście typu "bucket" w zasadzie oblicza, ile jest 0 s w wejściach i ile jest 1 s w danych wejściowych i tak dalej. Załóżmy, że istnieją n numery leży w zakresie [0, 10], to mediana jest n/2 th największym elementem, który może być zidentyfikowany poprzez znalezienie i takie, że bucket[0] + bucket[1] ... + bucket[i] większa lub równa n/2 ale bucket[0] + ... + bucket[i - 1] jest mniejsza niż n/2.

Zaletą jest to, że nawet twoje elementy wejściowe są przechowywane na wielu komputerach (tj. W rozproszonym przypadku), każda maszyna może utrzymywać własne segmenty i tylko zagregowane wartości są wymagane do przejścia przez intranet.

Można również użyć hierarchicznych segmentów, które obejmują wiele przebiegów. W każdym przebiegu liczba bucket[i] zlicza liczbę elementów wejściowych w określonym zakresie (na przykład [i * 2^K, (i+1) * 2^K]), a następnie zawęzić obszar problemu, identyfikując, który zasobnik będzie pożywki po każdym kroku, a następnie zmniejszyć K przezw w następnym kroku i powtarzaj, aż będziesz w stanie prawidłowo zidentyfikować medium.

---

zmiennoprzecinkowych ELEMENTY

Cała elementy pasują do pamięci:

Jeśli całe elementy można dopasować do pamięci, najpierw sortowania element N, a następnie znalezienie mediany dla każdego podzakresu jest najlepszą opcją. The linear time heap solution również działa dobrze w tym przypadku, jeśli liczba podzakresów jest mniejsza niż logN.

Całość elementy nie może się zmieścić w pamięci i przechowuje się w jednej maszynie:

Ogólnie, external sort zwykle wymaga trzech dyskowych skany. Dlatego jeśli liczba twoich podkategorii jest większa lub równa 3, najlepszym wyborem będzie najpierw posortowanie elementów N, a następnie znalezienie median dla każdego z zakresów podrzędnych przez załadowanie tylko niezbędnych elementów z dysku. W przeciwnym razie po prostu wykonanie skanowania dla każdego podzakresu i pobranie tych elementów w podzakresie jest lepsze.

całą elementów są przechowywane w wielu maszynach: Ponieważ znalezienie medianę jest operatorem holistyczne, co oznacza, że ​​nie może uzyskać ostateczną medianę całego wejściowych na podstawie median kilku częściach wejścia, jest to trudny problem, że nie można opisać tego rozwiązania w kilku zdaniach, ale są badania (zob. this jako przykład) skupiono się na tym problemie.

Answer 3

Mój pomysł:

• Sortowanie listy do tablicy (za pomocą dowolnego odpowiedniego algorytmu sortowania)

• Dla każdego zakresu, znaleźć indeksy początku i końca zakresu korzystania wyszukiwanie binarne

• Znajdź medianę po prostu dodając ich indeksy i dzieląc przez 2 (np.Mediana Zakres [x,y] czas arr[(x+y)/2])

przetwarzanie wstępne: O (n log n) dla algorytmu sortowania rodzajowymi (jak szybkiej rodzaju) lub czas pracy wybrany sortowania rutynowych

Czas na zapytania : O (log n)

dynamiczna lista:

powyżej przyjęto, że lista jest statyczny. Jeśli elementy można dowolnie dodawać lub usuwać między zapytaniami, zmodyfikowany Binary Search Tree może zadziałać, a każdy węzeł będzie utrzymywał liczbę potomków. Pozwoli to na taki sam czas pracy jak powyżej z listą dynamiczną.

Answer 4

Odpowiedź w końcu będzie "w zależności". Istnieje wiele różnych podejść, z których każda prawdopodobnie będzie odpowiednia w większości przypadków, które możesz napotkać. Problem polega na tym, że każdy z nich będzie różnił się dla różnych wejść. Gdzie jeden może lepiej działać dla jednej klasy wejść, inny będzie działał lepiej dla innej klasy wejść.

Jako przykład, podejście polegające na sortowaniu, a następnie przeprowadzeniu przeszukiwania binarnego na skrajach waszych zakresów, a następnie bezpośredniemu obliczeniu mediany będzie przydatne, gdy liczba zakresów, które należy przetestować, jest większa niż log (N). Z drugiej strony, jeśli liczba zakresów jest mniejsza niż log (N), może być lepiej przenieść elementy z danego zakresu na początek tablicy i użyć liniowego algorytmu wyboru czasu, aby znaleźć medianę.

Wszystko to sprowadza się do profilowania, aby uniknąć przedwczesnej optymalizacji. Jeśli podejście, które zastosujesz, okazuje się nie być wąskim gardłem dla wydajności twojego systemu, zastanawianie się, jak go poprawić, nie będzie przydatnym ćwiczeniem w stosunku do usprawniania tych części twojego programu, które są wąskimi gardłami.