Pracuję nad systemem list życzeń, w którym użytkownicy mogą dodawać elementy do różnych list życzeń, i zamierzam umożliwić użytkownikom ponowne zamówienie elementów w późniejszym terminie. Nie jestem do końca pewien, jak najlepiej przechować to w bazie danych, jednocześnie zachowując szybkość i nie zmieniając się w bałagan (ta aplikacja będzie używana przez dość dużą bazę użytkowników, więc nie chcę, aby spadła do czyszczenia rzeczy).
Początkowo próbowałem position
kolumny, ale wydaje się, że byłoby dość nieefektywne zmienianie wartości pozycji każdego innego elementu podczas przenoszenia.
Widziałem ludzi używających odsyłaczy do odniesienia do poprzedniej (lub następnej) wartości, ale znowu wydaje się, że musiałbyś zaktualizować całą masę innych pozycji na liście.
Innym rozwiązaniem, które widziałem, jest używanie liczb dziesiętnych i po prostu umieszczanie przedmiotów w przerwach między nimi, co wydaje się najlepszym rozwiązaniem do tej pory, ale jestem pewien, że musi być lepszy sposób.
Powiedziałbym, że typowa lista zawierałaby do około 20 przedmiotów i prawdopodobnie ograniczę ją do 50. Zmiana kolejności będzie polegała na przeciąganiu i upuszczaniu i prawdopodobnie zostanie wykonana partiami, aby zapobiec warunkom wyścigowym i tym podobne z żądania ajax. Używam postgres (na heroku), jeśli to ma znaczenie.
Czy ktoś ma jakieś pomysły?
Pozdrawiam za wszelką pomoc!
źródło
Odpowiedzi:
Po pierwsze, nie próbuj robić niczego sprytnego z liczbami dziesiętnymi, ponieważ będą cię na złość.
REAL
iDOUBLE PRECISION
są niedokładne i mogą niepoprawnie przedstawiać to, co w nich wkładasz.NUMERIC
jest dokładne, ale właściwa sekwencja ruchów zabraknie ci precyzji, a twoja implementacja źle się zepsuje.Ograniczenie ruchów do pojedynczych wzlotów i upadków sprawia, że cała operacja jest bardzo łatwa. Aby uzyskać listę kolejno ponumerowanych elementów, możesz przesunąć element w górę, zmniejszając jego pozycję i zwiększając numer pozycji niezależnie od tego, co wymyślił poprzedni dekrement. (Innymi słowy, poz
5
stanie4
i jaki był przedmiot4
staje się5
skutecznie swap jak kretyni opisano w swojej odpowiedzi.) Przesuwając go byłoby odwrotnie. Indeksuj swoją tabelę według tego, co jednoznacznie identyfikuje listę i pozycję, i możesz to zrobić za pomocą dwóchUPDATE
sekund w transakcji, która będzie przebiegać bardzo szybko. Chyba że użytkownicy zmieniają swoje listy z nadludzkimi prędkościami, nie spowoduje to dużego obciążenia.Ruchy metodą „przeciągnij i upuść” (np. Przesuń element,
6
aby usiąść między elementami9
i10
) są nieco trudniejsze i muszą być wykonane inaczej w zależności od tego, czy nowa pozycja znajduje się powyżej czy poniżej starej. W powyższym przykładzie musisz otworzyć dziurę, zwiększając wszystkie pozycje większe niż9
, aktualizując pozycję przedmiotu6
, aby była nowa,10
a następnie zmniejszając pozycję wszystkiego większego niż,6
aby wypełnić puste miejsce. Przy takim samym indeksowaniu, jak opisałem wcześniej, będzie to szybkie. Możesz faktycznie sprawić, że pójdzie to trochę szybciej niż to opisałem, minimalizując liczbę wierszy, które dotyka transakcja, ale jest to mikrooptymalizacja, której nie potrzebujesz, dopóki nie udowodnisz, że istnieje wąskie gardło.Tak czy inaczej, próba prześcignięcia bazy danych za pomocą domowego, zbyt sprytnego rozwiązania na pół nie zwykle kończy się sukcesem. Bazy danych warte swojej soli zostały starannie napisane, aby wykonywać te operacje bardzo, bardzo szybko przez ludzi, którzy są w tym bardzo, bardzo dobrzy.
źródło
Ta sama odpowiedź tutaj https://stackoverflow.com/a/49956113/10608
Rozwiązanie: zrób
index
łańcuch (ponieważ w zasadzie łańcuchy mają nieskończoną „dowolną precyzję”). Lub jeśli używasz int, zwiększajindex
o 100 zamiast 1.Problem z wydajnością jest następujący: między dwoma posortowanymi elementami nie ma „pośrednich” wartości.
Zamiast tego zrób tak (lepsze rozwiązanie poniżej):
Jeszcze lepiej: oto jak Jira rozwiązuje ten problem. Ich „ranga” (tak zwany indeks) jest wartością ciągu, która pozwala tonie oddychać pomiędzy pozycjonowanymi pozycjami.
Oto prawdziwy przykład bazy danych Jira, z którą pracuję
Zwróć uwagę na ten przykład
hzztzz:i
. Zaletą rangi sznurkowej jest to, że zabraknie miejsca między dwoma przedmiotami, nadal nie musisz zmieniać rangi niczego innego. Po prostu zacznij dodawać więcej znaków do ciągu, aby zawęzić fokus.źródło
Dlaczego? Załóżmy, że stosujesz podejście do tabeli z listami połączonymi z kolumnami (listID, itemID, nextItemID).
Wstawienie nowego elementu do listy kosztuje jedną wstawkę i jeden zmodyfikowany wiersz.
Zmiana położenia przedmiotu kosztuje trzy modyfikacje wiersza (przenoszony element, element przed nim i element przed nową lokalizacją).
Usunięcie elementu kosztuje jedno usunięcie i jeden zmodyfikowany wiersz.
Koszty te pozostają takie same, niezależnie od tego, czy lista zawiera 10 pozycji, czy 10 000 pozycji. We wszystkich trzech przypadkach modyfikacja jest mniejsza, jeśli wiersz docelowy jest pierwszym elementem listy. Jeśli częściej operujesz na ostatnim elemencie listy, może być korzystne zapisanie prevItemID zamiast następnego.
źródło
Czy mierzyć to? Czy to tylko zgadywanie? Nie rób takich założeń bez żadnego dowodu.
Szczerze mówiąc, to nie jest „dużo przedmiotów”, dla mnie to brzmi bardzo mało.
Proponuję trzymać się zasady „kolumny pozycji” (jeśli jest to najprostsza implementacja dla Ciebie). W przypadku tak małych list nie zaczynaj niepotrzebnej optymalizacji przed wystąpieniem prawdziwych problemów z wydajnością
źródło
To jest naprawdę kwestia skali i przypadku użycia ..
Ile oczekujesz pozycji na liście? Jeśli miliony, myślę, że gong dziesiętna trasa jest oczywista.
Jeśli 6, to numeracja liczb całkowitych jest oczywistym wyborem. s Również pytania dotyczą tego, w jaki sposób listy zostały uporządkowane. Jeśli używasz strzałek w górę i w dół (poruszanie się w górę lub w dół o jedno miejsce na raz), i użyłbym liczb całkowitych, a następnie zamieniłem się z poprzednim (lub następnym) w ruchu.
Jak często dokonujesz zmian, jeśli użytkownik może wprowadzić 250 zmian, to zatwierdzaj naraz, niż mówię liczby całkowite z ponowną numeracją ...
tl; dr: Potrzebujesz więcej informacji.
Edycja: „Listy życzeń” brzmią jak wiele małych list (założenie, że to może być fałsz). Więc mówię Integer z numeracją. (Każda lista zawiera własną pozycję)
źródło
Jeśli celem jest zminimalizowanie liczby operacji bazy danych na operację zmiany kolejności:
Przy założeniu, że
Przechowuj posortowaną listę życzeń użytkownika jako spakowaną sekwencję liczb całkowitych (tablic liczb całkowitych) w jednej kolumnie. Za każdym razem, gdy lista życzeń jest zmieniana, cała tablica (pojedynczy wiersz; pojedyncza kolumna) jest aktualizowana - co należy wykonać za pomocą pojedynczej aktualizacji SQL.
https://www.postgresql.org/docs/current/static/arrays.html
Jeśli cel jest inny, trzymaj się podejścia „kolumna pozycji”.
Jeśli chodzi o „szybkość”, należy przeprowadzić analizę porównawczą podejścia do procedury składowanej. Chociaż wydawanie ponad 20 oddzielnych aktualizacji dla jednego losowego losowania listy życzeń może być powolne, może być szybki sposób przy użyciu procedury składowanej.
źródło
OK. Ostatnio mam do czynienia z tym trudnym problemem, a wszystkie odpowiedzi w tym poście zadały wiele inspiracji. Z mojego punktu widzenia każde rozwiązanie ma swoje zalety i wady.
Jeśli
position
pole musi być sekwencyjne bez luk, wtedy w zasadzie będziesz musiał ponownie uporządkować całą listę. Jest to operacja O (N). Zaletą jest to, że po stronie klienta nie potrzeba żadnej specjalnej logiki, aby uzyskać zamówienie.Jeśli chcemy uniknąć operacji O (N), ALE JESZCZE utrzymujemy dokładną sekwencję, jednym z podejść jest użycie „odniesienia do siebie w odniesieniu do poprzedniej (lub następnej) wartości”. To jest scenariusz z listą powiązaną z podręcznikiem. Z założenia NIE spowoduje to „wielu innych pozycji na liście”. Wymaga to jednak po stronie klienta (usługi sieciowej lub aplikacji mobilnej) wdrożenia logiki przejścia listy powiązanej w celu uzyskania kolejności.
Niektóre warianty nie wykorzystują odniesienia, tj. Listy połączonej. Wybierają reprezentowanie całego porządku jako samodzielnego obiektu blob, takiego jak tablica JSON w ciągu
[5,2,1,3,...]
; taka kolejność będzie następnie przechowywana w oddzielnym miejscu. Takie podejście ma również efekt uboczny polegający na wymaganiu od strony klienta kodu utrzymania tego oddzielnego obiektu blob zamówienia.W wielu przypadkach tak naprawdę nie musimy przechowywać dokładnej kolejności, musimy jedynie utrzymać względną pozycję w każdym rejestrze. Dlatego możemy dopuścić luki między kolejnymi rekordami. Odmiany obejmują: (1) użycie liczb całkowitych z lukami, takimi jak 100, 200, 300 ... ale szybko zabraknie braków, a następnie będziesz potrzebować procesu odzyskiwania; (2) przy użyciu liczb dziesiętnych z naturalnymi lukami, ale musisz zdecydować, czy możesz żyć z ewentualnym ograniczeniem precyzji; (3) używając rangi opartej na łańcuchach, jak opisano w tej odpowiedzi, ale uważaj na trudne pułapki implementacyjne .
Prawdziwa odpowiedź może brzmieć „to zależy”. Ponownie sprawdź wymagania biznesowe. Na przykład, jeśli jest to system z listą życzeń, osobiście chętnie skorzystałbym z systemu organizowanego przez zaledwie kilka rang jako „must have”, „good-to-have”, „może-later”, a następnie prezentowałem przedmioty bez szczególnych porządek wewnątrz każdej rangi. Jeśli jest to system dostarczania, możesz bardzo dobrze wykorzystać czas dostawy jako przybliżoną pozycję, która ma naturalną lukę (i naturalne zapobieganie konfliktom, ponieważ żadna dostawa nie nastąpiłaby w tym samym czasie). Twój przebieg może się różnić.
źródło
Użyj liczby zmiennoprzecinkowej dla kolumny pozycji.
Następnie możesz zmienić kolejność listy, zmieniając tylko kolumnę pozycji w wierszu „przeniesionym”.
Zasadniczo, jeśli użytkownik chce ustawić „czerwony” po „niebieskim”, ale przed „żółtym”
Musisz po prostu obliczyć
Po kilku milionach zmian pozycji liczby zmiennoprzecinkowe mogą być tak małe, że nie ma „pomiędzy” - ale jest to tak samo prawdopodobne, jak zobaczenie jednorożca.
Możesz to zaimplementować za pomocą pola liczb całkowitych z początkową przerwą, powiedzmy 1000. Tak więc początkowe oreringowanie byłoby 1000-> niebieski, 2000-> Żółty, 3000-> Czerwony. Po „przesunięciu” koloru czerwonego po niebieskim miałbyś 1000-> niebieski, 1500-> czerwony, 2000-> żółty.
Problem polega na tym, że przy pozornie dużej początkowej luce wynoszącej 1000, zaledwie 10 ruchów doprowadzi cię do sytuacji takiej jak 1000-> niebieski, 1001-puce, 1004-> biege ...... gdzie nie będziesz już w stanie wstawić cokolwiek po „niebieskim” bez ponownego numerowania całej listy. Używając liczb zmiennoprzecinkowych, zawsze będzie punkt „w połowie” między dwiema pozycjami.
źródło
"pos": 1310719, + "pos": 638975.5
. Szczerze mówiąc, większość ludzi nie tworzy list trello z 4 milionami wpisów, ale rozmiar i sposób użycia listy Trello jest dość powszechny w przypadku treści, które można sortować. I wszystko, co można sortować przez użytkownika, nie ma w przybliżeniu nic wspólnego z wysoką wydajnością, szybkość sortowania int vs float jest do tego słuszna, szczególnie biorąc pod uwagę, że bazy danych są w większości ograniczone przez wydajność IO.