Оптимизация производительности IO - чтение 50 миллионов целых чисел, разделенных пробелами

Question

Если вы используете интерпретируемый Python 2.7.6 и пытаетесь прочитать около 50 миллионов целых чисел (подписанных, 32 бита) из файла, связанного с stdin, то что самое быстрое (производительность) способ сделать это, если они входят в одну строку (нет \ n в конце), пространство разделены ?, или, возможно, разделены запятой? Предпочтительно использовать генераторы и/или считывать фрагменты, чтобы весь файл не был сразу прочитан в памяти или список всех 50M целых чисел, сохраненных сразу. Список должен быть сведен к сумме всех смежных элементов xors (A[0]^A[1] + A[1]^A[2] + ...), числа очень близки друг к другу, поэтому сокращение не прерывает 32 бита целое число со знаком.

Исходная строка может быть добавлена ​​либо к числу целых чисел (n), либо к длине строки (L).

Я не владею питоном, и получаю недопустимые результаты (> 30 секунд). На десятую часть ограничений я делаю около 6 секунд, поэтому чувствую, что мне нужно улучшить это намного больше.

Мне кажется, что если бы они были отделены друг от друга, это могло бы быть возможно. Есть ли способ сказать python использовать другой разделитель для readline()?

Пробовал:

• for ch in stdin.read(), это занимает 3 секунды в цикле все ч, а строить целые числа с умножений, а затем делает сокращение вручную занимает слишком много времени.
• read(n), считывая фрагменты, а затем сохраняя неполный хвост для последующего использования, используя split и map int, для xrange и уменьшаем на куске последовательно, чтобы создать список сокращений, но снова, похоже, занять слишком много времени.

Я сделал это на более быстрых языках уже благодаря поиску интерпретируемых ответов python.

Это мой лучший код, который длится через 18 секунд в некоторых случаях, в других - слишком медленно. Но это быстрее, чем версия, где я построил целые числа с умножениями на аккумуляторе. Это также быстрее, чем чтение байта на байт: read(1).

def main(): 
    n,l=map(int,raw_input().split()) 
    #print n 
    #print l 

    r = 0 #result 
    p = 0 #previous 
    q = 0 #current 

    b = [] #buffer 
    for c in sys.stdin.read(): #character 
     if c == ' ': 
      q = int(''.join(b)) 
      b = [] 
      r += q^p #yes there is a bug with A[0] but lets optimize the loop for now 
      p = q 
     else: 
      b.append(c) 
    r += int(''.join(b))^p 

    print r 
main() 

я могу видеть, что это может (возможно) можно улучшить, если это было возможно инициализировать б только один раз, а затем не используя добавления, но на самом деле доступ к индексу, но когда я попытался b = [None]*12 я получил RTE во время присоединиться к cant join None, нужно присоединиться к диапазону, поэтому я бросил идею на данный момент. Также более быстрые функции выполняют то, что я уже делаю.

Update:

import re 
import sys 

from collections import deque 

def main(): 
    n,l=map(int,raw_input().split()) 
    #print n 
    #print l 

    r = 0 
    p = 0 
    q = 0 

    b = sys.stdin.read(l) 

    b = deque(b.rsplit(' ',4000000)) 
    n = len(b) 
    while n == 4000001: 
     c = b.popleft() 
     b = map(int,b) 
     for i in xrange(n-2,0,-1): 
      r += b[i]^b[i-1] 

     m = b[0] 
     b = deque(c.rsplit(' ',3999999)) 
     b.append(m) 
     n = len(b) 


    b = map(int,b) 
    for i in xrange(n-1,0,-1): 
     r += b[i]^b[i-1] 

    print r 
main() 

Это в 3 раза быстрее (10000000 может быть сделано в течение 6 секунд, но 50 принимают более 30), за 50 миллионов, это все еще слишком медленно, IO, кажется, не основное узкое место, но обработка данных.

Вместо deque можно использовать обычный список, вызывая pop (0) вместо popleft. Также можно не называть len (b) на каждом цикле, поскольку у вас есть n в начале и может вычесть вместо этого, но, кроме того, это кажется самым быстрым до сих пор.

