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.