Czy orurowanie, przesuwanie lub rozszerzanie parametrów jest bardziej wydajne?


26

Próbuję znaleźć najbardziej skuteczny sposób na iterację pewnych wartości, które są stałą liczbą wartości od siebie na liście słów oddzielonych spacjami (nie chcę używać tablicy). Na przykład,

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

Chcę więc móc iterować po liście i uzyskiwać dostęp tylko do 1,5,6,9 i 15.

EDYCJA: Powinienem był jasno powiedzieć, że wartości, które próbuję uzyskać z listy, nie muszą różnić się formatem od reszty listy. Tym, co je wyróżnia, jest wyłącznie ich pozycja na liście (w tym przypadku pozycja 1,4,7 ...). Tak więc lista może być,1 2 3 5 9 8 6 90 84 9 3 2 15 75 55ale nadal chcę te same liczby. Chcę też móc to zrobić, zakładając, że nie znam długości listy.

Metody, o których do tej pory myślałem, to:

Metoda 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

Metoda 2

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

Metoda 3 Jestem pewien, że pipowanie czyni tę opcję najgorszą, ale próbowałem znaleźć metodę, która nie używa zestawu, z ciekawości.

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

Co byłoby najbardziej wydajne, czy brakuje mi prostszej metody?


10
Nie użyłbym przede wszystkim skryptu powłoki, jeśli wydajność jest ważnym problemem. Jak duża jest twoja lista, że ​​to robi różnicę?
Barmar


2
Bez robienia statystyk dotyczących rzeczywistych przypadków twojego problemu nic nie wiesz. Obejmuje to porównywanie do „programowania w awk” itp. Jeśli statystyki są zbyt drogie, to szukanie wydajności prawdopodobnie nie jest tego warte.
David Tonhofer

2
Levi, jaki dokładnie jest „wydajny” sposób w twojej definicji? Chcesz znaleźć szybszy sposób na iterację?
Sergiy Kolodyazhnyy

Odpowiedzi:


18

Całkiem proste z awk. Otrzymasz wartość co czwarte pole do wprowadzania dowolnej długości:

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

Działa to poprzez wykorzystanie wbudowanych awkzmiennych, takich jak NF(liczba pól w rekordzie), i wykonanie prostej forpętli w celu iteracji wzdłuż pól, aby uzyskać te, które chcesz, bez konieczności wcześniejszego wiedzieć, ile będzie.

Lub, jeśli naprawdę chcesz po prostu tych konkretnych pól, jak podano w przykładzie:

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

Jeśli chodzi o pytanie dotyczące wydajności, najprostszą drogą byłoby przetestowanie tej lub każdej z pozostałych metod i użycie, timeaby pokazać, jak długo to trwa; możesz także użyć narzędzi takich jak stracesprawdzenie, jak przebiegają wywołania systemowe. Zastosowanie timewygląda jak:

$ time ./script.sh

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

Możesz porównać te wyniki między różnymi metodami, aby zobaczyć, który jest najbardziej wydajny pod względem czasu; inne narzędzia mogą być wykorzystane do innych wskaźników wydajności.


1
Dobra uwaga, @MichaelHomer; Dodałem na bok odpowiedź na pytanie „w jaki sposób mogę ustalić, która metoda jest najbardziej wydajna ”.
DopeGhoti

2
@LeviUzodike chodzi echovs <<<„identyczne” to zbyt mocne słowo. Można powiedzieć, że stuff <<< "$list"jest prawie identyczny z printf "%s\n" "$list" | stuff. Jeśli chodzi o echovs printf, kieruję cię do tej odpowiedzi
JoL

5
@DopeGhoti Właściwie to robi. <<<dodaje nowy wiersz na końcu. Jest to podobne do sposobu $()usuwania znaku nowej linii na końcu. Wynika to z faktu, że linie są zakończone przez nowe linie. <<<podaje wyrażenie jako linię, więc musi być zakończone znakiem nowej linii. "$()"pobiera wiersze i podaje je jako argument, więc warto je przekonwertować, usuwając kończący znak nowej linii.
JoL

3
@LeviUzodike awk jest bardzo niedocenianym narzędziem. Sprawi, że wszystkie pozornie złożone problemy będą łatwe do rozwiązania. Zwłaszcza, gdy próbujesz napisać złożone wyrażenie regularne dla czegoś takiego jak sed, często możesz zaoszczędzić godziny, pisząc je proceduralnie w awk. Nauka tego przyniesie duże dywidendy.
Joe

