Mam następujący problem. Potrzebuję posortować listę obiektów. Każdy obiekt ma w sobie tablicę liczb rzeczywistych z zakresu (0, 1>. Suma liczb w tablicy jest równa 1, a długość tablicy jest większa lub równa 1. Ta tablica jest posortowana od największej liczby do najmniejszej. Na podstawie takich tablic ma być posortowana lista obiektów. Na początku mają być te obiekty, które mają tablicę o długości 1, a zatem zawierającą tylko wartość 1 w tablicy. W drugiej kolejności mają być tablice 2-elementowe, ale na początku te, w których pierwszy element jest większy. Następnie tablice 3-elementowe również w kolejności od największego elementu, jeżeli pierwsze są równe, to porównywany jest drugi. Dalej tablice n-elementowe w kolejności od najkrótszych i od największych wartości na początku tablicy.
Tak więc posortowanie listy nie jest problemem, bo wiadomo jak to zrobić. Zasadnicza kwestia dotyczy uproszczenia algorytmu. Otóż przyszło mi do głowy, że istnieje funkcja, która dla zadanej tablicy zwróci wartość liczbową, wg której będzie można sortować listę i otrzyma się tą samą kolejność. Być może jest to jakiś znany parametr statystyczny i sprawa jest oczywista dla kogoś, kto się na tym zna i w tym siedzi.
Oczywiście zakładam, że istnieje wiele takich funkcji, które będą realizować to zadanie, dlatego oczekuję wszelkich pomysłów jak można by to zrobić.
Napisz funkcję porównującą.
Z użyciem takiej funkcji możesz dowolny algorytm sortowania zastosować.
Chyba nie dokładnie się wyraziłem. Kod mam w jawie i używam
Collections.sort(lista, komparator);
W komparatorze mam rzeczoną funkcję, która porównuje dwie tablice. Zatem nie chodzi mi o implementację algorytmu sortowania. Chcę napisać funkcję
int compact(double[] array){}
która pozwoli mi w komparatorze porównywać tylko wyniki tej funkcji. Raz obliczony wynik zapiszę w obiekcie również do innych porównań.
Ilość par do porównania wynosi N*(N-1)/2 ilość porównań w trakcie sortowania N*log2(N) może podstawmy zamiast N np 1000
par: 499500
porównań: 9966
Czyli w trakcie sortowania wykorzystano: 1.995 procenta możliwych porównań.
W świetle powyższego jak sądzisz ile z tych 2-ch procentów się powtarza?
Nie wiem o czym mówisz, ale jeszcze raz podkreślę: nie chodzi mi o sam algorytm sortowania, tylko funkcję pozwalającą tak skonstruowane tablice skrócić do jednej liczby.
- Nie ma takiej możliwości, no chyba że pasuje ci spora strata dokładności.
- Nawet jeżeli ci to pasuje to i tak tego nie potrzebujesz co wyraźnie dowiodłem ale, z tym że nie zrozumiałeś ("Nie wiem o czym mówisz").
- Przykład jak to zrobić (drugi, który mi przyszedł do głowy). Wystarczy przypisać malejące wagi do poszczególnych pól tablicy i otrzyma się liczbę spełniającą warunek do sortowania. Jednak wydaje mi się to mało eleganckie. Chciałbym, żeby ta liczba coś mówiła o rozkładzie wartości w tablicy.
- Do czego mi to potrzebne: sortuję listę i zapisuję otrzymane z tablic wartości. Dołączam do niej nową, nieposortowaną listę. Ponownie sortuję i wtedy nie obliczam na nowo wartości dla elementów z pierwszej listy.
Oczywiście to tylko kontrprzykłady do tego co napisałeś. Nadal interesuje mnie funkcja o takich własnościach. Pozwól, że to ja ocenię, czy coś mi jest potrzebne, czy nie jest. Nie chcę się wdawać w polemiki na ten temat, bo nic z nich nie wyniknie.
Musisz powiedzieć o tych tablicach coś więcej.
Czy jest maksymalny rozmiar?
Jaka musi być dokładność?
_13th_Dragon napisał(a):
Musisz powiedzieć o tych tablicach coś więcej.
Czy jest maksymalny rozmiar?
Jaka musi być dokładność?
Tablice określają prawdopodobieństwa, że dany obiekt będzie należał do konkretnej grupy. Z tego powodu suma jest równa 1. Rozmiar maksymalny można przyjąć, że jest znany, od 2 do powiedzmy 100. Na tą chwilę dokładność do 5 miejsca po przecinku wydaje się wystarczająca. Sortowanie ma preferować obiekty z większym prawdopodobieństwem poprawnego przypisania do grupy. Zmienny rozmiar tablicy wynika z tego, że pozostałe wartości są zerami, więc jak coś to ułatwi, to można przyjąć, że tablice są stałego rozmiaru, ale tylko na początku mają wartości różne od 0 w porządku malejącym, np. [0.9, 0.07, 0.03] jest równoważne [0.9, 0.07, 0.03, 0, 0, 0, 0, 0, 0, 0] przyjmując maksymalny rozmiar tablicy 10.
Więc wszystko jest proste do 5-go miejsca po przecinku to miej więcej 16 bitów potrzebne, razy 100 liczb wychodzi 1600 bitów, owszem istnieją biblioteki BigInt.