10
Czy sortowanie radix jest w stanie sortować dane zmiennoprzecinkowe na przykład 0,5, 0,9, 1,02 itd.?Sortowanie radix, sortowanie danych zmiennoprzecinkowych
A
Odpowiedz
1
Zestaw nie jest gotowy do użycia, ale masz kilka opcji. Możesz dyskretyzować dane, np. Pomnożając przez 100 i zaokrąglając (tak, byś miał, dla twojego przykładu powyżej, 5, 9 i 102). Można również gromadzić dane (grupowanie według zakresów, jak w 0 < x < = 1, 1 < x < = 2), a następnie sortować w obrębie każdego segmentu.
24
Tak, jest to możliwe. Wymaga dodatkowego podania, aby poprawnie obsługiwać wartości ujemne. Artykuły pod Pierre Terdiman i Michael Herf szczegółowo omawiają sposób jego implementacji. W skrócie, konwertujesz zmiennoprzecinkowe na unsigned integer, sortujesz je, a następnie konwertujesz z powrotem na float (jest to wymagane, w przeciwnym razie wartości ujemne zostaną niepoprawnie posortowane po wartościach dodatnich).
Ich metoda ma tę zaletę, że nie wprowadza żadnych błędów do danych (pod warunkiem, że procesor przechowuje wartość zmiennoprzecinkową zgodnie ze standardem IEEE 754).
+0
+1 za świetne artykuły. –
+1
Oto kolejny ciekawy artykuł (http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html) porównujący sortowanie radix z równoległą wersją scalania SPU. Podsumowując, sortuj scalaj, gdy jest bardziej złożony (złożoność to O (n log n) w przypadku O (n) sortowania radix), można łatwiej zrównoleglić i wygrać w końcu. –
Chciałbym zaimplementować sortowanie radix przez zmniejszenie jego segmentów na 0 i 1, co oznacza, że chciałbym przekształcić każde wejście na jego wartość binarną, a następnie przejść do sortowania radix, czy byłoby to opcja przyspieszenia sortowania, czy też radix sortuje się nieco wolniej niż wcześniej ?. Dzięki. – BGV