1
@LeviUzodike: Tak awkto samodzielny plik binarny, który musi się uruchomić. W przeciwieństwie do Perla, a zwłaszcza Pythona, interpreter awk uruchamia się szybko (wciąż cały zwykły narzut dynamiczny linkera związany z wykonywaniem kilku wywołań systemowych, ale awk używa tylko libc / libm i libdl, np. Służy stracedo sprawdzania wywołań systemowych uruchamiania awk) . Wiele powłok (takich jak bash) działa dość wolno, więc odpalenie jednego procesu awk może być szybsze niż zapętlanie tokenów na liście z wbudowanymi powłokami, nawet dla małych rozmiarów list. I czasami można napisać #!/usr/bin/awkskrypt, zamiast o #!/bin/shskrypcie.
Peter Cordes

35
  • Pierwsza zasada optymalizacji oprogramowania: nie .

    Dopóki nie dowiesz się, że szybkość programu jest problemem, nie musisz myśleć o jego szybkości. Jeśli twoja lista ma mniej więcej tę długość lub tylko ~ 100-1000 przedmiotów, prawdopodobnie nawet nie zauważysz, ile to zajmie. Istnieje szansa, że ​​poświęcisz więcej czasu na myślenie o optymalizacji, niż jaka byłaby różnica.

  • Druga zasada: środek .

    Jest to pewny sposób, aby się dowiedzieć, i ten, który daje odpowiedzi dla twojego systemu. Zwłaszcza w przypadku muszli jest ich tak wiele i nie wszystkie są identyczne. Odpowiedź na jedną powłokę może nie dotyczyć twojej.

    W większych programach profilowanie również tutaj. Najwolniejsza część może nie być taka, jak myślisz.

  • Po trzecie, pierwsza zasada optymalizacji skryptu powłoki: Nie używaj powłoki .

    Tak, naprawdę. Wiele powłok nie jest stworzonych jako szybkie (ponieważ uruchamianie programów zewnętrznych nie musi tak być), a nawet za każdym razem mogą ponownie analizować wiersze kodu źródłowego.

    Zamiast tego użyj czegoś takiego jak awk lub Perl. W trywialnym mikro-teście, który zrobiłem, awkbył dziesiątki razy szybszy niż jakakolwiek zwykła powłoka w uruchamianiu prostej pętli (bez I / O).

    Jeśli jednak używasz powłoki, użyj wbudowanych funkcji powłoki zamiast poleceń zewnętrznych. Używasz tutaj, exprktóre nie jest wbudowane w żadne powłoki znalezione w moim systemie, ale które można zastąpić standardowym rozszerzeniem arytmetycznym. Np. i=$((i+1))Zamiast i=$(expr $i + 1)zwiększać i. Twoje użycie cutw ostatnim przykładzie może być również zastąpione standardowymi rozszerzeniami parametrów.

    Zobacz także: Dlaczego używanie pętli powłoki do przetwarzania tekstu jest uważane za złą praktykę?

Kroki 1 i 2 powinny mieć zastosowanie do twojego pytania.


12
# 0,
podaj

8
To nie jest tak, że awkpętle są z konieczności lepsze lub gorsze niż pętle powłoki. Chodzi o to, że powłoka jest naprawdę dobra w uruchamianiu poleceń i kierowaniu danych wejściowych i wyjściowych do i z procesów, i szczerze mówiąc, niezgrabna we wszystkim innym; podczas gdy podobne narzędzia awkfantastyczne w przetwarzaniu danych tekstowych, ponieważ właśnie po to awksą tworzone (odpowiednio) powłoki i narzędzia .
DopeGhoti

2
@DopeGhoti, powłoki wydają się jednak obiektywnie wolniejsze. Niektóre bardzo proste, podczas gdy pętle wydają się być> 25 razy wolniejsze dashniż z gawk, i dashbyły najszybszą powłoką, którą testowałem ...
ilkkachu

1
@Joe, to jest :) dashi busyboxnie obsługuje (( .. ))- myślę, że to niestandardowe rozszerzenie. ++jest również wyraźnie wymieniony jako niewymagany, o ile mogę powiedzieć, i=$((i+1))lub : $(( i += 1))są bezpieczni.
ilkkachu