Answer 1

Прочитайте поток байтов до EOF. Как только вы нажмете пробел, преобразуйте список «цифр» байтов в целое число, сделайте свой XOR и сбросьте список. Или просто добавьте цифры в список, пока не нажмете пробел.Что-то вроде следующего непроверенного кода:

f = open("digits.txt", "rb") 
try: 
    bytes = [] 
    previous_num = None 
    byte = f.read(1) 
    while byte != "": 
     if byte != " ": 
      bytes.append(byte) 
     else: 
      # convert bytes to a number and reset list 
      current_num = int(''.join(map(str, bytes))) 
      if not previous_num: 
       previous_num = current_num 
      else: 
       # do your operation on previous and current number 
      bytes = [] 
     byte = f.read(1) 
finally: 
    f.close() 

Вы могли бы оптимизировать, прочитав в кусках байт, вместо одного байта за раз. Возможно, еще одним способом оптимизации этого является сохранение своего рода «нулевого» терминатора для списка, индекс, который сохраняет «длину» списка. Вместо того, чтобы протирать его в каждом цикле, вы выполняете свою операцию map на подмножестве с начальным/конечным индексом bytes. Но, надеюсь, это демонстрирует принцип.

Без этого, вы могли бы, возможно, использовать утилиту Unix, как sed заменить пробелы на символы новой строки и трубы вывода sed на скрипт на Python, и есть Python читать из stdin потока, используя его (возможно, оптимизированное) способность читать строку за раз.

(Но, на самом деле, Python, вероятно, неправильный ответ на все, что нужно скорейший ввод/вывод.)

Answer 2

Я побежал этот код:

#!python2.7 
from __future__ import print_function 
import os, time 

numbers = "100 69 38 24 17 11 3 22 " 
print("Numbers:", numbers) 


if not os.path.isfile('numbers.txt'): 
    with open('numbers.txt', 'w') as outfile: 
     n = 7*1000*1000 
     print("Repeating %d times..." % n) 
     print(numbers * n, file=outfile) 

print("Starting read. Time:", time.strftime("%c")) 
total = 0 
with open('numbers.txt') as f: 
    prv = None 
    for nxt in f.read().split(): 
     nxt = int(nxt) 
     if prv is not None: 
      total += prv^nxt 
     prv = nxt 

print("Finished. Time:", time.strftime("%c")) 
print("Total:", total) 

И получил следующие результаты:

$ python2.7 test.py 
Numbers: 100 69 38 24 17 11 3 22 
Starting read. Time: Fri Feb 3 19:20:32 2017 
Finished. Time: Fri Feb 3 19:21:36 2017 
Total: 2603999886 

Это 56 миллионов (небольших) номеров, на 5-летнем MacBook Pro, за 64 секунды или около того - около 1 миллиона номеров в секунду. Можете ли вы дать нам свои тайминги и что вы ожидаете получить?

Answer 3

Я был бы удивлен, если вы могли бы найти гораздо быстрее, чем реализация numpy.fromfile

Однако разбор Интс из текстового файла происходит гораздо медленнее, чем просто чтение двоичных данных. Вот несколько быстрых и грязных тестов, в которых используются два файла с одинаковыми целями ~ 50M. Первый формат текста, другой двоичный (написанные с использованием numpy.ndarray.tofile)

%timeit numpy.fromfile('numbers.txt', dtype=int, sep=' ') 
1 loop, best of 3: 23.6 s per loop 

%timeit numpy.fromfile('numbers.bin') 
1 loop, best of 3: 2.55 s per loop 

Answer 4

как об этом

from itertools import tee, izip as zip 
import re 

def pairwise(iterable): 
    a,b = tee(iterable) 
    next(b,None) 
    return zip(a,b) 

def process_data(data): 
    return sum(a^b for a,b in pairwise(data)) 

def process_str_file_re(fname): 
    exp = re.compile(r"\d+") 
    with open(fname,"rb") as archi: 
     return process_data(int(data.group()) for data in exp.finditer(archi.read())) 

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