Ist das Leiten, Verschieben oder Erweitern von Parametern effizienter?

26

Ich versuche, den effizientesten Weg zu finden, um bestimmte Werte zu durchlaufen, bei denen es sich um eine konsistente Anzahl von Werten handelt, die in einer durch Leerzeichen getrennten Liste von Wörtern voneinander entfernt sind (ich möchte kein Array verwenden). Beispielsweise,

list="1 ant bat 5 cat dingo 6 emu fish 9 gecko hare 15 i j"

Ich möchte also in der Lage sein, nur die Liste zu durchlaufen und nur auf 1,5,6,9 und 15 zuzugreifen.

BEARBEITEN: Ich hätte klarstellen müssen, dass die Werte, die ich aus der Liste abrufen möchte, nicht im Format vom Rest der Liste abweichen müssen. Was sie besonders macht, ist allein ihre Position in der Liste (in diesem Fall Position 1,4,7 ...). Die Liste könnte also lauten,1 2 3 5 9 8 6 90 84 9 3 2 15 75 55aber ich möchte immer noch die gleichen Nummern. Außerdem möchte ich in der Lage sein, dies zu tun, vorausgesetzt, ich kenne die Länge der Liste nicht.

Die Methoden, an die ich bisher gedacht habe, sind:

Methode 1

