Làm thế nào để kịch bản sed này nhanh hơn?

Question

Tôi đã thừa hưởng đoạn này sed kịch bản mà cố gắng để loại bỏ khoảng trống nhất định:

s/[\s\t]*|/|/g 
s/|[\s\t]*/|/g 
s/[\s] *$//g 
s/^|/null|/g 

hoạt động trên một tập tin đó là khoảng 1Gb lớn. Tập lệnh này chạy trong 2 giờ trên máy chủ Unix của chúng tôi. Bất kỳ ý tưởng làm thế nào để tăng tốc độ nó?

Ghi chú rằng \ s là viết tắt cho một không gian và \ t là viết tắt của một tab, kịch bản thực tế sử dụng không gian thực tế và tab và không những biểu tượng

Các tập tin đầu vào là một đường ống tập tin được phân định và là đặt cục bộ không có trên mạng. 4 dòng trong một tệp được thực hiện với sed -f

Answer 1

Điều tốt nhất tôi có thể làm được với sed, là kịch bản này:

s/[\s\t]*|[\s\t]*/|/g 
s/[\s\t]*$// 
s/^|/null|/ 

Trong các thử nghiệm của tôi, điều này chạy nhanh hơn khoảng 30% so với tập lệnh sed của bạn. Sự gia tăng hiệu suất đến từ việc kết hợp hai regexen đầu tiên và bỏ qua cờ "g" ở nơi không cần thiết.

Tuy nhiên, nhanh hơn 30% chỉ là cải thiện nhẹ (vẫn mất khoảng một tiếng rưỡi để chạy tập lệnh trên trên tệp dữ liệu 1GB của bạn). Tôi muốn xem tôi có thể làm tốt hơn không.

Cuối cùng, không có phương pháp nào khác mà tôi đã thử (awk, perl, và các cách tiếp cận khác với sed) có bất kỳ tốt hơn, ngoại trừ - tất nhiên - thực hiện đồng bằng ol 'C. Như được mong đợi với C, mã là một chút tiết để đăng bài ở đây, nhưng nếu bạn muốn một chương trình có khả năng sẽ nhanh hơn bất kỳ phương pháp nào khác ngoài đó, bạn có thể muốn take a look at it.

Trong các thử nghiệm của tôi, việc triển khai C hoàn thành khoảng 20% ​​thời gian cần thiết cho tập lệnh sed của bạn. Vì vậy, có thể mất khoảng 25 phút để chạy trên máy chủ Unix của bạn.

Tôi không dành nhiều thời gian để tối ưu hóa triển khai C. Không có nghi ngờ có một số nơi mà các thuật toán có thể được cải thiện, nhưng thẳng thắn, tôi không biết nếu nó có thể cạo một số lượng đáng kể thời gian vượt quá những gì nó đã đạt được. Nếu bất cứ điều gì, tôi nghĩ rằng nó chắc chắn đặt một giới hạn trên về loại hiệu suất bạn có thể mong đợi từ các phương pháp khác (sed, awk, perl, python, vv).

Chỉnh sửa: Phiên bản gốc có lỗi nhỏ khiến nó có thể in sai ở cuối đầu ra (ví dụ: có thể in "null" không có ở đó). Hôm nay tôi đã có một thời gian để xem và sửa nó. Tôi cũng đã tối ưu hóa một cuộc gọi đến strlen() giúp tăng hiệu suất hoạt động một chút.

Answer 2

Dường như với ví dụ của bạn rằng bạn đang dọn sạch khoảng trắng từ đầu và cuối của các trường được phân cách bằng dấu (|) trong một tệp văn bản. Nếu tôi thực hiện việc này, tôi sẽ thay đổi thuật toán thành:

for each line 
    split the line into an array of fields 
    remove the leading and trailing white space 
    join the fields back back together as a pipe delimited line handling the empty first field correctly. 

Tôi cũng sẽ sử dụng một ngôn ngữ khác như Perl hoặc Ruby cho việc này.

Ưu điểm của phương pháp này là mã dọn dẹp các dòng hiện đang xử lý ít ký tự hơn cho mỗi lời gọi và thực thi nhanh hơn nhiều mặc dù cần thêm nhiều lời gọi.

Answer 3

Hãy thử thay đổi hai dòng đầu tiên:

s/[ \t]*|[ \t]*/|/g 

Answer 4

Hãy thử làm nó trong một lệnh:

sed 's/[^|]*(|.*|).*/\1/' 

Answer 5

Các bạn đã thử Perl? Nó có thể nhanh hơn.

#!/usr/local/bin/perl -p 

s#[\t ]+\|#|#g; 
s#\|[\t ]+#|#g; 
s#[\t ]*$##; 
s#^\|#null|#; 

Edit: Trên thực tế, nó có vẻ là khoảng ba lần chậm hơn so với các chương trình sed. Kỳ lạ ...

