-
Data: 2012-12-19 21:38:56
Temat: Re: Potyczki
Od: "slawek" <s...@h...pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]
Użytkownik "M.M." <m...@g...com> napisał w wiadomości grup
dyskusyjnych:cbc6eb9c-b9e3-4cdd-aeba-1d0d569e74c3@go
oglegroups.com...
> Pamięci nie ma, więc trzeba posortować na dysku. Plik posortowany miałby
> rozmiar plik_wejsciowy * dlugosc_podciagu. Nie wiem na ile to będzie
Owszem, ale przecież można trzymać tylko coś
(tablicę/listę/drzewo/korkociąg) uchwytów/wskaźników/adresów do ciągów.
Dla 1 GiB = 2^30 bajtów powinno to być nie więcej niż 2^30 wskaźników, czyli
czterobajtowe i będzie tego cztery razy mniej (bo ciągi były jak pamiętam 16
bajtowe).
Ogólniej - "brute force" to będzie tak jak piszesz. Wic w tym, żeby znaleźć
jakieś genijalne rozwiązanie... może wystarczy tego na magisterkę z
informatyki, a może nawet na Nobla.
> A jakby tak po prostu wczytać tyle danych ile się zmieści do RAM. Potem
> wczytywać dane z pliku i wybrać najczęściej powtarzający się element?
A jak wszystkie sekwencje będą unikalne? Jest 2^(16*8) unikalnych sekwencji
16-bajtowych (tj. oktetowych?!), a to jest 2^128 > 10^36 możliwości. Masz
jakieś 10^20 GiB RAM?
> Fajne zadanie, szkoda że mam tyle klepatologii stosowanej i nie
> mam na nic czasu, byśmy zrobili benchmark.
Fajne zadanie. A przyszło mi w kontekście szperania po np. logach - chcemy
wyłapać coś, co pojawia się częściej niż statystycznie uzasadnione. Ok,
dlaczego akurat 16 bajtów? No bo przecież jak potrafimy dla 16-tu, to i dla
15-tu, 14-tu. A przy 16 bajtach to się pewnie da załapać nagłówki TCP itp.
itd.
Jak to się dzieje, że mózgownica łapie deja vu, że łapiemy się na czytaniu
tego samego cytatu drugi raz? To też tak w kontekście. (Ok, mamy masywne
przetwarzanie równoległe w galaretce zwanej mózgiem.)
> (w zadaniu nic
> nie ma o tym, czy mamy dodatkową pamięć dyskową).
Mamy, nie mamy, ... bez znaczenia. Załóżmy - mamy! Tzn. dysk twardy 1 GB to
mniej niż tydzień pracy informatyka, więc chyba lepiej kupić dysk, niż
męczyć się nad problemem dodatkowy tydzień?! Z drugiej strony... kusi aby
nie kupować, bo może program ma chodzić na paru milionach smartfonów (a te
nie mają HDD)?
Zadanko jest abstrakcyjno/teoretycznie - miało nie tyle "być rozwiązane" -
ale ilustrować, co ja rozumiem za problem informatyczny. Tj. nie
matematyczny, nie fizyczny, chemiczny czy humanistyczny... ale właśnie
informatyczny.
Za rozwiązanie nie przewiduję nagród.
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-03-15 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-15 Wrocław => Konsultant wdrożeniowy Comarch XL (Logistyka, WMS, Produk
- 2025-03-15 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-03-15 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+ experience) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+) <=
- 2025-03-15 KOMU w RP3 pasuje "Rumuńska łatwość gmerania w wyborach" i dlaczego nie PO-Trzaskanym?
- 2025-03-15 China-Kraków => Key Account Manager IT <=
- 2025-03-14 Spalił się autobus :-)
- 2025-03-14 Policjanci z Piątku
- 2025-03-14 Lublin => JavaScript / Node / Fullstack Developer <=
- 2025-03-14 Warszawa => Account Manager - Sprzedaż Usług Rekrutacyjnych <=
- 2025-03-14 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-03-14 VAT-R Umowa najmu na adres zamieszkania
- 2025-03-14 Gliwice => IT Expert (Network Systems area) <=