Как случайно удалить несколько строк из большого файла?

Question

У меня большой текстовый файл объемом 13 ГБ с 158 609 739 строками, и я хочу произвольно выбрать 155 000 000 строк.

Я попытался зашифровать файл, а затем вырезать первые строки 155000000, но, похоже, мойоперативной памяти (16 ГБ) недостаточно для этого.Я попытался использовать следующие конвейеры:

shuf file | head -n 155000000
sort -R file | head -n 155000000

Теперь вместо выбора строк я считаю более эффективным использование памяти: удалите 3 609 739 случайных строк из файла, чтобы получить окончательный файл из 15 500 000 000 строк.

Answer 1

Когда вы копируете каждую строку файла в выходной файл, оцените вероятность его удаления.Первая строка должна иметь 3 609 739/158 609 739 шансов на удаление.Если вы генерируете случайное число от 0 до 1 и это число меньше этого отношения, не копируйте его в вывод.Теперь шансы для второй линии составляют 3 609 738/158 609 738;если эта строка не удалена, шансы для третьей строки составляют 3 609 738/158 609 737.Повторяйте, пока не закончите.

Поскольку шансы меняются с каждой обработанной строкой, этот алгоритм гарантирует точное количество строк.Как только вы удалили 3 609 739, шансы равны нулю;если в любое время вам потребуется удалить все оставшиеся строки в файле, шансы равны единице.

Answer 2

Вы всегда можете предварительно сгенерировать, какие номера строк (список из 3 609 739 случайных чисел, выбранных без замены) вы планируете удалить, а затем просто перебирать файл и копировать в другой, пропуская строки по мере необходимости.Пока у вас есть место для нового файла, это будет работать.

Вы можете выбрать случайные числа с помощью random.sample Например,

random.sample(xrange(158609739), 3609739)

Answer 3

Доказательство ответа Марка Рэнсома

Давайте использовать цифры, о которых легче думать (по крайней мере, для меня!):

• 10 предметов
• удалить 3 из них

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

• первый предмет: 3/10 = 30%
• второй пункт: 2/9 = 22%
• третий пункт: 1/8 = 12%
• четвертый пункт: 0/7 = 0%
• пятый элемент: 0/6 = 0%
• шестой элемент: 0/5 = 0%
• седьмой пункт: 0/4 = 0%
• восьмой пункт: 0/3 = 0%
• девятый пункт: 0/2 = 0%
• десятый элемент: 0/1 = 0%

Как видите, как только он достигает нуля, он остается на нуле. Но что, если ничего не удаляется?

• первый пункт: 3/10 = 30%
• второй пункт: 3/9 = 33%
• третий пункт: 3/8 = 38%
• четвертый пункт: 3/7 = 43%
• пятый пункт: 3/6 = 50%
• шестой предмет: 3/5 = 60%
• седьмой пункт: 3/4 = 75%
• восьмой пункт: 3/3 = 100%
• девятый пункт: 2/2 = 100%
• десятый элемент: 1/1 = 100%

Таким образом, даже если вероятность варьируется в зависимости от строки, в целом вы получаете результаты, которые вы ищете. Я пошел еще дальше и закодировал тест на Python для миллиона итераций в качестве окончательного доказательства для себя - удалите семь элементов из списка 100:

# python 3.2
from __future__ import division
from stats import mean  # http://pypi.python.org/pypi/stats
import random

counts = dict()
for i in range(100):
    counts[i] = 0

removed_failed = 0

for _ in range(1000000):
    to_remove = 7
    from_list = list(range(100))
    removed = 0
    while from_list:
        current = from_list.pop()
        probability = to_remove / (len(from_list) + 1)
        if random.random() < probability:
            removed += 1
            to_remove -= 1
            counts[current] += 1
    if removed != 7:
        removed_failed += 1

print(counts[0], counts[1], counts[2], '...',
      counts[49], counts[50], counts[51], '...',
      counts[97], counts[98], counts[99])
print("remove failed: ", removed_failed)
print("min: ", min(counts.values()))
print("max: ", max(counts.values()))
print("mean: ", mean(counts.values()))

и вот результаты одного из нескольких моих тестов (все они были похожи):

