Eine (oder n) zufaellige Zeilen einer Datei extrahieren (aka. Zeilen einer Datei mischen)

[Meillo]

Hoi,

tobo hat mich mit seinem q-Alias (viewtopic.php?p=1258455#1258455) wieder einmal auf das Thema gebracht: Wie extrahiere ich in der Shell eine oder mehrere zufaellige Zeilen bzw. mische ich alle Zeilen durch?

Bisher verwende ich dafuer das Idiom:

1. Zeilen mischen
2. Erste n Zeilen extrahieren

Umgesetzt typischerweise so:

Code: Alles auswählen

... | sort -R | sed 5q

(Die `5' durch die gewuenschte Anzahl ersetzen.)

Der Vorteil: Ich kann es in eine Pipeline einbauen, weil die Zeilen nur einmal gelesen werden muessen. Und ich kann eine beliebige Anzahl von zufaelligen Zeilen extrahieren.

Der Nachteil: Es muessen alle Zeilen gepuffert werden.


Alternativ kann man shuf(1) verwenden:

Code: Alles auswählen

... | shuf -n 5

Bei grossen Datenmengen scheint shuf(1) deutlich schneller zu sein als sort(1).


Sowohl `sort -R' als auch `shuf' gibt es auch auf einem modernen FreeBSD. Aeltere Systeme, wie ein SunOS 5.10, das ich zur Hand habe, kennt keines davon. POSIX sind sie auch beide unbekannt.


Ich frage mich nun: Wie macht man es am besten in POSIX-kompatibler Weise? (Und so, dass man es in eine Pipeline einbauen kann?)

Habt ihr Ideen?



P.S.
Vielleicht sollte ich dazu https://en.wikipedia.org/wiki/Reservoir_sampling in awk implementieren ... (r-Alias? )

[Meillo]

Hier haette ich (nach 1h rumprobieren) eine Umsetzung (die viel einfacher ist als dass ich 1h dafuer gebraucht haben sollte):

Code: Alles auswählen

... | awk 'BEGIN{srand()} {print rand() "\t" $0}' | sort | cut -f2-

Aber geht auch etwas ohne awk und mit welchem Ansatz koennte man das Problem noch loesen?

[eggy]

Mit wc Länge/Zeilenanzahl der Datei herausfinden, dann n random Werte aus dem Bereich auswählen, dann Zeilen seletieren.

Ich hätts aber auch immer mit "sort -R | head -n 5" (oder tail, sed ist bei sowas nicht mein Tool der Wahl) gemacht ... und wenn nen System kein sort -R hat, dann kompiliert man's eben fix selbst zusammen

[Meillo]

Mit wc Länge/Zeilenanzahl der Datei herausfinden, dann n random Werte aus dem Bereich auswählen, dann Zeilen seletieren.

Wie machst du das in einer Pipeline? Das braucht doch zwei Durchlaeufe: einmal zum Zeilenzaehlen und einmal zum Auswaehlen.

.. und wenn nen System kein sort -R hat, dann kompiliert man's eben fix selbst zusammen

Deine pragmatischen Vorschlaege lassen mich immer wieder spontan losprusten!

eggy = unverbesserlich!

[eggy]

In meiner Welt hat man Scripte oder Perfomanceprobleme, selten beides

Aber da gab's doch noch nen paar Tools, die sich vielleicht mit ganz viel Überredungskunst für solchen Unfug missbrauchen lassen.
Grundsätzlich, was bräuchte man denn, um das Problem lösen zu können?
Entweder zweimal einlesen (was hier wirklich der einfachste Fall wäre) oder die Sachen die auf das Script zukommen mal kurz wegspeichern.
Und dafür würde sich dann ja tee aufdrängen. Also Idee von vorher, erweitert um tee.

Ansatz zwei... hmm. Vielleicht hab ich Tomaten auf den Augen, oder es ist einfach schon spät (oder noch nicht spät genug) und ich seh es grade nicht, aber vermutlich gibts noch ne elegante Lösung via namedpipes und/oder ausreichend große Puffer. Muss ich mal nen Weilchen drüber nachdenken, wie man die Gleichzeitigkeit aufgelöst bekäme, die Aufgabenstellung ist jedenfalls interessant.

Inkrementell aussortieren geht jedenfalls zeilenweise auf den ersten Blick erstmal nicht, jedenfalls wäre dann die Gleichverteilung beim Zufall futsch.
Wäre das egal, hätt ich gesagt, wir bauen einfach n Buckets, und schubsen die Ergebnisse darein oder eben auch nicht. Und am Ende nimmt man was in den Eimern liegt als Ausgabe.
Problem dabei ist nur, am Ende sind die letzten n Werte mit ner jeweiligen Wahrscheinlichkeit von 0.5 ausgewählt, die ersten paar Werte hingegen ziemlich sicher nicht vertreten, hübscher Zufall ist anders.
Man müsste also ne Gewichtung an den Wert anbringen, die pro Durchlauf, d.h. nach n Zeilen, den Faktor immer weiter in immer größeren Schritten absenkt.
Kann man machen, wenn man die Formel richtig wählt, statistisch vermutlich sogar ok, aber trotzdem hässlich.
(Ok, es ist zu spät. Ich krieg das grad nicht ordentlich zu Ende gedacht, w_n+1=w_n/2 ?)
Vermutlich gibts bessere Wege ... und vermutlich steht das auch alles viel klüger auf der Wikipedia Seite, die Du verlinkt hast
(ich les das morgen mal in Ruhe, heute bleibt eh nix mehr hängen)

Nen netter Ansatz, den ich vorhin beim Spicken in der Infopage gefunden hatte, sollte sich auch relativ einfach umsetzen lassen.
"info coreutils sort invocation" sagt:

‘-R’
‘--random-sort’
‘--sort=random’
Sort by hashing the input keys and then sorting the hash values.
Choose the hash function at random, ensuring that it is free of
collisions so that differing keys have differing hash values. This
is like a random permutation of the inputs (*note shuf
invocation::), except that keys with the same value sort together.

If multiple random sort fields are specified, the same random hash
function is used for all fields. To use different random hash
functions for different fields, you can invoke ‘sort’ more than
once.

The choice of hash function is affected by the ‘--random-source’
option.

Im Grunde auch nicht viel anders als Deine Idee, nur eben reproduzierbar.
Dann bleibt nun nur die Frage, Posix gefällige Hashfunktion? Gibts da was schönes? md5 ist von '91, das dürfte zu Deiner Sun passen, sonst eben md4, das ist zwar nur unwesentlich älter (Wikipedia meint '90) könnt aber die zusätzlich nötigen paar Wochen (Monate? Jahre?) bringen

Und um wieder zu den pragmatischen Vorschlägen zurückzukommen:
vipe wäre auch noch ne (absurde und nicht regelkonforme) Idee: Input einfach nach vim schubsen und das Problem da lösen lassen

[Meillo]

Ich habe Reservoir Sampling jetzt implementiert:

Code: Alles auswählen

#!/bin/sh
# reservoir sample algorithm

size="${1:-1}"

awk -v size="$size" '

BEGIN{
        srand()
}

NR <= size {
        r[NR] = $0
}

NR > size {
        j = int(rand() * NR + 1)
        if (j <= size) {
                r[j] = $0
        }
}

END {
        for (i in r) {
                print r[i]
        }
}
'

Es waehlt $1 oder 1 zufaellige Zeilen von Stdin aus.

Allerdings erzeugt Reservoir Sampling nur eine zufaellig Menge, nicht zwangslaeufig auch eine zufaellige Reihenfolge. Die Grundfuellung (bei size>1) ist immer in der gleichen Reihenfolge, danach ist es gemischt. Im Fall von awk koennte man darauf hoffen, dass die Arrays Hashes sind und darum ihre Reihenfolge zufaellig ist: `for (i in r)' garantiert ja gerade *keine* Reihenfolge. Aber es ist auch keine Zufaelligkeit garantiert.


Ausserdem ist das Verfahren nicht geeignet, um alle Zeilen der Eingabe durchzumischen.

[Meillo]

@eggy: Dieses Thema ist natuerlich rein akademischer Natur.

Die Sun entspricht so ziemlich ueberhaupt nicht POSIX. Das ist nur ein weiteres Testsetup, das ich gerne nutze. md5 gibt es in POSIX nicht, nur cksum(1).