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

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

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

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

 random.sample(xrange(158609739), 3609739) 

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

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

• 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 

Последнее замечание: random.random() – это [0.0, 1.0] (не включает 1.0 как возможность).

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

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

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

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

Вот возможное решение с использованием 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() 

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

Я изменил свой код, чтобы использовать 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) 

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

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

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

EDIT: Вот вам код, который поможет вам начать:

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

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

 thatScript.sh <inFile.txt >outFile.txt