70125 69667 70081 ... 70038 70085 70121 ... 70047 70040 70170
remove failed:  0
min:  69332
max:  70599
mean:  70000.0

Последнее замечание: Python's random.random() равен [0.0, 1.0) (не включает 1.0 как возможность).

Answer 4

Вот возможное решение с использованием Python:

import random

skipping = random.sample(range(158609739), 3609739)

input = open(input)
output = open(output, 'w')

for i, line in enumerate(input):
    if i in skipping:
        continue
    output.write(line)

input.close()
output.close()

Вот еще один метод Марка:

import random

lines_in_file = 158609739
lines_left_in_file = lines_in_file
lines_to_delete = lines_in_file - 155000000

input = open(input)
output = open(output, 'w')

try:
    for line in input:
        current_probability = lines_to_delete / lines_left_in_file
        lines_left_in_file -= 1
        if random.random < current_probability:
            lines_to_delete -= 1
            continue
        output.write(line)
except ZeroDivisionError:
    print("More than %d lines in the file" % lines_in_file)
finally:
    input.close()
    output.close()

Answer 5

Я полагаю, что вы ищете "Алгоритм S" из раздела 3.4.2 Кнута (Д.Е. Кнут, Искусство компьютерного программирования. Том 2: Полу численные алгоритмы, второе издание. Addison-Wesley, 1981) .

Вы можете увидеть несколько реализаций в http://rosettacode.org/wiki/Knuth%27s_algorithm_S

. В списке Perlmonks есть некоторые реализации Perl алгоритма S и алгоритма R , которые также могут оказаться полезными.

Эти алгоритмы основаны на осмысленной интерпретации чисел с плавающей запятой, таких как 3609739/158609739, 3609738/158609738 и т. Д., Которые могут не иметь достаточного разрешения со стандартным типом данных Float, если только Float тип данных реализован с использованием чисел с двойной точностью или более.

Answer 6

Я написал этот код, прежде чем увидел, что Даррен Инь выразил свой принцип.

Я изменил свой код, чтобы использовать имя skipping (я не осмелился выбрать kangaroo ...) и ключевое слово continue от Этана Фурмана, принцип кодирования которого -тоже самое.

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

import random
import os.path

def spurt(ff,skipping):
    for i,line in enumerate(ff):
        if i in skipping:
            print 'line %d excluded : %r' % (i,line)
            continue
        yield line

def randomly_reduce_file(filepath,nk = None,
                         d = {0:'st',1:'nd',2:'rd',3:'th'},spurt = spurt,
                         sample = random.sample,splitext = os.path.splitext):

    # count of the lines of the original file
    with open(filepath) as f:  nl = sum(1 for _ in f)

    # asking for the number of lines to keep, if not given as argument
    if nk is None:
        nk = int(raw_input('  The file has %d lines.'
                           '  How many of them do you '
                           'want to randomly keep ? : ' % nl))

    # transfer of the lines to keep,
    # from one file to another file with different name
    if nk<nl:
        with open(filepath,'rb') as f,\
             open('COPY'.join(splitext(filepath)),'wb') as g:
            g.writelines(  spurt(f,sample(xrange(0,nl),nl-nk) )  )
            # sample(xrange(0,nl),nl-nk) is the list
            # of the counting numbers of the lines to be excluded 
    else:
        print '   %d is %s than the number of lines (%d) in the file\n'\
              '   no operation has been performed'\
              % (nk,'the same' if nk==nl else 'greater',nl)

Answer 7

С переменной $ RANDOM вы можете получить случайное число от 0 до 32 767.

При этом вы можете читать в каждой строке и видеть, меньше ли $ RANDOM 155,000,000 / 158,609,739 * 32,767 (что составляет 32 021), и если это так, пропустите строку.

Конечно, это не даст вам точно 150 000 000 строк, но довольно близко к нему, в зависимости от нормальности генератора случайных чисел.

РЕДАКТИРОВАТЬ: Вот код, с которого можно начать:

#!/bin/bash
while read line; do
  if (( $RANDOM < 32021 ))
  then
    echo $line
  fi
done

Назовите это так:

thatScript.sh <inFile.txt >outFile.txt