Производительность простых парсеров for fun // Блог непонятно кого

No public Twitter messages.


Этот блог устарел и, скорее всего, больше не будет обновляться. В ближайшем будущем он переедет сюда.
24 августа 2013 // Программинг

Производительность простых парсеров for fun

Сегодня в скайп-конфе попросили написать простой парсер удаляющий из большого файла все строки содержащие определённое ключевое слово. Быстро набросал достаточно грубый скрипт на Node.JS, который разбивал все 550мб на массив по переносу строки и проверял каждый элемент в цикле и изумился — файл в 530мб и ~1.7млн строк нода умудрилась преобразовать всего за 3 секунды.

Вот его код:

fs = require('fs')

fs.readFile 'data.txt', 'utf8', (err, data) ->
  file = data.split '\n'
  out = ''

  for string in file
    if string.search('/partner/') is -1
      out += string + '\n'

  fs.appendFile 'node_out.txt', out, (err) -> console.error err

Время исполнения — 2,9 секунды.

Стало интересно, как с такой задачкой справятся другие языки и я попросил друга написать такой же парсер на Perl, а затем подтянулись спецы по другим языкам появились и варианты на Python, Bash и Java. Примеры кода и время исполнения следуют дальше:

 
Perl

#!/usr/bin/env perl

use strict;
use warnings;
use Time::HiRes qw(gettimeofday tv_interval);

my $t0 = [gettimeofday()];
open(OUTPUT, '>', 'perl_out.txt') or die "Error perl_out.txt [".$!."]\t";
open(INPUT, '<', 'data.txt') or die "Error data/in.log [".$!."]\t";
while (<INPUT>) {
	if (index($_, '/partner/') == -1) {
		print OUTPUT $_;
	}
}
close(OUTPUT);
close(INPUT);
print "Time [".scalar(tv_interval($t0))."]\n";

Время выполнения — 3,2 секунды.

 
Bash (рвал на голове волосы, что не смог додуматься решить задачку так с самого начала):

cat file.txt | grep -v "/partner/" > bash_out.txt

Время выполнения — 18 секунд.

 
Python

def remove_line(filename, string):
  rst = []

  with open(filename) as fd:
    t = fd.read()
    for line in t.splitlines():
      if string not in line:
        rst.append(line)

  with open(filename, 'w') as fd:
    fd.write('\n'.join(rst))
    fd.write('\n')

def main():
  remove_line('file.txt', '/partner/')

main()

Время выполнения — 5,5 секунды

 
Java

import java.io.File;
import java.io.IOException;
import java.io.FileWriter;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static void main(String[] args) throws IOException {
        String s = "";
        String g = "";
        String regex = "(/partner/)";
        Pattern p = Pattern.compile(regex);

        FileWriter os = new FileWriter ("data.txt");
        Scanner in = new Scanner(new File("file.txt"));
        while(in.hasNext()) {
            s = in.nextLine();

            Matcher m = p.matcher(s);

            if (!m.find()) {
                g = g + s + "\r\n";
            }
        }
        os.write(g);
        os.close();
    }

}

Время выполнения посчитать так и не удалось. Скрипт пришлось остановить спустя 40 минут с момента запуска :)

 
C

#include 
#include 
#include 

char *safe_fgets(FILE *f) {
	int step = 200;
	int R = step;
	int L = 0;
	char *s = malloc(step+1);
	s[0] = 0;
	s[R-1] = 0;

	for ( ;; ) {
		if ( !fgets(s+L,R-L+1,f) )
			if ( feof(f) && s[0] ) 
				return s;
			else {
				free(s);
				return 0;
			}

		if ( *(s+R-1) && *(s+R-1) != '\n' ) {
			s = realloc(s,R+step+1);
			L = R;
			R = R+step;
			s[R-1] = 0;
		}
		else
			return s;
	}
}
int main(int argc, char const *argv[]) {
	
	if (argc < 3) {
		printf("Please start with %s input.txt output.txt (for example)\n", argv[0]);
		return 0;
	}

	FILE *input;
	FILE *output;

	input = fopen(argv[1], "r");
	output = fopen(argv[2], "w");

	char *s;
	char *pch;
	for ( ;; ) {
		s = safe_fgets(input);
		if (s == 0)
			break;

		pch = strstr(s, "partner");
		if (!pch)
			fwrite(s, 1, strlen(s), output);
		free(s);
	}
	fclose(input);
	fclose(output);

	return 0;
}

Время выполнения — 2,9 секунды

Не удивительно, что победил Си, удивительно, что Node.JS отстал всего на 8 сотых. Скоро посмотрим на результаты C++ и PHP.



  • twitter
  • rss
  • хабр
  • жежека
  • ластфм