1
Re „myślenie więcej czasu” : to pomija ważny czynnik. Jak często to działa i dla ilu użytkowników? Jeśli program marnuje 1 sekundę, co może naprawić programista myślący o nim przez 30 minut, może to być strata czasu, jeśli tylko jeden użytkownik uruchomi go raz. Z drugiej strony, jeśli jest milion użytkowników, to milion sekund lub 11 dni czasu użytkownika. Jeśli kod zmarnuje minutę miliona użytkowników, to około 2 lata czasu użytkownika.
agc

13

W tej odpowiedzi udzielę jedynie ogólnych wskazówek, a nie punktów odniesienia. Testy porównawcze to jedyny sposób, aby rzetelnie odpowiedzieć na pytania dotyczące wydajności. Ale ponieważ nie mówisz, ile danych manipulujesz i jak często wykonujesz tę operację, nie ma sposobu na wykonanie użytecznego testu porównawczego. Co jest bardziej wydajne dla 10 przedmiotów, a co jest bardziej wydajne dla 1000000 przedmiotów, często nie jest takie samo.

Ogólna zasada polega na tym, że wywoływanie zewnętrznych poleceń jest droższe niż robienie czegoś przy użyciu czystych konstrukcji powłoki, o ile czysty kod powłoki nie wymaga pętli. Z drugiej strony pętla powłoki, która iteruje po dużym łańcuchu lub dużej ilości łańcucha, może być wolniejsza niż jedno wywołanie narzędzia specjalnego. Na przykład, wywoływanie pętli cutmoże być zauważalnie powolne w praktyce, ale jeśli znajdziesz sposób na zrobienie wszystkiego za pomocą pojedynczego cutwywołania, które prawdopodobnie będzie szybsze niż robienie tego samego z manipulowaniem łańcuchem w powłoce.

Należy pamiętać, że punkt odcięcia może się znacznie różnić między systemami. Może zależeć od jądra, od konfiguracji harmonogramu jądra, od systemu plików zawierającego zewnętrzne pliki wykonywalne, od tego, ile procesora w tej chwili naciska pamięć, i od wielu innych czynników.

Nie dzwoń, expraby wykonać arytmetykę, jeśli w ogóle martwisz się wydajnością. W rzeczywistości nie wzywaj exprdo wykonywania arytmetyki. Pociski mają wbudowaną arytmetykę, która jest wyraźniejsza i szybsza niż wywoływanie expr.

Wygląda na to, że używasz basha, ponieważ używasz konstrukcji bash, które nie istnieją w sh. Dlaczego więc, do cholery, nie miałbyś użyć tablicy? Tablica jest najbardziej naturalnym rozwiązaniem i prawdopodobnie też będzie najszybsza. Zauważ, że indeksy tablic zaczynają się od 0.

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

Twój skrypt może być szybszy, jeśli używasz sh, jeśli twój system ma kreskę lub ksh shzamiast zamiast bash. Jeśli używasz sh, nie otrzymujesz nazwanych tablic, ale nadal otrzymujesz tablicę jednego z parametrów pozycyjnych, które możesz ustawić set. Aby uzyskać dostęp do elementu w pozycji, która nie jest znana przed uruchomieniem, musisz użyć eval(zadbaj o prawidłowe cytowanie rzeczy!).

# 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

Jeśli kiedykolwiek chcesz uzyskać dostęp do tablicy tylko raz i przechodzisz od lewej do prawej (pomijając niektóre wartości), możesz użyć shiftzamiast indeksów zmiennych.

# 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

To, które podejście jest szybsze, zależy od powłoki i liczby elementów.

Inną możliwością jest użycie przetwarzania ciągów. Ma tę zaletę, że nie używa parametrów pozycyjnych, więc możesz użyć ich do czegoś innego. Będzie działać wolniej w przypadku dużych ilości danych, ale jest mało prawdopodobne, aby zauważalna różnica w przypadku małych ilości danych.

# 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

Z drugiej strony pętla powłoki, która iteruje po dużym łańcuchu lub dużej ilości łańcucha, może być wolniejsza niż jedno wywołanie narzędzia specjalnego ”, ale co, jeśli to narzędzie ma w sobie pętle takie jak awk? @ikkachu powiedział, że pętle awk są szybsze, ale czy można powiedzieć, że przy <1000 polach do iteracji, korzyść z szybszych pętli nie przewyższy kosztów wywołania awk, ponieważ jest to polecenie zewnętrzne (zakładając, że mógłbym wykonać to samo zadanie w powłoce pętle za pomocą tylko wbudowanych poleceń)?
Levi Uzodike

