logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

przeszukiwanie tablic wielowymiarowych w C

rpal 03 Wrz 2010 23:22 2497 13
REKLAMA
  • #1 8473388
    rpal
    Poziom 27  
    Jak w temacie, prosiłbym o jakiś pomysł na wydajne i szybkie przeszukiwanie powiedzmy 4 elementowych tablic (w kolumnach) w ramach algorytmu mającego odszukać najbardziej podobną wartość do zadanej. Nie mam żadnego pomysłu porównywanie od pierwszego do ostatniego indeksu tablicy dla każdego elementu to coś czuję ostania rzecz jaką można zrobić. Chodzi o tablicę o rozmiarze maksymalnego indeksu ok 9600 (ilość wierszy). Z tego powodu z założenia pamięć jest typu extend. Chodzi o pomysł na algorytm a nie o gotowiec.
  • REKLAMA
  • #2 8473466
    michalko12
    Specjalista - Mikrokontrolery
    To są tablice stałych elementów czy zmiennych, określ typ tych danych
  • REKLAMA
  • #3 8473487
    Konto nie istnieje
    Poziom 1  
  • REKLAMA
  • #4 8473798
    tmf
    VIP Zasłużony dla elektroda
    Elementy tych tablic pełniają jakieś zależności? Są posortowane? Jakiego typu są elementy? W najogólniejszym przypadku jest tak jak pisze atom, ale można to czasami zoptymalizować. Jeśli możesz posortować elementy to już będzie łatwiej. Jeśli nie to możesz zastosować indeksy, to szczególnie przyśpieszy działanie dla łańcuchów. Możesz też zmienić sposób organizacji danych, np. zastosować drzewa binarne.
  • #5 8473954
    Konto nie istnieje
    Poziom 1  
  • #6 8474422
    kubus_puchatek
    Poziom 18  
    Zrób drzewo zrównoważone. algorytm wydaje się trudny (równoważenie drzewa) ale za to działa wyśmienicie.
    Jednak jak przez to przejdziesz to ztrawersowanie drzewa do szukanego elementu przy 10 000 elementów zajmie 11 operacji. Jednaj do każdego elementu musisz dodać2 wskaźniki na gałęzie a to oznacza że musisz dodać po 3 bajty.
  • #7 8475028
    rpal
    Poziom 27  
    chodzi od to że mam 4 liczby typu int będące wierzchołkami prostokąta (może być i kwadratu. Tablica zawiera współrzędne teroretycznie n prostokątów a w praktyce coś koło 128 takich "czwórek" + jedną wartość char będącą identyfikatorem prostokąta. Prostokąty nie nachodzą na siebie. Taka tablica istotnie może być posortowana tylko wg której z wartości ? Teraz mam współrzedne wierzchołków miejsca na płaszczyźnie okreslonej współrzędnymi X,Y i należy jak najszybciej doszukać się w zbiorze współrzędnych (patrz wspomniana tablica) pierwszego z elementów dla którego zadany punkt (mający określone współrzędne x,y) zawiera się w jednej z tych "czwórek" . Takie to akademickie zadanie :) najprościej jest przeszukiwać po kolei taką tablicę dla każdego z wierzchołków ale to wcale nie najszybciej.
  • REKLAMA
  • #8 8475224
    gaskoin
    Poziom 38  
    a te prostokąty są zawsze równolegle do ziemii czy mogą być np obrócone ?
  • #10 8475534
    rpal
    Poziom 27  
    Odpowiem tak aby nie wymyślać za wiele. Chodzi o to że kombinuję na sterownikiem do panelu dotykowego ale programowalnego. Chcę odciążyć procek od interpretacji współrzędnych i zrobić to tak aby można było w dodatku jeszcze go programować poprzez wgranie nowych współrzędnych miejsc do macania :)
    Zwracać ma kod odpowiadający powiedzmy umownie nazwę - klawiszowi. Założenie jest takie że ma być kilkupoziome menu a panel wraz ze zwracanymi przez siebie danymi ma w zakresie wyboru ma podążać za zmieniającymi się ekranami. Może się mylę ale jeśli bym tym zajęciem obciążył zasadniczego procka to byłaby to dla niego spora robota . Jakiś mały Atmega np M162 moim zdaniem spokojnie się wyrobi z tym zagadnieniem a koszt samego przesięwzięcia nie przekroczy dedykowanego IC dla panelu dotykowego który i tak jest o tyle ubogi że nie interpretuje tego co sobie odczyta. Nawet jeśli pola do "macania" będą nieregularne (elipsa, koło czy też cokolwik innego) to zawsze da się to opisać jako prostokąt. Niestety nie mogę założyć jak będzie taki prostokąt umiejscowiony krótszym czy dłuższym bokiem do dołu. Takie założenie wymaga sporych zasobów pamięci ale te są przecież do zrobienia za pomocą pierwszego z brzegu SRAM któremu można jeszcze na dodatek przełączać banki pamięci. W końcu coś wymyślę, ale póki co nie mam żadnego punktu zaczepienia.
    Na razie pomysł mam taki aby na początek przelecieć całą tablicę od góry do dołu w poszukiwaniu współrzędnych lewego górnego rogu które będą większe lub równe odczytanym aktualnie współrzędnym z panelu, tworząc tymczasową tablicę z indeksami odpowiadającym tym kryteriom elemnentom globalnej tablicy. Potem zaś znowu od początku do końca pobierać z tej tymczasowej tablicy indeks na dopasowane elementy i sprawdzać czy z kolei odczytana współrzędna jest mniejsza lub równa dla zdefiniowanych wczsniej współrzędnych. Tak aż do pierwszego dopasowania. tym samy ograniczę sobie możliwość przeszukiwania całej tablicy, dla powiedzmy drugiego kroku. nie wiem czy nei namąciłem za bardzo.
  • #11 8475606
    Konto nie istnieje
    Konto nie istnieje  
  • #12 8475644
    rpal
    Poziom 27  
    kol albert to jest to samo tylko że z większą ilością kwadratów. Dajmy na to na wyświetlaczu 320x240 mam wyświetloną klawiaturę od 0-9 to mam do przeszukania tylko 10 górnych narożników i ew. 3 dolne gdybym sobie przyjął takie jak wcześniej opisałem założenie. Problem w tym jak zwiększyć trafność w ramach tych pierwszych dziesięciu przeszukań aby nie robić tego jak małpa od poczatku do końca.
  • Pomocny post
    #13 8475665
    Konto nie istnieje
    Konto nie istnieje  
  • #14 8475760
    rpal
    Poziom 27  
    Teraz zajarzylem, to niegłupie co napisałeś. Już pojąłem całą ideę tego zagadnienia.
REKLAMA