Wyzwanie dotyczy odczytu losowych linii z potencjalnie dużego pliku bez wczytywania całego pliku do pamięci.
Wejście
Liczba całkowita n
i nazwa pliku tekstowego.
Wynik
n
wiersze pliku tekstowego wybrane losowo równomiernie bez zamiany.
Możesz założyć, że n
mieści się w zakresie od 1 do liczby linii w pliku.
Zachowaj ostrożność, próbkując n
losowo liczby z zakresu, w którym odpowiedź jest jednorodna. rand()%n
na przykład w C nie jest jednolity. Każdy wynik musi być równie prawdopodobny.
Zasady i ograniczenia
Każda linia pliku tekstowego będzie miała tę samą liczbę znaków i nie będzie więcej niż 80.
Twój kod nie może czytać żadnej zawartości pliku tekstowego, z wyjątkiem:
- Linie, które wyprowadza.
- Pierwszy wiersz, aby sprawdzić, ile znaków w wierszu znajduje się w pliku tekstowym.
Możemy założyć, że każdy znak w pliku tekstowym zajmuje dokładnie jeden bajt.
Zakłada się, że separatory linii mają długość 1 bajta. Rozwiązania mogą korzystać z 2-bajtowych separatorów długich linii tylko wtedy, gdy określają to. Możesz również założyć, że ostatnia linia jest zakończona separatorem linii.
Twoja odpowiedź powinna być kompletnym programem, ale możesz podać dane wejściowe w dowolny dogodny sposób.
Języki i biblioteki
Możesz użyć dowolnego języka lub biblioteki.
Notatki
Wystąpił problem z obliczeniem liczby linii w pliku. Jak oni wskazują w komentarzach, możesz wywnioskować to na podstawie rozmiaru pliku i liczby znaków w wierszu.
Motywacja
Na czacie niektórzy pytali, czy to naprawdę pytanie „Wykonaj X bez Y”. Tłumaczę to, aby zapytać, czy ograniczenia są niezwykle sztuczne.
Zadanie losowego próbkowania linii z dużych plików nie jest rzadkie i w rzeczywistości muszę je czasem wykonać. Jednym ze sposobów na to jest bash:
shuf -n <num-lines>
Jest to jednak bardzo wolne w przypadku dużych plików, ponieważ odczytuje się w całym pliku.
fseek
, a w innych niemożliwe. Ponadto, co jeślin
jest większa niż liczba linii w pliku?sum()
. Brak wczytywania pliku do pamięci jest wyraźnym i spójnym ograniczeniem, które nie jest w żaden sposób arbitralne. Można go przetestować z plikiem większym niż pamięć, którego nie można obejść z powodu różnic językowych. Zdarza się również, że ma zastosowania w świecie rzeczywistym (chociaż nie jest to konieczne w przypadku golfa ...).Odpowiedzi:
Dyalog APL , 63 bajty
Monituje o nazwę pliku, a następnie o liczbę pożądanych linii losowych.
Wyjaśnienie
⍞
Monituj o wprowadzenie tekstu (nazwa pliku)⎕NTIE 0
Przywiąż plik, używając następnego dostępnego numeru remisu (-1 w czystym systemie)t←
Zapisz wybrany numer remisu jakot
83 80,⍨
Dołącz [83,80], uzyskując [-1,83,80]⎕NREAD
Przeczytaj pierwsze 80 bajtów pliku -1 jako liczby całkowite 8-bitowe (kod konwersji 83)10⍳⍨
Znajdź indeks pierwszej liczby 10 (LF)l←
Zapisz długość linii jakol
(⎕NSIZE t)÷
Podziel rozmiar pliku -1 za pomocą długości linii⎕
Monit o wprowadzenie danych liczbowych (żądana liczba linii )?
X losowych wyborów (bez zamiany) pierwszych Y liczb naturalnych Y¯1+
Dodaj -1, aby uzyskać numery linii 0-początkowe *l×
Pomnóż przez długość linii, aby uzyskać bajty początkowet 82l∘,¨
Przyłóż [-1,82, Długość linii] do każdego bajtu początkowego (tworzy lista argumentów za⎕NREAD
)⎕NREAD¨
Czytaj każdy wiersz jako znak 8-bitowy (kod konwersji 82)Praktyczny przykład
Plik /tmp/records.txt zawiera:
Spraw, aby program RandLines zawierał powyższy kod dosłownie, wprowadzając następujące dane do sesji APL:
W typie sesji APL
RandLines
naciśnij klawisz Enter.System przesuwa kursor do następnego wiersza, który jest pytaniem o długość 0 dla danych znakowych; wchodzić
/tmp/records.txt
.System wysyła teraz dane wyjściowe
⎕:
i oczekuje na wprowadzenie numeryczne; wchodzić4
.System generuje cztery losowe linie.
Prawdziwe życie
W rzeczywistości możesz podać nazwę pliku i policzyć jako argumenty, a wynik otrzymać w postaci tabeli. Można to zrobić, wprowadzając:
Teraz sprawisz, że MyLines zawiera trzy losowe linie z:
A może zwrócisz tylko jedną losową linię, jeśli nie określono liczby:
Teraz możesz zrobić oba:
oraz (zauważ brak lewego argumentu):
Czytanie kodu
Jednoliniowe golfa APL to zły pomysł. Oto jak napisałbym w systemie produkcyjnym:
* Mogę zapisać bajt uruchamiając w trybie 0 pochodzenia, co jest standardem w niektórych systemach APL: Wyjmij
¯1+
i włóż1+
wcześniej10
.źródło
Rubin,
104949290 bajtówNazwa pliku i liczba wierszy są przekazywane do wiersza poleceń. Na przykład, jeśli program ma
shuffle.rb
nazwę plikua.txt
, uruchomruby shuffle.rb a.txt 3
trzy losowe linie.-4 bajty od odkrycia
open
składni w Rubim zamiastFile.new
Oto 85-bajtowe rozwiązanie funkcji anonimowej, które jako argument przyjmuje ciąg i liczbę.
źródło
ruby shuffle.rb 3 < a.txt
daje widoczne stdin. Jednak IDK Ruby.Haskell,
240224236 bajtówOdczytuje nazwę pliku in ze standardowego wejścia.
Jak to działa:
Uruchomienie tego programu w przypadku plików z wieloma wierszami zajmuje dużo czasu i pamięci z powodu okropnej nieefektywności
shuffle
funkcji.Edycja: Brakowało mi części „losowo bez wymiany” (dziękuję @feersum za zauważenie!).
źródło
PowerShell v2 +, 209 bajtów
Pobiera dane wejściowe
$a
jako nazwę pliku i$n
liczbę wierszy. Zauważ, że$a
musi to być pełna ścieżka pliku i zakłada się, że jest to kodowanie ANSI.Następnie konstruujemy nowy
FileStream
obiekt i mówimy mu, aby uzyskał dostęp do pliku za$a
pomocąOpen
uprawnieniami.for
Pętla.Read()
s przez pierwszą linię, aż trafiliśmy na\n
charakter, zwiększając nasz licznik linia długości każdego znaku. Następnie ustawiamy$t
równy rozmiar pliku (tj. Długość strumienia) podzielony przez liczbę znaków w wierszu (plus jeden, więc zlicza terminator), minus jeden (ponieważ mamy indeksowane zero). Następnie budujemy nasz bufor$z
aby był również długością linii.Ostatnia linia konstruuje tablicę dynamiczną z
..
operatorem zakresu. 1 rura takim, że matryca doGet-Random
z-C
ount z$n
losowo wybierać$n
numery linii bez powtarzania. Szczęśliwe liczby są połączone w pętlę z|%{...}
. Każdą iterację przechodzimy.Seek
do określonej lokalizacji, a następnie.Read
w postaci znaków zapisanych w linii$z
. Przerzucamy ponownie$z
jako tablicę-join
znaków i razem, pozostawiając wynikowy ciąg w potoku, a dane wyjściowe są niejawne na końcu programu.Technicznie powinniśmy zakończyć
$f.Close()
wezwaniem do zamknięcia pliku, ale to kosztuje bajty! : pPrzykład
1 Technicznie oznacza to, że możemy obsłużyć maksymalnie 50 000 linii, ponieważ jest to największy zakres, który można dynamicznie utworzyć w ten sposób. : - / Ale nie możemy po prostu zapętlić czasów
Get-Random
poleceń$n
, odrzucając duplikaty każdej pętli, ponieważ nie jest to deterministyczne ...źródło
Python 3,
146139 bajtówDane wejściowe: [nazwa pliku] \ n [wiersze] \ n
To rozwiązanie mocno ukradło z @pppery, ale
jest tylkopython3.5ijest kompletnym programem.Edycja: Dzięki @Mego za zakres wbudowany i kompatybilność z python3.x. Edycja2: Wyjaśnienie, gdzie jest wydruk, ponieważ otrzymałem dwa komentarze na jego temat. (Komentarz oczywiście nie jest częścią kodu ani liczby bajtów).
źródło
r=range(f.seek(0,2)//l)
zadziała, co zrzuca 3 bajty i eliminuje potrzebę 3.5. Co więcej, zmniejsz liczbę kolejnych 3 bajtów, umieszczającrange
połączenie wsample
połączeniu. Ponadto nie jest to kompletny program - musisz wydrukować listę.r=[*range(f.seek(0,2)//l)]
ponieważ myślałem, że nie mogęsample
generatora. Okazuje się, że mogłem. @Mega: Jest kompletny, ponieważ wypisuje wszystkie wiersze wewnątrz listyprint(f.read(l))
Lua,
126122Wykorzystuje 2 bajty do podziału linii. Zmień 2 na 1 dla 1. Mam go tylko jako 2, ponieważ taki był mój plik testowy.
Znalazłem się pod wpisem PHP, ale nadal 2 miejsce (obecnie). Przeklnij, Ruby, wejdź!
źródło
Bash (cóż, coreutils), 100 bajtów
Wyjaśnienie
Pozwala to uniknąć odczytu całego pliku przy użyciu
dd
do wyodrębnienia potrzebnych fragmentów pliku bez odczytu pliku, niestety kończy się dość duży ze wszystkimi opcjami, które musimy określić:if
to plik wejściowybs
to rozmiar bloku (tutaj ustawiamy, do$n
którego jest długość pierwszego wierszaskip
ustawiana na losowe liczby całkowite wyodrębnione zshuf
i jest równaibs
wartości pomijającejskip
*ibs
bajtówcount
liczbęibs
odcinków długości do zwróceniastatus=none
jest potrzebna do usunięcia informacje zwykle wysyłane przezdd
Otrzymujemy długość linii za pomocą
head -1 $2|wc -c
i rozmiar pliku za pomocąstat -c%s $2
.Stosowanie
Zapisz powyżej jako
file.sh
i uruchom przy użyciufile.sh n filename
.Czasy
vs.
Razy powyżej dla pliku 68 MB wygenerowanego przy użyciu
seq 1000000 9999999 > test.txt
.Dzięki @PeterCordes za jego wskazówkę -1!
źródło
bs=
zamiast tegoibs=
, ponieważ ustawienieobs
również jest w porządku. Chyba nie można zastąpićif=$2
z<$2
chociaż, ponieważ jest to nadalxargs
jest linia poleceń.\<$2
też nie działa (xargs używa exec bezpośrednio, bez powłoki).2>&-
, więc nie ma niebezpieczeństwa, że dane wyjściowe będą nigdzie (np. jeśli stdin będzie deskryptorem pliku do odczytu i zapisu). Działa z GNUdd
: Nadal produkuje swójstdout
przed próbą i bez zapisu dostderr
.Python 3 -
161 160149 bajtówTen kod definiuje funkcję, która jest wywoływana jak
f(10,'input.txt')
źródło
C # 259 bajtów bez duplikatów
Nie golfił
File.ReadLines jest leniwy. Ma to dodatkową zaletę, że wszystkie linie mogą mieć różną długość.
Uruchomienie byłoby:
C # 206 bajtów z duplikatami
Nie golfił
źródło
Python (141 bajtów)
Utrzymuje każdą linię z jednakowym prawdopodobieństwem, użyj również z rurami. Nie odpowiada to jednak ograniczeniu pytania z wyprzedzeniem ...
Zastosowanie
cat largefile | python randxlines.py 100
lubpython randxlines 100 < largefile
(jak wskazano @petercordes)źródło
python ./randxlines.py 100 < largefile
przydałoby się jednak dla poprawnej odpowiedzi: w takim przypadkustdin
będzie widoczne.