@LeviUzodike Proszę ponownie przeczytać pierwszy akapit mojej odpowiedzi.
Gilles „SO- przestań być zły”

Można również wymienić shift && shift && shiftsię shift 3w trzecim przykładzie - chyba że powłoka używasz nie obsługuje.
Joe

2
@Joe Właściwie nie. shift 3zawiedzie, jeśli pozostanie zbyt mało argumentów. Potrzebujesz czegoś takiegoif [ $# -gt 3 ]; then shift 3; else set --; fi
Gilles 'SO - przestań być zły'

3

awkto świetny wybór, jeśli możesz wykonać całe przetwarzanie w skrypcie Awk. W przeciwnym razie po prostu przesyłasz wyjście Awk do innych narzędzi, niszcząc wzrost wydajności awk.

bashiteracja nad tablicą jest również świetna, jeśli zmieścisz całą listę wewnątrz tablicy (co dla nowoczesnych powłok jest prawdopodobnie gwarancją) i nie przeszkadza ci gimnastyka w składni tablicy.

Jednak podejście oparte na potoku:

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

Gdzie:

  • xargs grupuje listę oddzieloną spacjami w trzyosobowe partie, każda oddzielona nowym wierszem
  • while read zużywa tę listę i wyświetla pierwszą kolumnę każdej grupy
  • grep filtruje pierwszą kolumnę (odpowiadającą co trzeciej pozycji na oryginalnej liście)

Moim zdaniem poprawia zrozumiałość. Ludzie już wiedzą, co robią te narzędzia, więc łatwo jest czytać od lewej do prawej i rozumieć, co się stanie. Podejście to wyraźnie dokumentuje także długość kroku ( -n3) i wzorzec filtra ( 9), dzięki czemu można łatwo zmieniać:

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

Kiedy zadajemy pytania dotyczące „wydajności”, pamiętaj o „całkowitej wydajności w ciągu całego życia”. Obliczenia te obejmują wysiłek opiekunów, aby utrzymać kod w działaniu, a my, worki mięsne, jesteśmy najmniej wydajnymi maszynami w całej operacji.


2

Być może to?

cut -d' ' -f1,4,7,10,13 <<<$list
1 5 6 9 15

Przykro mi, ale wcześniej nie było jasne, ale chciałem móc uzyskać liczby na tych pozycjach bez znajomości długości listy. Ale dzięki, zapomniałem, że cut mógł to zrobić.
Levi Uzodike

1

Nie używaj poleceń powłoki, jeśli chcesz być wydajny. Ogranicz się do potoków, przekierowań, zamian itp. Oraz programów. Właśnie dlatego xargsi parallelnarzędzia istnieją - ponieważ bash podczas gdy pętle są nieefektywne i bardzo wolne. Pętli bash należy używać tylko jako ostatniego rozwiązania.

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} 

Ale powinieneś być nieco szybszy dzięki dobremu awk.


Przykro mi, ale wcześniej nie było jasne, ale szukałem rozwiązania, które byłoby w stanie wyodrębnić wartości na podstawie ich pozycji na liście. Właśnie stworzyłem taką oryginalną listę, ponieważ chciałem, aby oczywiste były wartości, których chciałem.
Levi Uzodike

1

Moim zdaniem najczystszym rozwiązaniem (i prawdopodobnie również najbardziej wydajnym) jest użycie zmiennych awk RS i ORS:

awk -v RS=' ' -v ORS=' ' 'NR % 3 == 1' <<< "$list"

1
  1. Za pomocą skryptu powłoki GNU sed i POSIX :

    echo $(printf '%s\n' $list | sed -n '1~3p')
  2. Lub z bash„s parametrów podstawienia :

    echo $(sed -n '1~3p' <<< ${list// /$'\n'})
  3. Non- GNU ( tj. POSIX ) sedoraz bash:

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

    Lub bardziej przenośnie, używając zarówno POSIX, jak sedi skryptu powłoki:

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

Dane wyjściowe któregokolwiek z tych:

1 5 6 9 15
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.