Производительность - Python против C # / C ++ / C читает символ за символом - PullRequest
0 голосов
/ 26 августа 2009

Итак, у меня есть эти гигантские XML-файлы (и под гигантскими, я имею в виду около 1,5 ГБ +), и у них нет CRLF. Я пытаюсь запустить программу, похожую на diff, чтобы найти различия между этими файлами.

Поскольку мне еще не удалось найти разностную программу, которая не взорвется из-за истощения памяти, я решил, что лучше всего было бы добавить CRLF после закрытия тегов.

Я написал скрипт на python для чтения char-by-char и добавления новых строк после '>'. Проблема в том, что я запускаю это на одноядерном ПК около 1995 года или что-то нелепое, и он обрабатывает только около 20 МБ / час, когда я конвертирую одновременно.

Любая идея, если написание этого на C # / C / C ++ вместо этого даст какие-либо преимущества? Если нет, кто-нибудь знает о программе diff, которая будет идти побайтово? Спасибо.


EDIT:

Вот код для моей функции обработки ...

def read_and_format(inputfile, outputfile):
    ''' Open input and output files, then read char-by-char and add new lines after ">" '''
    infile = codecs.open(inputfile,"r","utf-8")
    outfile = codecs.open(outputfile,"w","utf-8")

    char = infile.read(1) 
    while(1):
        if char == "":
            break
        else:
            outfile.write(char)
            if(char == ">"):
                outfile.write("\n")
        char = infile.read(1)

    infile.close()
    outfile.close()

EDIT2: Спасибо за потрясающие ответы. Увеличение размера чтения создало невероятное увеличение скорости. Проблема решена.

Ответы [ 8 ]

11 голосов
/ 26 августа 2009

Чтение и запись по одному символу за раз почти всегда будет медленным, потому что диски являются блочными устройствами, а не символьными устройствами - он будет читать намного больше, чем только один байт, который вы ищете и лишние части нужно выбросить.

Попробуйте читать и писать больше, скажем, 8192 байта (8 КБ), а затем находить и добавлять символы новой строки в этой строке перед тем, как записывать ее - вы должны значительно сэкономить на производительности, поскольку требуется намного меньше операций ввода-вывода.

Как указывает Л.Бушкин, ваша библиотека ввода-вывода может выполнять буферизацию, но если не существует какой-либо формы документации, показывающей, что это действительно происходит (для чтения и записи), довольно просто попробовать это сделать перед тем, как переписать в другой язык.

3 голосов
/ 26 августа 2009

Почему бы тебе просто не использовать sed? кот гигант.xml | sed 's /> /> \ x0a \ x0d / g' >iant-with-linebreaks.xml

1 голос
/ 26 августа 2009

Для типа проблемы, которую вы описываете, я подозреваю, что алгоритм, который вы используете для сравнения данных, будет иметь гораздо более существенный эффект, чем модель или язык ввода / вывода. На самом деле, распределение строк и поиск здесь могут быть более дорогими, чем что-либо еще.

Некоторые общие предложения, прежде чем написать это самостоятельно:

  1. Попробуйте запустить на более быстрой машине, если она у вас есть. Это будет иметь огромное значение.
  2. Ищите онлайн-инструмент для проведения различий в XML ... не пишите его самостоятельно.

Если вы собираетесь написать это на C # (или Java или C / C ++), я бы сделал следующее:

  1. Одновременное считывание довольно большого блока в память (скажем, между 200К и 1М)
  2. Выделите пустой блок, который в два раза больше этого размера (предполагается, что наихудший случай для каждого символа ->)
  3. Копировать из блока ввода в блок вывода, условно добавляя CRLF после каждого символа '>'.
  4. Запишите новый блок на диск.
  5. Повторяйте, пока все данные не будут обработаны.

Кроме того, вы могли бы также написать такую ​​программу для запуска в нескольких потоках, чтобы, хотя один раз поток выполнял вставки CRLF в память, отдельный поток считывал блоки с диска. Этот тип распараллеливания сложен ... поэтому я бы сделал это, только если вам действительно нужна максимальная производительность.

Вот действительно простая программа на C #, с которой можно начать, если вам это нужно. Он принимает путь к входному файлу и путь к выводу в командной строке и выполняет искомую замену ('>' ==> CRLF). Этот пример оставляет желать лучшего (параллельная обработка, потоковая передача, некоторая проверка и т. Д.) ... но это должно быть достойное начало.

using System;
using System.IO;

