834 NAMES - Imiona

[maciek0414]

Witam, mam problem z zadaniem http://pl.spoj.com/problems/NAMES/
Mój algorytm, mimo długiej walki, wciąż przekracza limit czasu...

Macie może jakiś pomysł jak usprawnić ten program bez gruntownej przebudowy?
http://ideone.com/jxHUWo

[tarpauwatratar]

Nie wiem co rozumiesz przez gruntowną przebudowę, ale po kolei zrobiłbym tak:

1) wywaliłbym sort bąbelkowy - prawie na pewno nie przejdzie
2) wywaliłbym quicksorta (std::sort jest zoptymalizowany)
3) wywaliłbym vector

[maciek0414]

a co byś wstawił za vector i czy mógłbyś proszę w kilku słowach napisać czemu vector tu nie pasuje?

[tarpauwatratar]

Ja użyłem zwykłych tablic.

Nie chodzi o to, że vector jest zły bo jego użycie w szeroko rozumianym programowaniu jest jak najbardziej zalecane. Problem polega na tym, że na SPOJu liczy się czas. Vector jest pod wieloma względami wygodniejszy od tablic, ale za wygodę płaci się czasem wykonywania programu. W praktyce życiowej różnica jest pomijalna, podobnie jak np. w przypadku smart pointerów, a wygoda niesamowita. Na SPOJu taka milisekundowa różnica może być kluczowa przy dużej liczbie testów, choć nie jest to (chyba) obecnie bardzo częste zjawisko.

Vector usuń na samym końcu, jeżeli 1) i 2) nie pomogą.

[narbej]

Wydaje mi się, że TLE jest z powodu [za]wolnego dodawania imion - przeglądanie za każdym razem wszystkich wprowadzonych dotychczas imion. Dlatego Inne zmiany [zaproponowane powyżej] mogą nie wpłynąć aż w takim stopniu, aby przeskoczyć tle. Poprawią one oczywiście czas z np 1.43 na 0.43 ale w tej chwili musisz chyba przede wszystkim zmmienić [drastycznie przyśpieszyć] sposób wprowadzania imion - nie chodzi o wczytywanie - i może tylko taka poprawka pozwoli uzyskać AC?.

[maciek0414]

W końcu SPOJ przyjął rozwiązanie!

Wielkie dzięki za podpowiedzi ^^

Jakbyście byli ciekawi to zamienienie sortu bąbelkowego i quicksortu na std::sort nie wystarczyło, na chwilę wywaliłem vector ale dalej był za wolny. Zaliczyło dopiero jak przemyślałem sposób liczenia powtórzeń i zamiast właśnie przeglądać wszystkie imiona za każdym razem, zrobiłem najpierw sortowanie alfabetyczne (razem z powtórkami), potem podliczenie powtórzeń i usunięcie nadmiarowych imion, następnie sortowanie ze względu na ilość powtórzeń, a na końcu jeszcze jakby "dosortowanie" alfabetyczne imion z tyloma samymi powtórzeniami (myślałem, że obejdzie się bez tego ostatniego sortowania ale wywalało błędną odpowiedź).
Jeszcze raz dziękuję

[narbej]

std::sort

• drugie sortowanie --> std::stable_sort: http://www.cplusplus.com/reference/algorithm/stable_sort/
  i wtedy trzecie sort nie jest potrzebne.

[marek_antoni]

Cześć

W jaki sposób jest sygnalizowany koniec danych wejściowych? Ponieważ muszę mieć ich komplet, aby następnie prawidłowo je posortować. Mogę założyć, że po wypisaniu wszystkich linii na wejście będzie podana pusta linia, bądź jakiś inny znak niż cyfra?

[yula]

nic nie możesz zakładać. Masz pobierać dane dopóki są na wejściu. Takich zadań z nie określoną ilością danych na wejściu

[marek_antoni]

OK. Dzięki za odpowiedź. Natomiast skąd program ma wiedzieć, że dane się skończyły? Można zaimplementować timer, który przejdzie do dalszej realizacji instrukcji, jeżeli dane nie napłyną w jakimś określonym ułamku sekundy, ale to chyba nie tak powinno działać?

[narbej]

EOF <-- google search is your friend

[marek_antoni]

Dziękuję za podpowiedzi.

Napisałem ten kod, co nie było łatwe. Limit nałożony na czas wydaje mi się absurdalnie krótki. Czy to nie jest tak, że sędzia sprawdza sposób wykonania zadania, a nie sam wynik? Napisałem ten kod w dwojaki sposób z użyciem hashTable i bez niego. Przygotowałem plik, w którym jest 100 000 pozycji i 100 różnych imion do posortowania. Na wyjściu pojawia się posortowanych 100 imion po 1000 wystąpień każde. Poniżej czasy wykonania w sekundach:

z użyciem HashTable:
Total time: 0.108
Input time: 0.065
Sort time: 0.043

bez użycia HashTable
Total time: 0.142
Input time: 0.103
Sort time: 0.039

Total time to całkowity czas wykonania, ponadto są tam timery liczące ile trwa wczytywanie danych, a ile sortowanie. Oczywiście na mojej maszynie, na Ideone chyba nie ma takiej możliwości, aby wstawić tak wielki plik wejściowy. Jeden kod jest akceptowany przez sędziego, a drugi nie - ze względu na czas wykonania, nie na wynik. Naprawdę chodzi tylko o czas?

[narbej]

Ciekawe który kod przechodzi? Mam tu swojego czarnego konia, ale może zdradzisz, tą słodką tajemnicę i rzucisz trochę światła?

W zadaniach chodzi autorom przede wszystkim i najczęściej o pomysł (algorytm) na rozwiązanie zadania. W tym zadaniu limit czasu, to jak na warunki SPOJA, wieczność - ponad sekunda. A czas jest często śrubowany właśnie po to by byle jaki pomysł nie miał racji bytu.

Czy potrafisz policzyć ile może być różnych imion w tym zadaniu? Czy zaledwie 100 (słownie: sto) to nie za wielki optymizm?

[marek_antoni]

Jasne. Załączam dwa pliki z odpowiednim kodem.

PS. Różnych imion może być 100 000, ale zastosowałem dobry algorytm sortowania, to nie jest sortowanie bąbelkowe

Edit: pliki już usunąłem, żeby nie wisiały tutaj za długo.