Tablice - korelacja

Problemy dotyczące programowania.

Moderatorzy: Moderatorzy, Administratorzy

gogi000
Użytkownik
Posty: 3
Rejestracja: 2016-02-27, 20:32

Tablice - korelacja

Post autor: gogi000 » 2016-02-27, 20:33

Witam. Mam pewien problem. Zadanie jest związane z korelacją. Zadanie polega na tym, że wprowadzam liczby z klawiatury do listy. Lista np { 2,3,4,5,6} i wprowadzam np drugą listę mniejszą od tej pierwszej np [4,5] . I ma wyglądać to tak:

{2,3,4,5,6}
{4,5} -> w pętli przesuwam tą tablice o krok w prawo

Funkcja ma zwracać indeks najlepszego dopasowania liczb.. Czyli w tym wypadku zwróci indeks 2 jeżeli liczę od zera.

Ktoś ma jakiś pomysł jak się za to zabrać?

Pajaczek
Użytkownik
Posty: 1439
Rejestracja: 2006-08-03, 13:16
Lokalizacja: Winny Gród

Re: Tablice - korelacja

Post autor: Pajaczek » 2016-02-27, 20:54

Jak duże mogą być te listy, co znaczy najlepsze dopasowanie? czy tych dopasowań może być więcej? i co w takiej sytuacji.
Jeżeli to ma być po prostu wyszukanie jednego ciągu w drugim, to poczytaj np. o algorytmie Knutha-Morrisa-Pratta.
Jeżeli dopasowanie może być mniej dosłowne to zdefiniuj na jakiej zasadzie chcesz określać odległość.

Ps. Oczywiście jeśli Twoje listy są relatywnie krótkie to może się nie opłacać cała zabawa, chyba że do celów szkoleniowych :twisted:

gogi000
Użytkownik
Posty: 3
Rejestracja: 2016-02-27, 20:32

Re: Tablice - korelacja

Post autor: gogi000 » 2016-02-27, 22:14

to ma działać tak długo aż tak lista mniejsza znajdzie taką samą wartość w tej większej liści i wtedy zwrócić indeks :
podaję jeszcze raz przykład bardziej opisany
wprowadzam pierwszą listę z klawiatury, która ma być sygnałem w formie liczb:
czyli np do tablicy wprowadzam takie liczby jak {1,2,3,4,5,6,7,8,9} i to jest moja pierwsza tablica.
następnie wprowadzam drugą tablice tylko, że krótszą od tej pierwszej bo to ma być ten sam sygnał tylko że przesunięty w czasie (korelacja)
czyli wprowadzam np {3,4} - gdzies te liczby musza sie pojawić w tej pierwszej tablicy bo to jest ten sam sygnał
no i teraz funkcja ma działać tak że zwróci mi indeks przesunięcia
przykład
{1,2,3,4,5,6,7,8,9}
{3,4}
porównuje 1,2 z 3,4 - nie zgadza się
przesunięcie
{1,2,3,4,5,6,7,8,9}
{3,4}
nie zgadza się
przesunięcie
{1,2,3,4,5,6,7,8,9}
{3,4}
zgadza i zwraca mi indeks tego przesunięcia czyli tam gdzie jest 3 w jednej i drugiej tablicy . Indeks będzie wynosił 2 bo 1 to indek zerowy 2 to indeks 1 , a 3 to indeks 2

Taka funkcja ma być uniwersalna nie zależnie ile wprowadze liczb do pierwszej tablicy i drugiej ( trzeba pamietać że ta tablica druga zawsze jest mniejsza)

Pajaczek
Użytkownik
Posty: 1439
Rejestracja: 2006-08-03, 13:16
Lokalizacja: Winny Gród

Re: Tablice - korelacja

Post autor: Pajaczek » 2016-02-27, 23:32

No to algorytm który Ci proponowałem nada się do tego świetnie i będzie w miarę szybki.
Co prawda jeżeli wzorzec (czyli Twoja druga tablica) jest w miarę krótki - kilka znaków - to można się pokusić o zrobienie tego naiwnie, czyli tak jak to zrobiłeś w opisie. I poradzi sobie z tym nawet początkujący programista. Jednak dla dużych zbiorów (wyszukanie wzorca co najmniej kilkuset znakowego, w zbierze kilku/kilkuset milionów obiektów) obliczenia mogły by już zajmować godziny.
Po Twoich pytaniach wnoszę, że raczej nie będą to złożone problemy. Poeksperymentuj, ale też poczytaj... jeżeli zrozumiesz algorytm to go zastosuj, jak nie to może dla Ciebie wystarczy metoda naiwna.

gogi000
Użytkownik
Posty: 3
Rejestracja: 2016-02-27, 20:32

Re: Tablice - korelacja

Post autor: gogi000 » 2016-02-28, 00:00