namespace ExpandBrackets
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length == 2)
            {
                using( StreamReader input = new StreamReader( args[0] ) )
                using( StreamWriter output = new StreamWriter( args[1] ) )
                {
                    int readSize = 0;
                    int blockSize = 100000;
                    char[] inBuffer = new char[blockSize];
                    char[] outBuffer = new char[blockSize*3];
                    while( ( readSize = input.ReadBlock( inBuffer, 0, blockSize ) ) > 0 )
                    {
                        int writeSize = TransformBlock( inBuffer, outBuffer, readSize );
                        output.Write( outBuffer, 0, writeSize );
                    }
                }
            }
            else
            {
                Console.WriteLine( "Usage:  repchar {inputfile} {outputfile}" );
            }
        }

        private static int TransformBlock( char[] inBuffer, char[] outBuffer, int size )
        {
            int j = 0;
            for( int i = 0; i < size; i++ )
            {
                outBuffer[j++] = inBuffer[i];
                if (inBuffer[i] == '>') // append CR LF
                {
                    outBuffer[j++] = '\r';
                    outBuffer[j++] = '\n';
                }
            }
            return j;
        }
    }
}
1 голос
/ 26 августа 2009

Вместо того, чтобы читать побайтово, что дает доступ к диску для каждого прочитанного байта, попробуйте прочитать ~ 20 МБ за раз и выполнить поиск + заменить на это:)

Вы, вероятно, можете сделать это в Блокноте ....

Billy3

0 голосов
/ 27 августа 2009

Как уже говорили другие, если вы сделаете это в C, это будет в значительной степени непобедимо, потому что C буферизует ввод / вывод, и getc () встроен (в моей памяти).

Ваша реальная проблема производительности будет в разн.

Может быть, есть неплохой, но я сомневаюсь, что для файлов такого размера. Ради интереса, я сделаю это сам. Стратегия, которую я бы использовал, заключается в том, чтобы в каждом файле было скользящее окно длиной в несколько мегабайт. Стратегия поиска несоответствий - поиск по диагонали. Если вы находитесь в строках i и j, сравните в следующей последовательности:

line(i+0) == line(j+0)

line(i+0) == line(j+1)
line(i+1) == line(j+0)

line(i+0) == line(j+2)
line(i+1) == line(j+1)
line(i+2) == line(j+0)

и так далее. Без сомнения, есть лучший способ, но если я собираюсь сам его кодировать и управлять скользящими окнами, я бы попробовал.

0 голосов
/ 26 августа 2009

Я поставил это как комментарий к другому ответу, но в случае, если вы его пропустили - вы можете посмотреть Перестрелка . Это высоко оптимизированный набор кода для различных задач на многих языках.

Согласно этим результатам, Python, как правило, примерно в 50 раз медленнее, чем c (но он быстрее, чем другие интерпретируемые языки). В сравнении Java примерно в 2 раза медленнее, чем c. Если бы вы перешли на один из более быстрых скомпилированных языков, я не понимаю, почему вы бы не увидели такого же увеличения.

Кстати, цифры, полученные в результате перестрелки, чудесно недоступны, вы не можете их оспаривать, вместо этого, если вы не верите, что цифры справедливы, потому что код для решения проблемы на вашем любимом языке не оптимизированы должным образом, тогда вы можете представить лучший код самостоятельно. Многие люди делают это, потому что большая часть кода там чертовски оптимизирована для каждого популярного языка. Если вы покажете им более оптимизированный компилятор или интерпретатор, они также могут включить в него результаты.

О: кроме C #, он представлен только MONO, поэтому, если компилятор Microsoft более оптимизирован, он не отображается. Кажется, что все тесты выполняются на машинах Linux. Я предполагаю, что Microsoft C # должна работать примерно с той же скоростью, что и Java, но в перестрелке моно показывается немного медленнее (примерно в 3 раза медленнее, чем C) ..

0 голосов
/ 26 августа 2009

вы можете попробовать xmldiff - http://msdn.microsoft.com/en-us/library/aa302294.aspx

Я не использовал его для таких огромных данных, но думаю, что он будет разумно оптимизирован

0 голосов
/ 26 августа 2009

Все языки, упомянутые обычно, в какой-то момент возвращаются к библиотеке времени выполнения C для побайтного доступа к файлу. Запись этого в C, вероятно, будет самым быстрым вариантом.

Однако я сомневаюсь, что это обеспечит огромный прирост скорости. Python довольно быстр, если вы все делаете правильно.

Основным способом добиться значительного улучшения скорости было бы введение потоков. Если вы читаете данные из файла в виде большого блока в одном потоке и имеете отдельный поток, в котором выполнялась обработка новой строки + обработка различий, вы можете значительно повысить скорость этого алгоритма. Вероятно, это было бы проще реализовать в C ++, C # или IronPython, чем в C или CPython напрямую, поскольку они предоставляют очень простые высокоуровневые инструменты синхронизации для обработки проблем с потоками (особенно при использовании .NET).

...