Witam , mam zadanie do wykonania, który ma wyszukiwać podane przeze mnie liczby i wypisywać ile jest ich w podanym ciągu. Przykład podaje do wyszukania liczby 1 2 1 4 i teraz wpisuje jakie liczby program ma sprawdzić np dla liczb: 5 4 3 1 program pokaże wyjście: 0 1 0 2. Chodzi mi teraz o to jaki algorytm mam zastosować, by wyszukiwanie to było jak najbardziej efektowne. Wiem jak zrobić coś takiego tylko dla jednej liczby, ale tutaj wyszukiwać ma wszystkie od razu.
0
0
Klasyczne zliczanie. Zależnie od zakresu danych użyj tablicy albo mapy. Niech indeksem/kluczem będzie dana liczba a wartością ilość wystąpień. W pythonie (żeby nie było że daje ci gotowca :P) wyglądałoby to tak:
from collections import defaultdict
counting = defaultdict(int)
input = [1,2,1,4]
for number in input:
counting[number]+=1
searched = [5,4,3,1]
for number in searched:
print(counting[number])
efektowne może to nie jest, ale jest efektywne bo działa w czasie O(n)
0
No ok jest rozwiązanie, ale jeśli da radę możesz zapisać to w C++? Bo Pythona niestety nie znam zbyt dobrze. A wyszukiwanie miało być efektywne, mój błąd.
0
Przecież Shalomowi nie chodziło o danie gotowca tylko o przykład jak to rozwiązać.
Pythona czyta się prawie jak pseudokod, więc nawet go nie znając nie powinieneś mieć problemu ze zrozumieniem (no, ew. defaultdict).
Żeby nie było że niekonstruktywnie, kod Shaloma zapisany w pseudokodzie (sam nie wiem co to za pythojava :P):
counting = map()
# map, czyli w pythonie dict, w javie Map<K, V> - powiązanie kluczy z wartościami.
# Alternatywnie jeśli liczby są ze znanego przedziału (np. 0-100), szybsza będzie tablica
# jeśli nie wiesz jak działa mapa to hm, poszukaj. Przykładowy art to np. http://java67.blogspot.com/2013/02/10-examples-of-hashmap-in-java-programming-tutorial.html (pierwszy z brzegu)
input = [1,2,1,4]
foreach (number in input): # dla każdej liczby na wejściu...
if (!counting.contains(number)):
counting[number] = 0 # (jeśli pojawia się pierwszy raz, ustawiamy jej zero pojawień się)
counting[number]+=1 # ...zwiększamy odpowiadającą jej wartość w mapie
searched = [5,4,3,1]
foreach (number in searched):
if (conting.contains(number)):
print (counting[number])
else: # jeśli szukana liczba się nie pojawiła ani razu to mamy specjalny przypadek
print 0
0
Ja bym to inaczej zrobił, bo zakładam że liczb może być miliony, jak nawet nie miliardy. Rozwiązania które podaliście, wbrew pozoru nie równa się czasowi: O(n) . Języki które podaliście, są językami wyższego poziomu, ale i tak są tłumaczone na najniższy.
Dlatego też odwołanie się do
zmienna[jakisIndex] , to też wyszukiwanie, bo komputer musi wiedzieć o którą część pamięci chodzi, tak więc myślę że kod maszynowy Pythona, musi wyszukać pointera do pamięci spośród wszystkich kluczy jakie są możliwe (czyli gdzieś w pamięci jest tablica z indexami tej tablicy asocjacyjnej, w CPU najpierw wyszukuje tego indexu w tej tablicy, następnie jeśli index był na 5 miejscu, to jest kolejna tablica z pointerami do pamięci , czyli w prostym rozumieniu:
$tablica['dupa'] = 52;
$tablica['dupa2'] = 52;
$tablica['dupa3'] = 5213
//jest jednoznaczne w z :
string klucze[3] = {'dupa', 'dupa2', 'dupa3'};
int wartosci = {52, 52, 5213};
// i takie odwołanie
echo $tablica['dupa']
//jest rownoznaczne z
int index = wyszukajWTablicy(klucze, 'dupa');
return wartosci[index]
C++ też nie ma w najniższym poziomie tablic asocjacyjnych -> są biblioteki map, które bazują na tym najniższym poziomie, czyli pętlach i ifach. A to tylko po to, by programista programował, a nie bawił się w rzeczy, które są łatwe, i są teoretycznie kardzeijami czasu.
Dlatego też moje rozwiązanie to standardowe wyszukiwanie połówkowe.
Zakładam że dane są statyczne, ale wejście jest dynamiczne, więc najpierw co zrobić trzeba by było, to machnąć tą tablicę quickSortem, następnie poprzez wyszukiwanie połówkowe znaleźć index na tą liczbę, i sprawdzać sąsiadów tej liczby, czy nie są takie same, aby znaleźć początek liczb takich samych:
int twojZnalezionyIndex;
int liczbaWyszukiwana;
int[] tablica;
while(tablica[twojZnalezionyIndex - 1] == liczbaWyszukiwana){
twojZnalezionyIndex--;
}
W ten sposób znajdzie się początek zapisu wyszukiwanych liczb. A później tylko liczysz:
int suma = 0;
while(tablica[twojZnalezionyIndex] == liczbaWyszukiwana){
suma++;
twojZnalezionyIndex++;
}
Reasumując mój wywód:
Jako to że masz do dyspozycji wysoki język , nie oznacza tego, że można od razu powiedzieć że złożoność algorytmu to O(n). Bo jeśli by tak było, to każdy algorytm będzie mieć taki czas złożoności, bo napiszę sobie własny język, własny kompilator, gdzie sobie zrobię gotową funkcję :
wynik = wyszukajWTablicyIZwrocTabliceIlosciPowtorzen (tablicaWejsciowa, tablicaZLiczbamiDoWyszukiwan)
3
Ja bym to inaczej zrobił, bo zakładam że liczb może być miliony, jak nawet nie miliardy. Rozwiązania które podaliście, wbrew pozoru nie równa się czasowi: O(n) . Języki które podaliście, są językami wyższego poziomu, ale i tak są tłumaczone na najniższy.
Ale to nie tak. Zakładasz że odwołanie się zajmuje O(n), a to oczywiście nieprawda. W praktyce hashtable albo drzewo (jako że mowa o javie, zależnie od implementacji interfejsu).
Odwołanie się zmienna[jakisIndex] jak najbardziej może być O(1) - http://en.wikipedia.org/wiki/Cuckoo_hashing (i z tego co pamiętam wstawianie zamortyzowane O(1) ).
Dla drzewa byłoby O(log(n)), O(log(n))
C++ też nie ma w najniższym poziomie tablic asocjacyjnych -> są biblioteki map, które bazują na tym najniższym poziomie, czyli pętlach i ifach. A to tylko po to, by programista programował, a nie bawił się w rzeczy, które są łatwe, i są teoretycznie kardzeijami czasu.
Myślałem że zadaniem programisty jest rozwiązywanie problemów, a nie programowanie dla programowania ;). Jeśli kod będzie za wolny, programista go przyśpieszy (o ile będzie umiał/wiedział co jest problemem, to inna sprawa). Sugerowanie nieużywania map/słowników jest... dziwne.
Zakładam że dane są statyczne, ale wejście jest dynamiczne, więc najpierw co zrobić trzeba by było, to machnąć tą tablicę quickSortem, następnie poprzez wyszukiwanie połówkowe znaleźć index na tą liczbę, i sprawdzać sąsiadów tej liczby, czy nie są takie same, aby znaleźć początek liczb takich samych
Nie rozumiem, czyli masz O(n log n) (albo pesymistyczne n^2 przy klasycznym quicksorcie :P) przetwarzania danych oraz O(log n) O(n) sprawdzania (takich samych liczb może być O(n)) - wcale nie lepsze gorsze od drzewa/hashtable, i prawdopodobnie z gorszą stałą.
Ogólnie często piszesz mądrze, ale moim zdaniem nie popisałeś się teraz ;).
PS. Pewnym przyśpieszeniem byłoby użycie tablicy, ale to jest do zastosowania jedynie liczby są z (relatywnie) małego przedziału.
0
Ogólnie często piszesz mądrze,
zdaje się ci. Czasem coś uda mi się ciekawego skopiować z googla, to może dlatego :)
Ale podałem przykład jak ja bym to zrobił zakładając dużą skalę liczb, dużo liczb, i analizowanie danych więcej niż 1 raz. Chętnie zobaczę pomysły na optymalniejsze rozwiązania. Mój jest dobry, jeśli masz pracować na tych danych przez dłuższy czas, a nie jedno razowo - bo wtedy bez sensu jest sortować tablicę dla 1 wyszukiwania.
Z tym cuckoo hashing, to bardzo ciekawa sprawa. Znów się czegoś dowiedziałem, dlatego lubie poruszać takie tematy :)
1
Dlatego też odwołanie się do
zmienna[jakisIndex] , to też wyszukiwanie, bo komputer musi wiedzieć o którą część pamięci chodzi, tak więc myślę że kod maszynowy Pythona, musi wyszukać pointera do pamięci spośród wszystkich kluczy jakie są możliwe
Wyszukiwanie w mapie to O(lgN), a nie O(N).
Cały algorytm działa więc w czasie O(N*lgN).
Jeżeli liczby do wyszukania możemy wczytać przed ciągiem w którym wyszukujemy, to możemy osiągnąć koszt O(N + M * lg M) i koszt pamięciowy O(M*lgM), gdzie N - długość ciągu, w którym wyszukujemy i M - długość ciągu wyszukiwanego.
Zrobi to dużą różnicę, gdy M będzie dużo mniejsze niż N.
Btw - co to ma wspólnego z Javą?
0
Dobra, z tego co widzę zapomniałem ująć najważniejszego w pierwszym poście, złożoność ma być logarytmiczna, nie liniowa.
0
Złożoność nie może być logarytmiczna, gdyż potrzebujesz O(n) aby wczytać dane wejściowe (np. z pliku).
0
W zadaniu , które dostałem złożoność ma być logarytmiczna , a do tego mam limit rozmiaru pliku w postaci 1 kb.
0
Potrzebny jest Ci licznik. Najprostszy i najwygodniejszy jaki znam to kontener bazujący na HashMap<K, Integer>, gdzie klucz K może być dowolnym typem obiektów do wyszukania - w Twoim wypadku to będzie Integer, a typem wartości koniecznie jakaś wartość numeryczna, czyli dla dużych liczników również Integer. :)
Taki kontener potrzebuje mieć dwie najważniejsze metody:
- wstawianie polegające najpierw na operacji get, która wyciągnie informację czy obiekt jest już obecny w mapie. Jeżeli nie istnieje, to wstawi go do mapy i nada mu wartość 1, a jeżeli istnieje, to wyciągnie obecną wartość w mapie i wstawi z powrotem po zwiększeniu o 1.
- wyciąganie wartości, które będzie niczym innym jak prostą operacją get uzupełnioną o zwracanie wyniku 0 w przypadku gdy obiektu w mapie nie ma.
Dzięki temu prosta pętla w której będziesz wstawiał do takiego licznika każdy nadchodzący element policzy Ci wszystko szybko i z bardzo małym użyciem pamięci bo tablica haszująca zawiera w zasadzie tylko elementy znalezione. Funkcja haszująca dla liczb całkowitych jest idealna, więc i efektywność takiej mapy jest najwyższa z możliwych (niemal brak kolizji dla odpowiednio dużego rozmiaru mapy).
Na koniec po prostu przeiterujesz wszystkie sprawdzane elementy w mapie i otrzymasz liczniki występowania każdego z nich.
Żeby nie teoretyzować masz tu przykład implementacji takiego licznika. Ten tu oparty jest na innym kontenerze haszującym niż standardowy (i skrócony), ale implementacje podstawowych metod nie zmienią się po zmianie na standardową HashMap:
public class HashCounterBox<E> implements CounterBox<E>
{
public HashCounterBox() { this.map = new HashMapBox<>(); }
//...
/**
* Dodaje element do zbioru. Jeżeli element istniał, to nie jest dodawany,
* lecz zwiększany jest jego licznik o 1.
* @param element element zbioru
* @return wartość bieżącego zbioru do łatwiejszego użycia
*/
@Override public HashCounterBox<E> insert(E element)
{
Integer value = map.get(element);
if(value == null)
value = 0;
map.put(element, value + 1);
return this;
}
/**
* Zmniejsza licznik elementu o 1 lub jeżeli wynosił on 1, to element jest
* ze zbioru usuwany (liczba wyniesie 0). Jeżeli w zbiorze nie ma
* elementu, to metoda ta nie robi nic.
* @param element element zbioru
* @return wartość bieżącego obiektu dla łatwiejszego użycia
*/
@Override public HashCounterBox<E> remove(E element)
{
final int howMany = this.howMany(element);
if(howMany > 1)
map.put(element, howMany - 1);
else if(howMany == 1)
map.remove(element);
return this;
}
/**
* Zwraca ilość wstawień do zbioru podanego elementu.
* @param element sprawdzany element
* @return ilość wstawień elementów lub 0
*/
public int howMany(E element)
{
Integer howMany = map.get(element);
if(howMany == null)
return 0;
return howMany;
}
private final HashMapBox<E, Integer> map; //MapBox
}
Gdzie się da jest używany autoboxing, więc Integer i int są przemieszane ze sobą.
A tu przykładowe wykorzystanie:
final List<Integer> forCount = ...; //twoje liczby do wyszukania
final List<Integer> source =...; //ciąg liczb do przeszukania
final CounterBox<Integer> counter = new HashCounterBox<>();
for(Integer next: source)
counter.insert(next); //wstawia do licznika wszystko jak leci
//...
for(Integer check: forCount) //wypisuje tylko ilości szukanych
System.out.print(counter.howMany(check) + " ");
ps. Dzięki Patrykowi znowu przypomniałem sobie, żeby na ostatnią chwilę nie robić jak małpa tego co proponuje IDE. :)