Jak wybrać losowy element tablicy, który odpowiada pewne kryteria w czasie O (1)

Mam listę receptur uzyskano z bazy danych, która wygląda następująco:Jak wybrać losowy element tablicy, który odpowiada pewne kryteria w czasie O (1)

List<RecipeNode> _recipeList;

RecipeNode, między innymi, ma właściwość, która odwołuje się jeden lub więcej znaczników (takich jak Kolacja, śniadanie, Side, Wegetariańska, wakacje i około 60 innych).

public sealed class RecipeNode 
    { 
     public Guid RecipeId; 
     public Byte[] Tags; //Tags such as 1, 5, 6, 8, 43 
     //... More stuff 
    }

Znalezienie losowy przepis z _recipeList w czasie O (1) byłoby oczywiście łatwe, jednak to, co trzeba zrobić, to znaleźć losowy przepis, który ma, powiedzmy, 5 w Tags w czasie O (1).

W tej chwili moim jedynym pomysłem jest utworzenie tablicy List<RecipeNodes>, z kluczem. Na przykład:

List<RecipeNode>[] _recipeListByTag;

Następnie _recipeListByTag[5] będzie zawierać listę wszystkich przepisów, które mają 5 w tablicy Tags. Mógłbym wtedy wybrać losowy dozwolony znacznik i losową recepturę w tym znaczniku w O (1).

Wadą tego podejścia jest wielkość tej wielowymiarowej tablicy: Recipes * Tags (np. Suma Tags.length dla wszystkich receptur), która zaczyna zajmować dużo pamięci, ponieważ przechowywam potencjalnie ogromny liczba receptur w tej tablicy. Oczywiście, ponieważ RecipeNode jest typem referencyjnym, powtarzam tylko wskaźniki 4-bajtowe do receptur, więc to nadal może być najlepsza metoda.

Czy istnieje bardziej wydajna struktura danych lub algorytm, który mógłbym użyć, aby umożliwić mi znalezienie losowej receptury zawierającej określoną dozwoloną etykietę? Dzięki!

Źródło

2012-01-28 Mike Christensen

Dlaczego nie używać po prostu 'SQlite'? I odzyskaj dane w stałym (o ile to możliwe) czasie. – Tigran

+1 Tigran - wygląda na problem dostosowany do DB. – Oded

Wydaje mi się bardzo dziwne, że używasz tablicy bajtów dla znaczników, zamiast czegoś faktycznie zorientowanego obiektowo, takiego jak lista odwołań do obiektów znaczników. Czy naprawdę masz takie ograniczenia pamięci, że tak naprawdę musisz robić takie hacki? –

List<RecipeNode>[] _recipeListByTag jest prawdopodobnie najlepszym rozwiązaniem dla Ciebie, a jej wielkość jest nieRecipes * Tags ponieważ każda lista w tablicy będzie zawierał tylko tyle recepty jak dopasować znacznik, a nie więcej. Jego rozmiar stałby się Recipes * Tags, gdyby każdy przepis zawierał każdy tag.

Jeśli ilość pamięci zajmowanej przez struktury danych jest tak bardzo droga, nie zapomnij zadzwonić do List.TrimExcess() po wypełnieniu każdej listy.

Źródło

2012-01-28 21:23:06

Przepraszam, że nie sformułowałem tego dobrze - Chodziło mi o to, że jeśli przepis zawierał znacznik 5 i znacznik 10, odniesienie do niego byłoby * powtórzone * w indeksie 5 i 10. Długość byłaby liczbą relacji między recepturami i tag. –

Zdecydowałem się przejść tę trasę i mieć tablicę dla każdego tagu. Nawet z milionem par, co jest kolejnym 4 mega na kupce, prawda? –

Tak sądzę. Ale 4 mega są teraz niczym. –

Dokonałbym eksportu z listy źródłowej do innej z odniesieniami do wszystkich elementów, które ci odpowiadają. Dokonuje losowego wyboru i bierze element z listy źródłowej, zgodnie z referencją. Jeśli istnieje możliwość, że ponownie użyjesz tej samej wyprowadzonej listy, umieść takie listy w większej ich liście. (Oczywiście, wybrany algorytm zależy od rzeczywistych statystyk twojej listy).

