Witam,
mam taki nietypowy algorytm i zastanawiam się jak go najlepiej zaimplementować. Mianowicie sytuacja wygląda następująco, mam przykładowy model Person o następujących kolumnach: id, name (imię i nazwisko), order (pozycja na liście).
Teraz zagadka. Jak, wykorzystując kolumnę order, pobierając przykładowo z bazy po 50 rekordów, posortować je tak aby osoby z tym samym nazwiskiem były od siebie maksymalnie oddalone na liście.
Próbuję to rozwiązać zmodyfikowaną przeze mnie wersją algorytmu sortowania przez wstawianie, ale chyba kiepsko to wymyśliłem.
W bazie wykorzystując kolumnę order. Ewentualnie, zastanawiam się jeśli tego by się nie dało zrobić sortować te rekordy jakoś przy wprowadzaniu ich do bazy danych.
Myślę, że to co nam opisałeś nawet nie jest sortowaniem zakładając, że przez sortowanie rozumiemy uporządkowanie obiektów w ciąg na podstawie porównań każdego dwóch z nich. Dla mnie sortowanie jest procesem w którym porównując obiekt A i B, inne obiekty w kolekcji nie mają wpływu na wynik tego porównaniu. To co tutaj próbujesz osiągnąć jest bardzo nietrywialne i zastanawiam się nad złożonością tego problemu w ogóle.
Wyobraź sobie takie ciąg wstawianych nazwisk
A
A B
A B C
A B C A
A B C B A, a może: A B C A B
Wyobrażam sobie, że pewnie wstawiając dowolne nazwisko do bazy trzeba bardzo dużo kombinacji sprawdzić żeby uzyskać optymalny wynik. Być może w małej liczbie elementów mógłbyś sprawdzić wszystkie możliwe kombinacje i dla nich wyliczyć wartość współczynnika jakiegoś i po nim posortować ale to będzie bardzo nieoptymalne.
Tak samo jak apohllo trudno mi sobie wyobrazić usecase.
Na temat ewentualnej algorytmiki i złożoności tego problemu mógłby się wypowiedzieć ktoś z większym doświadczeniem akademickim
Zgrupuj obiekty Person wg nazwiska.
Dla każdej grupy:
Wstawiaj do docelowej tabeli obiekty o danym nazwisku co k miejsc (k = ilość wszystkich rekordów / ilość rekordów w grupie).
Oczywiście jeśli dane miejsce jest już zajęte obiekt należy wstawić w najbliższe wolne miejsce.
Łatwe w implementacji choć niekoniecznie optymalne.
Raczej przy każdej operacji pobierania rekordów. Wydaje się, że problem dotyczy sposobu prezentacji danych, dlatego zrezygnowałbym z pamiętania porządku w kolumnie order (wstawianie nowego rekordu może być zbyt kosztowne).
Problem ciekawy, chętnie poznam lepsze rozwiązania.
Problem nie dotyczy sposobu prezentacji danych. Pomieszanie tego w idealny sposób w rozsądnym czasie jest chyba nierealne. Tak jak napisałem, te rekordy mogę też ‘porządkować’ przy wprowadzaniu ich do bazy. Wstępnie wymyśliłem coś takiego: pierwsza pętla pobiera elementy z tabeli dopóki ta tabela nie jest pusta, w środku biorę jeden element i ‘przymierzam’ go do bazy, jeżeli w pobliżu nie ma podobnych nazwisk to wstawia do bazy i usuwa. Do tego jakieś zabezpieczenie, żeby się nie zapętlił w niekorzystnym przypadku. Nie jest to za mądre, ale na razie nic innego mi nie przychodzi do głowy.
A może tak z innej strony co w ogóle chcesz osiądnąć, to że posortować w taki sposób to wszyscy wiedzą już tylko po co? Jaki jest przypadek uzycia tego? Opisz jakiś scenariusz, moze mozna to rozwiazac inaczej
Raczej przy każdej operacji pobierania rekordów.[/quote]
Prawie jak PHP 5.3.9 - we put a bug in yo patch, so u can patch while u patch. Innymi słowy: leczenie choroby trucizną.
Oczywiście nie mówię tutaj o pobieraniu 50tyś rekordów i grupowaniu ich wg autora, a następnie zapisywaniu nowej kolejności w bazie danych. Myślałem o sensownej liczbie rekordów które można wyświetlić na jednej stronie. Takie ustalanie kolejności można by zaimplementować nawet w JS. Tylko jak widać, nie o to chodziło autorowi pytania. @exage
To rozważania czysto teoretyczne, czy takie ułożenie nazwisk jest wymogiem w realnej aplikacji?
Może projektujesz coś na wzór sortowni Amazonu, gdzie podobne przedmioty nie mogą znajdować się na tej samej półce?