Answer 6

kịch bản Perl này cần được nhanh hơn nhiều nhiều

s/\s*|\s*/|/go; 
s/\s *$//o; 
s/^|/null|/o; 

Về cơ bản, đảm bảo regexes của bạn được biên dịch một lần ('o' cờ), và không cần phải sử dụng 'g' trên regexes chỉ áp dụng cho kết thúc và đầu dòng.

Ngoài ra, [\ s \ t] * tương đương với \ s *

Answer 7

Điều này có thể hiệu quả. Tôi đã chỉ thử nghiệm nó một chút.

awk 'BEGIN {FS="|"; OFS="|"} {for (i=1; i<=NF; i++) gsub("[ \t]", "", $i); $1=$1; if ($1 == "") $1 = "null"; print}' 

Answer 8

Làm thế nào về Perl:

#!/usr/bin/perl 

while(<>) { 
    s/\s*\|\s*/|/g; 
    s/^\s*//; 
    s/\s*$//; 
    s/^\|/null|/; 
    print; 
} 

EDIT: Thay đổi cách tiếp cận đáng kể. Trên máy tính của tôi, điều này gần gấp 3 lần so với kịch bản sed của bạn.

Nếu bạn thực sự cần tốc độ tốt nhất có thể, hãy viết chương trình C chuyên dụng để thực hiện tác vụ này.

Answer 9

sử dụng gawk chứ không phải sed.

awk -vFS='|' '{for(i=1;i<=NF;i++) gsub(/ +|\t+/,"",$i)}1' OFS="|" file 

Answer 10

Thử nghiệm của tôi chỉ ra rằng sed có thể trở thành cpu ràng buộc khá dễ dàng trên một cái gì đó như thế này. Nếu bạn có một máy tính đa lõi bạn có thể thử đẻ ra nhiều quy trình sed với một kịch bản mà trông giống như sau:

#!/bin/sh 
INFILE=data.txt 
OUTFILE=fixed.txt 
SEDSCRIPT=script.sed 
SPLITLIMIT=`wc -l $INFILE | awk '{print $1/20}'` 

split -d -l $SPLITLIMT $INFILE x_ 

for chunk in ls x_?? 
do 
    sed -f $SEDSCRIPT $chunk > $chunk.out & 
done 

wait 

cat x_??.out >> output.txt 

rm -f x_?? 
rm -f x_??.out 

Answer 11

Tôi nghĩ rằng * trong cụm từ thông dụng trong câu hỏi và hầu hết các câu trả lời có thể là sự sụt giảm lớn so với việc sử dụng +. Hãy xem xét thay thế đầu tiên trong câu hỏi

s/[\s\t]*|/|/g 

các * trận zero hoặc nhiều mục tiếp theo là một |, do đó mỗi | được thay thế ngay cả những người không cần phải thay thế. Thay đổi thay thế thành

s/[\s\t]+|/|/g 

sẽ chỉ thay đổi | ký tự đứng trước một hoặc nhiều dấu cách và tab.

Tôi không có sed, nhưng tôi đã làm một thử nghiệm với Perl. Trên dữ liệu tôi đã sử dụng tập lệnh với * mất gần 7 lần so với tập lệnh có +.

Thời gian nhất quán giữa các lần chạy.Đối với số +, chênh lệch giữa thời gian tối thiểu và tối đa là 4% mức trung bình và cho số * là 3,6%. Tỷ lệ thời gian trung bình là 1 :: 6,9 cho + :: *.

chi tiết của thí nghiệm

Tested sử dụng một tập tin 80MB với chỉ hơn 180.000 lần xuất hiện của [st]\., đó là những ký tự chữ thường s và t.

Thử nghiệm đã sử dụng tệp lệnh lô với 30 của mỗi lệnh trong số hai lệnh này, thay thế dấu sao và dấu cộng.

perl -f TestPlus.pl input.ltrar > zz.oo 
perl -f TestStar.pl input.ltrar > zz.oo 

Một kịch bản ở dưới, người kia chỉ đơn thuần là thay đổi *-+ và star-plus.

#! /bin/usr/perl 
use strict; 
use warnings; 
use Time::HiRes qw(gettimeofday tv_interval); 

my $t0 = [gettimeofday()]; 
while(<>) 
{ 
    s/[st]*\././g; 
} 

my $elapsed = tv_interval ($t0); 
print STDERR "Elapsed star $elapsed\n"; 

phiên bản Perl sử dụng:

c:\test> perl -v 
This is perl 5, version 16, subversion 3 (v5.16.3) built for MSWin32-x64-multi-thread 
(with 1 registered patch, see perl -V for more detail) 

Copyright 1987-2012, Larry Wall 

Binary build 1603 [296746] provided by ActiveState http://www.ActiveState.com 
Built Mar 13 2013 13:31:10