Jeśli używasz tylko jednego parametru, możesz zamówić listę według tego parametru i zapamiętaj w innej liście B, gdzie znajduje się element z tym samym początkiem wartości parametru. Później możesz po prostu wybrać losowo w przedziale (B [4]; b [5] -1). To spowodowałoby, że prędkość losowego wyboru była równa O (const).

Źródło

2012-01-28 21:14:41 Gangnus

Jeśli dobrze rozumiem, to wydaje się podobne do tego, co mówił @AlexD. Przechowywanie przesunięć, w których każda grupa zaczyna się i kończy. Myślę, że to jest to samo, co poszarpana tablica. –

Tak, jest to odpowiednik. Ale główna myśl - nie można zaproponować optymalnego algorytmu, nie znającego rzekomych statystyk jego użycia. – Gangnus

Jeśli używasz znaczników całkowitych z niewieloma możliwymi wartościami, nie musisz nawet zamawiać ich przez tagi. Lepiej weź max i min i zrób listę pokwitowań dla każdej pozycji między tymi dwoma. Byłby to rzadki poszarpany układ. – Gangnus

W tym przypadku osobiście wybrałbym rozwiązanie SQlite (ponieważ ja, osobiście wiem, że jest ono lepsze niż inne). Widzę, że martwisz się przestrzenią, a nie wydajnością pod względem szybkości, ale jeśli chodzi o stały czas odzyskiwania, martwisz się także elastycznością dostępu do danych. Imo, w tym przypadku, SQlite jest drogą do zrobienia.

Zaprojektuj swój mały DB w sposób, który chcesz i wykonaj zapytania i połączenia w wybrany przez siebie sposób.

This jest starym, ale zawsze ważnym przykładem tego, jak z niego korzystać. Istnieje również, oczywiście, rozwiązanie ORM (na przykład sterownik LINQ), ale dla mnie osobiście wydaje się trochę narzut.

Mam nadzieję, że to pomoże.

Źródło

2012-01-28 21:16:23 Tigran

Jeśli chcesz zachować dane w pamięci, nie zrobisz nic lepszego niż lista (4 bajtów) wskaźników dla każdego tagu. Jeśli możesz użyć DB ... cóż, inni już o tym napisali. W zależności od tego, jak ogromna jest "ogromna", możesz po prostu dodać trochę $$ $, aby dodać pamięć RAM do komputera docelowego.

Jeśli chcesz zachować dane w pamięci, ale chcesz być absurdalnie oszczędny w użyciu pamięci, możesz spróbować zmniejszyć 4 bajty na kombinację tag-receptura. Na przykład zachowaj wszystkie przepisy w dużej tablicy i (zakładając, że nie będziesz mieć więcej niż około miliona) przechowuj indeksy tablicy w 3 bajtach każdy.

Aby posunąć się dalej, można podzielić przepisy z danym znacznikiem na równe "wiadra" (każda zajmuje sąsiadujący obszar wielkiej tablicy), przechowywać indeks początkowy dla każdego "wiadra" (w 3- 4 bajty), a następnie zapisuje listę wartości delta między indeksami kolejnych receptur z podanym znacznikiem. Zakoduj wartości delta, używając tablicy bajtów, w taki sposób, aby pojedyncza wartość delta mogła w razie potrzeby wykorzystywać wszystko od 1 do 4 bajtów.

Ponieważ liczba receptur w "wiadrze" będzie ograniczona do stałej liczby, pobieranie za pomocą tego podejścia nadal będzie O (1).

(Zrobiłem wbudowane programowanie na mikromacie z tak małą ilością 256 bajtów pamięci RAM ... kiedy to robisz, zaczynasz myśleć o bardzo twórczych sposobach zapisywania bajtów lub nawet bitów. Jestem pewien, że idąc do takich długości nie będzie konieczne w twojej aplikacji, ale pomyślałem, że to ciekawy pomysł.)

Źródło

2012-01-28 21:28:31