set $list
found=false
find=9
count=1
while [ $count -lt $# ]; do
    if [ "${@:count:1}" -eq $find ]; then
    found=true
    break
    fi
    count=`expr $count + 3`
done

Methode 2

set list
found=false
find=9
while [ $# ne 0 ]; do
    if [ $1 -eq $find ]; then
    found=true
    break
    fi
    shift 3
done

Methode 3 Ich bin mir ziemlich sicher, dass Piping die schlechteste Option ist, aber ich habe aus Neugier versucht, eine Methode zu finden, bei der set nicht verwendet wird.

found=false
find=9
count=1
num=`echo $list | cut -d ' ' -f$count`
while [ -n "$num" ]; do
    if [ $num -eq $find ]; then
    found=true
    break
    fi
    count=`expr $count + 3`
    num=`echo $list | cut -d ' ' -f$count`
done

Was wäre also am effizientesten, oder fehlt mir eine einfachere Methode?

Levi Uzodike
quelle
10
Ich würde in erster Linie kein Shell-Skript verwenden, wenn Effizienz ein wichtiges Anliegen ist. Wie groß ist Ihre Liste, dass es einen Unterschied macht?
Barmar
6
Frühzeitige
2
Ohne Statistiken über tatsächliche Instanzen Ihres Problems zu erstellen, wissen Sie nichts. Dazu gehört der Vergleich mit "Programmieren in Arbeit" usw. Wenn Statistiken zu teuer sind, lohnt es sich wahrscheinlich nicht, nach Effizienz zu suchen.
David Tonhofer
2
Levi, was genau ist der "effiziente" Weg in Ihrer Definition? Sie möchten einen schnelleren Weg zum Iterieren finden?
Sergiy Kolodyazhnyy

Antworten:

18

Ziemlich einfach mit awk. Damit erhalten Sie den Wert jedes vierten Feldes für Eingaben beliebiger Länge:

$ awk -F' ' '{for( i=1;i<=NF;i+=3) { printf( "%s%s", $i, OFS ) }; printf( "\n" ) }' <<< $list
1 5 6 9 15

Dies funktioniert, indem Sie integrierte awkVariablen wie NF(die Anzahl der Felder im Datensatz) nutzen und einige einfache forSchleifen ausführen, um die Felder zu durchlaufen, um die gewünschten zu erhalten, ohne vorher wissen zu müssen, wie viele es geben wird.

Oder, wenn Sie in der Tat nur die in Ihrem Beispiel angegebenen Felder benötigen:

$ awk -F' ' '{ print $1, $4, $7, $10, $13 }' <<< $list
1 5 6 9 15

Bei der Frage nach der Effizienz ist es am einfachsten, diese oder jede Ihrer anderen Methoden zu testen und timezu zeigen, wie lange dies dauert. Sie können auch Tools verwenden, um stracezu sehen, wie die Systemaufrufe ablaufen. Verwendung von timesieht aus wie:

$ time ./script.sh

real    0m0.025s
user    0m0.004s
sys     0m0.008s

Sie können diese Ausgabe zwischen verschiedenen Methoden vergleichen, um festzustellen, welche zeitlich am effizientesten ist. Andere Tools können für andere Effizienzmetriken verwendet werden.

DopeGhoti
quelle
1
Guter Punkt, @MichaelHomer; Nebenbei habe ich die Frage "Wie kann ich feststellen, welche Methode die effizienteste ist ? "
DopeGhoti
2
@ LeviUzodike Bezüglich echovs <<<, "identisch" ist ein zu starkes Wort. Man könnte sagen, das stuff <<< "$list"ist fast identisch mit printf "%s\n" "$list" | stuff. In Bezug auf echovs printf,
leite
5
@ DopeGhoti Eigentlich schon. <<<fügt am Ende eine neue Zeile hinzu. Dies ist vergleichbar mit dem $()Entfernen eines Zeilenumbruchs vom Ende. Dies liegt daran, dass Zeilen durch Zeilenumbrüche abgeschlossen werden. <<<Füttert einen Ausdruck als Zeile, sodass er durch eine neue Zeile abgeschlossen werden muss. "$()"Nimmt Zeilen und stellt sie als Argument zur Verfügung, daher ist es sinnvoll, sie zu konvertieren, indem Sie den abschließenden Zeilenumbruch entfernen.
JoL
3
@ LeviUzodike awk ist ein viel zu wenig geschätztes Werkzeug. Es wird alle Arten von scheinbar komplexen Problemen leicht zu lösen machen. Besonders wenn Sie versuchen, einen komplexen regulären Ausdruck für etwas wie sed zu schreiben, können Sie oft Stunden sparen, indem Sie ihn prozedural in awk schreiben. Wenn Sie es lernen, profitieren Sie von hohen Dividenden.
Joe
1
@LeviUzodike: Ja, es awkhandelt sich um eine eigenständige Binärdatei, die gestartet werden muss. Im Gegensatz zu Perl oder speziell Python startet der awk-Interpreter schnell (immer noch der übliche dynamische Linker-Aufwand für einige Systemaufrufe, aber awk verwendet nur libc / libm und libdl. ZB stracezum Auschecken von Systemaufrufen beim awk-Start). . Viele Shells (wie Bash) sind ziemlich langsam, daher kann das Starten eines awk-Prozesses schneller sein als das Überlaufen von Tokens in einer Liste mit integrierten Shell-Funktionen, selbst bei kleinen Listengrößen. Und manchmal können Sie ein #!/usr/bin/awkSkript anstelle eines #!/bin/shSkripts schreiben .
Peter Cordes
35
  • Erste Regel der Softwareoptimierung: Nicht .

    Solange Sie nicht wissen, wie schnell das Programm ist, müssen Sie nicht darüber nachdenken, wie schnell es ist. Wenn Ihre Liste ungefähr so ​​lang oder nur ~ 100-1000 Elemente lang ist, werden Sie wahrscheinlich nicht einmal bemerken, wie lange es dauert. Es besteht die Möglichkeit, dass Sie mehr Zeit damit verbringen, über die Optimierung nachzudenken, als der Unterschied wäre.

  • Zweite Regel: Messen .

    Das ist der sichere Weg, um herauszufinden, und derjenige, der Antworten für Ihr System gibt. Besonders bei Muscheln gibt es so viele, und sie sind nicht alle identisch. Eine Antwort für eine Shell trifft möglicherweise nicht auf Ihre zu.

    In größeren Programmen gilt auch hier die Profilerstellung. Der langsamste Teil ist möglicherweise nicht der, von dem Sie glauben, dass er es ist.

  • Drittens die erste Regel der Shell-Skriptoptimierung: Verwenden Sie die Shell nicht .

    Ja wirklich. Viele Shells sind nicht besonders schnell (da das Starten externer Programme nicht unbedingt erforderlich ist) und analysieren die Zeilen des Quellcodes möglicherweise jedes Mal neu.

    Verwenden Sie stattdessen etwas wie awk oder Perl. In einem trivialen Mikro-Benchmark war ich awkbeim Ausführen einer einfachen Schleife (ohne E / A) Dutzende Male schneller als jede herkömmliche Shell.

    Wenn Sie jedoch die Shell verwenden, verwenden Sie die integrierten Funktionen der Shell anstelle von externen Befehlen. Hier verwenden Sie, exprwas nicht in Shells integriert ist, die ich auf meinem System gefunden habe, sondern das durch eine Standard-Arithmetik-Erweiterung ersetzt werden kann. ZB i=$((i+1))statt i=$(expr $i + 1)zu inkrementieren i. Ihre Verwendung von cutim letzten Beispiel kann auch durch Standardparametererweiterungen ersetzt werden.

    Siehe auch: Warum wird die Verwendung einer Shell-Schleife zum Verarbeiten von Text als unangemessen angesehen?

Die Schritte 1 und 2 sollten auf Ihre Frage zutreffen.

ilkkachu
quelle
12
# 0, zitiere deine Erweiterungen :-)
Kusalananda
8
Es ist nicht so, dass awkLoops notwendigerweise besser oder schlechter sind als Shell-Loops. Es ist so, dass die Shell wirklich gut darin ist , Befehle auszuführen und Eingaben und Ausgaben zu und von Prozessen zu leiten, und ehrlich gesagt ziemlich klobig bei allem anderen. während Werkzeuge wie awksind fantastisch bei der Verarbeitung von Textdaten, weil das, was Muscheln und Werkzeuge wie awkfür (jeweils) in erster Linie gemacht werden .
DopeGhoti
2
@ DopeGhoti, Shells scheinen allerdings objektiv langsamer zu sein. Einige sehr einfache while-Schleifen scheinen> 25-mal langsamer zu sein dashals mit gawkund dashwaren die schnellste Shell, die ich getestet habe ...
ilkkachu
1
@ Joe, es ist :) dashund busyboxnicht unterstützen (( .. ))- ich denke, es ist eine nicht standardmäßige Erweiterung. ++wird auch ausdrücklich als nicht erforderlich erwähnt, soweit ich das beurteilen kann i=$((i+1))oder : $(( i += 1))die sicher sind.
ilkkachu
1
Re „mehr Zeit Denken“ : dies vernachlässigt einen wichtigen Faktor. Wie oft wird es ausgeführt und für wie viele Benutzer? Wenn ein Programm 1 Sekunde vergeht, was durch den Programmierer behoben werden kann, der 30 Minuten lang darüber nachdenkt, ist es möglicherweise Zeitverschwendung, wenn es nur einen Benutzer gibt, der es einmal ausführt. Wenn es andererseits eine Million Benutzer gibt, sind das eine Million Sekunden oder 11 Tage Benutzerzeit. Wenn der Code eine Minute von einer Million Benutzern verschwendet hat, sind das ungefähr 2 Jahre Benutzerzeit.
4.
13

Ich werde in dieser Antwort nur einige allgemeine Ratschläge geben und keine Benchmarks. Benchmarks sind die einzige Möglichkeit, Fragen zur Leistung zuverlässig zu beantworten. Da Sie jedoch nicht angeben, wie viele Daten Sie bearbeiten und wie oft Sie diesen Vorgang ausführen, gibt es keine Möglichkeit, einen nützlichen Benchmark durchzuführen. Was für 10 Artikel effizienter ist und was für 1000000 Artikel effizienter ist, ist oft nicht dasselbe.

Generell ist das Aufrufen von externen Befehlen teurer als das Ausführen von reinen Shell-Konstrukten, sofern der reine Shell-Code keine Schleife enthält. Andererseits ist eine Shell-Schleife, die über eine große Zeichenfolge oder eine große Anzahl von Zeichenfolgen iteriert, wahrscheinlich langsamer als ein Aufruf eines Spezialwerkzeugs. Beispielsweise kann das Aufrufen einer Schleife cutin der Praxis sehr langsam sein. Wenn Sie jedoch eine Möglichkeit finden, das Ganze mit einem einzigen cutAufruf zu erledigen , ist dies wahrscheinlich schneller als mit der String-Manipulation in der Shell.

Beachten Sie, dass der Grenzwert zwischen den Systemen sehr unterschiedlich sein kann. Dies kann vom Kernel, der Konfiguration des Kernel-Schedulers, dem Dateisystem mit den externen ausführbaren Dateien, dem aktuellen CPU- und Speicherdruck und vielen anderen Faktoren abhängen.

Rufen Sie nicht expran, um zu rechnen, wenn Sie sich überhaupt um die Leistung sorgen. Rufen Sie exprin der Tat gar nicht zum Rechnen auf. Shells verfügen über eine integrierte Arithmetik, die klarer und schneller ist als das Aufrufen expr.

Sie scheinen bash zu verwenden, da Sie bash-Konstrukte verwenden, die in sh nicht existieren. Warum um alles in der Welt würden Sie kein Array verwenden? Ein Array ist die natürlichste und wahrscheinlich auch die schnellste Lösung. Beachten Sie, dass Array-Indizes bei 0 beginnen.

list=(1 2 3 5 9 8 6 90 84 9 3 2 15 75 55)
for ((count = 0; count += 3; count < ${#list[@]})); do
  echo "${list[$count]}"
done

Ihr Skript ist möglicherweise schneller, wenn Sie sh verwenden, wenn Ihr System shstatt bash dash oder ksh as hat . Wenn Sie sh verwenden, erhalten Sie keine benannten Arrays, aber Sie erhalten immer noch einen der Positionsparameter für das Array, die Sie festlegen können set. Um auf ein Element an einer Position zuzugreifen, die erst zur Laufzeit bekannt ist, müssen Sie verwenden eval(achten Sie darauf, dass Sie die Dinge richtig zitieren!).

# List elements must not contain whitespace or ?*\[
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
set $list
count=1
while [ $count -le $# ]; do
  eval "value=\${$count}"
  echo "$value"
  count=$((count+1))
done

Wenn Sie immer nur einmal auf das Array zugreifen möchten und von links nach rechts gehen (einige Werte überspringen), können Sie shiftanstelle von Variablen Indizes verwenden.

# List elements must not contain whitespace or ?*\[
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
set $list
while [ $# -ge 1 ]; do
  echo "$1"
  shift && shift && shift
done

Welcher Ansatz schneller ist, hängt von der Shell und der Anzahl der Elemente ab.

Eine andere Möglichkeit ist die Verwendung der Zeichenfolgenverarbeitung. Es hat den Vorteil, dass die Positionsparameter nicht verwendet werden, sodass Sie sie für andere Zwecke verwenden können. Bei großen Datenmengen ist dies langsamer, bei kleinen Datenmengen macht sich dies jedoch kaum bemerkbar.

# List elements must be separated by a single space (not arbitrary whitespace)
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
while [ -n "$list" ]; do
  echo "${list% *}"
  case "$list" in *\ *\ *\ *) :;; *) break;; esac
  list="${list#* * * }"
done
Gilles 'SO - hör auf böse zu sein'
quelle
" Andererseits ist eine Shell-Schleife, die über eine große Zeichenfolge oder eine große Anzahl von Zeichenfolgen iteriert, wahrscheinlich langsamer als ein Aufruf eines Spezialwerkzeugs ", aber was ist, wenn dieses Werkzeug Schleifen wie awk enthält? @ikkachu sagte, dass awk-Schleifen schneller sind, aber würden Sie sagen, dass bei <1000 zu durchlaufenden Feldern der Vorteil schnellerer Schleifen die Kosten für den Aufruf von awk nicht überwiegen würde, da dies ein externer Befehl ist (vorausgesetzt, ich könnte dieselbe Aufgabe in der Shell ausführen) Schleifen mit der Verwendung von nur eingebauten Befehlen)?
Levi Uzodike
@LeviUzodike Bitte lies den ersten Absatz meiner Antwort noch einmal durch.
Gilles 'SO - hör auf böse zu sein'
Sie können auch ersetzen shift && shift && shiftmit shift 3in Ihr drittes Beispiel - es sei denn , die Shell Sie verwenden sie nicht unterstützt.
Joe
2
@ Joe Eigentlich nein. shift 3würde scheitern, wenn es zu wenige verbleibende Argumente gäbe. Du brauchst so etwas wieif [ $# -gt 3 ]; then shift 3; else set --; fi
Gilles 'SO - hör auf böse zu sein'
3

awkist eine gute Wahl, wenn Sie die gesamte Verarbeitung innerhalb des Awk-Skripts durchführen können. Andernfalls leiten Sie die Awk-Ausgabe einfach an andere Dienstprogramme weiter, wodurch der Leistungszuwachs von zunichte gemacht wird awk.

bashDie Iteration über ein Array ist auch großartig, wenn Sie Ihre gesamte Liste in das Array einpassen können (was bei modernen Shells wahrscheinlich eine Garantie ist) und die Syntaxgymnastik des Arrays nichts ausmacht.

Ein Pipeline-Ansatz:

xargs -n3 <<< "$list" | while read -ra a; do echo $a; done | grep 9

Woher:

  • xargs gruppiert die durch Leerzeichen getrennte Liste in Dreiergruppen, wobei jede neue Zeile getrennt ist
  • while read verbraucht diese Liste und gibt die erste Spalte jeder Gruppe aus
  • grep filtert die erste Spalte (entsprechend jeder dritten Position in der ursprünglichen Liste)

Verbessert meiner Meinung nach die Verständlichkeit. Die Leute wissen bereits, was diese Tools tun, daher ist es einfach, von links nach rechts zu lesen und zu überlegen, was passieren wird. Dieser Ansatz dokumentiert auch eindeutig die Schrittlänge ( -n3) und das Filtermuster ( 9), sodass die Variabilität einfach ist:

count=3
find=9
xargs -n "$count" <<< "$list" | while read -ra a; do echo $a; done | grep "$find"

Wenn wir Fragen zur "Effizienz" stellen, denken Sie unbedingt an die "Gesamtlebensdauereffizienz". Diese Berechnung beinhaltet die Bemühungen der Betreuer, den Code am Laufen zu halten, und wir Fleischsäcke sind die am wenigsten effizienten Maschinen im gesamten Betrieb.

Bischof
quelle
2

Vielleicht das?

cut -d' ' -f1,4,7,10,13 <<<$list
1 5 6 9 15
doneal24
quelle
Es tut mir leid, dass ich vorher nicht klar war, aber ich wollte in der Lage sein, die Zahlen an diesen Positionen abzurufen, ohne die Länge der Liste zu kennen. Aber danke, ich habe vergessen, dass cut das kann.
Levi Uzodike
1

Verwenden Sie keine Shell-Befehle, wenn Sie effizient sein möchten. Beschränken Sie sich auf Pipes, Weiterleitungen, Ersetzungen usw. und Programme. Aus diesem Grunde xargsund parallelDienstprogramme vorhanden - weil bash While - Schleifen sind ineffizient und sehr langsam. Verwenden Sie Bash-Loops nur als letzte Lösung.

list="1 ant bat 5 cat dingo 6 emu fish 9 gecko hare 15 i j"
if 
    <<<"$list" tr -d -s '[0-9 ]' | 
    tr -s ' ' | tr ' ' '\n' | 
    grep -q -x '9'
then
    found=true
else 
    found=false
fi
echo ${found} 

Aber mit gut solltest du wohl etwas schneller werden awk.

KamilCuk
quelle
Es tut mir leid, dass ich vorher nicht klar war, aber ich suchte nach einer Lösung, die die Werte nur basierend auf ihrer Position in der Liste extrahieren kann. Ich habe die ursprüngliche Liste einfach so erstellt, weil ich wollte, dass die von mir gewünschten Werte offensichtlich sind.
Levi Uzodike
1

Meiner Meinung nach besteht die klarste (und wahrscheinlich auch performanteste) Lösung darin, die Variablen RS und ORS awk zu verwenden:

awk -v RS=' ' -v ORS=' ' 'NR % 3 == 1' <<< "$list"
user000001
quelle
1
  1. Verwenden des GNU- sed und POSIX- Shell-Skripts:

    echo $(printf '%s\n' $list | sed -n '1~3p')
  2. Oder mit bashder Parametersubstitution :

    echo $(sed -n '1~3p' <<< ${list// /$'\n'})
  3. Nicht- GNU ( dh POSIX ) sedund bash:

    sed 's/\([^ ]* \)[^ ]* *[^ ]* */\1/g' <<< "$list"

    Oder portabler mit POSIX sed und Shell-Skript:

    echo "$list" | sed 's/\([^ ]* \)[^ ]* *[^ ]* */\1/g'

Ausgabe von einem dieser:

1 5 6 9 15
agc
quelle