Ciąg krótszy jest zawsze wyciętą częścią ciągu dłuższego, ponieważ ciąg krótszy jest tym samym sygnałem tylko, przesuniętym w czasie.
Czyli nie zależnie jakie liczby dodam do tablicy dłuższej to jakaś ich część pojawi się w krótszej.
Czyli Np:
tab1 = {2,3,4,5,6,7}
tab2= {3,4} jeżeli tutaj są dwie liczby to porównuje z dwoma pierwszymi powyższej tablicy czyli z 3,4 z 2,3 ( 3,4 nie zgadza się z 2,3) . Więc teraz przesuwa 3,4 z małej tablicy o indeks w prawo i teraz patrzy czy 3,4 z małej tablicy = 3,4 z dużej tablicy . Tak zgadza się zwraca indeks czyli 1 bo są porównywane dwie liczby więc w dużej tablicy bieże pod uwagę 3 i 4 więc indeks tej 3 a trzy jest na indeksie 1.

lub
tab1={7,3,4,5,6}
tab2= { 4,5,6}
porównuje 4,5,6 z 7,3,4 ( nie zgadza się )
przesunięcie tab2 o jeden w prawo, czyli teraz porównuje 4,5,6 z 3,4,5 nie zgadza się , przesunięcie tab2 o jeden w prawo , porównuje 4,5,6 z 4,5,6 zgadza się zwraca indeks 2 bo 4,5,6 zaczyna się na indeksie 2 .
Zawsze bierzemy tą mniejszą tablice i przyrównujemy do tej większej . i patrzymy czy sie zgadza jak nie to mniejszą tabele przesuwamy w prawo tak długo aż znajdziemy to taką samą tablice jak mała tablica.

Liczby dużej tablicy moga być przypadkowe bo wprowadzam je z klawiatury , Natomiast liczby małej tablicy również wprowadzam z klawiatury lecz musze pamiętać ze musi być to ciąg liczb tak jak jest dodane do dużej tablicy.

tab1 = { 3,2,1,3,4,5,6,7,8,9,1}
tab2 = { 7,8,9,1}
Ciąg tab2 znajduje się w tab1 więc szukamy indeksu tab2 w tab1

Kod musi byc uniwersalny bo do do dużej tablicy moge sobie nawet wstawić 30 liczb lub więcej , a w małej musi być zawsze jedna mniej ponieważ musi być krótsza. Mniejsza tablica jest zawsze wycinkiem dłużesz i szukamy dla niej indeksu.

Pajaczek
Użytkownik
Posty: 1439
Rejestracja: 2006-08-03, 13:16
Lokalizacja: Winny Gród

Re: Tablice - korelacja

Post autor: Pajaczek » 2016-02-28, 12:28

No ja rozumiem, tylko nie bardzo rozumiem w czym masz jeszcze problem? Oczekujesz że ktoś to napisze za Ciebie? W pierwszym poście pytałeś o pomysł jak się za to zabrać, dlatego w ogóle wszedłem w tę dyskusję, ale jeśli Twoim pomysłem jest "napiszcie to za mnie" to sorry Winnetou. Pomysły rozwiązania masz powyżej co najmniej 2, z czego jeden właściwie sam przedstawiłeś.
Nawet 30 liczb i więcej mówisz... to nie jest żadna złożoność, chyba że tych wyszukiwań będziesz oczekiwał tysiące, setki tysięcy na sekundę. Ale to raczej nie przy ręcznym wprowadzaniu danych. Ja Ci mówiłem o komplikacji przy milionach danych wejściowych.
Jeśli masz jakieś problemy w implementacji pytaj, jeśli chodzi o naprowadzenie na rozwiązanie... pytaj. Jeśli szukasz gotowca... napisz ogłoszenie o płatnym zleceniu (kto wie, może ktoś Ci to nawet po dobroci zrobi za free, ale nie polegaj na tym założeniu).

Awatar użytkownika
webster
Użytkownik
Posty: 1265
Rejestracja: 2009-10-06, 11:58
Lokalizacja: Gdańsk
Kontakt:

Re: Tablice - korelacja

Post autor: webster » 2016-02-28, 17:40

Pajaczek pisze:No ja rozumiem, tylko nie bardzo rozumiem w czym masz jeszcze problem? Oczekujesz że ktoś to napisze za Ciebie? W pierwszym poście pytałeś o pomysł jak się za to zabrać, dlatego w ogóle wszedłem w tę dyskusję, ale jeśli Twoim pomysłem jest "napiszcie to za mnie" to sorry Winnetou. Pomysły rozwiązania masz powyżej co najmniej 2, z czego jeden właściwie sam przedstawiłeś.
Nawet 30 liczb i więcej mówisz... to nie jest żadna złożoność, chyba że tych wyszukiwań będziesz oczekiwał tysiące, setki tysięcy na sekundę. Ale to raczej nie przy ręcznym wprowadzaniu danych. Ja Ci mówiłem o komplikacji przy milionach danych wejściowych.
Jeśli masz jakieś problemy w implementacji pytaj, jeśli chodzi o naprowadzenie na rozwiązanie... pytaj. Jeśli szukasz gotowca... napisz ogłoszenie o płatnym zleceniu (kto wie, może ktoś Ci to nawet po dobroci zrobi za free, ale nie polegaj na tym założeniu).
Szkoda że nie ma tu "like", bo komentarz zasługuje :ok:
††† Chaos Of The Mirror - Valheru †††
††† I ♥ SlackWare RuLeZ †††

Slackware Poland FaceBook

ODPOWIEDZ