Próbowałem również przejść przez te linie, ale doszedłem do wniosku, że (wykorzystanie pamięci mądry) nie byłoby inaczej niż mój pomysł wielowymiarowej tablicy. Na przykład, jeśli receptury Tag 5 były przechowywane między indeksami tablicy 100 i 200, a receptury Tag 6 były przechowywane między 201 a 230, receptura, która miała oba znaczniki 5 * i * 6, nadal musiałaby być przechowywana dwa razy. –

@MikeChristensen, myślę, że może nie rozumiesz w pełni mojego pomysłu. W przypadku "tablic wielowymiarowych" potrzebujesz 4-bajtowego wskaźnika dla każdej kombinacji tag-receptura. Ta idea jest inną (zakodowaną w trójkątach) reprezentacją tej samej struktury, która ma na celu przesunięcie liczby bajtów na kombinację tag-recept do średnio 1-2 bajtów. Jeśli różnica między indeksami 1. i 2. receptury z tagiem 5 jest mniejsza niż 255, można zapisać różnicę w 1 bajcie, zamiast przechowywać 2 4-bajtowe indeksy. Jeśli był mniejszy niż 2^16, możesz zapisać go w 2 bajtach, itp. –

Aby użyć różnych liczb bajtów dla wartości delta, możesz użyć schematu podobnego do UTF-8. (Na początku każdego znaku wielobajtowego używają pewnych bitów do wskazania liczby bajtów, które ten znak zajmuje.) –

Czy to praca domowa? Wątpię, aby jakikolwiek program w świecie rzeczywistym wymagał od użytkownika dostępu do znaczników i byłby zbyt wolny, aby móc korzystać z bazy danych. Wątpię też, by jakikolwiek przepis na świecie miał numery numeric. Zrozumienie prawdziwej domeny może pomóc w uzyskaniu lepszej odpowiedzi.

Jednak jeśli tak naprawdę chodzi o przepisy i znaczniki liczbowe, a jeśli masz tylko 256 tagów, dlaczego nie wybierzesz losowej receptury milion razy? Szanse na brak znalezienia receptury z wymaganym znacznikiem są minimalne, a złożoność nadal wynosi O (1). Jeśli nie podoba ci się kurs, wybierz losową recepturę 10^20 razy. Złożoność to nadal O (1).

UPDATE:

Ponieważ nie jest to O (1) martwisz, ale czas potrzebny, aby wybrać losowy przepis, proponuję niech bazie obsłużyć to dla ciebie - ta sama baza danych który trzyma wszystkie przepisy w każdym razie i tę samą bazę danych, do której masz dostęp, aby pokazać losową recepturę.

Można wpisać przypadkowy rekord serwera SQL w następujący sposób: SELECT: SQL Server Random Sort. Jeśli używasz innej bazy danych, istnieją inne sposoby: http://www.petefreitag.com/item/466.cfm. Po prostu upewnij się, że klauzula WHERE ma w sobie Tag=17.

Źródło

2012-01-28 22:07:16 zmbq

Uwaga: Zgadzam się, wciąż nie jesteś całkowicie pewien, że ta technika da przepis z odpowiednią etykietą, ale będzie w każdym rzeczywistym przypadku ... – zmbq

Losowe wybieranie przepisu, a następnie odrzucanie go, jeśli nie pasuje do żadnego z pożądanych znaczników, spowolni działanie tej funkcji, szczególnie jeśli użytkownik zezwala tylko na 1 niejasny znacznik (jak dania afrykańskie). Lepiej jest utworzyć indeks receptur według znacznika, a następnie wyszukać prawidłowe receptury w O (1). Zastanawiam się, w jaki sposób najlepiej to zrobić przy minimalnym zużyciu pamięci. –

Myślałem, że martwisz się złożonością, a nie szybkością. Jeśli obawiasz się szybkości, umieść wszystko w bazie danych i pozwól, aby to dla ciebie uporządkowało. Będzie wystarczająco szybko. – zmbq

Jak wybrać losowy element tablicy, który odpowiada pewne kryteria w czasie O (1)

Odpowiedz

Powiązane problemy